The restarting automaton, as defined in Sect. 1.9, works on linear text, that is, words, despite the fact that, in linguistics (as well as in formal language theory and its applications), trees are often used to describe sentences of a language together with some structural information on these sentences. We just mention the well-known syntax or derivation trees (see Sect. 1.2) and the dependency trees (see Sect. 1.6). Therefore, it is only natural to extend the notion of a restarting automaton from words to trees.