An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata

DOI10.1007/978-3-540-74871-7_12MaRDI QIDQ3608505zbMATH OpenOpenAlexFDO

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

Publication date 5 March 2009

Published in Stochastic Algorithms: Foundations and Applications (Search for Journal in Brave)

Full work available at URL http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-51153

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Tight lower bounds on the size of sweeping automata
• On the power of Las Vegas II: Two-way finite automata
• On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
• On the power of Las Vegas. II: Two-way finite automata
• Note on the complexity of Las Vegas automata problems

Cited in

(8)

• Tight lower bounds on the size of sweeping automata
• Infinite vs. finite size-bounded randomized computations
• On the Size Complexity of Rotating and Sweeping Automata
• Size Complexity of Two-Way Finite Automata
• Size complexity of rotating and sweeping automata
• Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser's separation
• Lower bounds on the size of sweeping automata
• A technique for proving lower bounds on the size of sweeping automata

This page was built for publication: An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata

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