1-1hit |
As a generalization of the tree automaton, tree automata with various types of memory are introduced and their relation to context-free grammars with memory is studied. Relations between computation trees of tree automata with memory and derivation trees of context-free grammars with memory are established, and as a consequence, the languages generated by context-free grammars with memory are characterized in terms of the sets of trees recognizable by tree automata with memory. Also various types of traversal of labeled trees recognizable by tree automata with memory are considered.