The monotone Lambek calculus is NP-complete

DOI10.1007/978-3-642-54789-8_20MaRDI QIDQ5414974zbMATH OpenOpenAlexFDO

Authors Mati Pentus

Publication date 8 May 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-54789-8_20

zbMATH Keywords

complexityLambek calculusstructural rule

Mathematics Subject Classification ID

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

Recommendations

• Lambek calculus is NP-complete
• Lambek calculus with a unit and one division
• Product-Free Lambek Calculus Is NP-Complete
• The product-free Lambek-Grishin calculus is NP-complete
• An application of proof-nets to the study of fragments of the Lambek calculus

Cites work

• Completeness Results for Lambek Syntactic Calculus
• Cut elimination and strong separation for substructural logics: an algebraic approach
• scientific article; zbMATH DE number 1222927 (Why is no real title available?)
• scientific article; zbMATH DE number 2070201 (Why is no real title available?)
• scientific article; zbMATH DE number 3231118 (Why is no real title available?)
• Language in action. Categories, lambdas and dynamic logic
• Product-Free Lambek Calculus Is NP-Complete
• The atomic theory of left division of two-sided ideals of semirings with unit
• The atomic theory of multiplication and division of semiring ideals
• The Mathematics of Sentence Structure

Cited in

(8)

• Lambek calculus is NP-complete
• Lambek calculus with a unit and one division
• Term graphs and the NP-completeness of the product-free Lambek calculus
• The product-free Lambek-Grishin calculus is NP-complete
• Product-Free Lambek Calculus Is NP-Complete
• LaserTank is NP-Complete
• An application of proof-nets to the study of fragments of the Lambek calculus
• Complete problems for monotone NP

This page was built for publication: The monotone Lambek calculus is NP-complete

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