Undecidability of the Lambek calculus with subexponential and bracket modalities

DOI10.1007/978-3-662-55751-8_26zbMATH Open1495.03036arXiv1608.04020OpenAlexW2962744611MaRDI QIDQ1679987FDOQ1679987

Authors: Stepan Kuznetsov, Max Kanovich, Andre Scedrov 

Publication date: 22 November 2017

Abstract: The Lambek calculus is a well-known logical formalism for modelling natural language syntax. The original calculus covered a substantial number of intricate natural language phenomena, but only those restricted to the context-free setting. In order to address more subtle linguistic issues, the Lambek calculus has been extended in various ways. In particular, Morrill and Valentin (2015) introduce an extension with so-called exponential and bracket modalities. Their extension is based on a non-standard contraction rule for the exponential that interacts with the bracket structure in an intricate way. The standard contraction rule is not admissible in this calculus. In this paper we prove undecidability of the derivability problem in their calculus. We also investigate restricted decidable fragments considered by Morrill and Valentin and we show that these fragments belong to the NP class.

Full work available at URL: https://arxiv.org/abs/1608.04020

Recommendations

• Undecidability of the Lambek calculus with a relevant modality
• Complexity of Lambek calculi with modalities and of total derivability in grammars
• On Lambek's restriction in the presence of exponential modalities
• Reconciling Lambek's restriction, cut-elimination and substitution in the presence of exponential modalities
• The multiplicative-additive Lambek calculus with subexponential and bracket modalities

Mathematics Subject Classification ID

Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47) Logic of natural languages (03B65) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (12)

• Subexponentials in non-commutative linear logic
• Parsing/theorem-proving for logical grammar \textit{CatLog3}
• Bracket induction for Lambek calculus with bracket modalities
• Versions of a local contraction subexponential in the Lambek calculus
• Title not available (Why is that?)
• Undecidability of the Lambek calculus with a relevant modality
• On Lambek's restriction in the presence of exponential modalities
• Reconciling Lambek's restriction, cut-elimination and substitution in the presence of exponential modalities
• The multiplicative-additive Lambek calculus with subexponential and bracket modalities
• Undecidability of a newly proposed calculus for CatLog3
• Undecidability of consequence relation in full non-associative Lambek calculus
• Complexity of Lambek calculi with modalities and of total derivability in grammars

This page was built for publication: Undecidability of the Lambek calculus with subexponential and bracket modalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679987)