Size complexity of rotating and sweeping automata

DOI10.1016/J.JCSS.2011.06.004MaRDI QIDQ414916zbMATHOpenAlexFDO

Authors Richard Královič, Tobias Mömke, Christos 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 automataself-verificationhardness propagationsize complexitysweeping automata

Mathematics Subject Classification ID

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

Recommendations

• On the Size Complexity of Rotating and Sweeping Automata
• An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata
• Tight lower bounds on the size of sweeping automata
• Lower bounds on the size of sweeping automata
• A technique for proving lower bounds on the size of sweeping automata

Cites work

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

Cited in

(20)

• Lower bounds on the size of sweeping automata
• Reversibility of computations in graph-walking automata
• On the size of two-way reasonable automata for the liveness problem
• New size hierarchies for two way automata
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• On Hadamard series and rotating \(\mathbb{Q}\)-automata
• A technique for proving lower bounds on the size of sweeping automata
• Infinite vs. finite size-bounded randomized computations
• Oblivious two-way finite automata: decidability and complexity
• On a compact encoding of the swap automaton
• Descriptional complexity of limited automata
• From Hadamard expressions to weighted rotating automata and back
• Running Time Complexity of Printing an Acyclic Automaton
• Tight lower bounds on the size of sweeping automata
• Determinism vs. nondeterminism for two-way automata: representing the meaning of states by logical formulæ
• Simple picture processing based on finite automata and regular grammars
• On simulation cost of unary limited automata
• Non-self-embedding grammars, constant-height pushdown automata, and limited automata
• From Hadamard expressions to weighted rotating automata and back
• On the Size Complexity of Rotating and Sweeping Automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414916)