Undecidability of the Lambek Calculus with a Relevant Modality

DOI10.1007/978-3-662-53042-9_14zbMath1478.03043arXiv1601.06303OpenAlexW3100551312MaRDI QIDQ2835058

Stepan Kuznetsov, Andrej Scedrov, Max I. Kanovich

Publication date: 1 December 2016

Published in: Formal Grammar (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Related Items (9)

Versions of a local contraction subexponential in the Lambek calculus ⋮ Relational Models for the Lambek Calculus with Intersection and Constants ⋮ Unnamed Item ⋮ The multiplicative-additive Lambek calculus with subexponential and bracket modalities ⋮ Unnamed Item ⋮ Complexity of Lambek calculi with modalities and of total derivability in grammars ⋮ Subexponentials in non-commutative linear logic ⋮ Soft subexponentials and multiplexing ⋮ Non-associative, non-commutative multi-modal linear logic

Cites Work

• Unnamed Item
• Unnamed Item
• Linear logic
• On translating context-free grammars into Lambek grammars
• Decision problems for propositional linear logic
• Lambek calculus is NP-complete
• The Mathematics of Sentence Structure
• Quantales and (noncommutative) linear logic
• Lambek Grammars with One Division Are Decidable in Polynomial Time
• Product-Free Lambek Calculus Is NP-Complete
• Some Decision Problems in the Theory of Syntactic Categories
• Product-free Lambek calculus and context-free grammars
• On Lambek’s Restriction in the Presence of Exponential Modalities
• The String-Meaning Relations Definable by Lambek Grammars and Context-Free Grammars
• A comparison between lambek syntactic calculus and intuitionistic linear propositional logic

This page was built for publication: Undecidability of the Lambek Calculus with a Relevant Modality