Size complexity of rotating and sweeping automata
DOI10.1016/J.JCSS.2011.06.004zbMATH Open1242.68146OpenAlexW2057384603MaRDI QIDQ414916FDOQ414916
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
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
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)
Cites Work
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- Title not available (Why is that?)
- Halting space-bounded computations
- Title not available (Why is that?)
- Complementing two-way finite automata
- State complexity of some operations on binary regular languages
- 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
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
Cited In (20)
- Reversibility of computations in graph-walking automata
- On a compact encoding of the swap automaton
- Non-self-embedding grammars, constant-height pushdown automata, and limited automata
- New size hierarchies for two way automata
- Simple picture processing based on finite automata and regular grammars
- Lower bounds on the size of sweeping 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
- Descriptional complexity of limited automata
- From Hadamard expressions to weighted rotating automata and back
- 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æ
- On simulation cost of unary limited automata
- On the size of two-way reasonable automata for the liveness problem
- On Hadamard series and rotating \(\mathbb{Q}\)-automata
- Boolean language operations on nondeterministic automata with a pushdown of constant height
- 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)
