State complexity and limited nondeterminism

DOI10.1007/978-3-642-31623-4_20MaRDI QIDQ3167587zbMATH OpenOpenAlexFDO

Authors Alexandros Palioudakis, Kai Salomaa, Selim G. Akl

Publication date 2 November 2012

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31623-4_20

zbMATH Keywords

finite automatalanguage operationslimited nondeterminismstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of finite tree width NFAs
• Nondeterminism growth and state complexity
• Nondeterministic tree width of regular languages
• Operational state complexity of unary NFAs with finite nondeterminism
• Worst Case Branching and Other Measures of Nondeterminism

Cited in

(14)

• On finite automata with limited nondeterminism
• Nondeterminism growth and state complexity
• State complexity of pseudocatenation
• Finite nondeterminism versus DFAs with multiple initial states
• scientific article; zbMATH DE number 7301304 (Why is no real title available?)
• State complexity of finite tree width NFAs
• State-complexity of finite-state devices, state compressibility and incompressibility
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
• Nondeterministic tree width of regular languages
• Lower bound for converting an NFA with finite nondeterminism into an MDFA
• Left is Better Than Right for Reducing Nondeterminism of NFAs
• Alternating finite automata with limited universal branching
• The state complexity of \(L^{2}\) and \(L^k\)
• Operational state complexity of unary NFAs with finite nondeterminism

This page was built for publication: State complexity and limited nondeterminism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167587)