Multi-Bracketed Contextual Rewriting Grammars

Article type: Research Article

Authors: Kappes, Martin

Affiliations: Fachbereich Informatik, Johann Wolfgang Goethe-Universität, D - 60054 Frankfurt am Main, Germany. [email protected]

Note: [] Address for corresponednec: Fachbereich Informatik, Johann Wolfgang Goethe-Universität, D - 60054 Frankfurt am Main, Germany

Abstract: We study the generative capacity of multi-bracketed contextual rewriting grammars. This model is a generalization of multi-bracketed contextual grammars, which were studied in [Kap98a]. They possess an induced Dyck-structure to control the derivation process and to provide derivation trees. The generative capacity of this class is investigated and compared to Chomsky grammars and to tree adjoining grammars with local constraints. It will be shown that this class of grammars covers the basic natural language constructions such as duplication, multiple agreement and crossed-serial dependencies. Furthermore, two natural variants of the derivation relation, namely top-down and bottom-up derivation modes are examined.

Keywords: Contextual Grammars, Tree Adjoining Grammars, Multi-Bracketed Contextual Grammars

DOI: 10.3233/FI-1999-38302

Journal: Fundamenta Informaticae, vol. 38, no. 3, pp. 257-280, 1999