Skip to Main content Skip to Navigation
Journal articles

Polynomial Pregroup Grammars parse Context Sensitive Languages

Anne Preller 1
1 TEXTE - Exploration et exploitation de données textuelles
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Pregroup grammars with a possibly infinite number of lexi- cal entries are polynomial if the length of type assignments for sentences is a polynomial in the number of words. Polynomial pregroup grammars are shown to generate the standard mildly context sensitive formal languages as well as some context sensi- tive natural language fragments of Dutch, Swiss-German or Old Georgian. A polynomial recognition and parsing algorithm han- dles the various grammars uniformly. It also computes a planar graph for the semantic cross-serial dependencies in the case of natural languages.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Anne Preller <>
Submitted on : Monday, November 22, 2010 - 5:38:52 PM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM
Long-term archiving on: : Friday, October 26, 2012 - 4:22:10 PM


Files produced by the author(s)


  • HAL Id : lirmm-00538562, version 1



Anne Preller. Polynomial Pregroup Grammars parse Context Sensitive Languages. Linguistic Analysis, David R. Willingham, 2010, 36 (Lambek Festschrift), pp.483-516. ⟨lirmm-00538562⟩



Record views


Files downloads