An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata

DOI10.1007/978-3-540-74871-7_12zbMath1175.68246OpenAlexW1603510456MaRDI QIDQ3608505

Richard Královič, Tobias Mömke, Christos A. 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)

Related Items (4)

Infinite vs. finite size-bounded randomized computations ⋮ Size complexity of rotating and 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