An Exponential Gap Between Las Vegas and Deterministic Sweeping Finite Automata

摘要

A two-way finite automaton is sweeping if its input head can change direction only on the end-markers. For each n ≥ 2, we exhibit a problem that can be solved by a O(n~2 )-state sweeping Las Vegas automaton, but needs 2~(Ω(n)) states on every sweeping deterministic automaton.