Product-Free Lambek Calculus Is NP-Complete

DOI10.1007/978-3-540-92687-0_26zbMath1211.03041OpenAlexW1849857826MaRDI QIDQ3605542

Yury Savateev

Publication date: 24 February 2009

Published in: Logical Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92687-0_26

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47)

Related Items (8)

On Lambek’s Restriction in the Presence of Exponential Modalities ⋮ Logical foundations for hybrid type-logical grammars ⋮ Towards NP-P via proof complexity and search ⋮ Natural language semantics and computability ⋮ On translating context-free grammars into Lambek grammars ⋮ L-Completeness of the Lambek Calculus with the Reversal Operation Allowing Empty Antecedents ⋮ The Monotone Lambek Calculus Is NP-Complete ⋮ Undecidability of the Lambek Calculus with a Relevant Modality

Cites Work

• Unnamed Item
• Lambek calculus is NP-complete
• The Mathematics of Sentence Structure
• Lambek Grammars with One Division Are Decidable in Polynomial Time
• Non‐associative Lambek Categorial Grammar in Polynomial Time
• The Equivalence of Unidirectional Lambek Categorial Grammars and Context‐Free Grammars

This page was built for publication: Product-Free Lambek Calculus Is NP-Complete