Nondeterministic tree width of regular languages

DOI10.1007/978-3-319-19225-3_4MaRDI QIDQ5500678zbMATH OpenOpenAlexFDO

Authors Kai Salomaa, C. Câmpeanu

Publication date 7 August 2015

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

Full work available at URL https://doi.org/10.1007/978-3-319-19225-3_4

zbMATH Keywords

measures of nondeterminismnondeterministic finite automataregular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Nondeterminism growth and state complexity
• State complexity of finite tree width NFAs
• State complexity and limited nondeterminism
• Comparisons between measures of nondeterminism on finite automata
• Worst Case Branching and Other Measures of Nondeterminism

Cites work

• A Second Course in Formal Languages and Automata Theory
• Communication complexity method for measuring nondeterminism in finite automata
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• Finite automata and unary languages
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Intersection and union of regular languages and state complexity
• Minimal NFA Problems are Hard
• Minimizing finite automata is computationally hard
• Non-deterministic finite cover automata
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On measuring nondeterminism in regular languages
• One-unambiguous regular languages
• Rational sets in commutative monoids
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Simplifying nondeterministic finite cover automata
• State complexity and limited nondeterminism
• State complexity of finite tree width NFAs
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• The tractability frontier for NFA minimization
• Unary NFAs with limited nondeterminism

Cited in

(15)

• Structural properties of NFAs and growth rates of nondeterminism measures
• Branching measures and nearly acyclic NFAs
• Comparisons between measures of nondeterminism on finite automata
• Regular languages of thin trees
• THE REGULARITY OF TWO-WAY NONDETERMINISTIC TREE AUTOMATA LANGUAGES
• State complexity and limited nondeterminism
• Width of non-deterministic automata
• Regular Approximation of Weighted Linear Context-Free Tree Languages
• State complexity of finite tree width NFAs
• Branching measures and nearly acyclic NFAs
• Computing the width of non-deterministic automata
• Computation width and deviation number
• Widths of regular and context-free languages
• Maximal existential and universal width
• On deterministic finite automata equipped with partial orders

This page was built for publication: Nondeterministic tree width of regular languages

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