Review of Symbolic Logic:1-27 (forthcoming)

Abstract
We consider the Lambek calculus, or noncommutative multiplicative intuitionistic linear logic, extended with iteration, or Kleene star, axiomatised by means of an $\omega $ -rule, and prove that the derivability problem in this calculus is $\Pi _1^0$ -hard. This solves a problem left open by Buszkowski, who obtained the same complexity bound for infinitary action logic, which additionally includes additive conjunction and disjunction. As a by-product, we prove that any context-free language without the empty word can be generated by a Lambek grammar with unique type assignment, without Lambek’s nonemptiness restriction imposed.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/s1755020320000209
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 60,992
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Logics Without the Contraction Rule.Hiroakira Ono & Yuichi Komori - 1985 - Journal of Symbolic Logic 50 (1):169-201.
Some Decision Problems in the Theory of Syntactic Categories.Wojciech Buszkowski - 1982 - Mathematical Logic Quarterly 28 (33‐38):539-548.
Some Decision Problems in the Theory of Syntactic Categories.Wojciech Buszkowski - 1982 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 28 (33-38):539-548.

View all 11 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

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.
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.
Full Lambek Calculus in Natural Deduction.Ernst Zimmermann - 2010 - Mathematical Logic Quarterly 56 (1):85-88.
A Brief Survey of Frames for the Lambek Calculus.Kosta Došen - 1992 - Mathematical Logic Quarterly 38 (1):179-187.

Analytics

Added to PP index
2020-07-23

Total views
1 ( #1,481,938 of 2,439,423 )

Recent downloads (6 months)
1 ( #433,565 of 2,439,423 )

How can I increase my downloads?

Downloads

Sorry, there are not enough data points to plot this chart.

My notes