Pebble automaton explained

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

loglogn

tape cells functions for which the nondeterministic machine required

logn

tape cells), with the implication that a pebble adds power to Turing machines whose functions require space between

loglogn

and

logn.

[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.

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\}

. 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

DPAn

(resp.

PAn

). We also define

DPA=cupnDPAn

and likewise

PA=cupnPAn

.

Properties

TWA\subsetneqDPA

or these classes are incomparable, which is an open problem

PA\subsetneqREG

, i.e. tree-walking automata augmented with pebbles are strictly weaker than branching automata

DPA=PA

, i.e. whether tree-walking pebble automata can be determinized

PAn\subsetneqPAn+1

and

DPAn\subsetneqDPAn+1

Automata and logic

Tree-walking pebble automata admit an interesting logical characterization.[2] Let

FO+TC

denote the set of tree properties describable in transitive closure first-order logic, and

FO+posTC

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

PA\subseteqFO+TC

and, in fact,

PA=FO+posTC

- the languages recognized by tree-walking pebble automata are exactly those expressible in positive transitive closure logic.

See also

Notes and References

  1. Chang . Jik . Ibarra . Oscar . Palis . Michael . Ravikumar . B . On Pebble Automata . Theoretical Computer Science . November 1986 . 44 . 10.1016/0304-3975(86)90112-X. free .
  2. Engelfriet . Joost . Hoogeboom . Hendrik Jan . Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure . Logical Methods in Computer Science . 26 April 2007 . 3 . 2 . 10.2168/LMCS-3(2:3)2007. free . cs/0703079 .