State Complexity of Finite Tree Width NFAs

DOI10.25596/jalc-2012-245zbMath1322.68126OpenAlexW2398019323MaRDI QIDQ5178457

Kai Salomaa, Alexandros Palioudakis, Selim G. Akl

Publication date: 16 March 2015

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

zbMATH Keywords

finite automatastate complexitylimited nondeterminism

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Converting finite width AFAs to nondeterministic and universal finite automata ⋮ Existential and universal width of alternating finite automata ⋮ Branching Measures and Nearly Acyclic NFAs ⋮ Nondeterministic Tree Width of Regular Languages ⋮ Width measures of alternating finite automata ⋮ 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: State Complexity of Finite Tree Width NFAs