Nondeterministic State Complexity of Star-Free Languages
From MaRDI portal
Publication:5200063
DOI10.1007/978-3-642-22256-6_17zbMath1297.68137MaRDI QIDQ5200063
Markus Holzer, Katja Meckel, Martin Kutrib
Publication date: 29 July 2011
Published in: Implementation and Application of Automata (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22256-6_17
68Q45: Formal languages and automata
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Descriptional and computational complexity of finite automata -- a survey
- A lower bound technique for the size of nondeterministic finite automata
- Finite automata and unary languages
- Intersection and union of regular languages and state complexity
- Quotient complexity of closed languages
- State complexity of some operations on binary regular languages
- Determination of finite automata accepting subregular languages
- THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Complexity in Union-Free Regular Languages
- Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
- Power-separating regular languages
- QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
- Quotient Complexity of Bifix-, Factor-, and Subword-free Regular Language
- On finite monoids having only trivial subgroups
- Roots of Star Events
- On Decompositions of Regular Events
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES