On the Size Complexity of Two-Way Finite Automata with Drop-Once Pebbles
Georgy Kipriyanov, Alexander Okhotin · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2026
A two-way finite automaton with drop-once pebbles (O. Martynova, A. Okhotin, "A time to cast away stones: On a family of pebble automata", IJFCS, 37 (2026)) may drop its pebbles at any squares of the tape, but a pebble once dropped cannot be moved anymore. In this paper, it is proved that transforming an n-state deterministic automaton with k drop-once pebbles to a standard two-way deterministic finite automaton (2DFA) requires Θ(n^{k+1}) states in the worst case. For nondeterministic two-way automata with one drop-once pebble, it is proved that transforming them to a 2DFA requires at least 2^{n/3-o(n)} states, transforming to a two-way nondeterministic automaton (2NFA) takes at least 2^{n/6-o(n)} states, and, finally, determinizing them to a deterministic two-way automaton with one drop-once pebble requires at least 2^{n/6-o(n)} states.