Lambek Grammars, Tree Adjoining Grammars and Hyperedge Replacement Grammars

Richard Moot (1, 2)

1 SIGNES - Linguistic signs, grammar and meaning: computational logic for natural language
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Two recent extension of the non-associative Lambek calculus, the Lambek-Grishin calculus and the multimodal Lambek calculus, are shown to generate the same class of languages as tree adjoining grammars, using (tree generating) hyperedge replacement grammars as an intermediate step. As a consequence both extensions are mildly context-sensitive formalisms and benefit from polynomial parsing algorithms.

Domaines: Informatique et langage [cs.CL]

Richard Moot. Lambek Grammars, Tree Adjoining Grammars and Hyperedge Replacement Grammars. Ninth International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+ 9), 2008, Tübingen, Germany. pp.1-8. ⟨hal-00278794⟩