Product-free Lambek calculus is NP-complete

DOI10.1016/j.apal.2011.09.017zbMath1243.03029OpenAlexW4206777114MaRDI QIDQ408532

Yury Savateev

Publication date: 10 April 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2011.09.017

zbMATH Keywords

algorithmic complexityderivabilityLambek calculusproof nets

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)

Related Items

Kleene star, subexponentials without contraction, and infinite computations ⋮ On translating Lambek grammars with one division into context-free grammars

Cites Work

• Unnamed Item
• Lambek calculus is NP-complete
• The Mathematics of Sentence Structure
• Lambek Grammars with One Division Are Decidable in Polynomial Time
• Non‐associative Lambek Categorial Grammar in Polynomial Time

This page was built for publication: Product-free Lambek calculus is NP-complete