THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES
From MaRDI portal
Publication:5168427
DOI10.1142/S0129054114500063zbMath1295.68146MaRDI QIDQ5168427
Publication date: 4 July 2014
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Related Items
Operational complexity and pumping lemmas ⋮ Kleene closure and state complexity ⋮ Further Remarks on the Operational Nonterminal Complexity ⋮ Complexity of automatic sequences ⋮ Operational complexity and right linear grammars
Cites Work
- 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
- Magic numbers in the state hierarchy of finite automata
- MAGIC NUMBERS AND TERNARY ALPHABET
- 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
