Commutation-Augmented Pregroup Grammars and Mildly Context-Sensitive Languages

&
Studia Logica 87 (2-3):295-321 (2007)
  Copy   BIBTEX

Abstract

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.

Categories

Keywords

Reprint years

DOI

10.1007/s11225-007-9088-z

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,139

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Extended Pregroup Grammars Applied to Natural Languages.Aleksandra Kiślak-Malinowska - 2012 - Logic and Logical Philosophy 21 (3):229-252.
Highly constrained unification grammars.Daniel Feinstein & Shuly Wintner - 2008 - Journal of Logic, Language and Information 17 (3):345-381.
Contexts and the Concept of Mild Context-Sensitivity.M. Kudlek, C. Martín-Vide, A. Mateescu & V. Mitrana - 2003 - Linguistics and Philosophy 26 (6):703 - 725.
On the Effect of the IO-Substitution on the Parikh Image of Semilinear Full AFLs.Pierre Bourreau - 2015 - Journal of Logic, Language and Information 24 (1):1-26.
Pregroup Grammars and Chomsky’s Earliest Examples.J. Lambek - 2008 - Journal of Logic, Language and Information 17 (2):141-160.
Global index grammars and descriptive power.José M. Castaño - 2004 - Journal of Logic, Language and Information 13 (4):403-419.
Two Models of Minimalist, Incremental Syntactic Analysis.Edward P. Stabler - 2013 - Topics in Cognitive Science 5 (3):611-633.
Sequentially indexed grammars.Jan van Eijck - unknown
Second-order abstract categorial grammars as hyperedge replacement grammars.Makoto Kanazawa - 2010 - Journal of Logic, Language and Information 19 (2):137-161.
Toward discourse representation via pregroup grammars.Anne Preller - 2007 - Journal of Logic, Language and Information 16 (2):173-194.
The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-free Tree Grammars.Stephan Kepser & Jim Rogers - 2011 - Journal of Logic, Language and Information 20 (3):361-384.
Semantic Vector Models and Functional Models for Pregroup Grammars.Anne Preller & Mehrnoosh Sadrzadeh - 2011 - Journal of Logic, Language and Information 20 (4):419-443.
Exploring feature agreement in French with parallel pregroup computations.Joachim Lambek - 2010 - Journal of Logic, Language and Information 19 (1):75-88.
Lexicalized Non-Local MCTAG with Dominance Links is NP-Complete.Lucas Champollion - 2011 - Journal of Logic, Language and Information 20 (3):343-359.
On the expressive power of abstract categorial grammars: Representing context-free formalisms. [REVIEW]Philippe de Groote & Sylvain Pogodalla - 2004 - Journal of Logic, Language and Information 13 (4):421-438.

Analytics

Added to PP
2009-01-28

Downloads
47 (#316,329)

6 months
6 (#349,140)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Nissim Francez
Technion, Israel Institute of Technology

Citations of this work

Logic and Grammar.Joachim Lambek - 2012 - Studia Logica 100 (4):667-681.
Type Logics and Pregroups.Wojciech Buszkowski - 2007 - Studia Logica 87 (2-3):145-169.

Add more citations

References found in this work

Elements of the Theory of Computation.Harry R. Lewis & Christos H. Papadimitriou - 1984 - Journal of Symbolic Logic 49 (3):989-990.

Add more references