Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
On the Size Complexity of Rotating and Sweeping Automata
ETH Zurich.
ETH Zurich.
ETH Zurich.
2008 (English)In: Developments in Language Theory, Proceedings / [ed] Ito, M; Toyama, M, Springer Berlin/Heidelberg, 2008, Vol. 5257, p. 455-466Conference paper, Published paper (Refereed)
Abstract [en]

We examine the succinctness of one-way, rotating, sweeping, and two-way deterministic finite automata (1dfas, rdfas, sdfas, 2dfas). Here, a sdfa is a 2dfa whose head can change direction only on the endmarkers and a rdfa is a sdfa whose head is reset on the left end of the input every time the right endmarker is read. We introduce a list of language operators and study the corresponding closure properties of the size complexity classes defined by these automata. Our conclusions reveal the logical structure of certain proofs of known separations in the hierarchy of these classes and allow us to systematically construct alternative problems to witness these separations.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2008. Vol. 5257, p. 455-466
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 5257
Keywords [en]
automata theory, size complexity, exponential gap
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-52377DOI: 10.1007/978-3-540-85780-8_36ISI: 000260092300036ISBN: 978-3-540-85779-2 (print)OAI: oai:DiVA.org:kth-52377DiVA, id: diva2:466338
Conference
12th International Conference on Developments in Language Theory, Kyoto Sangyo Univ, Kyoto, JAPAN, SEP 16-19, 2008
Projects
Swiss National Science Foundation grant 200021-107327/1
Note
QC 20111216Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2018-01-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Mömke, Tobias
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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