Two-way unary automata versus logarithmic space

DOI10.1016/j.ic.2011.03.003zbMath1216.68143OpenAlexW2005397173WikidataQ61677514 ScholiaQ61677514MaRDI QIDQ549665

Viliam Geffert, Giovanni Pighizzini

Publication date: 18 July 2011

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

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

zbMATH Keywords

finite automatastate complexitylogarithmic spacespace complexityunary regular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Two-way automata making choices only at the endmarkers ⋮ State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ Two-way automata versus logarithmic space ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ ⋮ Two-way automata characterizations of L/poly versus NL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Turing machines that take advice
• Unary finite automata vs. arithmetic progressions
• Lower bounds on the size of sweeping automata
• Two-way deterministic finite automata are exponentially more succinct than sweeping automata
• Space-bounded reducibility among combinatorial problems
• Turing machines with sublogarithmic space
• Converting two-way nondeterministic unary automata into simpler automata.
• Relationships between nondeterministic and deterministic tape complexities
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Size Complexity of Two-Way Finite Automata
• Making Nondeterminism Unambiguous
• State-complexity of finite-state devices, state compressibility and incompressibility
• Nondeterminism and the size of two way finite automata
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY

This page was built for publication: Two-way unary automata versus logarithmic space