On the State Complexity of Complements, Stars, and Reversals of Regular Languages
From MaRDI portal
Publication:3533030
DOI10.1007/978-3-540-85780-8_34zbMath1161.68539MaRDI QIDQ3533030
Publication date: 30 October 2008
Published in: Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_34
68Q45: Formal languages and automata
Related Items
State Complexity of Projected Languages, On a structural property in the state complexity of projected regular languages, Magic Numbers and Ternary Alphabet
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound technique for the size of nondeterministic finite automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- Intersection and union of regular languages and state complexity
- The state complexities of some basic operations on regular languages
- A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
- Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
- State complexity of some operations on binary regular languages
- Nondeterminism and the size of two way finite automata
- Deterministic Blow-Ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS
- Magic Numbers in the State Hierarchy of Finite Automata
