Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems

Alexander Rubtsov Faculty of Computer Science, National Research University Higher School of Economics, Pokrovsky boulevard 11, Moscow, 109028, Russia, [email protected] Mikhail Vyalyi Faculty of Computer Science, National Research University Higher School of Economics, Pokrovsky boulevard 11, Moscow, 109028, Russia, [email protected]

Abstract

We consider general computational models: one-way and two-way finite automata, and logarithmic space Turing machines, all equipped with an auxiliary data structure (ADS). The definition of an ADS is based on the language of protocols of work with the ADS. We describe the connection of automata-based models with ‘‘Balloon automata’’ that are another general formalization of automata equipped with an ADS presented by Hopcroft and Ullman in 1967. This definition establishes the connection between the non-emptiness problem for one-way automata with ADS, languages recognizable by nondeterministic log-space Turing machines equipped with the same ADS, and a regular realizability problem (NRR) for the language of ADS’ protocols. The NRR problem is to verify whether the regular language on the input has a non-empty intersection with the language of protocols. The computational complexity of these problems (and languages) is the same up to log-space reductions.

Keywords: Finite automata; Balloon automata; Auxiliary data structures

1 Introduction

Many computational models are derived from (one-way) finite automata (FAs) via equipping them with an auxiliary data structure (ADS). The best-known model of this kind is pushdown automata (PDAs), the deterministic version of which is widely used in compilers. Other examples are $k$ -counter automata, $(k,r)$ -reversal-bounded counter automata (equipped with $k$ counters each of which can switch between increasing and decreasing modes at most $r$ times), stack automata, nested stack automata, bag automata [5], set automata (SAs) [8] and their another variant [9]; more examples can be found in [7].

During the investigation of balloon automata (BAs) [7], Hopcroft and Ullman connected the decidability of the membership and the emptiness problems for one-way and two-way models; we denote them as $M\text{-}xyBA$ and $E\text{-}xyBA$ respectively, where $x=1$ denotes one-way and $x=2$ denotes two-way models, and $y\in\{D,N\}$ stands for determinism or nondeterminism respectively. Eq. (1) summarizes results on decidability questions from [7], where $\mathop{\leq_{\mathrm{T}}}$ is a Turing-reduction and $\{A,B\}$ means that $A\mathop{\leq_{\mathrm{T}}}B$ and $B\mathop{\leq_{\mathrm{T}}}A$ .

\displaystyle\begin{split}\{\mathrm{M}\text{-}1\mathrm{DBA},\mathrm{M}\text{-}2\mathrm{DBA}\}&\mathop{\leq_{\mathrm{T}}}\{\mathrm{E}\text{-}1\mathrm{DBA},\mathrm{E}\text{-}1\mathrm{NBA},\mathrm{M}\text{-}1\mathrm{NBA},\mathrm{M}\text{-}2\mathrm{NBA}\}\mathop{\leq_{\mathrm{T}}}\\ &\mathop{\leq_{\mathrm{T}}}\mathrm{E}\text{-}2\mathrm{DBA}\mathop{\leq_{\mathrm{T}}}\mathrm{E}\text{-}2\mathrm{NBA}.\end{split}

(1)

We remark that the relation $\mathrm{E}\text{-}1\mathrm{NBA}\mathop{\leq_{\mathrm{T}}}\mathrm{E}\text{-}1\mathrm{DBA}$ was proved for the case of at least a two-letter input alphabet.

While a lot of models can be described as BA, it is hard to invent such a model with good computational properties. One of the reasons is that the equipment of finite automata with a complex data structure (or with several simple data structures) often leads to a universal computational model. For example, FAs equipped with two pushdown stores are equivalent to Turing machines (TMs), as well as FAs equipped with two non-restricted counters.

In this paper, we investigate the computational power of FAs equipped with an ADS. We describe the model using the language of correct protocols of work with the ADS. We provide a general approach to analyze the complexity of the emptiness problem and prove the following non-trivial result. If FAs are equipped with an ADS and nondeterministic logarithmic space TMs ( ${\log}\text{-}\mathrm{TM}$ s, see the definition in [16]) are equipped with the same ADS, then the FAs’ non-emptines problem and the TMs-recognizable languages are of the same complexity (up to log-space reductions). Our key tool is the regular realizability problem (see Definition 1 below).

1.1 Our Contribution

BAs were initially defined as automata with access to additional storage of unspecified structure—the balloon. A rather general axioms were imposed for the balloon and the interaction of the balloon and the automaton (see Definition 4 below). In this paper, we propose another definition based on a language of the ADS’ protocols that we denote as $\mathsf{P}$ , so we refer to the ADS as $\mathrm{B_{\mathsf{P}}}$ . We prove that languages recognizable by $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ form not just a rational cone as in the case of $1\mathrm{NBA}$ [7], but a principal rational cone generated by $\mathsf{P}$ (we provide the definition in Section 2.2).

This reformulation guarantees good structural properties, some of them follow from the connection with BA (Section 4), and provides the relation between $\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ and the nondeterministic regular realizability problem.

Definition 1.

Fix a formal language $F$ called a filter, the parameter of regular realizability problems $\mathrm{DRR}(F)$ and $\mathrm{NRR}(F)$ that are the problems of verifying non-emptiness of the intersection of the filter $F$ with a regular language $L({\cal A})$ described via the DFA or NFA ${\cal A}$ respectively. Formally,

		$\displaystyle\mathrm{NRR}(F)=\{{\cal A}\mid{\cal A}\text{ is an NFA and }L({\cal A})\cap F\neq\varnothing\},$
		$\displaystyle\mathrm{DRR}(F)=\{{\cal A}\mid{\cal A}\text{ is a DFA and }L({\cal A})\cap F\neq\varnothing\}.$

RR problems have independently been studied under the name regular intersection emptiness problems [21, 22]. A restricted version of RR problem (for context-free filters only) is a well-known CFL-reachability problem, which is related to problems in interprocedural program analysis [4, 6, 23, 10, 11, 3].

In this paper we focus on the computational complexity, so we use the weakest reduction suitable for our needs, the deterministic log-space reduction that we denote as $\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}$ . If $A\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}B$ and $B\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}A$ we write $A\sim_{\log}B$ and say that $A$ and $B$ are log-space equivalent. Note that in our constructions, emptiness and membership problems are the sets of instances’ descriptions with positive answers, i.e., $\mathrm{E}\text{-}xy\mathrm{B_{\mathsf{P}}}\mathrm{A}=\{\langle M\rangle\mid L(M)=\varnothing\}$ , $\mathrm{M}\text{-}xy\mathrm{B_{\mathsf{P}}}\mathrm{A}=\{\langle M,w\rangle\mid w\in L(M)\}$ , where $M$ is a $xy\mathrm{B_{\mathsf{P}}}\mathrm{A}$ and $\langle x\rangle$ is the description of $x$ . So, $\overline{\mathrm{E}\text{-}xy\mathrm{B_{\mathsf{P}}}\mathrm{A}}=\{\langle M\rangle\mid L(M)\neq\varnothing\}$ . We prove that $\overline{\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}}\sim_{\log}\mathrm{NRR}(\mathsf{P})$ . Based on this result, we establish computational universality of $\overline{\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}}$ (see Theorem 34 below). Note that in the universality result we need Turing reductions in polynomial time instead of log-space reductions.

We equip with ADS not only FAs but also ${\log}\text{-}\mathrm{TM}$ s. We denote deterministic and nondeterministic ${\log}\text{-}\mathrm{TM}$ s equipped with an ADS $\mathrm{B_{\mathsf{P}}}$ as $\mathrm{D}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}$ and $\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}$ respectively. We prove that

\mathrm{NRR}(\mathsf{P})\sim_{\log}{\mathscr{L}}(\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM})=\{L\mid L\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(\mathsf{P})\},

(2)

hereinafter ${\mathscr{L}}(\text{model})$ is the class of languages recognizable by the model. If $P$ is a problem (formal language) and $S$ is a set of problems (class of formal languages) the reductions mean as follows. $P\leq S$ means that $\exists P^{\prime}\in S:P\leq P^{\prime}$ and $S\leq P$ means that $\forall P^{\prime}\in S:P^{\prime}\leq P$ ; $S\sim P$ means $(P\leq S)\land(S\leq P)$ .

It is easy to verify that in the original proofs in [7], Turing reductions in (1) can be replaced by the log-space reductions provided we replace the emptiness problems with non-emptiness ones. So, we obtain

\displaystyle\begin{split}&\{\mathrm{M}\text{-}1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A},\mathrm{M}\text{-}2\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}\}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\{\overline{\mathrm{E}\text{-}1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}},\overline{\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}},\mathrm{M}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A},\mathrm{M}\text{-}2\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A},\\ &\mathrm{NRR}(\mathsf{P}),{\mathscr{L}}(\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM})\}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\overline{\mathrm{E}\text{-}2\mathrm{DBA}}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\overline{\mathrm{E}\text{-}2\mathrm{NBA}}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\overline{\mathrm{E}\text{-}\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}}.\end{split}

(3)

We also prove the reduction

\mathrm{M}\text{-}1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{DRR}(\mathsf{P}).

(4)

Results (3) combined with known facts imply assertions (5-8), where S is the set data structure as in SA, S₁ is the set data structure that supports the insertion of at most one word, that cannot be removed further but can be tested if a query-word in the set. In S_1,|Γ|=1 the word in the set is over an unary alphabet, ${\mathbf{PSPACE}}\textbf{\text{-}c}$ and ${\mathbf{NP}}\textbf{\text{-}c}$ are subclasses of complete languages.

		$\displaystyle{\mathbf{P}}={\mathscr{L}}(\mathrm{NPD}{\log}\text{-}\mathrm{TM}),\text{ where PD is Pushdown store},$		(5)
		$\displaystyle{\mathbf{PSPACE}}\supseteq{\mathscr{L}}(\mathrm{NS}{\log}\text{-}\mathrm{TM}),\exists L\in{\mathscr{L}}(\mathrm{NS}{\log}\text{-}\mathrm{TM}):L\in{\mathbf{PSPACE}}\textbf{\text{-}c},$		(6)
		$\displaystyle{\mathbf{PSPACE}}\supseteq{\mathscr{L}}(\mathrm{NS}_{1}{\log}\text{-}\mathrm{TM}),\exists L\in{\mathscr{L}}(\mathrm{NS}_{1}{\log}\text{-}\mathrm{TM}):L\in{\mathbf{PSPACE}}\textbf{\text{-}c},$		(7)
		$\displaystyle{\mathbf{NP}}\supseteq{\mathscr{L}}(\mathrm{NS}_{1,\|\Gamma\|=1}{\log}\text{-}\mathrm{TM}),,\exists L\in{\mathscr{L}}(\mathrm{NS}_{1,\|\Gamma\|=1}{\log}\text{-}\mathrm{TM}):L\in{\mathbf{NP}}\textbf{\text{-}c}.$		(8)

Assertion (5) is a well-known fact. Our technique here just shows a new connection: (5) directly follows from the fact that the emptiness problem for PDA is ${\mathbf{P}}$ -complete. Assertions (6-8) are new results to the best of our knowledge, we prove them in Section 6. Assertions (7-8) lead to (3) for the corresponding classes of automata. For (6), we have already obtained the result in [14] in the same way and present in this paper the generalized technique.

2 Definitions

2.1 Notation on binary relations

We associate with a binary relation $R\subseteq A\times B$ the corresponding mappings $A\to 2^{B}$ and $2^{A}\to 2^{B}$ that are denoted by the same letter $R$ , so $R(a)=\{b:aRb\}$ and $R(S)=\cup_{a\in S}R(a)$ . A relation $R$ is the composition of the relations $P\subseteq A\times C$ and $Q\subseteq C\times B$ if $R=\{(a,b)\mid\exists c:aPc\land cQb\}$ ; we denote the composition as $Q\circ P$ . In the case of a set $S\subseteq C$ we treat $S$ as a binary relation $S\subseteq C\times\{0,1\}$ in the composition $S\circ P=S^{\prime}$ that returns the set $S^{\prime}\subseteq A$ . We denote the reflexive and transitive closure of $R\subseteq A\times A$ by $R^{*}$ ; the symbol $*$ can also be placed above the relation, e.g., $\vdash^{\!\!\!{}^{*}}$ . We denote by $R^{-1}\subseteq B\times A$ the inverse relation, i.e., $aRb\iff bR^{-1}a$ .

2.2 Rational Transductions

Our technique is based on the connection of NRR problems with rational cones. We recall the definitions borrowing them from the book [2]. A finite state transducer (FST) is a nondeterministic finite automaton with an output tape, and DFST is the deterministic version of FST. For the deterministic version, it is important that a transducer can write a word (but not only a single symbol) on the output tape on processing a letter from the input tape. Let $T$ be an FST; we also denote by $T$ the corresponding relation, i.e., $uTv$ if there exists a run of $T$ on the input $u$ from the initial state to a final state such that at the end of the run the word $v$ is written on the output tape. The rational dominance relation $A\mathop{\leq_{\mathrm{rat}}}B$ holds if there exists an FST $T$ such that $A=T(B)$ , here $A$ and $B$ are languages. The relations computable by FSTs are known as rational relations. The following lemmata are algorithmic versions of well-known facts (see [2], Chapter III), the first one is the algorithmic version of the Elgot-Mezei theorem. The log-space algorithms follow from straight-forward constructions.

Lemma 2.

For FSTs $T_{1}$ and $T_{2}$ such that $T_{1}\subseteq\Sigma^{*}\times\Delta^{*}$ , $T_{2}\subseteq\Delta^{*}\times\Gamma^{*}$ , and FA ${\cal A}$ such that $L({\cal A})\subseteq\Delta^{*}$ , there exists an FST $T$ such that $T=T_{2}\circ T_{1}\subseteq\Sigma^{*}\times\Gamma^{*}$ , and NFA ${\cal B}$ recognizing the language $T_{1}^{-1}L({\cal A})$ . So, the relation $\mathop{\leq_{\mathrm{rat}}}$ is transitive. Moreover, $T$ and ${\cal B}$ are constructible in logarithmic space. We denote FST $T$ and NFA ${\cal B}$ as $T_{2}\circ T_{1}$ and ${\cal A}\circ T_{1}$ respectively.

Lemma 3.

For each FST $T$ there exists an FST $T^{-1}$ that computes the inverse relation of the relation $T$ . FST $T^{-1}$ is log-space constructible by FST $T$ .

A rational cone is a family of languages $\mathbf{C}$ that is closed under the rational dominance relation: $A\mathop{\leq_{\mathrm{rat}}}B$ and $B\in\mathbf{C}$ imply $A\in\mathbf{C}$ . If there exists a language $F\in\mathbf{C}$ such that $L\mathop{\leq_{\mathrm{rat}}}F$ for any $L\in\mathbf{C}$ , then $\mathbf{C}$ is a principal rational cone generated by $F$ ; we denote it as $\mathbf{C}={\cal T}(F)$ .

Rational transductions for context-free languages were thoroughly investigated in the 1970s, particularly by the French school. The main results of this research were published in Berstel’s book [2]. As described in [2], it follows from the Chomsky-Schützenberger theorem that ${\mathsf{CFL}}$ is a principal rational cone: ${\mathsf{CFL}}={\cal T}(D_{2})$ , where $D_{2}$ is the Dyck language on two types of brackets.

2.3 Computational Models

Firstly, we define BA. We provide the definition that is equivalent to the original definition from [7] but has technical differences, for the sake of convenience. Then we provide the definitions of other models: the refined definition of Balloon automata in terms of protocols and computational models based on ${\log}\text{-}\mathrm{TM}$ that are connected with $\mathrm{NRR}$ -problem as well as with $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ .

As it said, the balloon is a storage medium of unspecified structure. Thus its states are represented by (a subset of) positive integers. A BA can get limited information about the state of the balloon (the balloon information function in the definition below) and can modify the states of the balloon (the balloon control function). Here we need 1BAs only. So we give the definition for them. The definitions for 2BAs are similar, they are provided in [7].

Definition 4.

A $1$ -way balloon automaton (1BA) is defined by a tuple

\langle S,\Sigma_{\vartriangleright\vartriangleleft},B_{S},B_{I},\mathsf{get}_{\mathsf{B_{I}}},\mathsf{upd}_{\mathsf{B_{S}}},F,s_{0},\delta\rangle,\quad\text{where}

•

$S$ is the finite set of automaton states.
•

$\Sigma_{\vartriangleright\vartriangleleft}=\Sigma\cup\{\vartriangleright,\vartriangleleft\}$ , where $\Sigma$ is the finite input alphabet and ${\vartriangleright,\vartriangleleft}$ are the endmarkers. The input has the form $\vartriangleright\!w\!\vartriangleleft,\,w\in\Sigma^{*}$ .
•

$B_{S}\subseteq\mathbb{Z}_{>0}$ is the set of the balloon states.
•

$B_{I}$ is the finite set of the balloon information states.
•

$\mathsf{get}_{\mathsf{B_{I}}}:B_{S}\to B_{I}$ is a total computable function (balloon information function).
•

$\mathsf{upd}_{\mathsf{B_{S}}}$ is a partially computable function from $S\times B_{S}$ to $B_{S}$ (balloon control function).
•

$F\subsetneq S$ is the set of the final states.
•

$s_{0}\in S\setminus F$ is the initial state.
•

$\delta$ is the transition relation (a partial function for deterministic automata) defined as $\delta\subseteq(S\times\Sigma_{\vartriangleright\vartriangleleft,\varepsilon}\times B_{I})\times S$ ; hereinafter $\Gamma_{\varepsilon}=\Gamma\cup\{\varepsilon\}$ for any alphabet $\Gamma$ .

Definition 5.

A configuration of a $1\mathrm{BA}$ is a triple $(q,u,i)\in S\times\Sigma_{\vartriangleright\vartriangleleft}^{*}\times B_{S}$ , where $u$ is the unprocessed part of the input $w$ so $u$ is either $\vartriangleright\!w\!\vartriangleleft$ or a suffix of $w\!\vartriangleleft$ . The initial configuration of $1\mathrm{BA}$ is $(s_{0},\vartriangleright\!w\!\vartriangleleft,1)$ , a move of $1\mathrm{BA}$ is defined by the relation $\vdash$ on configurations as follows: $(q,\sigma u,i)\vdash(p,u,j)$ , where $\sigma\in\Sigma_{\vartriangleright\vartriangleleft,\varepsilon}$ if $j=\mathsf{upd}_{\mathsf{B_{S}}}(p,i),\,p\in\delta(q,\sigma,\mathsf{get}_{\mathsf{B_{I}}}(i))$ . A $1\mathrm{BA}$ accepts the input $w$ if there exists a sequence of moves (computational path) such that after processing of $\vartriangleright\!w\!\vartriangleleft$ the final state is reached, i.e., $(s_{0},\vartriangleright\!w\!\vartriangleleft,1)\vdash^{\!\!\!{}^{*}}(q_{f},\varepsilon,i)$ , where $q_{f}\in F,\,i\in B_{S}$ .

It is not easy to define classes of balloon automata (like PDAs or SAs) since one needs to define valid families of functions $\mathsf{get}_{\mathsf{B_{I}}}$ and $\mathsf{upd}_{\mathsf{B_{S}}}$ . One can see an example of PDAs definition in terms of BA in [7]. We suggest another approach for the definition of BA classes in Section 4. The approach simplifies the definitions since it is only needed to define a language of correct protocols to define an ADS.

We define a protocol as a sequence of triples $p_{i}=u_{i}\mathsf{q}_{i}\mathsf{r}_{i}$ of the query-word $u_{i}$ , the query $\mathsf{q}_{i}$ and the response $\mathsf{r}_{i}$ on the query. Numerous extra conditions are listed in the following formal definition.

Definition 6.

Let $\Gamma_{\textsf{write}},\Gamma_{\mathsf{query}},\Gamma_{\mathsf{resp}}$ be finite disjoint alphabets such that $\Gamma_{\mathsf{query}}\neq\varnothing,\Gamma_{\mathsf{resp}}\neq\varnothing$ . Let $\mathsf{valid}\subseteq\Gamma_{\mathsf{query}}\times\Gamma_{\mathsf{resp}}$ be a relation that provides the correspondence between queries and possible responses. A protocol is a word $p$ such that $p=p_{1}\cdots p_{n}$ , where $n\geq 0$ , $p_{i}=u_{i}\mathsf{q}_{i}\mathsf{r}_{i}$ , $u_{i}\in\Gamma_{\textsf{write}}^{*}$ , $q_{i}\in\Gamma_{\mathsf{query}}$ , $r_{i}\in\Gamma_{\mathsf{resp}}$ , and $\mathsf{r}_{i}\in\mathsf{valid}(\mathsf{q}_{i})$ . We call a word $p_{i}$ a query block. We say that a language $\mathsf{P}\subseteq(\Gamma_{\textsf{write}}^{*}\Gamma_{\mathsf{query}}\Gamma_{\mathsf{resp}})^{*}$ is a language of correct protocols if the axioms (i-v) hold:

(i)

$\varepsilon\in\mathsf{P}$ ;
(ii)

$\forall p\in\mathsf{P}:p$ is a protocol;
(iii)

$\forall p\in\mathsf{P}:$ if $p=p_{1}p_{2}$ and $p_{1}$ is a protocol, then $p_{1}\in\mathsf{P}$ ;
(iv)

$\forall p\in\mathsf{P}\;\forall u\in\Gamma_{\textsf{write}}^{*}\;\forall\mathsf{q}\in\Gamma_{\mathsf{query}}\;\exists\mathsf{r}\in\Gamma_{\mathsf{resp}}:pu\mathsf{q}\mathsf{r}\in\mathsf{P}$ ;
(v)

$\forall pu\mathsf{q}\mathsf{r}\in\mathsf{P}:$ if $p^{\prime}\in\mathsf{P}$ and $p^{\prime}=pu\mathsf{q}\mathsf{r}^{\prime}s$ , then $\mathsf{r}^{\prime}=\mathsf{r}$ ;
(vi)

$\exists\mathsf{q}\in\Gamma_{\mathsf{query}},\mathsf{r}\in\Gamma_{\mathsf{resp}}\;\forall p_{1},p_{2}\in\mathsf{P}:p_{1}\mathsf{q}\mathsf{r}p_{2}\in\mathsf{P}$ .

Axiom (vi) does not hold in the general case, e.g., for SAs and counter automata without zero tests. It is needed to describe the connection of automata with an ADS with BAs in Section 4.

A language of correct protocols $\mathsf{P}$ generates the corresponding class of languages, the principal rational cone ${\cal T}(\mathsf{P})$ . All examples of BAs languages classes in [7] can be presented as ${\cal T}(\mathsf{P})$ . We provide here only two examples.

Example 7.

It is well-known [2] that ${\mathsf{CFL}}={\cal T}(D_{2})$ , where $D_{2}$ is the Dyck language with two types of parentheses. It is also well-known that a Dyck word is a protocol of the stack. We transform the language $D_{2}$ into a language of protocols ${\mathsf{D_{2}}\text{-}\mathsf{PROT}}$ as follows.

We define the alphabets $\Gamma_{\textsf{write}}=\varnothing$ , $\Gamma_{\mathsf{query}}=\{\mathsf{push}_{\textsf{(}},\mathsf{push}_{\textsf{[}},\mathsf{pop}\}$ , $\Gamma_{\mathsf{resp}}=\{\textsf{(},\textsf{)},\textsf{[},\textsf{]}\}$ , $\mathsf{valid}=\{(\mathsf{push}_{\textsf{[}},\textsf{[}\,),(\mathsf{push}_{\textsf{(}},\textsf{(}\,),(\mathsf{pop},\textsf{]}\,),(\mathsf{pop},\textsf{)}\,)\}$ . To define correct protocols we use an FST $T$ that erases all symbols from $\Gamma_{\mathsf{query}}$ of the input. So,

{\mathsf{D_{2}}\text{-}\mathsf{PROT}}=\{p\mid T(p)\in D_{2}\}.

By the definition $D_{2}\mathop{\leq_{\mathrm{rat}}}{\mathsf{D_{2}}\text{-}\mathsf{PROT}}$ , so we have that ${\cal T}(D_{2})\subseteq{\cal T}({\mathsf{D_{2}}\text{-}\mathsf{PROT}})$ . It is also easy to show that ${\mathsf{D_{2}}\text{-}\mathsf{PROT}}\mathop{\leq_{\mathrm{rat}}}D_{2}$ , so ${\cal T}({\mathsf{D_{2}}\text{-}\mathsf{PROT}})={\cal T}(D_{2})={\mathsf{CFL}}$ .

Note that we set here $\Gamma_{\textsf{write}}=\varnothing$ for the sake of simplicity. One can use another variant: $\Gamma_{\textsf{write}}=\{\textsf{(},\textsf{[}\}$ , $\Gamma_{\mathsf{query}}=\{\textsf{multipush},\mathsf{pop}\}$ , $\Gamma_{\mathsf{resp}}=\{\textsf{pushed},\textsf{)},\textsf{]}\}$ . ∎

The following example is a starting point for the generalization presented in this paper.

Example 8.

The data structure Set consists of the set $\SS$ which is initially empty. Set supports the following operations: $\mathsf{in}(x):\SS\to\SS\cup\{x\}$ , $\mathsf{out}(x):\SS\to\SS\setminus\{x\}$ , $\mathsf{test}(x):x\stackrel{{\scriptstyle?}}{{\in}}\SS$ . We define the protocol language SA-PROT consistently with [13, 14], so the elements of alphabets below are individual symbols while they are words in [13, 14]. $\Gamma_{\textsf{write}}=\{a,b\}$ , $\Gamma_{\mathsf{query}}=\{\#\mathsf{in},\#\mathsf{out},\#\mathsf{test}\},\Gamma_{\mathsf{resp}}=\{\#,+\#,-\#\},\mathsf{valid}=\{(\#\mathsf{in},\#),(\#\mathsf{out},\#),(\#\mathsf{test},+\#),(\#\mathsf{test},-\#)\}$ .

It was proved in [13] that ${\mathscr{L}}(1\mathrm{NSA})={\cal T}({\text{\sf{SA\text{-}PROT}}})$ . ∎

Definition 9.

Fix a language of correct protocols $\mathsf{P}$ . An automaton equipped with auxiliary data structure $\mathrm{B_{\mathsf{P}}}$ (defined by $\mathsf{P}$ ) is defined by a tuple

\langle S,\Sigma_{\vartriangleright\vartriangleleft},\Gamma_{\textsf{write}},\Gamma_{\mathsf{query}},\Gamma_{\mathsf{resp}},F,s_{0},\delta\rangle,\text{ where}

•

$S$ , $\Sigma_{\vartriangleright\vartriangleleft}$ , $F$ , $s_{0}$ are the same as in Definition 4, so as $\Sigma_{\vartriangleright\vartriangleleft,\varepsilon}$ .
•

$S=S_{\textsf{write}}\cup S_{\mathsf{query}}$ , $S_{\textsf{write}}\cap S_{\mathsf{query}}=\varnothing$ .
•

$\mathsf{P}\subseteq(\Gamma_{\textsf{write}}^{*}\Gamma_{\mathsf{query}}\Gamma_{\mathsf{resp}})^{*}$ .

•

$\delta$ is the transition relation defined as

\delta\subseteq([S_{\textsf{write}}\times\Sigma_{\vartriangleright\vartriangleleft,\varepsilon}]\times[\Gamma_{\textsf{write}}^{*}\times S])\cup(S_{\mathsf{query}}\times\Gamma_{\mathsf{query}}\times\Gamma_{\mathsf{resp}}\times S_{\textsf{write}}).

The automaton has a one-way write-only query tape. During the processing of the input, it writes query-words $u_{i}\in\Gamma_{\textsf{write}}^{*}$ on the query tape, performs queries $\mathsf{q}_{i}$ , and receives responses $\mathsf{r}_{i}$ such that $u_{1}\mathsf{q}_{1}\mathsf{r}_{1}\cdots u_{n}\mathsf{q}_{n}\mathsf{r}_{n}\in\mathsf{P}$ . After each query, the query tape is erased.

A configuration of an ADS-automaton is a tuple

(s,v,u,p)\in S\times\Sigma_{\vartriangleright\vartriangleleft}^{*}\times\Gamma_{\textsf{write}}^{*}\times(\Gamma_{\textsf{write}}^{*}\Gamma_{\mathsf{query}}\Gamma_{\mathsf{resp}})^{*},

where $v$ is the unprocessed part of the input $w$ , i.e., $v$ is the suffix of $\vartriangleright\!w\!\vartriangleleft$ , $u$ is the content of the work tape, and $p$ is the protocol of the automaton operating with the data structure. A move of an automaton is defined via the relation $\vdash$ on configurations which is defined as follows:

	$\displaystyle(s,av,u,p)$	$\displaystyle\vdash(s^{\prime},v,ux,p),$	$\displaystyle\text{ if }s\in S_{\textsf{write}},\,(s,a,x,s^{\prime})\in\delta,$		(9)
	$\displaystyle(s,v,u,p)$	$\displaystyle\vdash(s^{\prime},v,\varepsilon,pu\mathsf{q}\mathsf{r}),$	$\displaystyle\text{ if }s\in S_{\mathsf{query}},\,(s,\mathsf{q},\mathsf{r},s^{\prime})\in\delta,\,pu\mathsf{q}\mathsf{r}\in\mathsf{P}.$		(10)

A configuration is initial if it has the form $(s_{0},\vartriangleright\!w\!\vartriangleleft,\varepsilon,\varepsilon)$ , a configuration is accepting if it has the form $(s_{f},\varepsilon,\varepsilon,p)$ , where $s_{f}\in F,p\in\mathsf{P}$ . A word $w$ is accepted by an automaton with ADS if $(s_{0},\vartriangleright\!w\!\vartriangleleft,\varepsilon,\varepsilon)\vdash^{\!\!\!{}^{*}}(s_{f},\varepsilon,\varepsilon,p)$ . An automaton is deterministic if for all configurations $c,c_{1},c_{2}$ from $c\vdash c_{1}$ and $c\vdash c_{2}$ follows $c_{1}=c_{2}$ .

For the next two models, we provide the definitions on the implementation level only.

Definition 10.

A $\mathrm{D}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}$ ( $\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}$ ) is a deterministic (nondeterministic) ${\log}\text{-}\mathrm{TM}$ $M$ equipped with an ADS defined by the language of correct protocols $\mathsf{P}$ . I.e., $M$ is equipped with an additional write-only one-way query tape that is used to write down a query word $u_{i}$ and perform a query. After a query $\mathsf{q}_{i}$ is performed, the tape is erased and the finite state control of $M$ receives the result $\mathsf{r}_{i}$ of the query $\mathsf{q}_{i}$ . The query results are consistent with $\mathsf{P}$ , i.e., $p_{1}\cdots p_{n}\in\mathsf{P}$ , $p_{i}=u_{i}\mathsf{q}_{i}\mathsf{r}_{i}$ .

A configuration of $\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}$ is a triple $(c,u,p)$ where $c$ is the configuration of ${\log}\text{-}\mathrm{TM}$ -part, $u$ is the word written on the query tape, and $p\in\mathsf{P}$ is the protocol that is the result of all the performed queries. A $\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}$ $M$ accepts a word $w$ if $(c_{0}(w),\varepsilon,\varepsilon)\vdash^{\!\!\!{}^{*}}(c_{f},\varepsilon,p)$ , where $c_{0}(w)$ is the initial configuration of the ${\log}\text{-}\mathrm{TM}$ -part of $M$ , $c_{f}$ is the accepting configuration of ${\log}\text{-}\mathrm{TM}$ -part of $M$ , and $p\in\mathsf{P}$ , the relation $\vdash$ corresponds to the $M$ ’s moves.

Definition 11.

Let $F$ be an arbitrary formal language (filter). A $\mathrm{DA}_{F}{\log}\text{-}\mathrm{TM}$ ( $\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM}$ ) is a deterministic (non-deterministic) log-space TM equipped with a read-only one-way infinite tape called advice tape. At the beginning of the computation, the advice tape contains a word $y\Lambda^{\infty}$ , where $y\in F$ and $\Lambda$ is a symbol that indicates empty cells.

A configuration of an $\mathrm{A}_{F}{\log}\text{-}\mathrm{TM}$ $M$ is a pair $(c,u)$ where $c$ is the configuration of the ${\log}\text{-}\mathrm{TM}$ -part of $M$ , $u$ is the unprocessed part of $y$ . $M$ accepts a word $x$ if there exists $y\in F$ such that $(c_{0}(x),y)\vdash^{\!\!\!{}^{*}}(c_{f},\varepsilon)$ , where $c_{0}(x)$ is the initial configuration of the ${\log}\text{-}\mathrm{TM}$ -part of $M$ , $c_{f}$ is the accepting configuration of the ${\log}\text{-}\mathrm{TM}$ -part of $M$ .

An equivalent model to $\mathrm{DA}_{F}{\log}\text{-}\mathrm{TM}$ s appeared in [17] and its journal version [19] under the name ‘‘models of generalized nondeterminism (GNA)’’ and lead to the appearance of the $\mathrm{DRR}(F)$ problem. In this paper we repeat the steps of [17, 19] to establish the connection between $\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM}$ and $\mathrm{NRR}(F)$ problem in Section 5 to prove one of the main results of the paper Eq. (2). We also show the equivalence between $\mathrm{DA}_{F}{\log}\text{-}\mathrm{TM}$ s and GNA. The difference is that in GNA it is allowed not to process the advice till the end of the word, so it was demanded for $F$ to be a prefix-closed language in [17, 19].

3 Principal Rational Cones and
the NRR-Problem

In this section, we provide the core of our technique. We prove that ${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})$ is a principal rational cone generated by the language of correct protocols $\mathsf{P}$ , i.e., ${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})={\cal T}(\mathsf{P})$ ; it is the first main result of the section. This fact yields structural results about the family ${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})$ , as well as the results on the complexity of the emptiness problem. We focus in this section on the connection between the non-emptiness problem and the $\mathrm{NRR}(\mathsf{P})$ problem. We prove that these problems are equivalent under log-space reductions, it is the second main result of the section. It leads us to the main results of the paper in Section 5. We provide in this section structural results that naturally arise in the proofs. Other structural results are discussed in Section 4 since their relation to [7].

Most of the results of this section directly generalize the results of [13, Section 3] (see the full journal version [15]). In most cases, to get a generalized result, one can substitute SA protocols (see Example 8) with general protocols as defined in Definition 6. So, our general approach comes from the generalization of the technique that was developed for SAs. One can also find in [15] more technically detailed proofs.

Lemma 12.

There exists a $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ $M_{\mathsf{P}}$ recognizing $\mathsf{P}$ .

Proof.

Let us assume that $M_{\mathsf{P}}$ has on the input the word of the form $p_{1}\cdots p_{n}$ , where $p_{i}=u_{i}\mathsf{q}_{i}\mathsf{r}_{i}$ (since it is a regular condition). $M_{\mathsf{P}}$ writes a word $u_{i}$ on the query tape, performs the query $\mathsf{q}_{i}$ and tests that the responce is $\mathsf{r}_{i}$ . If all tests are correct than $p$ is accepted; otherwise, it is rejected. ∎

Lemma 13.

For each language of correct protocols $\mathsf{P}\subseteq(\Gamma_{\textsf{write}}^{*}\Gamma_{\mathsf{query}}\Gamma_{\mathsf{resp}})^{*}$ there exists a language of correct protocols $\mathsf{P}_{\{a,b\}}\subseteq(\{a,b\}^{*}\Gamma_{\mathsf{query}}\Gamma_{\mathsf{resp}})^{*}$ , provided $(\Gamma_{\mathsf{query}}\cup\Gamma_{\mathsf{resp}})\cap\{a,b\}=\varnothing$ , such that the following properties hold

•

${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})={\mathscr{L}}(1\mathrm{NB}_{\mathsf{P}_{\{a,b\}}}\mathrm{A})$ ,
•

${\mathscr{L}}(1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A})={\mathscr{L}}(1\mathrm{DB}_{\mathsf{P}_{\{a,b\}}}\mathrm{A})$ ,
•

There exists a DFST $T$ such that $T(\mathsf{P})=\mathsf{P}_{\{a,b\}}$ and $T^{-1}$ is a DFST,
•

For each $1x\mathrm{B_{\mathsf{P}}}\mathrm{A}$ $M$ there exists an equivalent $1x\mathrm{B}_{\mathsf{P}_{\{a,b\}}}\mathrm{A}$ $M_{\{a,b\}}$ such that $M_{\{a,b\}}$ is log-space constructible by $M$ and vice versa ( $x\in\{N,D\}$ ).

Proof.

Enumerate all letters from $\Gamma_{\textsf{write}}$ and encode the $i$ -th letter as $ab^{i}a$ . Such encoding is computable by a DFST $T$ and the inverse encoding is computed by $T^{-1}$ that is a DFST as well. So, $\mathsf{P}_{\{a,b\}}=T(\mathsf{P})$ (we assume that $T$ preserves letters from $\Gamma_{\mathsf{query}}\cup\Gamma_{\mathsf{resp}}$ ). Now we show that for each $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ $M$ there exists an equivalent $1\mathrm{NB}_{\mathsf{P}_{\{a,b\}}}\mathrm{A}$ $M_{\{a,b\}}$ .

By our construction, $M_{\{a,b\}}$ simulates $M$ , i. e., $M_{\{a,b\}}$ has states of the form $(s,\mathsf{aux})$ where $s$ is a state of $M$ and $\mathsf{aux}$ is an auxiliary information needed for simulation; so for each configuration $((s,\mathsf{aux}),v,u^{\prime},p^{\prime})$ of $M_{\{a,b\}}$ there is a corresponding configuration $(s,v,u,p)$ of $M$ , where $p^{\prime}=T(p)$ and $u^{\prime}$ is a prefix of $T(u)$ . $M_{\{a,b\}}$ computes $T(u)$ by simulation of $T$ via finite control and information of this simulation is stored in $\mathsf{aux}$ ; the other part of finite control simulates $M$ ’s transitions.

Each $1\mathrm{NB}_{\mathsf{P}_{\{a,b\}}}\mathrm{A}$ $M_{\{a,b\}}$ can be simulated by a $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ $M$ in the same way, one shall use $T^{-1}$ instead of $T$ . Note that described simulations preserve determinism and the transformations between $M$ and $M_{\{a,b\}}$ are log-space computable. ∎

Lemma 14.

Let $T$ be an FST with the input alphabet $\Delta$ and the output alphabet $\Sigma$ and $M$ be a $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ over the alphabet $\Sigma$ . There exists a $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ $M^{\prime}=M\circ T$ recognizing the language $T^{-1}(L(M))$ . If $T$ is a DFST and $M$ is a $1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ then $M^{\prime}$ is a $1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ as well.

Proof.

The simulation is performed in a straight-forward way. $M^{\prime}$ guesses an image $w\in T(w^{\prime})$ of the input word $w^{\prime}$ such that $w\in L(M)$ if $T(w^{\prime})\cap L(M)\neq\varnothing$ , computes $w$ by simulation of $T$ and simulates $M$ on the input $w$ . $M^{\prime}$ has configurations of the form $((s,\mathsf{aux}),v^{\prime},u,p)$ that correspond to configurations $(s,v,u,p)$ of $M$ . As in the proof of Lemma 13, the $\mathsf{aux}$ information is used to simulate $T$ via finite state control. The construction preserves determinism of $1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ if $T$ is a DFST. ∎

Lemma 15.

Let $M$ be a $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ . There exists an FST $T_{M}$ such that $w\in L(M)$ iff $T_{M}(w)\cap\mathsf{P}\neq\varnothing$ . Moreover, $p\in T_{M}(w)$ iff $M$ has a run on $w$ such that $(s_{0},w,\varepsilon,\varepsilon)\vdash^{\!\!\!{}^{*}}(s_{f},\varepsilon,\varepsilon,p)$ .

We denote by $s\xrightarrow[x]{a}s^{\prime}$ the move of $T_{M}$ from the state $s$ to the state $s^{\prime}$ on which it reads $a$ from the input tape and writes $x$ on the output tape.

Proof.

One can construct $T_{M}$ by $M$ as follows. $T_{M}$ has the same states as $M$ (and the same initial state and set of accepting states). In the case of move (9), $T_{M}$ has the move $s\xrightarrow[x]{a}s^{\prime}$ , and in the case of move (10), $T_{M}$ has moves $s\xrightarrow[\mathsf{q}\mathsf{r}^{\prime}]{\varepsilon}s^{\prime}$ for all $\mathsf{r}^{\prime}$ such that $(s,\mathsf{q},\mathsf{r}^{\prime},s^{\prime})\in\delta_{M}$ .

Assertion $p\in T_{M}(w)\cap\mathsf{P}$ implies that $M$ has the corresponding run by axiom (v) in Definition 6. So, if $T_{M}(w)$ contains a correct protocol $p$ then $M$ has the run $(s_{0},w,\varepsilon,\varepsilon)\vdash^{\!\!\!{}^{*}}(s_{f},\varepsilon,\varepsilon,p)$ . The implication in the other direction directly follows from the construction of $T_{M}$ . ∎

Definition 16.

An FST $T_{M}$ from Lemma 15 called extractor (of protocols).

Theorem 17.

${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})={\cal T}(\mathsf{P})$ .

Proof.

Lemma 15 implies that for each $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ $M$ there exists an extractor $T_{M}$ such that $L(M)=T_{M}^{-1}(\mathsf{P})$ , and by Lemma 3 there exists FST $T=T_{M}^{-1}$ such that $L(M)=T(\mathsf{P})$ , so $L(M)\mathop{\leq_{\mathrm{rat}}}\mathsf{P}$ and therefore ${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})\subseteq{\cal T}(\mathsf{P})$ .

The inclusion ${\cal T}(\mathsf{P})\subseteq{\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})$ follows from Lemmata 12 and 14: for each $L=T^{\prime}(\mathsf{P})$ we take an FST $T=T^{\prime-1}$ and apply the lemmata. ∎

Theorem 18.

$\overline{\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(\mathsf{P})\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\overline{\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}}$ .

Proof.

Let $M$ be the input of the non-emptiness problem $\overline{\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}}$ and $T_{M}$ be the corresponding extractor. By Lemma 15, $w\in L(M)\iff T_{M}(w)\cap\mathsf{P}\neq\varnothing$ . So, $L(M)\neq\varnothing\iff T_{M}(\Sigma^{*})\cap\mathsf{P}\neq\varnothing$ . Construct an NFA ${\cal A}$ recognizing $T_{M}(\Sigma^{*})$ by Lemma 2 in log space. So,

L(M)\neq\varnothing\iff L({\cal A})\cap\mathsf{P}\neq\varnothing\stackrel{{\scriptstyle\text{Def.~{}\ref{def:RR}}}}{{\iff}}{\cal A}\in\mathrm{NRR}(\mathsf{P}).

So we have proved $\overline{\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(\mathsf{P})$ .

The reduction $\mathrm{NRR}(\mathsf{P})\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\overline{\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}}$ follows from Lemmata 12 and 14. We construct by ${\cal A}$ on the input of $\mathrm{NRR}(\mathsf{P})$ the automaton $M=M_{\mathsf{P}}\circ T$ , where $xTy\iff(x=y)\land(x\in L({\cal A}))$ . ∎

Theorem 19.

$\mathrm{M}\text{-}1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{DRR}(\mathsf{P})$ .

Proof.

We construct a DFA ${\cal A}$ on the input of $\mathrm{DRR}(\mathsf{P})$ by $(w,M)$ on the input of $\mathrm{M}\text{-}1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ via a log-space transducer. The idea is that ${\cal A}$ simulates $M$ ’s run on the input $w$ and checks the correctness of the protocol by reading the input word, that is a protocol $p\in\mathsf{P}$ . The protocol $p$ is accepted iff $p$ is the protocol of $M$ on processing of $w$ and $M$ accepts $w$ .

A state of ${\cal A}$ is a tuple $(s,i,\mathsf{aux})$ where $s\in S_{M}$ , $i$ is the index of the letter $w_{i}$ over the $M$ ’s head and $\mathsf{aux}$ is the auxiliary information needed for the simulation. To simulate a transition of $M$ , the following actions are performed by ${\cal A}$ . If $M$ writes a word $v$ (a subword of the future query word) to the query tape, ${\cal A}$ stores $v$ in the finite memory (a part of $\mathsf{aux}$ component of its states) and checks whether the unprocessed part of its input begins with $v$ (if not, the input word $p$ is rejected). If $M$ performs a query $\mathsf{q}$ , ${\cal A}$ verifies that the unprocessed part of its input begins with $\mathsf{q}\mathsf{r}$ and performs the transition that $M$ does after receiving $\mathsf{r}$ as a response. ${\cal A}$ accepts the input $p$ if it was not rejected during the simulation, $i=|w|+1$ (i.e., $M$ ’s head is over $\vartriangleleft$ ) and $M$ is in accepting state.

It follows from the construction that ${\cal A}$ accepts $p$ iff $p$ is the protocol of $M$ processing the input $w$ . Note that this protocol is unique since $M$ is a $1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ . Also since $M$ is $1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ , ${\cal A}$ is log-space constructible. Finally, $L({\cal A})\cap\mathsf{P}\neq\varnothing\iff w\in L(M)$ , so $\mathrm{M}\text{-}1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{DRR}(\mathsf{P})$ . ∎

4 Connection with Balloon Automata

We provide a high-level description of classes ${\mathscr{M}}_{B}$ of BAs. The definition in a more formal style could be found in [7].

Definition 20.

A subset of BAs ${\mathscr{M}}_{B}$ is a class of BAs if the following conditions hold.

(I)

${\mathscr{M}}_{B}$ contains all automata with $\mathsf{get}_{\mathsf{B_{I}}}$ such that, for each state $s$ , $\mathsf{upd}_{\mathsf{B_{S}}}(s,i)$ is either $i$ for all $i$ or $\mathsf{upd}_{\mathsf{B_{S}}}(s,i)=j$ for all $i$ and some constant $j$ .
(II)

If ${\cal A},{\cal B}\in{\mathscr{M}}_{B}$ , $\mathsf{upd}_{\mathsf{B_{S}}}^{\cal A},\mathsf{get}_{\mathsf{B_{I}}}^{\cal B}$ , $\mathsf{upd}_{\mathsf{B_{S}}}^{\cal A},\mathsf{upd}_{\mathsf{B_{S}}}^{\cal B}$ are the corresponding functions of ${\cal A}$ and ${\cal B}$ , then ${\mathscr{M}}_{B}$ includes each automaton ${\cal C}$ such that $\mathsf{get}_{\mathsf{B_{I}}}^{\cal C}$ and $\mathsf{upd}_{\mathsf{B_{S}}}^{\cal C}$ are the functions that are obtained from the functions of ${\cal A}$ and ${\cal B}$ via finite control, i.e., for each state $s\in S_{\cal C}$ $\mathsf{get}_{\mathsf{B_{I}}}^{\cal C}(s,i)$ equals to either $\mathsf{get}_{\mathsf{B_{I}}}^{\cal A}(s,i)$ or $\mathsf{get}_{\mathsf{B_{I}}}^{\cal B}(s,i)$ for all $i$ , for each $i,j$ if $\mathsf{upd}_{\mathsf{B_{S}}}^{\cal C}(i)\neq\mathsf{upd}_{\mathsf{B_{S}}}^{\cal C}(j)$ then either $\mathsf{upd}_{\mathsf{B_{S}}}^{\cal A}(i)\neq\mathsf{upd}_{\mathsf{B_{S}}}^{\cal A}(j)$ or $\mathsf{upd}_{\mathsf{B_{S}}}^{\cal B}(i)\neq\mathsf{upd}_{\mathsf{B_{S}}}^{\cal A}(j)$ .

Property (I) implies that ${\mathscr{M}}_{B}$ contains automata that can reset any state $i$ of the balloon to the initial state $1$ (or to some fixed state $j$ as well). Together with Property (II) it implies that the balloon has a reset operation that sets the balloon’s state to the initial state. This property does not hold for SAs, so there is no direct correspondence between classes of languages of BAs and automata with an ADS in the general case.

Theorem 21.

For each ADS $\mathrm{B_{\mathsf{P}}}$ there exists a balloon $\mathrm{B}$ and a subset of BAs ${\mathscr{M}}_{B}$ such that the corresponding classes of languages coincide, i.e. ${\mathscr{L}}(xy\mathrm{B_{\mathsf{P}}}\mathrm{A})={\mathscr{L}}(xy\mathrm{BA})$ and Property (II) holds. If $\mathsf{P}$ has the reset operation (vi), Property (I) also holds, i.e ${\mathscr{M}}_{B}$ is a class (in terms of Definition 20).

Proof.

We begin with the construction of the balloon $B$ and the bijection from $xy\mathrm{B_{\mathsf{P}}}\mathrm{A}$ to $xy\mathrm{BA}$ such that $xy\mathrm{BA}$ form the set ${\mathscr{M}}_{B}$ satisfying Property (II). A state of the balloon $B$ is an integer that is the encoding of pairs of words $(p,u)$ , where $p$ is the current protocol, i.e., the protocol of all previous operations before the upcoming move, and $u$ is the word on the query-tape. We enumerate all $p\in\mathsf{P}$ and all $u\in\Sigma^{*}$ and use the standard enumeration of pairs of integers.

Firstly, we define functions $\mathsf{upd}_{\mathsf{B_{S}}}$ and $\mathsf{get}_{\mathsf{B_{I}}}$ for the BA $M^{B}_{\mathsf{P}}$ recognizing $\mathsf{P}$ . Recall that for any language of correct protocols $\mathsf{P}$ there exists $1\mathrm{D}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ $M_{\mathsf{P}}$ recognizing $\mathsf{P}$ by Lemma 12. The function $\mathsf{upd}_{\mathsf{B_{S}}}$ simulates write operations and queries: it just updates the ballon’s state according to the encoding. The function $\mathsf{get}_{\mathsf{B_{I}}}:\mathbb{Z}_{>0}\to\Gamma_{\mathsf{resp}}\cup\{\bot\}$ returns responses or $\bot$ if there were no query. For an arbitrary $xy\mathrm{B_{\mathsf{P}}}\mathrm{A}$ $M$ the $xy\mathrm{BA}$ $M^{B}$ is constructed as follows. The function $\mathsf{get}_{\mathsf{B_{I}}}^{M}$ is the same as for $M^{B}_{\mathsf{P}}$ for any $M^{B}$ . The function $\mathsf{upd}_{\mathsf{B_{S}}}^{M}$ is a modification of the function for $M^{B}_{\mathsf{P}}$ according to the finite state control of $M$ . We define the class ${\mathscr{F}}(\mathsf{upd}_{\mathsf{B_{S}}})$ more formally below to show that Property (II) holds.

As the result, the states of the ballon $B$ just encode the part of $xy\mathrm{B_{\mathsf{P}}}\mathrm{A}$ that describes the data structures, and $\mathsf{upd}_{\mathsf{B_{S}}}$ and $\mathsf{get}_{\mathsf{B_{I}}}$ simulate the work with the data structure defined by $\mathsf{P}$ . So we provided the bijection between $xy\mathrm{B_{\mathsf{P}}}\mathrm{A}$ and $xy\mathrm{BA}$ .

We move to a formal definition of the class ${\mathscr{F}}(\mathsf{upd}_{\mathsf{B_{S}}})$ . At first, we define ${\mathscr{F}}_{1}(\mathsf{upd}_{\mathsf{B_{S}}})$ satisfying Property (II). Assume that $M_{\mathsf{P}}$ writes at most one letter to the query tape per move and it also has a state $s_{\varepsilon}$ in which it neither writes nor performs query. So, $\mathsf{upd}_{\mathsf{B_{S}}}(s_{\varepsilon},i)=i$ for all $i$ (hereinafter in $M_{\mathsf{P}}^{B}$ ). We mark a state $s$ as $s_{a}$ if $M_{\mathsf{P}}$ writes $a$ on the output tape and mark a state $s$ as $s_{\mathsf{q}}$ if $M$ performs query $\mathsf{q}$ . From definition follows that $\mathsf{upd}_{\mathsf{B_{S}}}(s_{m},i)=\mathsf{upd}_{\mathsf{B_{S}}}(s^{\prime}_{m},i)$ for all states $s$ and $s^{\prime}$ marked by the same mark ( $a$ , $\varepsilon$ or $\mathsf{q}$ ). So we define a function $\mathsf{upd}_{\mathsf{B_{S}}}^{\mathsf{P}}:(\Gamma_{\textsf{write},\varepsilon}\cup\Gamma_{\mathsf{query}})\times\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ so that $\mathsf{upd}_{\mathsf{B_{S}}}^{\mathsf{P}}(m,i)=\mathsf{upd}_{\mathsf{B_{S}}}(s_{m},i)$ . So for any $xy\mathrm{BA}$ $M$ the function $\mathsf{upd}_{\mathsf{B_{S}}}^{M}$ defined as follows. The states of $M$ are marked by symbols from $\Gamma_{\textsf{write},\varepsilon}\cup\Gamma_{\mathsf{query}}$ and $\mathsf{upd}_{\mathsf{B_{S}}}^{M}(s_{m},i)=\mathsf{upd}_{\mathsf{B_{S}}}^{\mathsf{P}}(m,i)$ . It is easy to see that from our definition of ${\mathscr{F}}_{1}(\mathsf{upd}_{\mathsf{B_{S}}})$ follows the bijection between $xy\mathrm{B_{\mathsf{P}}}\mathrm{A}$ and $xy\mathrm{BA}$ and Property (II) holds as well.

If $\mathsf{P}$ has the reset operation (vi), then we shall modify the interpretation of $B$ since ${\mathscr{F}}(\mathsf{upd}_{\mathsf{B_{S}}})$ does not satisfy our definition anymore. Firstly we describe the interpretation of $\mathsf{upd}_{\mathsf{B_{S}}}$ functions for $xy\mathrm{BA}$ $M^{B}$ from Property (I). If $\mathsf{upd}_{\mathsf{B_{S}}}(s,i)=j$ , $i$ and $j$ encode pairs $(p_{i},u_{i})$ and $(p_{j},u_{j})$ respectively and $(p_{j},u_{j})$ is not obtained from $(p_{i},u_{i})$ by a single move of $M^{B}_{\mathsf{P}}$ , then we interpretate the state change $i\to j$ as follows. The corresponding to $M^{B}$ $xy\mathrm{B_{\mathsf{P}}}\mathrm{A}$ $M$ performs the reset operation and then performs sequence of queries that move the configuration from $(\varepsilon,\varepsilon)$ to $(p_{j},u_{j})$ during $\varepsilon$ moves. Note that by the definition of Property (I) $M^{B}$ has finitely many $j$ ’s in the range of $\mathsf{upd}_{\mathsf{B_{S}}}$ so $M$ is well-defined. Denote $\mathsf{upd}_{\mathsf{B_{S}}}$ functions for automata from Property (I) as ${\mathscr{F}}_{I}(\mathsf{upd}_{\mathsf{B_{S}}})$ . So ${\mathscr{F}}(\mathsf{upd}_{\mathsf{B_{S}}})$ is a closure of ${\mathscr{F}}_{I}(\mathsf{upd}_{\mathsf{B_{S}}})$ and ${\mathscr{F}}_{1}(\mathsf{upd}_{\mathsf{B_{S}}})$ in terms of Property (II). From Property (II) and our construction of $xy\mathrm{B_{\mathsf{P}}}\mathrm{A}$ ’s for Property (I) follows the construction of $xy\mathrm{B_{\mathsf{P}}}\mathrm{A}$ for any of $xy\mathrm{BA}$ from the closure in terms of Property (II). So, we have proved the second part of the theorem. ∎

So all the results from [7] that do not rely on (I) hold for $B_{\mathsf{P}}$ -automata. We are most interested in (1) and its complexity analogue (3). Many structural results from [7] follow from the fact that ${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})$ is a principal cone (Theorem 17), namely, closure of ${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})$ over union and rational transductions¹¹1Intersection and quotient with regular languages, gsm forward mapping are the partial cases of rational transductions.. We shall also mention the closure over gsm inverse mappings proved in [7] for all $xy\mathrm{BA}$ that implies the same closure for all $xy\mathrm{B_{\mathsf{P}}}\mathrm{A}$ .

Lemma 22.

If $\mathrm{B_{\mathsf{P}}}$ contains the reset operation then ${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})$ is closed over concatenation and iteration.

Proof.

We construct $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ ’s $M^{2}$ and $M^{*}$ by $1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}$ $M$ recognizing $L(M)\cdot L(M)$ and $L(M)^{*}$ respectively in a straight-forward way. $M^{2}$ simulates $M$ and nondeterministically guess the split of the input $uv$ such that $u,v\in L(M)$ at the end of the $u$ . If after processing of $u$ , $M$ is in an accepting state, $M^{2}$ performs the reset operation and simulates $M$ on $v$ . $M^{*}$ guesses the split of the input into $u_{1}u_{2}\ldots u_{m},u_{i}\in L(M)$ and acts in the similar way. ∎

The standard technique from [2] implies the following lemma.

Lemma 23.

If $\mathsf{P}\#\mathsf{P}\mathop{\leq_{\mathrm{rat}}}\mathsf{P}$ , $\#\not\in\Gamma$ , then ${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})$ is closed over concatenation. If $(\mathsf{P}\#)^{*}\mathop{\leq_{\mathrm{rat}}}\mathsf{P}$ , $\#\not\in\Gamma$ , then ${\mathscr{L}}(1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A})$ is closed over iteration.

Proof idea.

The construction is similar to the one from the proof of Lemma 22. FSTs $T_{L^{2}}$ and $T_{L^{*}}$ uses marks $\#$ to split the input and simulate an FST $T_{L}$ corresponding to the language $L$ , i.e., $L=T_{L}(\mathsf{P})$ . ∎

Remark 24.

We leave open the question of the reduction in the opposite direction. I.e., does for each class of BAs exist a language of correct protocols $\mathsf{P}$ such that BAs recognize the same class of languages as $\mathrm{B_{\mathsf{P}}}$ automata? The essence of the problem is as follows. If axioms (I-II) for the class of BAs are satisfied, does it imply that there exists a ‘‘universal’’ BA $M_{U}$ such that ${\mathscr{L}}(1\mathrm{NBA})={\cal T}(L(M_{U}))$ and for each $M\in 1\mathrm{NBA}$ there exists an FST $T$ such that $L(M)=L(M_{U}\circ T)$ ?

5 RR Problems and ${\log}\text{-}\mathrm{TM}$ Models

5.1 $\mathrm{A}_{F}{\log}\text{-}\mathrm{TM}$ models

In [17, 19] it was shown that $\mathrm{DRR}(\mathrm{Pref}(F\Lambda^{*}))$ is a complete problem in the class of languages recognizable by GNA with advices from $F$ (this model corresponds to $\mathrm{DA}_{F}{\log}\text{-}\mathrm{TM}$ , $\mathrm{Pref}(L)$ is the set of all prefixes of $L$ ). We prove that $\mathrm{DRR}(\mathrm{Pref}(F\Lambda^{*}))$ and $\mathrm{DRR}(F)$ are complete problems in the class ${\mathscr{L}}(\mathrm{DA}_{F}{\log}\text{-}\mathrm{TM})$ . We begin with the proof of similar result for $\mathrm{NRR}(F)$ and ${\mathscr{L}}(\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM})$ . We introduce the following auxiliary lemma for the sake of the proof.

Lemma 25 ([12]).

$F_{1}\mathop{\leq_{\mathrm{rat}}}F_{2}\Rightarrow\mathrm{NRR}(F_{1})\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(F_{2})$ .

Lemma 26.

${\mathscr{L}}(\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM})\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(F)$ .

Proof.

An $\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM}$ $M$ takes on the input a word $x$ and also takes $y\in F$ on the advice tape. $x\in L(M)\iff\exists y\in F:M(x,y)=1$ , where $M(x,y)=1$ if $M$ halts in an accepting state, $M(x,y)=0$ if $M$ halts in a rejecting state.

A surface-configuration of a $\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM}$ is a tuple $(q,\mathsf{mem},i,j)$ of the state $q$ , log-space memory configuration $\mathsf{mem}$ and the positions $i$ of the head on the input tape and $j$ of the head on the advice (one-way) tape. The tuples $(q,\mathsf{mem},i)$ are the states of finite automata ${\cal A}$ on the input of $\mathrm{NRR}(F)$ problem constructed by $M$ and $x$ . The initial state is $(q_{0},\varnothing,0)$ , where $q_{0}$ is the initial state of the $\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM}$ , accepting states are states of the form $(q_{f},\mathsf{mem},i)$ where $q_{f}$ is an accepting state of the $\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM}$ . The transitions between the states are determined by letters of $y$ , i.e. $(q,\mathsf{mem},i,j)\vdash(q^{\prime},\mathsf{mem}^{\prime},i^{\prime},j^{\prime})$ , $i^{\prime}\in\{i-1,i,i+1\}$ , $j^{\prime}\in\{j,j+1\}$ if $(q^{\prime},\mathsf{mem}^{\prime},i^{\prime})\in\delta_{\cal A}((q,\mathsf{mem},i,j),y_{j})$ . The list of the ${\cal A}$ ’s transitions $\delta_{\cal A}$ is log-space computable so as the set of the ${\cal A}$ ’s states as well.

Without loss of generality, we assume that $M$ always processes $y$ till the end, i.e. till mits $\Lambda$ on the advice tape. So, by the construction of ${\cal A}$ , we obtain

	$\displaystyle x\in L(M)$	$\displaystyle\iff\exists y\in F:M(x,y)\iff\exists y\in F,k\geq 0:y\Lambda^{k}\in L({\cal A})\iff$
		$\displaystyle\iff{\cal A}\in\mathrm{NRR}(F\Lambda^{*})\stackrel{{\scriptstyle\text{Lemma~{}\ref{lemma:leratRR}}}}{{\iff}}{\cal A}^{\prime}\in\mathrm{NRR}(F),$

where ${\cal A}^{\prime}$ is constructed by ${\cal A}$ due to the reduction in Lemma 25. Since $M$ is fixed, we get that

x\stackrel{{\scriptstyle?}}{{\in}}L(M)\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}{\cal A}\stackrel{{\scriptstyle?}}{{\in}}\mathrm{NRR}(F\Lambda^{*})\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}{\cal A}^{\prime}\stackrel{{\scriptstyle?}}{{\in}}\mathrm{NRR}(F),

and we obtain that ${\mathscr{L}}(\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM})\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(F)$ by the transitivity of the log-space reductions. ∎

Remark 27.

Note that $F\mathop{\sim_{\mathrm{rat}}}F\Lambda^{*}\mathop{\sim_{\mathrm{rat}}}\mathrm{Pref}(F\Lambda^{*})$ so the $\mathrm{NRR}$ problems for these filters are equivalent (up to $\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}$ reductions). The equivalence holds since nondeterministic FST’s can have several images for the same word, particularly write many $\Lambda$ ’s at the end of the word. It does not hold for deterministic FSTs, so $F\Lambda^{*}\xcancel{\leq}_{\mathrm{drat}}F$ . So to obtain the corresponding lemma for $\mathrm{DA}_{F}{\log}\text{-}\mathrm{TM}$ we need to modify the proof of Lemma 26.

Lemma 28.

${\mathscr{L}}(\mathrm{DA}_{F}{\log}\text{-}\mathrm{TM})\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{DRR}(F)$ .

Proof.

We repeat the steps of the proof of Lemma 26. Note that ${\cal A}$ is a DFA, since $M$ is a deterministic machine. To construct ${\cal A}^{\prime}$ we construct an auxiliary DFA ${\cal A}^{\prime\prime}$ by ${\cal A}$ as follows. ${\cal A}^{\prime\prime}$ has the states $(q,\bcancel{\Lambda})$ and $(q,\Lambda)$ for each state $q$ of ${\cal A}$ . The auxiliary bit of a state indicates whether ${\cal A}^{\prime\prime}$ met $\Lambda$ . So for each transition $q\xrightarrow{\Lambda}p$ of ${\cal A}$ there are two corresponding transitions $(q,b)\xrightarrow{\Lambda}(p,\Lambda)$ , $b\in\{\Lambda,\bcancel{\Lambda}\}$ . For states $(q,\Lambda)$ ${\cal A}^{\prime}$ has only transitions by $\Lambda$ . For the transitions $q\xrightarrow{a}p$ , $a\neq\Lambda$ , ${\cal A}^{\prime\prime}$ has transitions $(q,\bcancel{\Lambda})\xrightarrow{a}(p,\bcancel{\Lambda})$ . A state $(q,b)$ is an accepting if $q$ is an accepting state of ${\cal A}$ .

Now we construct ${\cal A}^{\prime}$ . It is obtained from ${\cal A}$ by removing all $\Lambda$ -transitions. Each ${\cal A}$ ’s accepting state is an accepting for ${\cal A}^{\prime}$ and ${\cal A}^{\prime}$ also has accepting states determined as follows. If $(q,\bcancel{\Lambda})$ has $\Lambda$ -path to an accepting state $(q_{f},\Lambda)$ in ${\cal A}^{\prime\prime}$ , then $q$ is an accepting state in ${\cal A}^{\prime}$ . It is easy to see that $y\in L({\cal A}^{\prime})\iff\exists k\geq 0\;y\Lambda^{k}\in L({\cal A})$ and ${\cal A}^{\prime\prime}$ is log-space computable from ${\cal A}$ and ${\cal A}^{\prime}$ is log-space computable from ${\cal A}$ and ${\cal A}^{\prime\prime}$ . ∎

Lemma 29.

$\mathrm{NRR}(F)\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}{\mathscr{L}}(\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM})$ and $\mathrm{DRR}(F)\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}{\mathscr{L}}(\mathrm{DA}_{F}{\log}\text{-}\mathrm{TM})$ . Moreover, there exist an $\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM}$ $M_{\mathrm{NRR}}$ that recognizes the problem $\mathrm{NRR}(F)$ and $M_{\mathrm{DRR}}$ that recognizes $\mathrm{DRR}(F)$ as well.

Proof.

The proof is straightforward. $M_{\mathrm{NRR}}$ gets on the input an NFA ${\cal A}$ and verifies whether ${\cal A}$ accepts the word $y\in F$ written on the advice tape. If $y\in L({\cal A})$ , $M_{\mathrm{NRR}}$ nondeterministically guesses the ${\cal A}$ ’s run on $y$ . So, by Definition 11, ${\cal A}\in L(M_{\mathrm{NRR}})$ iff $\exists y\in F:y\in L({\cal A})\iff{\cal A}\in\mathrm{NRR}(F)$ .

The construction for $M_{\mathrm{DRR}}$ is the same. ∎

Theorem 30.

		$\displaystyle{\mathscr{L}}(\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM})=\{L\mid L\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(F)\},$
		$\displaystyle{\mathscr{L}}(\mathrm{DA}_{F}{\log}\text{-}\mathrm{TM})=\{L\mid L\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{DRR}(F)\}.$

Proof.

By the definition of $\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}$ , $L\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(F)$ iff there exists a ${\log}\text{-}\mathrm{TM}$ transducer $T$ that maps the input $x$ of the problem $x\stackrel{{\scriptstyle?}}{{\in}}L$ to the input $T(x)$ of the problem $\mathrm{NRR}(F)$ . We construct an $\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM}$ $M$ recognizing $L$ via the composition of $T$ and $\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM}$ $M_{\mathrm{NRR}}$ from Lemma 29.

So $\{L\mid L\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(F)\}\subseteq{\mathscr{L}}(\mathrm{NA}_{F}{\log}\text{-}\mathrm{TM})$ ; the opposite inclusion follows from Lemma 26. We repeat the same arguments for the deterministic case and apply Lemma 28 for the opposite inclusion. ∎

5.2 $\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}$ models

In Section 3 we exploited the following idea. In the case of a nondeterministic model, performing queries one by one and proceeding the computation depending on the queries’ results computationally equivalent to guessing all the queries results and verifying whether all the results were correct in the end (by testing whether obtained protocol was correct). In fact, this idea works even in the case of a deterministic model in Theorem 19. Now we exploit it again for ${\log}\text{-}\mathrm{TM}$ -based models.

Lemma 31.

\mathrm{M}\text{-}\mathrm{NA}_{\mathsf{P}}{\log}\text{-}\mathrm{TM}\sim_{\log}\mathrm{M}\text{-}\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}\ \text{and}\ \mathrm{M}\text{-}\mathrm{D}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{M}\text{-}\mathrm{DA}_{\mathsf{P}}{\log}\text{-}\mathrm{TM}.

We provide only the proof idea since the proof follows our general technique that we have applied above a lot.

Proof idea.

Let $M_{A}$ be a $\mathrm{NA}_{\mathsf{P}}{\log}\text{-}\mathrm{TM}$ , $M_{B}$ be a $\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}$ , and $x$ be an input word. Since both kinds of ${\log}\text{-}\mathrm{TM}$ s are nondeterministic, $M_{A}$ can guess and verify $M_{B}$ ’s successful run on $x$ provided that $M_{B}$ ’s protocol is written on the advice tape; $M_{B}$ can guess $y\in\mathsf{P}$ and a successful run of $M_{A}$ on $(x,y)$ , and verify it: the transitions on configurations are simulated on log space and the fact $y\in\mathsf{P}$ is verified by performing subsequently the queries from the sequence $y$ .

The case of deterministic models is similar to Theorem 19. $M_{A}$ just simulates $M_{B}$ and tests whether the query words on the advice tape, queries an the results are the same as $M_{B}$ has during processing of the input. ∎

Combining all together, we obtain the main theorem of the section.

Theorem 32.

	$\displaystyle\mathrm{NRR}(\mathsf{P})\sim_{\log}{\mathscr{L}}(\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM})=\{L\mid L\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(\mathsf{P})\},$		(11)
	$\displaystyle{\mathscr{L}}(\mathrm{D}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM})\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{DRR}(\mathsf{P}),$		(12)
	$\displaystyle{\mathscr{L}}(\mathrm{D}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM})\subseteq\{L\mid L\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{DRR}(\mathsf{P})\}.$		(13)

Proof.

We begin with the proof of (11). By Lemma 31

\mathrm{M}\text{-}\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}\sim_{\log}\mathrm{M}\text{-}\mathrm{NA}_{\mathsf{P}}{\log}\text{-}\mathrm{TM}.

(14)

By Lemmata 26 and 29

{\mathscr{L}}(\mathrm{NA}_{\mathsf{P}}{\log}\text{-}\mathrm{TM})\sim_{{\log}}\mathrm{NRR}(\mathsf{P}).

(15)

Eqs. (14) and (15) imply

{\mathscr{L}}(\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM})\sim_{\log}\mathrm{NRR}(\mathsf{P}).

(16)

By Theorem 30

{\mathscr{L}}(\mathrm{NA}_{\mathsf{P}}{\log}\text{-}\mathrm{TM})=\{L\mid L\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(\mathsf{P})\}.

(17)

Eqs. (14) and (17) imply

{\mathscr{L}}(\mathrm{N}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM})=\{L\mid L\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(\mathsf{P})\}.

(18)

Eqs. (16) and (18) form (11).

Now we move to the proof of (12) and (13). By Lemma 28

{\mathscr{L}}(\mathrm{DA}_{\mathsf{P}}{\log}\text{-}\mathrm{TM})\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{DRR}(\mathsf{P}).

(19)

By Lemma 31

\mathrm{M}\text{-}\mathrm{D}\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{M}\text{-}\mathrm{DA}_{\mathsf{P}}{\log}\text{-}\mathrm{TM}.

(20)

Eqs. (19) and (20) imply (12). By Theorem 30

{\mathscr{L}}(\mathrm{DA}_{\mathsf{P}}{\log}\text{-}\mathrm{TM})=\{L\mid L\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{DRR}(\mathsf{P})\}.

(21)

Eqs. (20) and (21) imply (13). ∎

6 Applications

In this section we prove the applications (5-8) described in Section 1.1.

Theorem 33.

Assertions (5-8) hold.

Proof.

SA-PROT was defined in Example 8. It was proved in [14] that the problems $\overline{\mathrm{E\text{-}1NSA}}\sim_{\log}\mathrm{NRR}({\text{\sf{SA\text{-}PROT}}})$ are ${\mathbf{PSPACE}}$ -complete. So we obtain (6) by applying Theorem 32. We prove (5) in the same way by combining the facts ${\mathsf{D_{2}}\text{-}\mathsf{PROT}}\sim_{\mathrm{rat}}D_{2}$ (Example 7) and $\mathrm{NRR}(D_{2})$ is P-complete [12], and apply Lemma 25 and Theorem 32.

To prove (7-8) we use facts about the filters $\mathrm{Per}_{k}=\{(w\#)^{k}\mid w\in\Sigma_{k}\}$ , where $\Sigma_{k}$ is a $k$ -letter alphabet. The problem $\mathrm{NRR}(\mathrm{Per}_{1})$ is ${\mathbf{NP}}$ -complete and $\mathrm{NRR}(\mathrm{Per}_{k})$ , $k>1$ , is ${\mathbf{PSPACE}}$ -complete [1, 18]. We construct set-protocols based on these languages as follows. Let $\Gamma_{\textsf{write}}=\Sigma_{k}$ , $\Gamma_{\mathsf{query}}=\{\mathsf{in},\mathsf{test}\}$ , $\Gamma_{\mathsf{resp}}=\{+,-\}$ . The response to the $\mathsf{in}$ -query is positive only for the first query, $\mathsf{test}$ -queries are the same as in Example 8. We denote the language of correct protocols with $\Gamma_{\textsf{write}}=\Sigma_{k}$ as ${\mathsf{S_{1,k}PROT}}$ . It is easy to see that $\mathrm{Per}_{k}\mathop{\leq_{\mathrm{rat}}}{\mathsf{S_{1,k}PROT}}$ : an FST $T$ maps words of the form $w\mathsf{in}+w\mathsf{test}+\cdots w\mathsf{test}+$ to $w\#w\#\cdots w\#$ by replacing queries and responses by $\#$ ; the sequence of queries with responses $\mathsf{in}+,\mathsf{test}+,\ldots,\mathsf{test}+$ is verifiable via a finite state control (the inputs with invalid sequence are rejected by the FST), so $\mathrm{NRR}(\mathrm{Per}_{k})\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}({\mathsf{S_{1,k}PROT}})$ by Lemma 25.

Now we prove that ${\mathsf{S_{1,k}PROT}}\mathop{\leq_{\mathrm{rat}}}\mathrm{Per}_{k}$ . The FST $T$ takes on the input a word $(w\#)^{n}$ and acts as follows. While translating a block $w\#$ to the output, it has the following options: (i) change at least one letter, (ii) erase at least one letter and maybe change others, (iii) add at least one letter and maybe change others, (iv) do not change $w$ . Until $T$ has not write $\mathsf{in}$ , it replaces $\#$ by $\mathsf{test}-$ in the cases (i-iii), and either by $\mathsf{test}-$ or by $\mathsf{in}+$ in the case (iv). After $T$ wrote $\mathsf{in}+$ , it replaces $\#$ by $\mathsf{test}+$ in the case (iv) and either by $\mathsf{test}-$ or by $\mathsf{in}-$ in the cases (i-iii). It is easy to see that $T((w\#)^{n})$ consists of all correct protocols with either $w$ first $\mathsf{in}$ -query or without $\mathsf{in}$ -queries at all, and exactly $n$ queries. So $T(\mathrm{Per}_{k})={\mathsf{S_{1,k}PROT}}$ and assertions (7-8) follows from Lemma 25 and Theorem 32. ∎

7 On computational complexity
of correct protocol languages

Theorem 18 essentially says that the computational complexity of the non-emptiness problem for ADS-automata is the same as the computational complexity of the NRR problem for the corresponding correct protocols languages. It can be used to answer the question about the range of complexities of the non-emptiness problems for ADS-automata. It extends the known results about the complexity of RR problems [20]. It appears that these complexities are almost universal. It means that for any nonempty language $X$ there exists a language of correct protocols $\mathsf{P}$ such that $X$ is reducible to $\overline{\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}}$ . The reductions in the two directions differ. In one direction it is a log-space $m$ -reduction. In the other, we present the proof only for Turing reductions in polynomial time.

Theorem 34.

For any nonempty language $X\subseteq\{0,1\}^{*}$ there exists a language of correct protocols $\mathsf{P}$ such that

X\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\overline{\mathrm{E}\text{-}1\mathrm{N}\mathrm{B_{\mathsf{P}}}\mathrm{A}}\;\stackrel{{\scriptstyle\text{Th.~{}\ref{th:RReqNonEmp}}}}{{\sim_{\log}}}\;\mathrm{NRR}(\mathsf{P})\mathop{\leq^{\mathrm{P}}_{\mathrm{T}}}X.

In the proof of Theorem 34 we use the language of protocols defined as follows. Set $\Gamma_{\textsf{write}}=\{0,1\}$ , $\Gamma_{\mathsf{query}}=\{\#,r\}$ , $\Gamma_{\mathsf{resp}}=\{+,-,r\}$ . The relation $\mathsf{valid}$ is defined as follows: $\mathsf{valid}(\#)=\{+,-\}$ , $\mathsf{valid}(r)=\{r\}$ . The language of correct protocols $\mathsf{P}$ consists of protocols such that, for every query block $u_{i}\mathsf{q}_{i}\mathsf{r}_{i}$ , either $\mathsf{q}_{i}=\mathsf{r}_{i}=r$ and $u_{i}=\varepsilon$ , or $\mathsf{q}_{i}=\#$ , $\mathsf{r}_{i}=+$ and $u_{i}\in L$ , or $\mathsf{q}_{i}=\#$ , $\mathsf{r}_{i}=-$ and $u_{i}\notin L$ . Here $L\subseteq\{0,1\}^{*}$ is a language depending on $X$ in the statement of the theorem.

The exact choice of $L$ is complicated. So we start with the presentation of basic ideas behind the proof of Theorem 34. We encode binary words using a log-space computable injective map $\mathrm{sq}\colon\{0,1\}^{*}\to\{0,1\}^{*}$ such that $\mathrm{sq}(X)\subseteq L$ and $\mathrm{sq}(\bar{X})\subseteq\bar{L}$ . It suffices for the first reduction in the theorem, $X\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(\mathsf{P})$ , since the protocol $\mathrm{sq}(x)\#+$ is correct iff $x\in X$ .

For the second reduction, i.e., $\mathrm{NRR}(\mathsf{P})\mathop{\leq^{\mathrm{P}}_{\mathrm{T}}}X$ , we need much more requirements. Let ${\cal A}$ be an input automaton for $\mathrm{NRR}(\mathsf{P})$ and $S$ be its state set. We are going to decide $L({\cal A})\cap\mathsf{P}\neq\varnothing$ in polynomial time using oracle calls of the oracle $X$ . For this purpose we reduce the question $L({\cal A})\cap\mathsf{P}\neq\varnothing$ to the question $R\neq\varnothing$ for some regular language $R\in\{y,n,\#,+,-,r\}^{*}$ . By definition, $w\in R$ if there exists an accepting run of ${\cal A}$ that processes a correct protocol $p$ such that $p$ is obtained from $w$ by substitutions of letters $y$ and $n$ with words of $L$ and $\bar{L}$ respectively (different words may be used for different occurrences of the letters). To check the correctness of the run processing the protocol, we need to compute, for all pairs $s^{\prime},s^{\prime\prime}\in S$ , all possible transitions from $s^{\prime}$ to $s^{\prime\prime}$ by processing words from $L$ only as well as all possible transitions from $s^{\prime}$ to $s^{\prime\prime}$ by processing words from $\bar{L}$ only.

Thus, the main part of the reduction consists of solving NRR problems $L({\cal A}_{s^{\prime}s^{\prime\prime}})\cap L\neq\varnothing$ and $L({\cal A}_{s^{\prime}s^{\prime\prime}})\cap\bar{L}\neq\varnothing$ for all pairs $s^{\prime},s^{\prime\prime}\in S$ . Here ${\cal A}_{s^{\prime}s^{\prime\prime}}$ are auxiliary automata. The states and the transitions of ${\cal A}_{s^{\prime}s^{\prime\prime}}$ coincide with the states and the transitions of ${\cal A}$ . The initial state of ${\cal A}_{s^{\prime}s^{\prime\prime}}$ is $s^{\prime}$ and the only accepting state is $s^{\prime\prime}$ .

Note that $L({\cal A}_{s^{\prime}s^{\prime\prime}})$ may be infinite and it causes the first difficulty: one need to consider arbitrary long words in the protocol language. To avoid this difficulty we require that any infinite regular language intersects both $L$ and $\bar{L}$ . Therefore $L({\cal A}_{s^{\prime}s^{\prime\prime}})\cap L\neq\varnothing$ and $L({\cal A}_{s^{\prime}s^{\prime\prime}})\cap\bar{L}\neq\varnothing$ if $L({\cal A}_{s^{\prime}s^{\prime\prime}})$ is infinite.

If $L({\cal A}_{s^{\prime}s^{\prime\prime}})$ is finite, it means that the transition graph is DAG (after removing states that are not reachable and coreachable in ${\cal A}_{s^{\prime}s^{\prime\prime}}$ ). The second difficulty: it might be exponentially many words in $L({\cal A}_{s^{\prime}s^{\prime\prime}})$ . Again, to overcome it, we pose specific requirements on $L$ to guarantee that that verifying $L({\cal A}_{s^{\prime}s^{\prime\prime}})\cap L\neq\varnothing$ and $L({\cal A}_{s^{\prime}s^{\prime\prime}})\cap\bar{L}\neq\varnothing$ requires polynomially many oracle calls of the oracle $X$ .

Now we provide formal arguments for the above plan of proof. We encode binary words by the injective map

\mathrm{sq}\colon x\mapsto\beta(x)11\beta(x)11,

(22)

where $\beta\colon\{0,1\}^{*}\to\{0,1\}^{*}$ is the morphism defined on the symbols as $\beta(0)=01$ , $\beta(1)=10$ .

For an NFA ${\cal A}$ with the state set $S$ we define a relation

s^{\prime}\xhookrightarrow{u}s^{\prime\prime}

that holds if ${\cal A}$ can reach $s^{\prime\prime}$ on processing $u$ starting from the state $s^{\prime}$ .

Now we list the requirements on the language $L$ .

1.

As it mentioned before, $\mathrm{sq}(X)\subseteq L$ and $\mathrm{sq}(\bar{X})\subseteq\bar{L}$ .
2.

There exists a language $W\subseteq\{0,1\}^{*}$ such that both $W\cap L$ and $W\cap\bar{L}$ are recognized in polynomial time, and, for any NFA ${\cal A}$ over the alphabet $\{0,1\}$ and any pair of its states $s_{1}$ , $s_{2}$ , either $L({\cal A}_{s_{1}s_{2}})$ is finite, or there exist $w_{1}\in L\cap W$ , $w_{2}\in\bar{L}\cap W$ such that $w_{1}\in L({\cal A}_{s_{1}s_{2}})$ and $w_{2}\in L({\cal A}_{s_{1}s_{2}})$ .
3.

The language $W$ is sparse: $|W\cap\{0,1\}^{\leq n}|=\mathop{\mathrm{poly}}\nolimits(n)$ . Moreover, the lists of words in $L\cap W\cap\{0,1\}^{\leq n}$ and, respectively, in $\bar{L}\cap W\cap\{0,1\}^{\leq n}$ can be generated in polynomial time.
4.

If $|u|=|v|$ , $u\neq v$ , and $uv\notin W$ then $uv\in L$ iff $u\prec v$ , where $\prec$ is the lexicographical order.
5.

If $|w|$ is odd and $w\notin W$ then $w\in L$ . If $w=xx$ and $w\notin\mathrm{sq}(\{0,1\}^{*})\cup W$ then $w\in L$ .

The sets of $L$ -transitions and $\bar{L}$ -transitions are defined as follows:

\delta^{L}_{{\cal A}}(s)=\big{\{}s^{\prime}\in S:\exists u\ s\xhookrightarrow{u}s^{\prime},\ u\in L\big{\}},\quad\delta^{\bar{L}}_{{\cal A}}(s)=\big{\{}s^{\prime}\in S:\exists u\ s\xhookrightarrow{u}s^{\prime},\ u\in\bar{L}\big{\}}.

The main part of the proof of Theorem 34 is the following lemma.

Lemma 35.

Let $L$ be a language satisfying Requirements 1–5. Then there exists a polynomial time algorithm with the oracle $X$ that outputs the sets $\delta^{L}_{{\cal A}}(s)$ , $\delta^{\bar{L}}_{{\cal A}}(s)$ , where ${\cal A}$ is an input of $\mathrm{NRR}(\mathsf{P})$ and $s$ is its state.

Before presenting the algorithm from the lemma, we analyze the most difficult case separately.

Proposition 36.

Let $L$ be a language satisfying Requirements 1–5 and ${\cal A}$ be an NFA with the initial state $s_{0}$ and the unique accepting state $s_{f}$ such that $L({\cal A})$ is finite, $L({\cal A})\cap W=\varnothing$ , and each word in $L({\cal A})$ has an even length. Then conditions $s_{f}\in\delta^{L}_{{\cal A}}(s_{0})$ and $s_{f}\in\delta^{\bar{L}}_{{\cal A}}(s_{0})$ can be verified by a polynomial time algorithm with the oracle $X$ .

Proof.

By solving the reachability problem, one can detect the set of reachable and coreachable states of ${\cal A}$ . All other states can be deleted without affecting $L({\cal A})$ . From now on, we assume that all the states $s\in S$ are reachable and coreachable.

Since $L({\cal A})$ is finite, the transition graph of ${\cal A}$ is a DAG as well as all its subgraphs. For each pair of states $s_{1},s_{2}\in Q$ , let $\ell(s_{1},s_{2})$ be the set

\big{\{}k:\exists u\ s_{1}\xhookrightarrow{u}s_{2}\ \text{and}\ |u|=k\big{\}}.

Using topological sorting, one can construct all the sets $\ell(s_{1},s_{2})$ in polynomial time by the backward induction based on the relation

\ell(s_{1},s_{2})=\bigcup_{s\in N(s_{1})}\big{(}1+\ell(s,s_{2})\big{)},

where $N(s_{1})$ is the set of states that are reachable from $s$ in one move and $1+X=\{y:y=1+x,\;x\in X\}$ .

For a positive integer $\ell$ and a state $s$ of ${\cal A}$ , we define

\mathrm{Left}(s,\ell)=\big{\{}u:s_{0}\xhookrightarrow{u}s,\ |u|=\ell\big{\}},\quad\mathrm{Right}(s,\ell)=\big{\{}u:s\xhookrightarrow{u}s_{f},\ |u|=\ell\big{\}}.

We order the sets $\mathrm{Left}(s,\ell)$ and $\mathrm{Right}(s,\ell)$ in the lexicographical order. Let $\min_{0}(s,\ell)$ be the minimal word in $\mathrm{Left}(s,\ell)$ , and $\max_{0}(s,\ell)$ be the maximal word in $\mathrm{Left}(s,\ell)$ , and $\min_{1}(s,\ell)$ be the minimal word in $\mathrm{Right}(s,\ell)$ , and $\max_{1}(s,\ell)$ be the maximal word in $\mathrm{Right}(s,\ell)$ .

There exists an inductive procedure that computes $\min_{0}(s,\ell)$ , $\max_{0}(s,\ell)$ , $\min_{1}(s,\ell)$ , and $\max_{1}(s,\ell)$ in polynomial time. The procedure also verifies the conditions $\mathrm{Left}(s,\ell)\neq\varnothing$ , $\mathrm{Right}(s,\ell)\neq\varnothing$ . We describe computation of $\min_{0}(s,\ell)$ , the other words are computed similarly.

Suppose that $u$ is the prefix of $\min_{0}(s,\ell)$ of the length $0\leq k<\ell$ (if $k=\ell$ , then the procedure returns $u$ and stops). Let $S_{k}=\{s^{\prime}:s_{0}\xhookrightarrow{u}s^{\prime}\}$ . This set can be computed in polynomial time. If there exists $s^{\prime}\in S_{k}$ and $s^{\prime\prime}\in S$ such that $s^{\prime\prime}\in\delta_{{\cal A}}(s^{\prime},0)$ and $\ell-k-1\in\ell(s^{\prime\prime},s)$ , then $u0$ is a prefix of $\min_{0}(s,\ell)$ of the length $k+1$ . Otherwise, if there exists $s^{\prime}\in S_{k}$ and $s^{\prime\prime}\in S$ such that $s^{\prime\prime}\in\delta_{{\cal A}}(s^{\prime},1)$ and $\ell-k-1\in\ell(s^{\prime\prime},s)$ , then $u1$ is a prefix of $\min_{0}(s,\ell)$ . If both conditions are not satisfied, then $\mathrm{Left}(s)=\varnothing$ .

According to Requirement 4 on $L$ , if there exist a state $s$ and an integer $\ell$ such that $\min_{0}(s,\ell)\prec\max_{1}(s,\ell)$ , then $s_{f}\in\delta^{L}_{{\cal A}}(s_{0})$ . Otherwise, $\max_{1}(s,\ell)\preceq\min_{0}(s,\ell)$ for all $s$ , $\ell$ . Since $L({\cal A})\cap W=\varnothing$ , in this case $s_{f}\in\delta^{L}_{{\cal A}}(s_{0})$ if and only if there exist a state $s$ and an integer $\ell$ such that $\min_{0}(s,\ell)=\max_{1}(s,\ell)$ and either $\min_{0}(s,\ell)=\beta(x)11$ and $x\in X$ or $\min_{0}(s,\ell)\max_{1}(s,\ell)\notin\mathrm{sq}(\{0,1\}^{*})$ due to Requirements 1, 5. The condition $x\in X$ can be verified by an oracle call, the rest of conditions can be verified in polynomial time.

A similar check can be done for the condition $s_{f}\in\delta^{\bar{L}}_{{\cal A}}(s_{0})$ . It is equivalent to the following: there exist a state $s$ and an integer $\ell$ such that either $\min_{1}(s,\ell)\prec\max_{0}(s,\ell)$ , or $\min_{1}(s,\ell)=\max_{0}(s,\ell)=\beta(x)11$ and $x\notin X$ . ∎

Proof of Lemma 35.

The algorithm maintains the sets $S^{+}\subseteq S$ , $S^{-}\subseteq S$ . Initially, $S^{+}=S^{-}=\varnothing$ . We will prove that at the end $S^{+}=\delta^{L}_{{\cal A}}(s)$ , $S^{-}=\delta^{\bar{L}}_{{\cal A}}(s)$ . The algorithm analyzes states $s^{\prime}\in S$ one by one and adds $s^{\prime}$ to the sets $S^{+}$ , $S^{-}$ according to the following rules.

In the first step, the algorithm decides whether $L({\cal A}_{ss^{\prime}})$ is infinite. It can be done in polynomial time. If the answer is ‘yes’, then the algorithm adds $s^{\prime}$ to both sets $S^{+}$ , $S^{-}$ and continues with the next state. The correctness of this step is guaranteed by Requirement 2.

If the answer at the first step is ‘no’, the lengths of words in $L({\cal A}_{ss^{\prime}})$ do not exceed $|S|$ (otherwise, there exists a run of ${\cal A}$ from $s$ to $s^{\prime}$ containing a cycle, which implies that $L({\cal A}_{ss^{\prime}})$ is infinite). In the second step, the algorithm checks whether $L({\cal A}_{ss^{\prime}})\cap L\cap W\neq\varnothing$ and, respectively, whether $L({\cal A}_{ss^{\prime}})\cap\bar{L}\cap W\neq\varnothing$ . It can be done in polynomial time due to Requirement 3. If the first condition holds, then the algorithm adds $s^{\prime}$ to $S^{+}$ . If the second condition holds, then the algorithm adds $s^{\prime}$ to $S^{-}$ .

In the third step, the algorithm constructs an NFA ${\cal A}^{\prime}$ recognizing $L({\cal A}_{ss^{\prime}})\setminus W$ . Let $P$ be the set of prefixes of all words in $W\cap\{0,1\}^{\leq|S|}$ . Due to Requirement 3, $|P|=\mathop{\mathrm{poly}}\nolimits(|S|)$ and $P$ can be constructed in polynomial time. The states of ${\cal A}^{\prime}$ are the pairs $(\tilde{s},p)$ , $\tilde{s}\in S$ , $p\in P\cup\{\bot\}$ . The set of transitions $\delta_{{\cal A}^{\prime}}((s,p),a)$ consists of pairs $(\tilde{s},p^{\prime})$ such that $\tilde{s}\in\delta_{{\cal A}}(s,a)$ and $p^{\prime}=pa\in P$ , and pairs $(\tilde{s},\bot)$ such that $\tilde{s}\in\delta_{{\cal A}}(s,a)$ and $p^{\prime}=pa\notin P$ . The set of transitions $\delta_{{\cal A}^{\prime}}((s,\bot),a)$ consists of pairs $(\tilde{s},\bot)$ such that $\tilde{s}\in\delta_{{\cal A}}(s,a)$ . The initial state is $(s,\varepsilon)$ . Accepting states are pairs $(s^{\prime},\bot)$ and $(s^{\prime},p)$ , where $p\notin W$ . This definition implies that ${\cal A}^{\prime}$ can be constructed in polynomial time. To prove the correctness of the construction, note that processing a word $w\in W\cap\{0,1\}^{\leq|S|}$ from $(s,\varepsilon)$ finishes at the state $(s^{\prime},w)$ which is not accepting. For a word $w\in L({\cal A}_{ss^{\prime}})\setminus W$ there exists an accepting run of ${\cal A}_{ss^{\prime}}$ . The corresponding run of ${\cal A}^{\prime}$ finishes at a state of the form $(s^{\prime},w)$ or $(s^{\prime},\bot)$ . Thus, $w$ is accepted by $A^{\prime}$ .

In the fourth step, the algorithm checks whether $L({\cal A}_{ss^{\prime}})\setminus W$ contains a word of odd length. It can be done in polynomial time since words of odd length form a regular language and the intersection of this language with $L({\cal A}_{ss^{\prime}})\setminus W$ is recognized by an NFA with $2|S^{\prime}|$ states, where $S^{\prime}$ is the state set of ${\cal A}^{\prime}$ . If the answer is ‘yes’, then the algorithm adds $q^{\prime}$ to $S^{+}$ . The correctness of this step is guaranteed by Requirement 5.

In the fifth step, the algorithm constructs an NFA ${\cal A}^{\prime\prime}$ that accepts exactly the words of even length from $L({\cal A}_{ss^{\prime}})\setminus W$ , apply to it the algorithm of Proposition 36, updates $S^{+}$ , $S^{-}$ if necessary, and continues with the next state.

It is clear from the above remarks that at the end $S^{+}\subseteq\delta^{L}_{{\cal A}}(s)$ , $S^{-}\subseteq\delta^{\bar{L}}_{{\cal A}}(s)$ .

Suppose that $s^{\prime}\in\delta^{L}_{{\cal A}}(s)$ . If $L({\cal A}_{ss^{\prime}})$ is infinite then $s^{\prime}$ is added to $S^{+}$ at the first step. If $L({\cal A}_{ss^{\prime}})\cap W\cap L\cap\{0,1\}^{\leq|Q|}\neq\varnothing$ , then $s^{\prime}$ is added at the second step. Otherwise, $(L({\cal A}_{ss^{\prime}})\cap L)\setminus W$ should be non-empty. If there are words of odd length in $L({\cal A}_{ss^{\prime}})\setminus W$ , then $s^{\prime}$ is added at the fourth step. And, finally, if $L({\cal A}_{ss^{\prime}})\setminus W$ consists of words of even length only, $s^{\prime}$ is added at the fifth step due to Proposition 36. Therefore, $S^{+}=\delta^{L}_{{\cal A}}(s)$ at the end of the algorithm.

Suppose that $s^{\prime}\in\delta^{\bar{L}}_{{\cal A}}(s)$ . If $L({\cal A}_{ss^{\prime}})$ is infinite then $s^{\prime}$ is added to $S^{-}$ at the first step. If $L({\cal A}_{ss^{\prime}})\cap W\cap\bar{L}\cap\{0,1\}^{\leq|S|}\neq\varnothing$ , then $s^{\prime}$ is added at the second step. Otherwise, $(L({\cal A}_{ss^{\prime}})\cap\bar{L})\setminus W\neq\varnothing$ and $s^{\prime}$ is added at the fifth step due to Proposition 36. Therefore, $S^{-}=\delta^{\bar{L}}_{{\cal A}}(s)$ at the end of the algorithm. ∎

Now we prove that Requirements 1–5 on $L$ are compatible.

Lemma 37.

There exists $L$ satisfying Requirements 1–5.

Proof.

We define $W$ at first. For each triple $a,b,c$ of non-empty binary words there are two words in $W$ in the form $ab^{2r(a,b,c)}c$ and $ab^{2q(a,b,c)+1}c$ and for each $w\in W$ there exists a unique triple $a,b,c$ such that either $w=ab^{2r(a,b,c)}c$ or $w=ab^{2q(a,b,c)+1}c$ . The definition of $W$ is inductive. Order all triples $x,y,z$ of non-empty binary words with respect to the length of $xyz$ and order the triples with the same length of $xyz$ with respect to the lexicographical order on the triples of binary words (binary words are also ordered lexicographically).

Assume that for all $(x,y,z)$ less than $(a,b,c)$ we have defined $s(x,y,z)$ and $t(x,y,z)$ properly. Thus the set $W^{\prime}\subseteq W$ has been already defined. The total number of $(x,y,z)$ less than $(a,b,c)$ does not exceed $\binom{|abc|-1}{2}\cdot(2^{|abc|}-1)$ . Thus, there are at most $2\binom{|abc|-1}{2}\cdot(2^{|abc|}-1)$ words from $W^{\prime}$ having lengths in the range $[2^{3|abc|+3},2^{3|abc|+4}-1]$ . So, there exist at least

\frac{2^{3|abc|+3}}{2\binom{|abc|-1}{2}\cdot(2^{|abc|}-1)}-1>2|abc|>2|b|

consecutive integers $i$ in the range such that no word in $W^{\prime}$ has the length $i$ . At least $|b|$ of them are even and at least $|b|$ of them are odd. It guarantees that the sets

		$\displaystyle E=\{j:ab^{2j}c\notin W^{\prime},\ 2^{3\|abc\|+3}\leq\|ab^{2j}c\|<2^{3\|abc\|+4}\}\ \text{and}$
		$\displaystyle O=\{j:ab^{2j+1}c\notin W^{\prime},\ 2^{3\|abc\|+3}\leq\|ab^{2j+1}c\|<2^{3\|abc\|+4}\}$

are non-empty. Set $r(a,b,c)$ be the minimal $j$ in $E$ and $q(a,b,c)$ be the minimal $j$ in $O$ .

To define $L$ , we require that the words from $W$ in the form $ab^{2q(a,b,c)+1}c$ are in $L$ , while the words from $W$ in the form $ab^{2r(a,b,c)}c$ are in $\bar{L}$ . Note that it implies Requirement 2, since any infinite regular language contains all words in the form $ab^{k}c$ , $k>0$ , for some $a$ , $b$ , $c$ .

By construction, for each $w\in W$ the length of defining triple $a,b,c$ is logarithmic in the length of $w$ . Thus $|W\cap\{0,1\}^{\leq n}|=\mathop{\mathrm{poly}}\nolimits(n)$ . To construct the list of words in $L\cap W\cap\{0,1\}^{\leq n}$ and the list of words in $\bar{L}\cap W\cap\{0,1\}^{\leq n}$ one need to perform only polynomial number of steps of the defining procedure and each step can be performed in polynomial time. Therefore, Requirement 3 is satisfied.

The rest of $L$ is defined to satisfy Requirements 1, 4, and 5. Note that $\mathrm{sq}(\{0,1\}^{*})\cap W=\varnothing$ , since, for each $x\in\{0,1\}^{*}$ , $\mathrm{sq}(x)$ does not contain proper periodic subwords of length greater $|\mathrm{sq}(x)|/2$ but each word in $W$ do contain such words. It means that the construction of $W$ does not conflict with Requirement 1. ∎

Now Theorem 34 follows from Lemma 35 and Lemma 37.

Proof of Theorem 34.

Choose $L$ as in the proof of Lemma 37. The reduction $X\mathop{\leq^{\mathrm{}}_{\mathrm{log}}}\mathrm{NRR}(\mathsf{P})$ is given by a map $x\mapsto\mathrm{sq}(x)\#+$ . It is clear that the map is computed in logarithmic space. The correctness of reduction follows from Requirement 1.

Now we describe the second reduction, $\mathrm{NRR}(\mathsf{P})\mathop{\leq^{\mathrm{P}}_{\mathrm{T}}}X$ . Let ${\cal A}$ be an input NFA for $\mathrm{NRR}(\mathsf{P})$ . The reducing algorithm computes all sets $\delta^{L}_{{\cal A}}(s)$ , $\delta^{\bar{L}}_{{\cal A}}(s)$ using Lemma 35.

Let ${\cal B}$ be an NFA with the same state set as ${\cal A}$ . The alphabet of $B$ is $\{y,n,\#,+,-,r\}$ . Transitions $\delta_{{\cal B}}(s,a)$ coincide with transitions $\delta_{{\cal A}}(s,a)$ for $a\in\{\#,+,-,r\}$ . For the rest of transitions, $\delta_{{\cal B}}(s,y)=\delta^{L}_{{\cal A}}(s)$ and $\delta_{{\cal B}}(s,n)=\delta^{\bar{L}}_{{\cal A}}(s)$ . The initial state and the accepting states of ${\cal B}$ and of ${\cal A}$ coincide.

Let $R=L({\cal B})\cap\big{(}y\#+\mid n\#-\mid rr\big{)}^{*}$ . Then $L({\cal A})\cap\mathsf{P}\neq\varnothing$ iff $R\neq\varnothing$ . The latter condition is verified in polynomial time since $R$ is regular. ∎

Acknowledgments

This work is supported by the Russian Science Foundation grant 20–11–20203.

References

[1] T. Anderson, J. Loftus, N. Rampersad, N. Santean, and J. Shallit. Special Issue: LATA 2008 Detecting palindromes, patterns and borders in regular languages. Information and Computation, 207(11):1096–1118, 2009.
[2] J. Berstel. Transductions and context-free languages. Ed. Teubner, 1979.
[3] A. Bouajjani, J. Esparza, and O. Maler. Reachability analysis of pushdown automata: Application to model-checking. In International Conference on Concurrency Theory, pages 135–150. Springer, 1997.
[4] D. Chistikov, R. Majumdar, and P. Schepper. Subcubic certificates for cfl reachability. Proc. ACM Program. Lang., 6(POPL), jan 2022.
[5] M. Daley, M. Eramian, and I. Mcquillan. The bag automaton: A model of nondeterministic storage. J. Autom. Lang. Comb., 13(3):185–206, June 2008.
[6] D. Dolev, S. Even, and R. Karp. On the security of ping-pong protocols. Information and Control, 55(1):57–68, 1982.
[7] J. E. Hopcroft and J. D. Ullman. An approach to a unified theory of automata. In SWAT 1967, pages 140–147, 1967.
[8] M. Kutrib, A. Malcher, and M. Wendlandt. Set automata. International Journal of Foundations of Computer Science, 27(02):187–214, 2016.
[9] K.-J. Lange and K. Reinhardt. Set automata. In Combinatorics, Complexity and Logic; Proceedings of the DMTCS’96, pages 321–329. Springer, 1996.
[10] D. Melski and T. Reps. Interconvertibility of a class of set constraints and context-free-language reachability. Theoretical Computer Science, 248(1-2):29–98, 2000.
[11] T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’95, page 49–61, New York, NY, USA, 1995. Association for Computing Machinery.
[12] A. Rubtsov and M. Vyalyi. Regular realizability problems and context-free languages. In DCFS 2015, volume 9118 of LNCS, pages 256–267. Springer, 2015.
[13] A. Rubtsov and M. Vyalyi. On computational complexity of set automata. In DLT 2017, pages 332–344, Cham, 2017. Springer International Publishing.
[14] A. Rubtsov and M. Vyalyi. On emptiness and membership problems for set automata. In CSR 2018, pages 295–307, Cham, 2018. Springer International Publishing.
[15] A. Rubtsov and M. Vyalyi. On computational complexity of set automata. Information and Computation, to appear.
[16] M. Sipser. Introduction to the theory of computation. Cengage Learning, 2013.
[17] M. Vyalyi. On models of a nondeterministic computation. In CSR 2009, pages 334–345, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
[18] M. Vyalyi. On the models of nondeterminizm for two-way automata (in Russian). Proceedings of VIII international conference <<Discrete models in the theory of control systems>>., pages 54–60, 2009.
[19] M. N. Vyalyi. On regular realizability problems. Probl. Inf. Transm., 47(4):342–352, 2011.
[20] M. N. Vyalyi. On expressive power of regular realizability problems. Probl. Inf. Transm., 49(3):276–291, 2013.
[21] P. Wolf. On the decidability of finding a positive ilp-instance in a regular set of ilp-instances. In DCFS 2019, volume 11612 of LNCS, pages 272–284. Springer, 2019.
[22] P. Wolf and H. Fernau. Regular intersection emptiness of graph problems: Finding a needle in a haystack of graphs with the help of automata. CoRR, abs/2003.05826, 2020.
[23] M. Yannakakis. Graph-theoretic methods in database theory. In Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS ’90, page 230–242, New York, NY, USA, 1990. Association for Computing Machinery.

Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems

Abstract

1 Introduction

1.1 Our Contribution

Definition 1.

2 Definitions

2.1 Notation on binary relations

2.2 Rational Transductions

Lemma 2.

Lemma 3.

2.3 Computational Models

Definition 4.

Definition 5.

Definition 6.

Example 7.

Example 8.

Definition 9.

Definition 10.

Definition 11.

3 Principal Rational Cones and the NRR-Problem

Lemma 12.

Proof.

Lemma 13.

Proof.

Lemma 14.

Proof.

Lemma 15.

Proof.

Definition 16.

Theorem 17.

Proof.

Theorem 18.

Proof.

Theorem 19.

Proof.

4 Connection with Balloon Automata

Definition 20.

Theorem 21.

Proof.

Lemma 22.

Proof.

Lemma 23.

Proof idea.

Remark 24.

5 RR Problems and 𝐥𝐨𝐠⁡-​𝐓𝐌{\log}\text{-}\mathrm{TM} Models

5.1 𝐀𝑭​𝐥𝐨𝐠⁡-​𝐓𝐌\mathrm{A}_{F}{\log}\text{-}\mathrm{TM} models

Lemma 25 (​​[12]).

Lemma 26.

Proof.

Remark 27.

Lemma 28.

Proof.

Lemma 29.

Proof.

Theorem 30.

Proof.

5.2 𝐁𝗣​𝐥𝐨𝐠⁡-​𝐓𝐌\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM} models

Lemma 31.

Proof idea.

Theorem 32.

Proof.

6 Applications

Theorem 33.

Proof.

7 On computational complexity of correct protocol languages

Theorem 34.

Lemma 35.

Proposition 36.

Proof.

Proof of Lemma 35.

Lemma 37.

Proof.

Proof of Theorem 34.

Acknowledgments

References

3 Principal Rational Cones and
the NRR-Problem

5 RR Problems and ${\log}\text{-}\mathrm{TM}$ Models

5.1 $\mathrm{A}_{F}{\log}\text{-}\mathrm{TM}$ models

Lemma 25 ([12]).

5.2 $\mathrm{B_{\mathsf{P}}}{\log}\text{-}\mathrm{TM}$ models

7 On computational complexity
of correct protocol languages