Size complexity of rotating and sweeping automata

DOI10.1016/j.jcss.2011.06.004zbMath1242.68146OpenAlexW2057384603MaRDI 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

randomizationfinite automatasize complexityself-verificationhardness propagationsweeping automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

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

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

This page was built for publication: Size complexity of rotating and sweeping automata