The Multiplicative-Additive Lambek Calculus with Subexponential and Bracket Modalities

Journal of Logic, Language and Information 30 (1):31-88 (2020)
  Copy   BIBTEX

Abstract

We give a proof-theoretic and algorithmic complexity analysis for systems introduced by Morrill to serve as the core of the CatLog categorial grammar parser. We consider two recent versions of Morrill’s calculi, and focus on their fragments including multiplicative connectives, additive conjunction and disjunction, brackets and bracket modalities, and the! subexponential modality. For both systems, we resolve issues connected with the cut rule and provide necessary modifications, after which we prove admissibility of cut. We also prove algorithmic undecidability for both calculi, and show that categorial grammars based on them can generate arbitrary recursively enumerable languages.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,442

External links

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

Through your library

Similar books and articles

On the Recognizing Power of the Lambek Calculus with Brackets.Makoto Kanazawa - 2018 - Journal of Logic, Language and Information 27 (4):295-312.
On Involutive Nonassociative Lambek Calculus.Wojciech Buszkowski - 2019 - Journal of Logic, Language and Information 28 (2):157-181.
The conjoinability relation in Lambek calculus and linear logic.Mati Pentus - 1994 - Journal of Logic, Language and Information 3 (2):121-140.
Dialectica Categories for the Lambek Calculus.Valeria Correa Vaz De Paiva & Harley Eades Iii - 2018 - In Proceedings of the Symposium on Logical Foundations of Computer Science (LFCS 2018). Deerfield Beach, FL, USA:
Lambek Calculus with Conjugates.Igor Sedlár & Andrew Tedder - 2020 - Studia Logica 109 (3):447-470.
The Lambek calculus enriched with additional connectives.Makoto Kanazawa - 1992 - Journal of Logic, Language and Information 1 (2):141-171.
A note on the Lambek-van Benthem calculus.Wojciech Buszkowski - 1984 - Bulletin of the Section of Logic 13 (1):31-35.
Linguistic applications of first order intuitionistic linear logic.Richard Moot & Mario Piazza - 2001 - Journal of Logic, Language and Information 10 (2):211-232.

Analytics

Added to PP
2020-10-22

Downloads
3 (#1,316,028)

6 months
1 (#454,876)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Untersuchungen über das logische Schließen. I.Gerhard Gentzen - 1935 - Mathematische Zeitschrift 35:176–210.
The Mathematics of Sentence Structure.Joachim Lambek - 1958 - Journal of Symbolic Logic 65 (3):154-170.
Evidence against the context-freeness of natural language.Stuart M. Shieber - 1985 - Linguistics and Philosophy 8 (3):333 - 343.

View all 26 references / Add more references