Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
From MaRDI portal
Publication:1566750
DOI10.1016/S0304-3975(00)00029-3zbMath0939.68068MaRDI QIDQ1566750
Kazuo Iwama, Yahiko Kambayashi, K. Takaki
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q45: Formal languages and automata
Related Items
THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES, State Complexity of Projected Languages, MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS, On a structural property in the state complexity of projected regular languages, Concatenation of regular languages and descriptional complexity, A family of NFAs which need 2\(^{n}-\alpha\) deterministic states, State complexity of combined operations, Magic numbers in the state hierarchy of finite automata, THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES, Concatenation of Regular Languages and Descriptional Complexity, NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY, Deterministic blow-ups of minimal NFA's, ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION, On the State Complexity of Complements, Stars, and Reversals of Regular Languages, DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, Magic Numbers and Ternary Alphabet
Cites Work