Multidimensional trees and a Chomsky-Schützenberger-Weir representation theorem for simple context-free tree grammars.

Weir [43] proved a Chomsky-Schützenberger-like representation theorem for the string languages of tree-adjoining grammars, where the Dyck language Dn in the Chomsky-Schützenberger characterization is replaced by the intersection D2nng-1(D2n), where g is a certain bijection on the alphabet consisting of 2n pairs of brackets. This article presents a generalization of this theorem to the string 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-Schützenberger theorem to the tree languages of simple context-free tree grammars. I use Baldwin and Strawn's [2] notion of multidimensional trees to state this latter theorem in a very general, abstract form. [ABSTRACT FROM AUTHOR]