Unambiguous finite automaton

In automata theory, an unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such that each word has at most one accepting path. Each deterministic finite automaton (DFA) is an UFA, but not vice versa. DFA, UFA, and NFA recognize exactly the same class of formal languages.
On the one hand, an NFA can be exponentially smaller than an equivalent DFA. On the other hand, some problems are easily solved on DFAs and not on UFAs. For example, given an automaton "A", an automaton "A" which accepts the complement of "A" can be computed in linear time when "A" is a DFA, it is not known whether it can be done in polynomial time for UFA. Hence UFAs are a mix of the worlds of DFA and of NFA; in some cases, they lead to smaller automata than DFA and quicker algorithms than NFA.
Formal definition.
An "NFA" is represented formally by a 5-tuple, "A"=("Q", Σ, Δ, "q0", "F").
An "UFA" is an NFA such that, for each word "w = a1a2 … an", there exists at most one sequence of states "r0,r1, …, rn", in "Q" with the following conditions:
In words, those conditions state that, if "w" is accepted by "A", there is exactly one accepting path, that is, one path from an initial state to a final state, labelled by "w".
Example.
Let "L" be the set of words over the alphabet {"a","b"} whose "n"th last letter is an "a". The figures show a DFA and a UFA accepting this language for "n=2".
The minimal DFA accepting "L" has "2n" states, one for each subset of {1..."n"}. There is an UFA of "n"+1 states which accepts "L": it guesses the "n"th last letter, and then verifies that only "n"-1 letters remain. It is indeed unambiguous as there exists only one "n"th last letter.
Inclusion, universality, equivalence.
Three PSPACE-hard problems for general NFA belong to PTIME for DFA and are now considered.
Inclusion.
It is decidable in polynomial-time whether an UFA's language is a subset of another UFA's language.
Let "A" and "B" be two UFAs. Let "L"("A") and "L"("B") be the languages accepted by those automata. Then "L"("A")⊆"L"("B") if and only if "L"("A"∩"B")="L"("A"), where "A"∩"B" denotes the Cartesian product automaton, which can be proven to be also unambiguous. Now, "L"("A"∩"B") is a subset of "L"("A") by construction; hence both sets are equal if and only if for each length "n"∈ℕ, the number of words of length "n" in "L"("A"∩"B") is equal to the number of words of length "n" in "L"("A"). It can be proved that is sufficient to check each "n" up to the product of the number of states of "A" and "B".
The number of words of length "n" accepted by an automaton can be computed in polynomial time using dynamic programming, which ends the proof.
Universality, equivalence.
The problem of universality and of equivalence, also belong to PTIME, by reduction to the inclusion problem.
Checking whether an automaton in unambiguous.
For a nondeterministic finite automaton "A" with "n" states and an "m" letter alphabet, it is decidable in time "O(n2m)" whether "A" is unambiguous.
It suffices to use a fixpoint algorithm to compute the set of pairs of states "q" and "q' " such that there exists a word "w" which leads both to "q" and to "q' ". The automaton is unambiguous if and only if there is no such a pair such that both states are accepting. There are "Θ"("n"2) state pairs, and for each pair there are "m" letters to consider to resume the fixpoint algorithm, hence the computation time.
State complexity.
Mathematical proofs that every UFA for a language needs a certain number of states were pioneered by Schmidt. Leung proved that a DFA equivalent to an formula_1-state UFA requires formula_2 states in the worst case, and that a UFA equivalent to a finitely ambiguous formula_1-state NFA requires formula_4 states in the worst case.
Jirásek, Jirásková and Šebej researched state complexity of basic regular operations on languages represented by UFA. They proved in particular that for every formula_1-state UFA where formula_6, the complement of the language it accepts is accepted by a UFA with at most formula_7 states. This result was later improved by Indzhev and Kiefer to at most formula_8 states for all formula_9.
For a one-letter alphabet Okhotin proved that a DFA equivalent to an formula_1-state UFA requires formula_11 states in the worst case.