Nondeterministic Tree Width of Regular Languages

DOI10.1007/978-3-319-19225-3_4zbMath1320.68109OpenAlexW801472226MaRDI QIDQ5500678

Kai Salomaa, Cezar Campeanu

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

regular languagesnondeterministic finite automatameasures of nondeterminism

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The tractability frontier for NFA minimization
• Minimizing finite automata is computationally hard
• On measuring nondeterminism in regular languages
• Finite automata and unary languages
• Intersection and union of regular languages and state complexity
• Communication complexity method for measuring nondeterminism in finite automata
• Rational sets in commutative monoids
• Unary NFAs with Limited Nondeterminism
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• State Complexity and Limited Nondeterminism
• A Second Course in Formal Languages and Automata Theory
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• Minimal NFA Problems are Hard
• Non-Deterministic Finite Cover Automata
• State Complexity of Finite Tree Width NFAs
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• One-unambiguous regular languages

This page was built for publication: Nondeterministic Tree Width of Regular Languages