Magic numbers in the state hierarchy of finite automata

DOI10.1016/j.ic.2007.07.001zbMath1130.68069OpenAlexW2074307142MaRDI 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 languagesfinite-state automatadescriptional complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES ⋮ Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata ⋮ The Range of State Complexities of Languages Resulting from the Cascade Product — The Unary Case ⋮ Kleene closure and state complexity ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Magic Numbers in Periodic Sequences ⋮ Pairs of complementary unary languages with ``balanced nondeterministic automata ⋮ Binary coded unary regular languages ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Concatenation of regular languages and descriptional complexity ⋮ On a structural property in the state complexity of projected regular languages ⋮ Unnamed Item ⋮ Non-Self-Embedding Grammars and Descriptional Complexity ⋮ THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES ⋮ SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ State complexity of binary coded regular languages ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Chrobak Normal Form Revisited, with Applications ⋮ Remarks on Separating Words ⋮ State Complexity of Projected Languages ⋮ Optimal state reductions of automata with partially specified behaviors ⋮ 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 ⋮ DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ ⋮ 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
• 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