Change search
ReferencesLink to record
Permanent link

Direct link
Size complexity of rotating and sweeping automata
ETH Zurich.
ETH Zurich.
ETH Zurich.
2012 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 78, no 2, 537-558 p.Article in journal (Refereed) Published
Abstract [en]

We examine the succinctness of one-way, rotating, sweeping, and two-way deterministic nite automata ( 1dfas, rdfas, sdfas, 2dfa s) and their nondeterministic and randomized counterparts. 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 to the left end of the input every time the right end-marker is read. We study the size complexity classes de ned by these automata, i. e., the classes of problems solvable by small automata of certain type. For any pair of classes of one-way, rotating, and sweeping deterministic ( 1d, rd, sd ), self-verifying ( 1D, rD, sD) and nondeterministic (1n, rn, sn ) automata, as well as for their complements and reversals, we show that they are equal, incomparable, or one is strictly included in the other. The provided map of the complexity classes has interesting implications on the power of randomization for nite automata. Among other results, it implies that LasVegas sweeping automata can be exponentially more succinct than sdfa s. We introduce a list of language operators and study the corresponding closure properties of the size complexity classes de ned by these automata as well. Our conclusions reveal also the logical structure of certain proofs of known separations among the complexity classes and allow us to systematically construct alternative witnesses of these separations.

Place, publisher, year, edition, pages
2012. Vol. 78, no 2, 537-558 p.
Keyword [en]
Finite automata, Sweeping automata, Size complexity, Self-verification, Randomization, Hardness propagation
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-60836DOI: 10.1016/j.jcss.2011.06.004ISI: 000299719100010OAI: diva2:478004

QC 20130213

Available from: 2012-01-15 Created: 2012-01-15 Last updated: 2013-02-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Mömke, Tobias
In the same journal
Journal of computer and system sciences (Print)
Computer and Information 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: 16 hits
ReferencesLink to record
Permanent link

Direct link