The Monotone Lambek Calculus Is NP-Complete

DOI10.1007/978-3-642-54789-8_20zbMath1285.03018OpenAlexW2133903059MaRDI QIDQ5414974

M. R. 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) 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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The atomic theory of left division of two-sided ideals of semirings with unit
• Cut elimination and strong separation for substructural logics: an algebraic approach
• Language in action. Categories, lambdas and dynamic logic
• The atomic theory of multiplication and division of semiring ideals
• The Mathematics of Sentence Structure
• Product-Free Lambek Calculus Is NP-Complete
• Completeness Results for Lambek Syntactic Calculus

This page was built for publication: The Monotone Lambek Calculus Is NP-Complete