ABSTRACT
The tree structure is one of themost basic and widespread data structure. Recent developmentsmotivated by XML languages (Bray et al., 2008) have raised new interest for trees. Trees are also a genuine structure formodeling systems runs, as for instanceprogramexecutions. Earlyworks on trees (Thatcher andWright, 1968; Doner, 1970) were motivated by algebraic properties of structures and decidability of related logics, as first investigated by Büchi on strings. Hopefully, many of the properties of regular (string) languages can be lifted to trees. A notion of tree automaton can be defined, which expressiveness is exactly captured bymonadic second-order formulas: such regular tree languages are closed under Boolean operations, tree automata can be minimized, and a pumping lemma can be applied.
