Ambiguity, Nondeterminism and State Complexity of Finite Automata

DOI10.14232/actacyb.23.1.2017.9zbMath1389.68044OpenAlexW2611884230MaRDI QIDQ5350151

Yo-Sub Han, Kai Salomaa, Arto Salomaa

Publication date: 25 August 2017

Published in: Acta Cybernetica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.14232/actacyb.23.1.2017.9

zbMATH Keywords

finite automatanondeterminismstate complexitydegree of ambiguity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (8)

Markov chains and unambiguous automata ⋮ Existential and universal width of alternating finite automata ⋮ Branching Measures and Nearly Acyclic NFAs ⋮ On degrees of ambiguity for Büchi tree automata ⋮ Solving string problems on graphs using the labeled direct product ⋮ Unnamed Item ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Structural properties of NFAs and growth rates of nondeterminism measures

This page was built for publication: Ambiguity, Nondeterminism and State Complexity of Finite Automata