Skip to main content

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.


Popular posts from this blog

Oxford Admissions

An initial draft of this post was about how to make rankings more meaningful, a piece of mathsy computer science, as you expect it from this blog. My motivation is personal: I'm involved in selecting CS undergraduate students. Some people might be curious how Oxford admissions work: it's certainly a favourite subject for UK politicians and news media. Therefore I decided to postpone my original plan and to write this post about Oxford admissions. I hope I'm not playing with too much fire and the blog will not suddenly become famous for the wrong reasons!

The tenor in newspapers and political campaigns is that the Oxbridge admissions process is “opaque” and unfair. Here I am going to offer transparency and some comments on fairness. The views expressed here are my own, and may not necessarily coincide with the university's views.

Oxford's goal is to admit the strongest applicants. One can disagree with this basic premise, but we try to admit those applicants who w…

Probabilistic Models of Computation

This post has 0 ideas. At least, no ideas that are younger than 50 years or so. I'm talking about the two most fundamental models of probabilistic computation and the two most fundamental results about them, according to my subjective judgement.

Every computer scientist knows finite automata: State $1$ is the start state, and state $3$ is the only accepting state. Some words are accepted (i.e., have an accepting run), for instance the word $aa$. Other words are rejected (i.e., have no accepting run), for instance the word $ba$. Most questions about finite automata are decidable. For instance, the emptiness problem, which asks whether the automaton accepts at least one word. This problem is decidable in polynomial time: view the automaton as a graph, and search the graph for a path from the initial state to an accepting state. One can also decide whether two given automata are equivalent, i.e., do they accept the same words? This problem is computationally hard though: PSPACE-co…

The Price of Memory

In an earlier post I defined the price of memory, $u$, and asked:
Is $u < 1$? Worth €100.
Determine $u$. Worth another €100, even if $u=1$. I'm happy to announce that there is now a solution:
The price of memory, $u$, is 1. I don't want to repeat the precise definition of $u$, but here is a short recap: Suppose you have an acyclic finite MDP and a strategy $\sigma$ that guarantees to visit a red transition with probability 1. This strategy $\sigma$ might use memory, i.e., might base its behaviour in a state on the history of the run, as indicated in yellow:
Any such strategy $\sigma$ induces a randomized strategy $\overline\sigma$ that acts like $\sigma$ in average, but is memoryless. In each state, when averaged over all runs, the strategies $\sigma$ and $\overline\sigma$ take the same actions with the same probabilities:
One can show that $\sigma$ and $\overline\sigma$ visit red transitions equally often in average; in particular, $\overline\sigma$ visits at least…