Product-Free Lambek Calculus Is NP-Complete
From MaRDI portal
Publication:3605542
DOI10.1007/978-3-540-92687-0_26zbMath1211.03041OpenAlexW1849857826MaRDI QIDQ3605542
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
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
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