Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs

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)

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

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

• Equivalence problem of non-deterministic finite automata
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item