Converting two-way nondeterministic unary automata into simpler automata.

DOI10.1016/S0304-3975(02)00403-6zbMath1045.68080WikidataQ57380802 ScholiaQ57380802MaRDI QIDQ1401239

Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

Publication date: 17 August 2003

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

zbMATH Keywords

Formal languages; Finite state automata; Unary languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

On the Size of Two-Way Reasonable Automata for the Liveness Problem, SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA, DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ, On Simulation Cost of Unary Limited Automata, Investigations on Automata and Languages Over a Unary Alphabet, State complexity of operations on two-way finite automata over a unary alphabet, Descriptional complexity of two-way pushdown automata with restricted head reversals, Two-way automata making choices only at the endmarkers, On the state complexity of operations on two-way finite automata, Two-way unary automata versus logarithmic space, Complexity of multi-head finite automata: origins and directions, Descriptional complexity of limited automata, Removing nondeterminism in constant height pushdown automata, Oblivious two-way finite automata: decidability and complexity, Two-way automata versus logarithmic space, Semitensor product approach to controllability, reachability, and stabilizability of probabilistic finite automata, Two-way automata characterizations of L/poly versus NL, Magic numbers in the state hierarchy of finite automata, Complementing two-way finite automata, On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages, Translation from classical two-way automata to pebble two-way automata, Two-Way Automata versus Logarithmic Space, Nondeterminism Is Essential in Small 2FAs with Few Reversals, On the Size of Two-Way Reasonable Automata for the Liveness Problem, TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE, Hyper-minimizing minimized deterministic finite state automata, Size Complexity of Two-Way Finite Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite automata and unary languages
• A note on the reduction of two-way automata to one-way automata
• Lower bounds on the size of sweeping automata
• Two-way deterministic finite automata are exponentially more succinct than sweeping automata
• Optimal Simulations between Unary Automata
• Two-way automaton computations
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• Nondeterminism and the size of two way finite automata