Tree walking automata were introduced during the 70s as a model for describing regular languages of trees [AU77]. The run of such an automaton, instead of being a tree as for standard tree automata, form a path in the input tree. At each step of the run, the (unique) head of the automato is located in some node, and based on the current configuration of the tree and the current state of the automaton goes to one of the children of the current node, or go to the parent of the current node, and changes of states. Iterating this process, the automaton walks a path in the tree, possibly ending accepting the input tree. Tree walking automata are easy to show to define regular languages of finite trees.

In this talk, we will cover several subjects related to tree walking automata, including, the separation properties (deterministic tree walking automata are strictly weaker than non-deterministic ones [BC06], which in turn are strictly weaker than regular languages [BC08]) and closure properties (under complementation in particular [MSS06]). We will also present the models of pebble automata and relate it to first-order logic with transitive closure [EH99]. We will conclude with the separation of this logic from monadic logic over finite trees [BSSS06,BS10].