Unambiguous Automata: From PSPACE to P

Computer science is about leveraging mathematical structure, for instance, in order to accelerate algorithms. More often than we'd like we can't accelerate much: For instance, checking two NFAs for language inclusion or equivalence is PSPACE-complete. Even the problem whether an NFA accepts all words is PSPACE-complete. For DFAs, those problems are easy. This means that for NFAs we can't do much better than determinizing (using the subset construction and incurring an exponential blowup) and solving the resulting DFA problem.

In this post I'll discuss an automata problem that seems to call for determinization and is, in fact, PSPACE-complete for NFAs. But there is an efficient algorithm for unambiguous automata.

Here is an example of an unambiguous automaton:

The notion of accepting states is not used in this post. By unambiguousness I just mean that the automaton has no diamonds, that is, for any states $q, r$, any word $w$ labels at most one path from $q$ to $r$. (In other words, all paths from $q$ to $r$ are labelled by different words.) One can check an NFA for unambiguousness in polynomial time, by searching for diamonds in the product of the automaton with itself. We'll assume that every state is reachable from every other state.

By determinization of the automaton I mean the subset construction. In the example we get (from start state $1$):

We call a set $\alpha$ of states a cut if it can be reached from a single state and cannot reach the empty set in the determinization. Formally, $\alpha$ is a cut if there is a state $q$ and a word $w$ such that $\delta(q,w) = \alpha$ and $\delta(q,w x) \ne \emptyset$ holds for all words $x$. In the example, the sets $\{1,2,3\}$ and $\{1,2,4\}$ are cuts, reached from state $1$ via $a a$ and $a a b$.

Checking whether a given NFA has a cut is PSPACE-complete. But an unambiguous automaton has a cut if and only if the spectral radius of the average transition matrix is $1$, which can be checked in polynomial time. Details of that are in the previous post but are not important here. We solve a potentially harder problem:

Given an unambiguous automaton that has a cut.
Compute a cut $\alpha$.
Compute also a state $q$ and a word $w$ with $\delta(q,w) = \alpha$.

It's curious that the spectral-radius algorithm decides the existence of a cut without computing a cut. Neither gives the spectral-radius algorithm an indication whether a shortest word that leads to a cut has polynomial length.

Fix some state $q$. Imagine there is a cut from some other state $q_1$, that is, $\delta(q_1, v_1)$ is a cut for some word $v_1$. Since all states are reachable from each other, there is a word $v_0$ that labels a path from $q$ to $q_1$. Then $\delta(q,v_0 v_1)$ is also a cut. Again since all states are reachable from each other, there is a word $v_2$ that labels a path from a state in $\delta(q, v_0 v_1)$ to $q$, hence $\delta(q, v_0 v_1 v_2) \ni q$. It follows from the definition of a cut that $\delta(q, v_0 v_1 v_2)$ is also a cut ("once a cut, always a cut"). So when we search for cuts, we may as well fix the start state $q$ and focus on cuts that contain $q$. Let's fix $q$ for the rest of the post.

Our approach for computing a cut is to start from the singleton set $\{q\}$ and to gradually increase the set until it is a cut. Here is how we might increase the set:

Let $w$ be a word. Suppose there are a word $v$ and a state $q' \ne q$ with $\delta(q,v) \supseteq \{q, q'\}$ and $\delta(q',w) \ne \emptyset$.
Then $\delta(q,v w) \supsetneq \delta(q,w)$.

Let $r \in \delta(q',w)$. The situation can be visualized as follows:

It can be read off that \[ \delta(q,v w) \ \supseteq \ \delta(q,w) \cup \{r\} \,. \] We also see in the picture that $v w$ labels a path from $q$ to $r$ via $q'$. By unambiguousness it follows that $r \not\in \delta(q,w)$ because otherwise $v w$ would label a second path from $q$ to $r$. So the inclusion $\delta(q, v w) \supseteq \delta(q, w)$ is strict.

Let's call a word $v$ as in the proposition an extender:

Let $w$ be a word. A word $v$ is an extender (for $w$) if there there is a state $q' \ne q$ with $\delta(q,v) \supseteq \{q, q'\}$ and $\delta(q',w) \ne \emptyset$.

Now we can rephrase the proposition:

Let $w$ be a word.
For any extender $v$ we have $\delta(q,v w) \supsetneq \delta(q,w)$.

The proposition allows us to increase the set $\delta(q,w)$ by appending $w$ to an extender. We can find an extender in polynomial time (if it exists): We only have to search the product of the automaton with itself to check if there is a path from $(q,q)$ to $(q,q')$ where $q' \ne q$ is a state with $\delta(q',w) \ne \emptyset$. If such a path exists, it is labelled by an extender. The shortest path yields an extender of length at most $n^2$, where $n$ is the number of states in the automaton.

The proposition above yields a method of increasing a set $\delta(q,w)$. Is it complete? That is, is there an extender as long as we haven't hit a cut yet? The answer is yes:

Let $w$ be a word such that $\delta(q,w)$ is not a cut.
Then there is an extender $v$. Hence, by the proposition above, $\delta(q,v w) \supsetneq \delta(q,w)$.

Let $v$ be word such that $\delta(q,v) \ni q$ is a cut. Then $\delta(q,v w)$ is a cut ("once a cut, always a cut"), and it includes $\delta(q,w)$ because $\delta(q,v)$ contains $q$. So we have \[ \delta(q, v w) \supseteq \delta(q, w)\,, \] and the inclusion is strict because $\delta(q, v w)$ is a cut and $\delta(q,w)$ isn't. This means there is a state $q' \in \delta(q,v) \setminus \{q\}$ with $\delta(q', w) \ne \emptyset$. So $v$ is an extender.

We get the following theorem:

Given an unambiguous automaton that has a cut, and a state $q$, the following algorithm is a polynomial-time algorithm that computes a word $w$ of length at most $n^3$ (where $n$ is the number of states in the automaton) such that $\delta(q,w)$ is a cut.

1. $w := \varepsilon$ (the empty word)
2. while there is an extender $v$:
      $w := v w$
3. return $w$

Let's run the algorithm on the previous example automaton:

1. $w := \varepsilon$ (the empty word)
2. the word $a$ is an extender, as $\delta(1,a) = \{1,2\}$ and $\delta(2,\varepsilon) = \{2\}$:
   $w := a w = a$
3. the word $a$ is an extender, as $\delta(1,a) = \{1,2\}$ and $\delta(2,a) = \{3\}$:
   $w := a w = aa$
4. return $w = aa$, as there is no extender

Looking again at the determinization, the word $w = aa$ takes state $1$ to the cut $\{1,2,3\}$:

In the previous post I promised to show how to compute the probability that an infinite word (chosen uniformly at random) is accepted by a given unambiguous Büchi automaton. When I make good on that promise in the next post, the key ingredient will be the cut-computation method presented above.

If an unambiguous automaton does not have a cut then one can show that it has a killing word, that is, a word $w$ with $\delta(q,w) = \emptyset$ for all states $q$. Here is an open problem:

If an unambiguous automaton does not have a cut, does it always have a killing word of polynomial length? Can it be computed in polynomial time?

The idea of this post can be found in the following paper:
M.-P. Béal, E. Czeizler, J. Kari, D. Perrin. Unambiguous Automata. In Mathematics in Computer Science, 1(4):625-638, 2008. Springer.
Our CAV'16 paper has it closer to the form presented here.

Update (March 2019): The open problem has been solved.