On the Recognizing Power of the Lambek Calculus with Brackets

Journal of Logic, Language and Information 27 (4):295-312 (2018)
  Copy   BIBTEX

Abstract

Every language recognized by the Lambek calculus with brackets is context-free. This is shown by combining an observation by Jäger with an entirely straightforward adaptation of the method Pentus used for the original Lambek calculus. The case of the variant of the calculus allowing sequents with empty antecedents is slightly more complicated, requiring a restricted use of the multiplicative unit.

Categories

Keywords

Reprint years

DOI

10.1007/s10849-018-9269-3

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,296

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

Language-Theoretic and Finite Relation Models for the (Full) Lambek Calculus.Christian Wurm - 2017 - Journal of Logic, Language and Information 26 (2):179-214.
The Lambek calculus enriched with additional connectives.Makoto Kanazawa - 1992 - Journal of Logic, Language and Information 1 (2):141-171.
The Pentus Theorem for Lambek Calculus with Simple Nonlogical Axioms.Maria Bulińska - 2005 - Studia Logica 81 (1):43-59.
Product-free Lambek calculus and context-free grammars.Mati Pentus - 1997 - Journal of Symbolic Logic 62 (2):648-660.
A Labelled Deductive System for Relational Semantics of the Lambek Calculus.Miroslawa Kolowska-Gawiejnowicz - 1999 - Mathematical Logic Quarterly 45 (1):51-58.
On Commutative and Nonassociative Syntactic Calculi and Categorial Grammars.Maciej Kandulski - 1995 - Mathematical Logic Quarterly 41 (2):217-235.
Lambek calculus and its relational semantics: Completeness and incompleteness. [REVIEW]Hajnal Andréka & Szabolcs Mikulás - 1994 - Journal of Logic, Language and Information 3 (1):1-37.
On reduction systems equivalent to the Lambek calculus with the empty string.Wojciech Zielonka - 2002 - Studia Logica 71 (1):31-46.
Parsing Pregroup Grammars and Lambek Calculus Using Partial Composition.Denis Béchet - 2007 - Studia Logica 87 (2-3):199-224.
On the Complexity of Nonassociative Lambek Calculus with Unit.Maria Bulińska - 2009 - Studia Logica 93 (1):1-14.

Analytics

Added to PP
2018-05-15

Downloads
24 (#679,414)

6 months
13 (#219,908)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

The Mathematics of Sentence Structure.Joachim Lambek - 1958 - Journal of Symbolic Logic 65 (3):154-170.
Multimodal linguistic inference.Michael Moortgat - 1996 - Journal of Logic, Language and Information 5 (3-4):349-385.
Multimodal Linguistic Inference.Michael Moortgat - 1995 - Logic Journal of the IGPL 3 (2-3):371-401.
Product-free Lambek calculus and context-free grammars.Mati Pentus - 1997 - Journal of Symbolic Logic 62 (2):648-660.
Computing interpolants in implicational logics.Makoto Kanazawa - 2006 - Annals of Pure and Applied Logic 142 (1):125-201.

View all 6 references / Add more references