Undecidability of the Lambek calculus with subexponential and bracket modalities

DOI10.1007/978-3-662-55751-8_26MaRDI QIDQ1679987zbMATH OpenOpenAlexFDO

Authors Stepan Kuznetsov, Max Kanovich, Andre Scedrov

Publication date 22 November 2017

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

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)

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.

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

Cited in

(12)

• Subexponentials in non-commutative linear logic
• Parsing/theorem-proving for logical grammar \textit{CatLog3}
• scientific article; zbMATH DE number 1984520 (Why is no real title available?)
• Bracket induction for Lambek calculus with bracket modalities
• Versions of a local contraction subexponential in the Lambek calculus
• 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)