Stack of Pebbles

Pebbles

Leiden papers on automata with pebbles, together with HJHs talks on the subject.
Joost Engelfriet
Hendrik Jan Hoogeboom

  Mikołaj Bojańczyk (Warsaw) has written a survey on Tree-Walking Automata as invited speaker to LATA 2008. The main focus is on how the expressive power is changed by adding features such as pebbles or nondeterminism.

Joost Engelfriet.
Two-Way Pebble Transducers for Partial Functions and their Composition.
Acta Informatica, March 2015.

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


presentation
PODS Beijing, June 2007

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)

Bart in China

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

Joost Engelfriet, Hendrik Jan Hoogeboom and Bart Samwel.
XML Transformation by Tree-Walking Transducers with Invisible Pebbles.

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

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 n-ary 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 congurations, 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 binary patterns can often be reduced through the use of invisible pebbles.


J. Engelfriet.
The Complexity of Typechecking Tree-Walking Tree Transducers,
Acta Informatica 46 (2009) 139-154, doi: 10.1007/s00236-008-0087-y. Author copy ps-file (⇒ pdf-ed)

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


presentation
(Aachen, june 2005)


J. Engelfriet, H.J. Hoogeboom.
Automata with Nested Pebbles Capture
First-Order Logic with Transitive Closure.

Published in LMCS (Logical Methods in Computer Science), a fully refereed, open access, free, electronic journal. Volume 3, Issue 2, Paper 3. pdf
doi: 10.2168/LMCS-3(2:3)2007

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.

single head on trees The special case of k=1 for trees, shows that single-head deterministic tree-walking automata with nested pebbles are characterized by first-order logic with unary deterministic transitive closure. This refines our earlier result that placed these automata between first-order and second-order logic on trees.
presentation
STACS Marseille, Feb 2006

presentation
Workshop on Tree Automata
(Bonn, june 2006)

Workshop on Tree Automata

J. Engelfriet, H.J. Hoogeboom.
Nested Pebbles and Transitive Closure.

Extended abstract of the paper above.
Presented at STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, february 23-25, 2006.
Lecture Notes in Computer Science 3884, B. Durand, W. Thomas (Eds.), pages 477-488, 2006. doi:10.1007/11672142_39

Abstract. First-order logic with k-ary deterministic transitive closure has the same power as two-way k-head deterministic automata that use a finite set of nested pebbles. This result is valid for strings, ranked 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. Other examples of such families are grids, toruses, and rectangular mazes.

 

  from a lecture by Sebastian J. Engelfriet, S. Maneth.
A Comparison of Pebble Tree Transducers with Macro Tree Transducers.
Acta Informatica 39 (2003) 613-698. doi:10.1007/s00236-003-0120-0

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.


  J. Engelfriet, S. Maneth.
Two-way Finite State Transducers with Nested Pebbles.
In: Proceedings MFCS'02 (K. Diks, W. Rytter, eds.), Lecture Notes in Computer Science, v. 2420, 234-244, 2002.

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.


  Pebbles Flintstone (c) Hannah & Barbara J. Engelfriet, H.J. Hoogeboom.
Tree-Walking Pebble Automata.
In: Jewels are forever, contributions to Theoretical Computer Science in honor of Arto Salomaa (J. Karhumäki, H. Maurer, G. Paun, G. Rozenberg, eds.), Springer Verlag, 72-83, 1999.
ps-file (gzipped) (⇒ pdf-ed).

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.



J. Engelfriet, H.J. Hoogeboom, J.-P. van Best.
Trips on Trees.
Acta Cybernetica 14 (1999) 51-64. (special issue on the occasion of the 60th birthday of Prof. F. Gécseg)
pdf (local copy).

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.

up up2