Stronger bounds on the degree of ambiguity of finite automata

Abstract

Ambiguity measures the number of accepting runs in nondeterministic finite automata (NFA). We consider finitely ambiguous NFA, where there exists a constant $N$ such that over every word $w$ there are at most $N$ accepting runs. In such a case we also say that the NFA is $N$-ambiguous. Importantly $N$ depends only on the NFA, it does not depend on the length of the word. Weber and Seidl showed that every NFA is $N$-ambiguous for $N=2^{O(n\log n)}$, where $n$ is the number of states. We improve this to $N=2^{O(n)}$, which is asymptotically tight.