Magic numbers in the state hierarchy of finite automata

DOI10.1016/j.ic.2007.07.001zbMath1130.68069MaRDI QIDQ2461796

Viliam Geffert

Publication date: 21 November 2007

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2007.07.001

zbMATH Keywords

regular languages; finite-state automata; descriptional complexity

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES, Chrobak Normal Form Revisited, with Applications, Remarks on Separating Words, State Complexity of Projected Languages, DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ, Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata, On a structural property in the state complexity of projected regular languages, Concatenation of regular languages and descriptional complexity, Pairs of complementary unary languages with ``balanced nondeterministic automata, THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES, MAGIC NUMBERS AND TERNARY ALPHABET, Concatenation of Regular Languages and Descriptional Complexity, NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the state complexity of reversals of regular languages
• Finite automata and unary languages
• A lower bound for the nondeterministic space complexity of context-free recognition
• Lower bounds on space complexity for contextfree recognition
• An optimal lower bound for nonregular languages
• A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
• Space hierarchy theorem revised.
• Converting two-way nondeterministic unary automata into simpler automata.
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• Optimal Simulations between Unary Automata
• On the maximal order in $S_n$ and $S*_n$
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• Nondeterminism and the size of two way finite automata
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata