An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata

DOI10.1007/978-3-540-74871-7_12zbMATH Open1175.68246OpenAlexW1603510456MaRDI QIDQ3608505FDOQ3608505

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

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
• Publication:4938639
• Note on the complexity of Las Vegas automata problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (8)

• Size complexity of rotating and sweeping automata
• 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
• Title not available (Why is that?)
• Tight lower bounds on the size of sweeping automata
• On the Size Complexity of Rotating and Sweeping Automata
• Size Complexity of Two-Way Finite 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)