A Time to Cast Away Stones: On a Family of Pebble Automata
Olga Martynova, Alexander Okhotin · International Journal of Foundations of Computer Science · 2025
Deterministic graph-walking automata equipped with finitely many “drop-once” pebbles are investigated: these automata explore a graph by following its edges using finitely many states, and they can also leave pebbles at some nodes, but cannot lift these pebbles anymore. It is proved that for every such automaton there is a graph-walking automaton without pebbles that recognizes the same set of graphs. To be precise, for an automaton with m drop-once pebbles and n states, operating on graphs with k labels of edge end-points, an automaton without pebbles with [Formula: see text] states accepting the same set of graphs is constructed. The results apply to two-way finite automata (with [Formula: see text]) and to tree-walking automata as special cases.