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.68539OpenAlexW1578832536MaRDI 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
Related Items
Closure properties and descriptional complexity of deterministic regular expressions ⋮ Magic Numbers in Periodic Sequences ⋮ On the gap between separating words and separating their reversals ⋮ On a structural property in the state complexity of projected regular languages ⋮ State Complexity of Projected Languages ⋮ Operational Accepting State Complexity: The Unary and Finite Case ⋮ Complexity of bifix-free regular languages ⋮ Complexity of bifix-free regular languages ⋮ Magic Numbers and Ternary Alphabet ⋮ The Complexity of Languages Resulting from the Concatenation Operation
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
