Change search
ReferencesLink to record
Permanent link

Direct link
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, 455-466 p.Conference 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, 455-466 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 5257
Keyword [en]
automata theory, size complexity, exponential gap
National Category
Computer Science
URN: urn:nbn:se:kth:diva-52377DOI: 10.1007/978-3-540-85780-8_36ISI: 000260092300036ISBN: 978-3-540-85779-2OAI: diva2:466338
12th International Conference on Developments in Language Theory, Kyoto Sangyo Univ, Kyoto, JAPAN, SEP 16-19, 2008
Swiss National Science Foundation grant 200021-107327/1
QC 20111216Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2011-12-16Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Mömke, Tobias
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
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: 10 hits
ReferencesLink to record
Permanent link

Direct link