Change search
ReferencesLink to record
Permanent link

Direct link
An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata
ETH Zurich.
ETH Zurich.
ETH Zurich.
2007 (English)In: Stochastic Algorithms: Foundations and Applications: 4th International Symposium, SAGA 2007, Zurich, Switzerland, September 13-14, 2007, Springer, 2007, Vol. 4665, 130-141 p.Conference paper (Refereed)
Abstract [en]

A two-way finite automaton is sweeping if its input head canchange direction only on the end-markers.  For each n >= 2, we exhibit a problem that can be solved by an O(n^2)-state sweeping Las Vegas automaton, but needs 2^{Omega(n)} states on every sweeping deterministic automaton.

Place, publisher, year, edition, pages
Springer, 2007. Vol. 4665, 130-141 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 4665
Keyword [en]
Sweeping automata, exponential gap, randomization
National Category
Computer Science
URN: urn:nbn:se:kth:diva-51153DOI: 10.1007/978-3-540-74871-7_12ISI: 000250543700011ISBN: 978-3-540-74870-0OAI: diva2:463533
4th International Symposium on stochastic algorithms: foundations and applications (SAGA 2007), Zurich, Switzerland, September 13-14, 2007
Swiss National Science Foundation grant 200021-107327/1
QC 20120111Available from: 2012-01-11 Created: 2011-12-09 Last updated: 2012-01-11Bibliographically approved

Open Access in DiVA

fulltext(192 kB)120 downloads
File information
File name FULLTEXT01.pdfFile size 192 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full

Search in DiVA

By author/editor
Mömke, Tobias
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 120 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 22 hits
ReferencesLink to record
Permanent link

Direct link