pipette
ESEspañol

Stronger bounds on the degree of ambiguity of finite automata

Stefan Kiefer, Filip Mazowiecki, Andrew Ryzhikov, Antoni Wi\'sniewski

Preprint

In the authors' words

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

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.