Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Unary NFAs with Limited Nondeterminism
verfasst von : Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
Erschienen in: SOFSEM 2014: Theory and Practice of Computer Science
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider unary finite automata employing limited nondeterminism. We show that for a unary regular language, a minimal finite tree width nondeterministic finite automaton (NFA) can always be found in Chrobak normal form. A similar property holds with respect to other measures of nondeterminism. The latter observation is used to establish relationships between classes of unary regular languages recognized by NFAs of given size where the nondeterminism is limited in various ways. Finally, we show that the branching measure of a unary NFA is always either bounded by a constant or has an exponential growth rate.