A Technique for Proving Lower Bounds on the Size of Sweeping Automata
Hing Leung · Journal of automata, languages and combinatorics · 2009
A sweeping automaton is a two-way deterministic finite automaton which makes turns only at the endmarkers. Sipser [12] has proved that one-way nondeterministic finite automata can be exponentially more succinct in sizes than sweeping automata. In this paper, we propose a technique based on the work in [6] for establishing lower bounds on the size of sweeping automata. We show that Sipser's technique is a special case of our method. In addition, we prove two lower bound results with the new technique.