A family of NFAs which need 2\(^{n}-\alpha\) deterministic states

DOI10.1016/S0304-3975(02)00891-5zbMath1022.68067OpenAlexW2062010498MaRDI QIDQ1400001

Akihiro Matsuura, Kazuo Iwama, Mike S. Paterson

Publication date: 30 July 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00891-5

zbMATH Keywords

nondeterministic finite automatonmagic numberDeterministic finite automatonsize of automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES, Magic Numbers in Periodic Sequences, State complexity of cyclic shift, Concatenation of regular languages and descriptional complexity, On a structural property in the state complexity of projected regular languages, On the State Complexity of Complements, Stars, and Reversals of Regular Languages, DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET, MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS, Magic numbers in the state hierarchy of finite automata, THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, State Complexity of Projected Languages, MAGIC NUMBERS AND TERNARY ALPHABET, Magic Numbers and Ternary Alphabet, Concatenation of Regular Languages and Descriptional Complexity, NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY, The Complexity of Languages Resulting from the Concatenation Operation, Descriptional complexity of regular languages, Deterministic blow-ups of minimal NFA's

Cites Work

• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• 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