Pebbles

Abstract. Two-way finite state transducers are considered that use a finite number of pebbles, of which the life times must be nested. For every nondeterministic transducer that realizes a partial function, an equivalent deterministic transducer can be constructed. The composition of two deterministic transducers can be realized by one such transducer with a minimal number of pebbles.
doi:10.1007/s00236-015-0224-3 (open access)

(This improves some results of "Two-way Finite State Transducers with Nested Pebbles" MFCS'02, see below.)

Abstract. The pebble tree automaton and the pebble tree transducer are enhanced by additionally allowing an unbounded number of "invisible" pebbles (as opposed to the usual "visible" ones). The resulting pebble tree automata recognize the regular tree languages (i.e., can validate all generalized DTD's) and hence can find all matches of MSO definable patterns. Moreover, when viewed as a navigational device, they lead to an XPath-like formalism that has a path expression for every MSO definable binary pattern. The resulting pebble tree transducers can apply arbitrary MSO definable tests to (the observable part of) their configurations, they (still) have a decidable typechecking problem, and they can model the recursion mechanism of XSLT. The time complexity of the typechecking problem for conjunctive queries that use MSO definable patterns can often be reduced through the use of invisible pebbles.

Trees and Invisible Pebbles
AutoMathA, Liège, June 2009

Bart Samwel:
Pebble Scope and the Power of Pebble Tree Transducers,
M.Sc. Thesis (⇒ pdf-ed)

Tutorial on Tree Transducers (including invisible pebbles) Lausanne, CSL/GAMES, september 2007.

Extended abstract of the paper above.
Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2007, extended abstract) » doi:10.1145/1265530.1265540 (author pdf) 'best newcomer award'

Abstract. Tree-walking tree transducers can be typechecked in double exponential time. More generally, compositions of k tree-walking tree transducers can be typechecked in (k+1)-fold exponential time. Consequently k-pebble tree transducers, which form a model of XML transformations and XML queries, can be typechecked in (k+2)-fold exponential time. The results hold for both ranked and unranked trees.

(This is a detailed proof of Theorem 8 of the PODS paper above.)

Abstract. String languages recognizable in (deterministic) log-space are characterized either by two-way (deterministic) multi-head automata, or following Immerman, by first-order logic with (deterministic) transitive closure. Here we elaborate this result, and match the number of heads to the arity of the transitive closure. More precisely, first-order logic with k-ary deterministic transitive closure has the same power as deterministic automata walking on their input with k heads, additionally using a finite set of nested pebbles. This result is valid for strings, ordered trees, and in general for families of graphs having a fixed automaton that can be used to traverse the nodes of each of the graphs in the family. Examples of such families are grids, toruses, and rectangular mazes. For nondeterministic automata, the logic is restricted to positive occurrences of transitive closure.

presentation
Workshop on Tree Automata
(Bonn, june 2006)

Abstract. The n-pebble tree transducer was recently proposed as a model for XML query languages. The four main results on deterministic transducers are: First, (1) the translation τ of an n-pebble tree transducer can be realized by a composition of n+1 0-pebble tree transducers. Next, the pebble tree transducer is compared with the macro tree transducer, a well-known model for syntax-directed semantics, with decidable type checking. The 0-pebble tree transducer can be simulated by the macro tree transducer, which, by the first result, implies that (2) τ can be realized by an (n+1)-fold composition of macro tree transducers. Conversely, every macro tree transducer can be simulated by a composition of 0-pebble tree transducers. Together these simulations prove that (3) the composition closure of n-pebble tree transducers equals that of macro tree transducers (and that of 0-pebble tree transducers). Similar results hold in the nondeterministic case. Finally, (4) the output languages of deterministic n-pebble tree transducers form a hierarchy with respect to the number n of pebbles.

Abstract. Two-way finite state transducers are considered with a fixed number of pebbles, of which the life times are nested. In the deterministic case, the transductions computed by such pebble transducers are closed under composition, and they can be realized by the composition of one-pebble transducers. The ranges of the k-pebble transducers form a hierarchy with respect to k, their finiteness problem is decidable, and they can be generated by compositions of k macro tree transducers. Related results hold in the nondeterministic case.

Summary. The tree languages accepted by (finite state) tree-walking automata are known to form a subclass of the regular tree languages which is not known to be proper. They include all locally first-order definable tree languages. We allow the tree-walking automaton to use a finite number of pebbles, which have to be dropped and lifted in a nested fashion. The class of tree languages accepted by these treewalking pebble automata contains all first-order definable tree languages and is still included in the class of regular tree languages. It also contains all deterministic top-down recognizable tree languages.

Abstract. A "trip" is a triple (g; u; v) where g is, in general, a graph and u and v are nodes of that graph. The trip is from u to v on the graph g. For the special case that g is a tree (or even a string) we investigate ways of specifying and implementing sets of trips. The main result is that a regular set of trips, specified as a regular tree language, can be implemented by a tree-walking automaton that uses marbles and one pebble.