Product-free Lambek calculus is NP-complete

DOI10.1016/J.APAL.2011.09.017zbMATH Open1243.03029OpenAlexW4206777114MaRDI QIDQ408532FDOQ408532

Authors 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

proof netsLambek calculusalgorithmic complexityderivability

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) Decidability of theories and sets of sentences (03B25)

Cites Work

• scientific article; zbMATH DE number 1341472 (Why is no real title available?)
• Lambek Grammars with One Division Are Decidable in Polynomial Time
• Lambek calculus is NP-complete
• Non‐associative Lambek Categorial Grammar in Polynomial Time
• The Mathematics of Sentence Structure

Cited In (4)

• Lambek calculus is NP-complete
• An application of proof-nets to the study of fragments of the Lambek calculus
• On translating Lambek grammars with one division into context-free grammars
• Kleene star, subexponentials without contraction, and infinite computations

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

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