Polynomial Complementation of Nondeterministic Two-Way Finite Automata by $1$-Limited Automata

The study of the resources used by computational models is a central topic in automata theory. One classical problem in this area is to determine the cost of applying operations between languages (e.g., union, intersection, concatenation, Kleene star, etc.). Here, the cost is defined as the increase in size of the resulting (or target) devices after applying the operation to the languages recognized by the original (or source) machines.

In this paper, we focus on the cost of the complementation of regular languages. This operation is usually cheap (i.e., costs at most polynomial) when dealing with deterministic devices, while it is often expensive (i.e., at least exponential) for nondeterministic devices; see Table 1. The reason for this separation has been understood for a long time and originates from the nature of nondeterminism, as illustrated by the case of classical (one-way) nondeterministic finite automata ($1$nfas). Indeed, the semantics of such a device is that a word is accepted as long as there exists a computational path leading to an accepting state. Therefore, in order to acknowledge that a word does not belong to the recognized language, one should somehow check that every computational path leads to a non-accepting state,¹¹1For ease of discussion, we admit here that the automata are complete, that is, no computational path gets stuck in the middle of the input. a semantic which is hardly captured by nondeterminism. This issue does not exist for one-way deterministic finite automata ($1$dfas), because they admit a unique computational path on each input, and thus existential and universal quantifications on computational paths coincide. Indeed, it is folklore that exchanging accepting and non-accepting states of a $1$dfa, while keeping the rest of the structure (initial state and transitions) unchanged, yields a $1$dfa recognizing the complement of the language.1 On the other hand, it is well known that transforming a $1$nfa into another one recognizing the complement of the language may cost as much as determinizing it and then complementing it (as explained above) in the worst case [18, 1, 10].

Yet, the corresponding question remains unsolved for other regular language recognizers, and in particular when dealing with two-way finite automata, an extension of finite automata allowing the machine to move its head both back and forth, and which still characterizes regular languages. Indeed, although complementing two-way deterministic automata ($2$dfas) has been non-trivially²²2The main challenge when complementing $2$dfas is to detect infinite computations induced by loops. shown to cost linear only [4], the cost for complementing their nondeterministic counterparts ($2$nfas) is still unknown in the general case. Worse still, the best-known upper bound is exponential and is obtained by transforming the source $2$nfa into an equivalent $1$dfa. That is, neither two-wayness nor nondeterminism are exploited for complementing arbitrary $2$nfas. Indeed, also the cost for determinizing $2$nfas is a longstanding open question known as “the Sakoda and Sipser problem” [18] (see e.g. [14] for a survey). As shown in [4], the two problems are related via the linear-cost complementation of $2$dfas. On the one hand, finding an exponential (or super-polynomial) lower bound for complementing $2$nfas would imply a similar lower bound for determinizing them. On the other hand, finding a polynomial (or sub-exponential) upper bound for determinizing $2$nfas would imply a similar upper bound for complementing them. It is worth noting that a polynomial-cost complementation of $2$nfas has been obtained in some particular cases, e.g., in the unary and letter-bounded settings [4, 2], or when the $2$nfa makes a restricted use of nondeterminism, known as outer-nondeterminism [3].

In this paper, we study the cost of complementing two-way finite automata following a different approach: Instead of using the same model as source and target devices, we relax the target machines by equipping them with some extra features while keeping the expressive power unchanged. More precisely, we use as target device a machine called 1-limited automaton (1-la), which is an extension of $2$nfas with some rewriting capability. Technically, each time the machine visits a cell for the first time it is allowed to change its contents. This model is not more powerful than $2$nfas [22, Thm. 12.1], i.e., it recognizes regular languages only. However, there are cases where it can represent languages more succinctly than $2$nfas (for a recent survey on this model, see [15]). This approach has already been used to provide succinct representations of operations that have exponential cost when both source and target machines are $1$dfas (Kleene star, reversal and concatenation), but can be done at a polynomial cost when the target machine is a deterministic 1-la (d1-la) [17].

In the survey [15], the author identifies some problems regarding the descriptional complexity of 1-las. In particular, the question of the cost of the conversion of $2$nfas into equivalent d1-las [15, Problem 4], as well as those of the cost of determinizing 1-las [15, Problem 2] are raised. Just as complementing $2$nfas relates to the Sakoda and Sipser problem, complementing $2$nfas with 1-las relates to these problems; see Figure 1.

In this section, we recall some fundamental definitions and notations used throughout the paper. We assume that the reader is familiar with basic concepts from formal languages and automata theory (see, e.g., [8]).

For a set $S$, $\mathrm{\#}S$ denotes its cardinality and $2^S$ denotes its powerset. For $n\in \mathbb{N}$, $[n]$ denotes the set consisting of the first $n$ natural numbers (including $0$), namely $[n]=\{0,\mathrm{\dots },n-1\}$; in particular $[0]=\mathrm{\varnothing }$ and $[1]=\{0\}$. Given an alphabet $\mathrm{\Sigma }$, the set of strings over $\mathrm{\Sigma }$ is denoted by ${\mathrm{\Sigma }}^{\ast }$. It includes the empty string denoted by $\epsilon$. The length of a word $w\in {\mathrm{\Sigma }}^{\ast }$ is denoted by $|w|$, and the set of strings over $\mathrm{\Sigma }$ of length $i$ is denoted by ${\mathrm{\Sigma }}^i$. The number of occurrences of a symbol $\sigma \in \mathrm{\Sigma }$ in $w$ is denoted by ${|w|}_{\sigma }$. The positions of symbols within a string $w$ are indexed from $0$ to $|w|-1$. We use the notation $w[i]$ to indicate the symbol at position $i\in [|w|]$ of $w$ (i.e., the $(i+1)$-th symbol of $w$, e.g., $w[0]$ is the first symbol of $w$) and $w[i,j]$ for the factor of $w$ from index $i$ to index $j$ included, . If $i>j$, we set $w[i,j]=\epsilon$ by convention. Hence, the length of $w[i,j]$ is $0$ if $i>j$ and $j-i+1$ otherwise.

We shall often assume $Q=[n]$ for $n=\mathrm{\#}Q$, so that $Q$ is ordered, with $-1\notin Q$ as a minimum.

In $2$nfas, the input is written on the tape surrounded by the two endmarkers, the left endmarker being at tape position zero. Hence, on input $w$, the right endmarker is at position $|w|+1$. In one move, $𝖠$ reads an input symbol, changes its state, and moves the head one position backward or forward depending on whether $\delta$ returns $-1$ (a left move) or $+1$ (a right move), respectively. Furthermore, the head cannot pass the endmarkers. The machine accepts the input if there exists a computational path which starts from the initial state $q_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}$ with the head on the cell at position $1$ (i.e., scanning the first letter of $w$ if $w\ne \epsilon$ and scanning $⊲$ otherwise) and eventually halts in the final state $q_{𝖿}$ with the head scanning the right endmarker. The language accepted by $𝖠$ is denoted by $ℒ(𝖠)$.

A $2$nfa is one-way ($1$nfa) if its head can never move left, i.e., if no transition returns $-1$. The transition function of a $1$nfa is seen as a function $\delta :Q\times \mathrm{\Sigma }\to 2^Q$ (that is, the endmarkers and the instruction for head direction are irrelevant).

The above models are all read-only machines. We now define $1$-limited automata (1-las, for short) that extend $2$nfas with a limited write ability. Just as $2$nfas, 1-las have a finite set of states, an initial and an accepting state, and work both ways on a tape that initially contains the input surrounded by the two endmarkers. However, they are allowed to replace the contents of each tape cell (except for those containing the endmarkers) when the head visits the cell for the first time – during subsequent visits to the cell, the contents cannot be changed any longer. Acceptance for 1-las is defined exactly as for $2$nfas, and the language accepted by a given 1-la $𝖠$ is denoted by $ℒ(𝖠)$. It is known that 1-las recognize regular languages only [22, Thm 12.1].

In this section, we present a construction that transforms an arbitrary $n$-state $1$nfa into an equivalent self-verifying $2$nfa$+\mathrm{𝖼𝗀}$ with polynomially many states and $2$ annotation symbols. As in [4, 3], our simulation is based on the inductive counting technique, which originates from the proof of the well-celebrated Immerman–Szelepcsényi theorem [9, 20].

Let $𝖠=⟨Q,\mathrm{\Sigma },\delta ,q_{\mathrm{𝗌𝗍𝖺𝗋𝗍}},q_{𝖿}⟩$ be an $n$-state $1$nfa. We assume $Q=[n]$ which is thus equipped with the natural ordering. For $w\in {\mathrm{\Sigma }}^{\ast }$, we define $X_w^{𝖠}$ to be the set of states the automaton $𝖠$ reaches after reading $w$, i.e., $X_w^{𝖠}=\delta (q_{\mathrm{𝗌𝗍𝖺𝗋𝗍}},w)\text{.}$ Working on $w$, a $2$nfa can iteratively simulate nondeterministic computation paths of $𝖠$ by bringing the head back to the left endmarker before starting a new simulation. It may thus find several states belonging to $X_w^{𝖠}$. Suppose that the number $m$ of states reached after reading $w$ is given, i.e., $m=\mathrm{\#}{X}_w^{𝖠}$. Then, by simulating $m$ times $𝖠$ on $w$, and controlling at each iteration but the first that the state reached at the end of the simulation is larger than the preceding one, a $2$nfa can enumerate all the $m$ states of $X_w^{𝖠}$. This process is described in Procedure 1, where nsimul_$A$ stands for the nondeterministic simulation of $𝖠$ from the initial configuration.⁴⁴4In enumeration algorithms, the outputs are not returned at the end of the execution, but yielded as soon as they are found. This allows an outer calling procedure to treat them one-by-one (see, e.g., Procedures 3 and 4). In Procedure 1, this yielding is indicated with the output keyword on Line 6.

Hence, according to whether one or none of them is the accepting state, the $2$nfa recognizes whether $w$ belongs to $ℒ(𝖠)$ or to its complement; see Procedure 3 in which the accepting state is passed as a parameter $q_t$. Remarkably, a $2$nfa ${𝖡}_m$ with $𝒪(n^{2}m)\subseteq 𝒪(n^3)$ states can implement this process. Indeed, such a $2$nfa only has to simultaneously store in its finite control the index $i\le m$ of the iteration, the previously found state (${𝚚}_{\mathrm{𝚙𝚛𝚎𝚟}}$), and the state in the current simulation (${𝚚}_{\mathrm{𝚗𝚎𝚡𝚝}}$). One strategy to detect whether an input $w$ belongs to the complement of $ℒ(𝖠)$ would therefore be to first compute $m=\mathrm{\#}{X}_w^{𝖠}$, and then run the $2$nfa ${𝖡}_m$. Yet, computing $\mathrm{\#}{X}_w^{𝖠}$ is not an easy task.

Suppose now that $\mathrm{\#}{X}_w^{𝖠}$ is unknown, but that there exists a nondeterministic procedure nsimul_$A$, which, starting from some position $|u|$, where $u$ is a prefix of the input $w$, eventually halts at the same position returning a state $q$ if and only if $q\in X_u^{𝖠}$. Then a $2$nfa equipped with nsimul_$A$ may inductively compute $\mathrm{\#}{X}_u^{𝖠}$ for each successive prefix $u$ of $w$ as follows. Initially, $\mathrm{\#}{X}_{\epsilon }^{𝖠}=1$ since $X_{\epsilon }^{𝖠}=\{q_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}\}$ by definition. Let $u\sigma$ be a prefix of $w$. In order to compute $\mathrm{\#}{X}_{u\sigma }^{𝖠}$ from $\mathrm{\#}{X}_u^{𝖠}$, the automaton tests for each state $p$ whether it belongs to $X_{u\sigma }^{𝖠}$, and counts those for which the answer is positive. This process is described in Procedure 4, in which $\sigma$ is read from the tape (indicated as read()). Testing whether a given state $p$ belongs to $X_{u\sigma }^{𝖠}$ is based on the following basic observation:

Using the knowledge of $m=\mathrm{\#}{X}_u^{𝖠}$ and nsimul_$A$, the automaton enumerates the $m$ distinct states belonging to $X_u^{𝖠}$ in ascending order as explained before (i.e., using Procedure 1). As soon as it finds one from which a transition on $\sigma$ allows to enter $p$, it breaks the loop as $p\in X_{u\sigma }^{𝖠}$ has been witnessed. If otherwise the $m$ states are correctly found but none of them has an outgoing transition to $p$ on $\sigma$, a witness of $p\notin X_{u\sigma }^{𝖠}$ has been obtained. Once the number of states in $X_{u\sigma }^{𝖠}$ has been computed, the automaton forgets those of $X_u^{𝖠}$, moves its head one cell to the right, and proceeds with the next iteration of the induction.

However, implementing nsimul_$A$ with a $2$nfa is challenging. Indeed, since there is an unbounded number of prefixes of inputs, it is not possible to bring the head back to its initial position (in order to restart a computation of $𝖠$), and then recover the position $|u|$. To overcome this issue, we use annotations, so that it is possible to simulate computations of $𝖠$ without moving the head more than $2n$ cells to the left of position $|u|$. In this way, the automaton can recover the position $|u|$ by maintaining, in its finite control, the distance of the head from that position.

Let $w\in {\mathrm{\Sigma }}^{\ast }$. The idea is to consider an annotated word $x\in {(\mathrm{\Sigma }\times \{0,1\})}^{\ast }$ such that ${\pi }_1(x)=w$ and the following property holds. Logically dividing $x$ into factors of length $n$ (or possibly less for the last one), the $i$-th factor encodes $X_{w[0,i\cdot n-1]}^{𝖠}$. Formally, decomposing $x$ as $x=x_1\mathrm{\cdots }{x}_{k+1}$ with $|x_{k+1}|\le n$ and $|x_i|=n$ for each $i\le k$, every ${\pi }_2(x_i)$ (except, possibly ${\pi }_2(x_{k+1})$ if it has length less than $n$) encodes the set $X_{{\pi }_1(x_1\mathrm{\cdots }{x}_i)}^{𝖠}=X_{w[0,i\cdot n-1]}^{𝖠}$. In this way, our nondeterministic procedure nsimul_$A$ starting from some position $i\cdot n+j$, $0\le i\le k$ and , operates in two phases. First, it scans ${\pi }_2(x_i)$, from which it extracts some nondeterministically-chosen state $p\in X_{w[0,i\cdot n-1]}^{𝖠}$ – for $i=0$, we assume $x_i=⊳$ from which the machine extracts $p=q_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}$. Second, it performs a direct simulation of $𝖠$ on ${\pi }_1(x_{i+1}[0,j])$, starting from the selected state $p$ and halting as soon as the cell at position $i\cdot n+j$ is entered. At that time, the reached state in the simulated path, belongs to $\delta (p,w[i\cdot n,i\cdot n+j-1])$, and thus to $X_{w[0,i\cdot n+j-1]}^{𝖠}$ since $p\in X_{w[0,i\cdot n-1]}^{𝖠}=\delta (q_{\mathrm{𝗌𝗍𝖺𝗋𝗍}},w[0,i\cdot n-1])$.

A subset $S$ of $Q=[n]$ is naturally encoded as a length-$n$ word $\mathrm{𝖾𝗇𝖼}(S)\in {\{0,1\}}^{\ast }$ as follows:

Hence, provided ${\pi }_2(x_i)=\mathrm{𝖾𝗇𝖼}(X_{w[0,i\cdot n]}^{𝖠})$, in order for nsimul_$A$ to select $p\in X_{w[0,i\cdot n]}^{𝖠}$ during its first phase, it is sufficient to choose a position $p$ of $x_i$ such that ${\pi }_2(x_i[p])=1$. The annotation of a word $w\in {\mathrm{\Sigma }}^{\ast }$ is defined now.

Our goal is to design a $2$nfa $𝖡$ over $\mathrm{\Psi }=\mathrm{\Sigma }\times \{0,1\}$ of polynomial size in $n$, with two distinguished states $q_{\mathrm{𝖺𝖼𝖼}}$ (for acceptance) and $q_{\mathrm{𝗋𝖾𝗃}}$ (for rejection) that satisfies:

• $\mathrm{■}$

  $𝖡$ accepts $x$ if and only if ${\pi }_1(x)\in ℒ(𝖠)$ and $x=\mathrm{𝖺𝗇𝗇𝗈𝗍}({\pi }_1(x))$;

• $\mathrm{■}$

  $𝖡$ rejects $x$ if and only if ${\pi }_1(x)\notin ℒ(𝖠)$ and $x=\mathrm{𝖺𝗇𝗇𝗈𝗍}({\pi }_1(x))$.

Notice that $𝖡$ itself is not self-verifying, as it can neither accept nor reject an input $x$ such that $x\ne \mathrm{𝖺𝗇𝗇𝗈𝗍}({\pi }_1(x))$. However, the $2$nfa$+\mathrm{𝖼𝗀}$ $⟨𝖡,\mathrm{\Sigma },\{0,1\}⟩$ is self-verifying since every input $w\in {\mathrm{\Sigma }}^{\ast }$ admits an annotated variant $\mathrm{𝖺𝗇𝗇𝗈𝗍}(w)$ that should be either accepted or rejected by $𝖡$ according to whether $w$ belongs to $ℒ(𝖠)$ or not.

The design of $𝖡$ follows the above-explained inductive counting strategy. In particular, it uses the already-presented procedures enum_$X$, member_$X$, and count_next_$X$ (see Procedures 1, 3, and 4), as well as nsimul_$A$. To implement the latter, $𝖡$ maintains two variables in its finite control: the value of its head position modulo $n$ (so it knows where each factor $x_i$ begins, and to which state $p$ an annotation symbol $1$ correspond), and the distance of its current head position to the position $|z|$, where $z$ is the input prefix under consideration. By the locality of nsimul_$A$, the latter information is an integer less than $2n$.

Not only $𝖡$ has to behave correctly on inputs $\mathrm{𝖺𝗇𝗇𝗈𝗍}(w)$: it also has to detect ill-formed inputs, namely words $x\in {\mathrm{\Psi }}^{\ast }$ for which $x\ne \mathrm{𝖺𝗇𝗇𝗈𝗍}({\pi }_1(x))$. To this end, each time the length of the prefix $z$ under consideration is a positive multiple of $n$, before considering the next prefix, $𝖡$ checks the annotation of the length-$n$ suffix $x_i$ ($i=|z|/n$) of $z$. This can easily be done, since at that time $m=\mathrm{\#}{X}_{{\pi }_1(z)}^{𝖠}$ has been computed. Hence, the automaton can check that ${\pi }_2(x_i)$ has $m$ occurrences of $1$, and, using enum_$X$, that ${\pi }_2(x_i[p])=1$ for each $p\in X_{{\pi }_1(z)}^{𝖠}$.

Evaluating the size of $𝖡$, we get that $𝒪(n^3)$ states are sufficient for implementing nsimul_$A$, including the two above-mentioned state components relative to the head position. Next, $𝖡$ further uses a $𝒪(n^4)$-state component for storing $𝚖=\mathrm{\#}{X}_u^{𝖠}$, ${𝚖}_{\mathrm{𝚗𝚎𝚡𝚝}}\le \mathrm{\#}{X}_{u\tau }^{𝖠}$, and two intermediate states $𝚚$ and ${𝚚}_{\mathrm{𝚙𝚛𝚎𝚟}}$. Hence, the total number of states belongs to $𝒪(n^7)$.

A direct consequence is that complementing 1-las costs at most a single exponential.

In this section, we show how to simulate an arbitrary $n$-state $2$nfa $𝖠$ over $\mathrm{\Sigma }$ with a self-verifying $2$nfa$+\mathrm{𝖼𝗀}$ $𝖬$ that has polynomially many states in $n$ and $2$ annotation symbols.

The self-verifyingness of the obtained $2$nfa$+\mathrm{𝖼𝗀}$ $𝖬$ is actually implied by a stronger condition which is satisfied by its underlying $2$nfa $𝖡$ over $\mathrm{\Psi }=\mathrm{\Sigma }\times \{0,1\}$. This is stated in the following lemma whose proof is our main technical contribution.

Notice that, in the above lemma, $𝖡$ itself is not a self-verifying $2$nfa. Indeed, on inputs not belonging to $\mathrm{𝖺𝗇𝗇𝗈𝗍}({\mathrm{\Sigma }}^{\ast })$, $𝖡$ neither accepts nor rejects.⁶⁶6$𝖡$ is actually a don’t-care automaton [13], namely an automaton with the self-verifying property on inputs from a restricted domain (here, inputs of the form $\mathrm{𝖺𝗇𝗇𝗈𝗍}(w)$ for some $w\in {\mathrm{\Sigma }}^{\ast }$). Yet, as the goal is to check whether a word $w\in {\mathrm{\Sigma }}^{\ast }$ belongs to $ℒ(𝖠)$, and since each such word has an annotated version $\mathrm{𝖺𝗇𝗇𝗈𝗍}(w)$ that is either accepted or rejected by $𝖡$, we obtain self-verifyingness for the $2$nfa$+\mathrm{𝖼𝗀}$ $𝖬=⟨𝖡,\mathrm{\Sigma },\{0,1\}⟩$.

The rest of the section is devoted to the proof of Lemma 4.2, and is structured as follows. In Section 4.1, we recall the principle of Shepherdson’s construction [19], introducing the basic concepts and properties on which such a simulation as much as ours relies. The definition of $\mathrm{𝖺𝗇𝗇𝗈𝗍}(w)$ is given at the end of the section. The automaton $𝖡$ is then designed in Section 4.2, where the proof of Lemma 4.2 is finally completed.