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