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.
History 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 log log n {\displaystyle \log \log n} tape cells functions for which the nondeterministic machine required log n {\displaystyle \log n} tape cells), with the implication that a pebble adds power to Turing machines whose functions require space between log log n {\displaystyle \log \log n} and log n . {\displaystyle \log n.} 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.
Tree-walking automata with nested pebbles A tree-walking automaton with nested pebbles is a tree-walking automaton with an additional finite set of fixed size containing pebbles, identified with { 1 , 2 , … , n } {\displaystyle \{1,2,\dots ,n\}} . 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?". There is an important stack restriction on the order in which pebbles can be put or lifted - the i+1-th pebble can be put only if the pebbles from 1st to i-th are already on the tree, and the i+1-th pebble can be lifted only if pebbles from i+2-th to n-th are not on the tree. Without this restriction, the automaton has undecidable emptiness and expressive power beyond regular tree languages. The class of languages recognized by deterministic (resp. nondeterministic) tree-walking automata with n pebbles is denoted D P A n {\displaystyle DPA_{n}} (resp. P A n {\displaystyle PA_{n}} ). We also define D P A = ⋃ n D P A n {\displaystyle DPA=\bigcup _{n}DPA_{n}} and likewise P A = ⋃ n P A n {\displaystyle PA=\bigcup _{n}PA_{n}} .
Properties there exists a language recognized by a tree-walking automaton with 1 pebble, but not by any ordinary tree walking automaton; this implies that either T W A ⊊ D P A {\displaystyle TWA\subsetneq DPA} or these classes are incomparable, which is an open problem
P A ⊊ R E G {\displaystyle PA\subsetneq REG} , i.e. tree-walking automata augmented with pebbles are strictly weaker than branching automata it is not known whether D P A = P A {\displaystyle DPA=PA} , i.e. whether tree-walking pebble automata can be determinized it is not known whether tree-walking pebble automata are closed under complementation the pebble hierarchy is strict for tree-walking automata, for every n P A n ⊊ P A n + 1 {\displaystyle PA_{n}\subsetneq PA_{n+1}} and D P A n ⊊ D P A n + 1 {\displaystyle DPA_{n}\subsetneq DPA_{n+1}}
Automata and logic Tree-walking pebble automata admit an interesting logical characterization. Let F O + T C {\displaystyle FO+TC} denote the set of tree properties describable in transitive closure first-order logic, and F O + pos T C {\displaystyle FO+{\text{pos}}\,TC} the same for positive transitive closure logic, i.e. a logic where the transitive closure operator is not used under the scope of negation. Then it can be proved that P A ⊆ F O + T C {\displaystyle PA\subseteq FO+TC} and, in fact, P A = F O + pos T C {\displaystyle PA=FO+{\text{pos}}\,TC} - the languages recognized by tree-walking pebble automata are exactly those expressible in positive transitive closure logic.
See also Tree walking automata Branching automata Transitive closure logic Pebble game
References
