Size complexity of rotating and sweeping automata

DOI10.1016/j.jcss.2011.06.004zbMath1242.68146MaRDI QIDQ414916

Richard Královič, Tobias Mömke, Christos A. Kapoutsis

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.06.004

zbMATH Keywords

randomization; finite automata; size complexity; self-verification; hardness propagation; sweeping automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

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

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

On the Size of Two-Way Reasonable Automata for the Liveness Problem, On Hadamard Series and Rotating Q-Automata, DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ, On Simulation Cost of Unary Limited Automata, From Hadamard expressions to weighted rotating automata and back, From Hadamard expressions to weighted rotating automata and back, Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata, Descriptional complexity of limited automata, Simple picture processing based on finite automata and regular grammars, New size hierarchies for two way automata, Reversibility of computations in graph-walking automata, Oblivious two-way finite automata: decidability and complexity, Boolean language operations on nondeterministic automata with a pushdown of constant height, Infinite vs. finite size-bounded randomized computations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Halting space-bounded computations
• Lower bounds on the size of sweeping automata
• Two-way deterministic finite automata are exponentially more succinct than sweeping automata
• Amplification of slight probabilistic advantage at absolutely no cost in space
• State complexity of some operations on binary regular languages
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Complementing two-way finite automata
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• On the Size Complexity of Rotating and Sweeping Automata
• An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata
• Small Sweeping 2NFAs Are Not Closed Under Complement
• Size Complexity of Two-Way Finite Automata
• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
• Nondeterminism and the size of two way finite automata
• On the power of Las Vegas II: Two-way finite automata