Size complexity of rotating and sweeping automata

• DOI: 10.1016/j.jcss.2011.06.004
• Publication Date: 2011-07-05T05:51:18Z
• Authors: Christos Kapoutsis; Richard Královič; Tobias Mömke
• Keywords: Succinctness; Nondeterministic algorithm; Closure (psychology); Deterministic finite automaton; ω-automaton

AbstractWe examine the succinctness of one-way, rotating, sweeping, and two-way deterministic finite automata (1DFAs, RDFAs, SDFAs, 2DFAs) and their nondeterministic and randomized counterparts. Here, a SDFA is a 2DFA whose head can change direction only on the end-markers 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 defined 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 (1Δ, RΔ, SΔ) 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 finite automata. Among other results, it implies that Las Vegas sweeping automata can be exponentially more succinct than SDFAs. We introduce a list of language operators and study the corresponding closure properties of the size complexity classes defined 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.