A Characterization of ETOL Tree Languages by Cooperating Regular Tree Grammars.
Zoltán Fülöp, Sebastian Maneth · 1999
In this paper we show that the class of tree languages generated by ETOL tree systems is equal to the class of tree languages generated by distributed regular tree grammars cooperating with terminal strategy. 1 Introduction In theoretical computer science the classical theory of automata and formal languages was generalized to that of tree automata and tree languages. The base of this generalization is that an alphabet is generalized to a ranked alphabet, in which every symbol has a rank in the set of nonnegative integers. (An ordinary alphabet is considered as a ranked alphabet of which all symbols have rank 1.) Then, having a ranked alphabet, one can build up terms (called trees) from its symbols. A set of trees is called a tree language. Grammars generating tree languages are called tree grammars and automata recognizing tree languages are called tree automata. Devices that define transductions over trees, and thus generalize sequential machines, are called tree transducers. Regula...