Two-way unary automata versus logarithmic space

DOI10.1016/j.ic.2011.03.003zbMath1216.68143WikidataQ61677514 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 automata; state complexity; logarithmic space; space complexity; unary regular languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ, State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis, 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, Two-way automata making choices only at the endmarkers, Oblivious two-way finite automata: decidability and complexity, Two-way automata versus logarithmic space, Two-way automata characterizations of L/poly versus NL, Boolean language operations on nondeterministic automata with a pushdown of constant height

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