Multidimensional trees and a Chomsky–Schützenberger–Weir representation theorem for simple context-free tree grammars
Makoto Kanazawa · Journal of Logic and Computation · 2014
Weir [ 43 ] proved a Chomsky–Schützenberger-like representation theorem for the string languages of tree-adjoining grammars, where the Dyck language D n in the Chomsky–Schützenberger characterization is replaced by the intersection D 2 n ∩ g −1( D 2 n ), where g is a certain bijection on the alphabet consisting of 2 n 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.