On the Relationship Between Multiple Brackets and Selector Languages in Bracketed Contextual Grammars

Issue title: Contagious Creativity – In Honor of the 80th Birthday of Professor Solomon Marcus

Article type: Research Article

Authors: Kappes, Martin

Affiliations: DoCoMo Eurolabs, Landsberger Strasse 312, 80687 Munich, Germany. kappes@docomolab-euro.com

Note: [] Address for correspondence: DoCoMo Eurolabs, Landsberger Strasse 312, 80687 Munich, Germany

Abstract: Bracketed contextual grammars are a variant of Marcus' contextual grammars with an induced Dyck-structure to control the derivation process and to provide derivation trees. Many variants of bracketed contextual grammars have been proposed in literature. In this paper, we study the relationship between various mechanisms in such grammars, in particular the number of brackets, the used selector languages, and the ability to introduce more than a single pair of brackets in a derivation step, with respect to the generative capacity of the resulting models.

Keywords: Contextual grammars, bracketed contextual grammars

Journal: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 229-239, 2005