In computer science, a pebble automaton is any variant of an automaton which augments the original model with a finite number of "pebbles" that may be used to mark tape positions.
Pebble automata were introduced in 1986, when it was shown that in some cases, a deterministic transducer augmented with a pebble could achieve logarithmic space savings over even a nondeterministic log-space transducer (ie, compute in
tape cells functions for which the nondeterministic machine required
tape cells), with the implication that a pebble adds power to Turing machines whose functions require space between
[1] Constructions were also shown to convert a hierarchy of increasingly powerful stack machine models into equivalent deterministic finite automata with up to 3 pebbles, showing additional pebbles further increased power.
A tree-walking automaton with nested pebbles is a tree-walking automaton with an additional finite set of fixed size containing pebbles, identified with
Besides ordinary actions, an automaton can put a pebble at a currently visited node, lift a pebble from the currently visited node and perform a test "is the i-th pebble present at the current node?".
Without this restriction, the automaton has undecidable emptiness and expressive power beyond regular tree languages.
nondeterministic) tree-walking automata with n pebbles is denoted
Tree-walking pebble automata admit an interesting logical characterization.
denote the set of tree properties describable in transitive closure first-order logic, and
- the languages recognized by tree-walking pebble automata are exactly those expressible in positive transitive closure logic.