Size complexity of rotating and sweeping automata
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
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.
Finite automata, Sweeping automata, Size complexity, Self-verification, Randomization, Hardness propagation
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-60836DOI: 10.1016/j.jcss.2011.06.004ISI: 000299719100010OAI: oai:DiVA.org:kth-60836DiVA: diva2:478004
QC 201302132012-01-152012-01-152013-02-13Bibliographically approved