Order-2 bygone-state opacity of labeled finite-state automata
Kuize Zhang · 2026
Read Order-2 bygone-state opacity of labeled finite-state automata by Kuize Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26503.txt.
Introduction
Kuize Zhang formalises a layered secrecy property for finite-state automata. An automaton is a machine that moves between states as events occur. Two agents watch different subsets of its events through labels. The second agent knows exactly what the first can observe. The question is what the second agent can infer about the first agent's estimate of a past state.
Zhang calls the target property order-2 bygone-state opacity. It holds when the second agent can never be sure that the first agent pinned down a past state uniquely. He builds a verification tool from concurrent composition and the classical observer construction. The check runs in doubly exponential time, a very large but finite bound. The contribution extends inference about automata from one watching agent to two ordered agents. That ordering captures realistic settings where one observer monitors another.
Catalog record
| CREATOR | Kuize Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.26503
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Order-2 bygone-state opacity of labeled finite-state automata Kuize Zhang Abstract Abstract In this paper, we formulate a scenario that an agent can never be sure that another agent can uniquely determine the state of a finite-state automaton based on its observations to the automaton at the current and any past time as the property of order- 2 bygone-state opacity. Based on our concurrent composition and the classical observer, we derive a tool to verify this property in doubly exponential time. The interest of this result lies in that we extend inference of finite automata from a single agent to two ordered agents. Keywords labeled finite-state automaton, order- 2 bygone-state opacity, concurrent composition, observer, order- 2 observer Section 1 Introduction In this paper, we consider the scenario consisting of a finite-state automaton (FSA) G and 2 agents A_{1} and A_{2} . The FSA is publicly known to both agents, each agent A_{i} can observe a subset E_{i} of events of G via a labeling function \ell_{i}:E_{i}\to\Sigma_{i} with \Sigma_{i} an alphabet, and agent A_{2} knows agent A_{1} ’s observable events and labeling function. We formulate and compute what A_{2} knows about A_{1} ’s bygone-state estimate of G based on an observed label sequence generated by G . We also formulate such a property as follows: for every trace generated by G , if A_{1} can uniquely determine G ’s consistent state at a past time according to the label sequence generated by the trace, then G can generate another trace such that based on the label sequence generated by the second trace A_{1} cannot uniquely determine G ’s consistent state at a past time, and the two traces look the same to agent A_{2} before and after the respective time instants A_{1} is doing state estimations (see Figure 1 as an illustration). Roughly speaking, A_{2} cannot be sure whether A_{1} can uniquely determine G ’s state according to its inferences of A_{1} ’s bygone-state estimates of G based on A_{2} ’s observation to G . Such a property will be called order- 2 bygone-state opacity . When there is only one agent, this property degenerates to the infinite-step opacity [ 10 ] : A_{1} cannot uniquely determine G ’s state according to every observation to G at every past time. The infinite-step opacity verification problem is \mathsf{PSPACE} -complete in labeled finite-state automata (LFSAs) [ 10 ] and currently the most efficient algorithm for verifying this property is based on the combination of the concurrent composition [ 16 ] and the observer (that is, the classical powerset construction [ 9 ] ), see [ 15 ] for details. G A_{1} A_{2} infer Q^{\prime}|\alpha\beta\subset 2^{Q} observation \gamma\zeta infer G|\gamma\zeta=Q^{\prime} observation \alpha\beta Figure 1 : An illustration of order- 2 bygone-state opacity: agent A_{2} observes label sequence \alpha\beta from G , infers all possible traces s_{1}s_{2} such that s_{1} and s_{2} generate label sequences \alpha and \beta , then agent A_{1} observes \gamma and \zeta from s_{1} and s_{2} and computes state estimate Q^{\prime} of G based on \gamma and \zeta . All such Q^{\prime} form A_{2} ’s inferences of A_{1} ’s state estimates based on \alpha\beta . The main results of the paper are twofold: we formulate order- 2 bygone-state opacity, and derive a tool to verify this property in 2 - \mathsf{EXPTIME} based on our concurrent composition [ 16 ] and the classical observer [ 9 ] . Section 2 Preliminaries Section 2.1 Notation Notation. Symbol \mathbb{N} denotes the set of nonnegative integers. For two nonnegative integers i\leq j , \llbracket i,j\rrbracket denotes the set of all integers no less than i and no greater than j . For a set S , |S| denotes its cardinality and 2^{S} its power set. Symbols \subset , \not\subset , and \subsetneq denote the subset of , not a subset of , and a strict subset of relations, respectively. For two sets A and B , A\setminus B denotes \{x\in A|x\notin B\} . Let \Sigma denote a finite alphabet . Elements of \Sigma are called letters . As usual, \Sigma^{*} denotes the set of words or strings (i.e., finite-length sequences of letters) over \Sigma including the empty word \epsilon , and denote \Sigma^{+}:=\Sigma^{*}\setminus\{\epsilon\} . The length of a word w\in\Sigma^{*} is the number of letters, counting repetitions, occurring in w , and is denoted by |w| . For a word w\in\Sigma^{*} , its mirror image w^{R} is obtained by reversing the order of the letters of w . For a string (a_{1},b_{1})\dots(a_{n},b_{n})=:s , a_{1}\dots a_{n}=:s(L) , b_{1}\dots b_{n}=:s(R) . In this paper, we consider 2 agents, and use alphabets \Sigma_{i} to denote the label sets of agent A_{i} , i=1,2 . A (formal) language is a subset of \Sigma^{*} . For two languages L_{1},L_{2}\subset\Sigma^{*} , their concatenation L_{1}L_{2} is defined as \{e_{1}e_{2}|e_{1}\in L_{1},e_{2}\in L_{2}\} . For two formal languages L_{1},L_{2}\subset\Sigma^{*} , denote their interleaving as L_{1}\interleave L_{2}=\{e_{1}\dots e_{n}|(\exists\text{ subsequences }i_{1}\dots i_{r},j_{1},\dots,j_{s})[(i_{1}<\cdots<i_{r})\wedge(j_{1}<\cdots<j_{s})\wedge(r+s=n)\wedge\{i_{1},\dots,i_{r},j_{1},\dots,j_{s}\}=\{1,\dots,n\}\wedge e_{i_{1}}\dots e_{i_{r}}\in L_{1}\wedge e_{j_{1}}\dots e_{j_{s}}\in L_{2}]\} . Hence each word of L_{1}\interleave L_{2} is obtained by interleaving a word of L_{1} and a word of L_{2} . Symbols used throughout the paper: G=(Q,E,\delta,Q_{0}) : finite-state automaton \mathcal{S}=(G,\Sigma,\ell) : labeled finite-state automaton G^{\inv} : inverse finite-state automaton L(G) : language generated by G \mathcal{M}(\mathcal{S},\alpha)=\mathcal{M}_{\ell}(G,\alpha) : current-state estimate of G with respect to label sequence \alpha \mathcal{M}(\mathcal{S},\alpha,\alpha\beta)=\mathcal{M}_{\ell}(G,\alpha,\alpha\beta) : bygone-state estimate of G with respect to label sequences \alpha and \alpha\beta \CC(\mathcal{S}^{1},\mathcal{S}^{2}) : concurrent composition of labeled finite-state automata \mathcal{S}^{1} and \mathcal{S}^{2} \CC_{\ell}(G^{1},G^{2}) : concurrent composition of finite-state automata G^{1} and G^{2} endowed with the same labeling function \ell \Obs(\mathcal{S})=\Obs_{\ell}(G) : observer of labeled finite-state automaton \mathcal{S}=(G,\Sigma,\ell) \Obs^{\inv}(\mathcal{S})=\Obs_{\ell}^{\inv}(G) : inverse observer of labeled finite-state automaton \mathcal{S}=(G,\Sigma,\ell) Y_{1}\Cap Y_{2} with Y_{1},Y_{2}\subset Q\times 2^{Q} : \left\{X_{1}\cap X_{2}|(\exists q\in Q)[(q,X_{1})\in Y_{1}\wedge(q,X_{2})\in Y_{2}]\right\} (particularly if such a state q does not exist, then Y_{1}\Cap Y_{2}=\{\emptyset\} .) (G,\Sigma_{i},\ell_{i})=:G_{A_{i}} : finite-state automaton G and agent A_{i} endowed with labeling function \ell_{i}:E\to\Sigma_{i} \mathcal{M}_{\ell_{i}}(G,\alpha)=:\mathcal{M}_{i}(G,\alpha) : current-state estimate of G done by agent A_{i} with respect to label sequence \alpha \mathcal{M}_{\ell_{i}}(G,\alpha,\alpha\beta)=:\mathcal{M}_{i}(G,\alpha,\alpha\beta) : bygone-state estimate of G done by agent A_{i} with respect to label sequences \alpha and \alpha\beta \Obs_{\ell_{i}}(G)=:\Obs_{A_{i}} : observer of G with respect to agent A_{i} \Obs_{\ell_{i}}^{\inv}(G)=:\Obs_{A_{i}}^{\inv} : inverse observer of G with respect to agent A_{i} \mathcal{M}_{A_{1}\leftarrow A_{2}}(G,\alpha) : order- 2 current-state estimate of G with respect to agents A_{1} and A_{2} and A_{2} ’s label sequence \alpha \mathcal{M}_{A_{1}\leftarrow A_{2}}(G,\alpha,\alpha\beta) : order- 2 bygone-state estimate of G with respect to agents A_{1} and A_{2} and A_{2} ’s label sequences \alpha and \alpha\beta \Obs_{A_{1}\leftarrow A_{2}}(G) : order- 2 observer \Obs_{A_{1}\leftarrow A_{2}}^{\inv}(G) : order- 2 inverse observer \CC_{\ell_{\epsilon}}\left(\Obs_{A_{1}\leftarrow A_{2}}(G),\Obs_{A_{1}\leftarrow A_{2}}^{\inv}(G)\right) : concurrent composition of order- 2 observer \Obs_{A_{1}\leftarrow A_{2}}(G) and order- 2 inverse observer \Obs_{A_{1}\leftarrow A_{2}}^{\inv}(G) endowed with the \epsilon -labeling function Section 2.2 Labeled finite-state automata Definition 1 A finite-state automaton (FSA) is a quadruple \displaystyle G=(Q,E,\delta,Q_{0}), (1) where 1. Q is a finite set of states , 2. E is an alphabet of events , 3. \delta:Q\times E\to 2^{Q} is the transition function (equivalently described as \delta\subset Q\times E\times Q such that (q,e,q^{\prime})\in\delta if and only if q^{\prime}\in\delta(q,e) ), 4. Q_{0}\subset Q is a set of initial states . Definition 2 The inverse finite-state automaton , denoted as G^{\inv} , of FSA G as