Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 4665
Keyword [en]
Sweeping automata, exponential gap, randomization
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-51153DOI: 10.1007/978-3-540-74871-7_12ISI: 000250543700011ISBN: 978-3-540-74870-0 (print)OAI: oai:DiVA.org:kth-51153DiVA: diva2:463533
Conference
4th International Symposium on stochastic algorithms: foundations and applications (SAGA 2007), Zurich, Switzerland, September 13-14, 2007
Projects
Swiss National Science Foundation grant 200021-107327/1
Note
QC 20120111Available from: 2012-01-11 Created: 2011-12-09 Last updated: 2012-01-11Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full textwww.Springerlink.com

Search in DiVA

By author/editor
Mömke, Tobias
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 134 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 37 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf