Multidimensional trees and a Chomsky Schutzenberger Weir representation theorem for simple context free tree grammars
Weir [34] proved a Chomsky Schutzenberger like representation theorem for the string languages of tree adjoining grammars, where the Dyck language Dn in the Chomsky Schutzenberger characterization is replaced by the intersection D2n g(D2n) where g is a certain bijection on the alphabet consisting of 2n pairs of brackets. This paper presents a generalization of this theorem to the string languages that are the yield images of the tree languages generated by simple (i.e. linear and non deleting) context free tree grammars. This result is obtained through a natural generalization of the original Chomsky Schutzenberger theorem to the tree languages of simple context free tree grammars. We use Rogers's [24,23] notion of multi dimensional trees to state this latter theorem in a very general, abstract form.
J. Log. Comput.