pipette
ENEnglish

Stronger bounds on the degree of ambiguity of finite automata

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

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.