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

K. Takaki, Yahiko Kambayashi, Kazuo Iwama

Publication date: 4 June 2000

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (31)

The range of state complexities of languages resulting from the cascade product -- the general case (extended abstract) ⋮ THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES ⋮ State complexity of combined operations ⋮ The Range of State Complexities of Languages Resulting from the Cascade Product — The Unary Case ⋮ ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION ⋮ Kleene closure and state complexity ⋮ A family of NFAs which need 2\(^{n}-\alpha\) deterministic states ⋮ Magic Numbers in Periodic Sequences ⋮ On the accepting state complexity of operations on permutation automata ⋮ 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 ⋮ Unnamed Item ⋮ 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 ⋮ State complexity of binary coded regular languages ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ State Complexity of Projected Languages ⋮ On the stabilization of nondeterministic finite automata via static output feedback ⋮ 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 ⋮ More on the descriptional complexity of products of finite automata ⋮ The Ranges of Accepting State Complexities of Languages Resulting from Some Operations ⋮ State complexity of binary coded regular languages ⋮ The range of state complexities of languages resulting from the cascade product -- the unary case (extended abstract)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs