Commutation-Augmented Pregroup Grammars and Mildly Context-Sensitive Languages

The paper presents a generalization of pregroup, by which a freely-generated pregroup is augmented with a finite set of commuting inequations, allowing limited commutativity and cancelability. It is shown that grammars based on the commutation-augmented pregroups generate mildly context- sensitive l...

Full description

Saved in:
Bibliographic Details
Published in:Studia logica 2007-12, Vol.87 (2/3), p.295-321
Main Authors: Francez, N., Kaminski, M.
Format: Article
Language:English
Subjects:
Alphabets
Automata
Commuting
Computational linguistics
Derivational morphology
Grammar
Language
Linguistics
Logical proofs
Polynomials
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The paper presents a generalization of pregroup, by which a freely-generated pregroup is augmented with a finite set of commuting inequations, allowing limited commutativity and cancelability. It is shown that grammars based on the commutation-augmented pregroups generate mildly context- sensitive languages. A version of Lambek's switching lemma is established for these pregroups. Polynomial parsability and semilinearity are shown for languages generated by these grammars.
ISSN:0039-3215
1572-8730
DOI:10.1007/s11225-007-9088-z