Chapter 7: Pattern Recognition Based on Tree Languages

Whereas the theory of string languages has been developed mainly for applications in the areas of programming languages and compiler design, tree grammars and automata were introduced in the mid 1960s for solving decidability problems within second order logic [Doner (1965); Thatcher and Wright (1968)]. A tree grammar is generalization of a string grammar, i.e. its left- and right-hand sides are trees. Regular tree grammars were introduced in [Brainerd (1969)] Their left-hand sides consist of one-node trees labelled with nonterminal symbols…