Pebble automaton

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 tape cells functions for which the nondeterministic machine required \log n tape cells), with the implication that a pebble adds power to Turing machines whose functions require space between \log\log n and \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, \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 DPA_{n} (resp. PA_{n}). We also define DPA = \bigcup_{n} DPA_{n} and likewise 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 TWA \subsetneq DPA or these classes are incomparable, which is an open problem
• PA \subsetneq REG, i.e. tree-walking automata augmented with pebbles are strictly weaker than branching automata
• it is not known whether 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 PA_{n} \subsetneq PA_{n+1} and DPA_{n} \subsetneq DPA_{n+1}

Automata and logic

Tree-walking pebble automata admit an interesting logical characterization. Let FO+TC denote the set of tree properties describable in transitive closure first-order logic, and 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 PA \subseteq FO+TC and, in fact, PA = FO+\text{pos},TC - the languages recognized by tree-walking pebble automata are exactly those expressible in positive transitive closure logic.

References

References

1. (November 1986). "On Pebble Automata". Theoretical Computer Science.
2. (26 April 2007). "Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure". Logical Methods in Computer Science.