Term graphs and the NP-completeness of the product-free Lambek calculus

DOI10.1007/978-3-642-20169-1_10zbMATH Open1231.03019OpenAlexW1545349388MaRDI QIDQ2999263FDOQ2999263

Authors: Timothy A. D. Fowler 

Publication date: 11 May 2011

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

Full work available at URL: https://doi.org/10.1007/978-3-642-20169-1_10

Recommendations

• LC graphs for the Lambek calculus with product
• Product-Free Lambek Calculus Is NP-Complete
• The product-free Lambek-Grishin calculus is NP-complete
• The monotone Lambek calculus is NP-complete
• Lambek calculus is NP-complete

Mathematics Subject Classification ID

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) Structure of proofs (03F07) Complexity of proofs (03F20)

Cited In (4)

• LC graphs for the Lambek calculus with product
• The product-free Lambek-Grishin calculus is NP-complete
• Non-perturbative graph languages, halting problem and complexity
• Product-Free Lambek Calculus Is NP-Complete

This page was built for publication: Term graphs and the NP-completeness of the product-free Lambek calculus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2999263)