Product-free Lambek calculus is NP-complete

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

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

• Lambek calculus is NP-complete
• The Mathematics of Sentence Structure
• Lambek Grammars with One Division Are Decidable in Polynomial Time
• Title not available (Why is that?)
• Non‐associative Lambek Categorial Grammar in Polynomial Time

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)