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: 91,928

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

The Lambek calculus enriched with additional connectives.Makoto Kanazawa - 1992 - Journal of Logic, Language and Information 1 (2):141-171.
On reduction systems equivalent to the Lambek calculus with the empty string.Wojciech Zielonka - 2002 - Studia Logica 71 (1):31-46.
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.
Language-Theoretic and Finite Relation Models for the (Full) Lambek Calculus.Christian Wurm - 2017 - Journal of Logic, Language and Information 26 (2):179-214.
On the Complexity of Nonassociative Lambek Calculus with Unit.Maria Bulińska - 2009 - Studia Logica 93 (1):1-14.
A Labelled Deductive System for Relational Semantics of the Lambek Calculus.Miroslawa Kolowska-Gawiejnowicz - 1999 - Mathematical Logic Quarterly 45 (1):51-58.
A note on the Lambek-van Benthem calculus.Wojciech Buszkowski - 1984 - Bulletin of the Section of Logic 13 (1):31-35.
On the directional Lambek calculus.Wojciech Zielonka - 2010 - Logic Journal of the IGPL 18 (3):403-421.
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 Commutative and Nonassociative Syntactic Calculi and Categorial Grammars.Maciej Kandulski - 1995 - Mathematical Logic Quarterly 41 (2):217-235.
The finite model property for BCI and related systems.Wojciech Buszkowski - 1996 - Studia Logica 57 (2-3):303 - 323.
Two Weak Lambek-Style Calculi: DNL and DNL.Wojciech Zielonka - 2012 - Logic and Logical Philosophy 21 (1):53-64.
Cut-rule axiomatization of the syntactic calculus L.Wojciech Zielonka - 2001 - Journal of Logic, Language and Information 10 (2):339-352.
Full Lambek Calculus in natural deduction.Ernst Zimmermann - 2010 - Mathematical Logic Quarterly 56 (1):85-88.

Analytics

Added to PP
2018-05-15

Downloads
24 (#657,313)

6 months
13 (#194,670)

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