The complexity of Horn fragments of linear logic

DOI10.1016/0168-0072(94)90085-XzbMATH Open0812.03007MaRDI QIDQ1337693FDOQ1337693

Authors: Max Kanovich 

Publication date: 16 May 1995

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

Recommendations

• scientific article; zbMATH DE number 1114332
• scientific article; zbMATH DE number 785051
• Linear logic as a logic of computations
• Lambek calculus is NP-complete
• The undecidability theorem for the Horn-like fragment of linear logic (revisited)

zbMATH Keywords

NP-completenessPSPACE-completenesscomplexity of derivabilitygeneralized Horn implicationsHorn fragments of linear logicHorn programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Linear logic
• Bounded linear logic: A modular approach to polynomial-time computability
• Computational interpretations of linear logic
• Intuitionistic propositional logic is polynomial-space complete
• Efficient program synthesis: semantics, logic, complexity

Cited In (17)

• The undecidability theorem for the Horn-like fragment of linear logic (revisited)
• Title not available (Why is that?)
• On the decision problem for MELL
• Towards NP-P via proof complexity and search
• System NEL is undecidable
• Linear logic automata
• Title not available (Why is that?)
• Petri nets, Horn programs, linear logic and vector games
• Direct encodings of NP-complete problems into Horn sequents of multiplicative linear logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Collaborative planning with confidentiality
• Computational Complexity of a Hybridized Horn Fragment of Halpern-Shoham Logic
• Relating state-based and process-based concurrency through linear logic (full-version)
• Lambek calculus is NP-complete
• An application of proof-nets to the study of fragments of the Lambek calculus
• RASP and ASP as a fragment of linear logic

This page was built for publication: The complexity of Horn fragments of linear logic

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