NII Technical Report (NII-2013-003E):Multi-dimensional Trees and a Chomsky-Schützenberger-Weir Representation Theorem for Simple Context-Free Tree Grammars
Makoto Kanazawa · Institutional Repositories DataBase (IRDB) · 2013
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
Institutional Repositories DataBase (IRDB) · National Institute of Informatics · article · 2013
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.
Open the resolved locator · 10.20736/0000001273
Metadata licence: OpenAlex metadata (CC0)