What question did this study set out to answer?

The aim is to generalize the Chomsky-Schützenberger theorem to simple context-free tree grammars.

April 1, 2026Open Access

NII Technical Report (NII-2013-003E)：Multi-dimensional Trees and a Chomsky-Schützenberger-Weir Representation Theorem for Simple Context-Free Tree Grammars

Key Points

The aim is to generalize the Chomsky-Schützenberger theorem to simple context-free tree grammars.
Utilized the concept of multi-dimensional trees by James Rogers
Extended the original theorem to encompass a broader class of tree languages
Formulated the theorem in an abstract manner
Established a generalized representation theorem for simple context-free tree grammars
Demonstrated that this generalization aligns with the existing framework of tree-adjoining grammars

Abstract

David J. Weir proved a Chomsky-Schützenberger-like representation theorem for the string languages of tree-adjoining grammars. This paper presents a generalization of this theorem to the string languages of 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. We use James Rogers's notion of multi-dimensional trees to state this latter theorem in a very general, abstract form.

Bookmark

View Full Paper