Product-Free Lambek Calculus Is NP-Complete

DOI10.1007/978-3-540-92687-0_26zbMath1211.03041MaRDI 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

03B25: Decidability of theories and sets of sentences

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03B47: Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)

Related Items

On Lambek’s Restriction in the Presence of Exponential Modalities, L-Completeness of the Lambek Calculus with the Reversal Operation Allowing Empty Antecedents, The Monotone Lambek Calculus Is NP-Complete, Towards NP-P via proof complexity and search, On translating context-free grammars into Lambek grammars, Logical foundations for hybrid type-logical grammars, Natural language semantics and computability, 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