
PebblesLeiden papers on automata with pebbles, together with HJHs talks on the subject. 
Mikołaj Bojańczyk (Warsaw) has written a survey on TreeWalking 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.
TwoWay Pebble Transducers for Partial Functions and their Composition. Acta Informatica, March 2015.
Abstract.
Twoway 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.
(This improves some results of "Twoway Finite State Transducers with Nested Pebbles" MFCS'02, see below.) 

presentation
PODS Beijing, June 2007
Trees and Invisible Pebbles
Bart Samwel: Tutorial on Tree Transducers (including invisible pebbles) Lausanne, CSL/GAMES, september 2007. 
Joost Engelfriet, Hendrik Jan Hoogeboom and Bart Samwel.
XML Transformation by TreeWalking Transducers with Invisible Pebbles.
Proceedings of the twentysixth ACM SIGMODSIGACTSIGART Symposium on
Principles of Database Systems
(PODS 2007)
'best newcomer award'
»
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 nary patterns. Moreover, when viewed as a navigational device, they lead to an XPathlike 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 TreeWalking Tree Transducers, Acta Informatica 46 (2009) 139154, doi: 10.1007/s002360080087y. Author copy psfile (⇒ pdfed) Abstract. Treewalking tree transducers can be typechecked in double exponential time. More generally, compositions of k treewalking tree transducers can be typechecked in (k+1)fold exponential time. Consequently kpebble 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 FirstOrder 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: Abstract. String languages recognizable in (deterministic) logspace are characterized either by twoway (deterministic) multihead automata, or following Immerman, by firstorder 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, firstorder logic with kary 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. 
The special case of k=1 for trees, shows that singlehead deterministic treewalking automata with nested pebbles are characterized by firstorder logic with unary deterministic transitive closure. This refines our earlier result that placed these automata between firstorder and secondorder logic on trees.  
presentation
STACS Marseille, Feb 2006
presentation

Nested Pebbles and Transitive Closure.
Extended abstract of the paper above.
Abstract. Firstorder logic with kary deterministic transitive closure has the same power as twoway khead 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. 
J. Engelfriet, S. Maneth.
A Comparison of Pebble Tree Transducers with Macro Tree Transducers. Acta Informatica 39 (2003) 613698. doi:10.1007/s0023600301200 Abstract. The npebble 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 npebble tree transducer can be realized by a composition of n+1 0pebble tree transducers. Next, the pebble tree transducer is compared with the macro tree transducer, a wellknown model for syntaxdirected semantics, with decidable type checking. The 0pebble 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 0pebble tree transducers. Together these simulations prove that (3) the composition closure of npebble tree transducers equals that of macro tree transducers (and that of 0pebble tree transducers). Similar results hold in the nondeterministic case. Finally, (4) the output languages of deterministic npebble tree transducers form a hierarchy with respect to the number n of pebbles. 

J. Engelfriet, S. Maneth.
Twoway Finite State Transducers with Nested Pebbles. In: Proceedings MFCS'02 (K. Diks, W. Rytter, eds.), Lecture Notes in Computer Science, v. 2420, 234244, 2002. Abstract. Twoway 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 onepebble transducers. The ranges of the kpebble 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. 

J. Engelfriet, H.J. Hoogeboom.
TreeWalking 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, 7283, 1999. psfile (gzipped) (⇒ pdfed). Summary. The tree languages accepted by (finite state) treewalking automata are known to form a subclass of the regular tree languages which is not known to be proper. They include all locally firstorder definable tree languages. We allow the treewalking 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 firstorder definable tree languages and is still included in the class of regular tree languages. It also contains all deterministic topdown recognizable tree languages. 


J. Engelfriet, H.J. Hoogeboom, J.P. van Best.
Trips on Trees. Acta Cybernetica 14 (1999) 5164. (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 treewalking automaton that uses marbles and one pebble. 
up up^{2} 