Worst Case Branching and Other Measures of Nondeterminism

DOI10.1142/S0129054117500137zbMath1371.68163OpenAlexW2616617106MaRDI QIDQ5268392

Alexandros Palioudakis, Selim G. Akl, Kai Salomaa

Publication date: 20 June 2017

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054117500137

zbMATH Keywords

finite automatanondeterminismbranchingstate complexitylimited nondeterminism

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Left is Better Than Right for Reducing Nondeterminism of NFAs, Existential and universal width of alternating finite automata, From Parallelism to Nonuniversality: An Unconventional Trajectory

Cites Work

• Unambiguous finite automata over a unary alphabet
• Descriptional and computational complexity of finite automata -- a survey
• On measuring nondeterminism in regular languages
• Amounts of nondeterminism in finite automata
• On the relation between ambiguity and nondeterminism in finite automata
• On finite automata with limited nondeterminism
• Communication complexity method for measuring nondeterminism in finite automata
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY