Improved limits on ambiguity in nondeterministic finite automata
Stronger bounds on the degree of ambiguity of finite automata
Formal Languages and Automata Theory
Summary
Nondeterministic finite automata (NFA) are models used to process sequences of inputs, where multiple ways to accept the same input are possible. Ambiguity measures how many such accepting paths exist for a given input. The authors improved the known upper bound on the maximum number of accepting paths for any input in an NFA with a given number of states, making this bound exponentially smaller than previously known. This tighter bound helps better understand the complexity and behavior of these automata.
What this means in practice
- •For formal language engineers: Design automata-based parsers with guarantees on the maximum number of accepting executions per input to optimize performance.
- •For software verification teams: Use precise bounds on automata ambiguity to improve model checking tools that rely on nondeterministic automata representations.
A theory result. No direct application yet.
Authors
Stefan Kiefer, Filip Mazowiecki, Andrew Ryzhikov, Antoni Wiśniewski
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.