Polynomial Pregroup Grammars parse Context Sensitive Languages - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2009

Polynomial Pregroup Grammars parse Context Sensitive Languages

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.
Fichier principal
Vignette du fichier
PregrougGrammarsContextSensitiveLanguages.pdf (381.37 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00412876 , version 1 (02-09-2009)

Identifiers

  • HAL Id : lirmm-00412876 , version 1

Cite

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

Share

Gmail Mastodon Facebook X LinkedIn More