State complexity of finite tree width NFAs

DOI10.25596/JALC-2012-245MaRDI QIDQ5178457zbMATH OpenOpenAlexFDO

Authors Alexandros Palioudakis, Kai Salomaa, Selim G. Akl

Publication date 16 March 2015

Full work available at URL https://doi.org/10.25596/jalc-2012-245

zbMATH Keywords

limited nondeterminismfinite automatastate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity and limited nondeterminism
• Nondeterminism growth and state complexity
• Nondeterministic tree width of regular languages
• Worst Case Branching and Other Measures of Nondeterminism
• Finite nondeterminism versus DFAs with multiple initial states

Cited in

(17)

• Converting finite width AFAs to nondeterministic and universal finite automata
• Deciding path size of nondeterministic (and input-driven) pushdown automata
• Lower bound for converting an NFA with finite nondeterminism into an MDFA
• Maximal universal width of an AFA is NP-hard
• Branching measures and nearly acyclic NFAs
• State complexity and limited nondeterminism
• Alternating finite automata with limited universal branching
• Descriptional complexity of finite automata -- selected highlights
• Finite nondeterminism versus DFAs with multiple initial states
• Structural properties of NFAs and growth rates of nondeterminism measures
• Improved upper bounds for determinizing NIDPDAs with limited nondeterminism
• Nondeterministic tree width of regular languages
• Existential and universal width of alternating finite automata
• Comparisons between measures of nondeterminism on finite automata
• Width of non-deterministic automata
• Existential and universal width of alternating finite automata
• Width measures of alternating finite automata

This page was built for publication: State complexity of finite tree width NFAs

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