Preprint 2014-15
Anahi Gajardo, Camilo Lacalle:
Revisiting of 2-pebble automata from a dynamical approach
Abstract:
Pebble automata are at an intermediate point between finite automata, which can only read, and Turing machines: pebble automata cannot write but mark the tape with pebbles, of which they have a finite amount. On the square grid Z^2, their ability to recognise figures and exiting labyrinths has been considered. Also, their ability to explore the empty space was studied. Their power depends strongly on the number of available pebbles. Here we put our attention on 2-pebble machines with 1 symbol, and we take the symbolic dynamics point of view by studying its trace subshift, i.e., the set of sequences of
