Skip to Main content Skip to Navigation
Reports

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 lexical 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 sensitive natural language fragments of Dutch, Swiss-German or Old Georgian. A polynomial recognition and parsing algorithm handles 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 metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00412876
Contributor : Anne Preller <>
Submitted on : Wednesday, September 2, 2009 - 3:39:43 PM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM
Long-term archiving on: : Tuesday, June 15, 2010 - 11:05:45 PM

File

PregrougGrammarsContextSensiti...
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00412876, version 1

Collections

Citation

Anne Preller. Polynomial Pregroup Grammars parse Context Sensitive Languages. RR-09024, 2009, pp.1-26. ⟨lirmm-00412876⟩

Share

Metrics

Record views

209

Files downloads

168