Stronger bounds on the degree of ambiguity of finite automata

Stefan Kiefer, Filip Mazowiecki, Andrew Ryzhikov +1

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 ever…