The complexity of Horn fragments of linear logic

DOI10.1016/0168-0072(94)90085-XMaRDI QIDQ1337693zbMATH OpenFDO

Authors Max Kanovich

Publication date 16 May 1995

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

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)

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)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1489627 (Why is no real title available?)
• Bounded linear logic: A modular approach to polynomial-time computability
• Computational interpretations of linear logic
• Efficient program synthesis: semantics, logic, complexity
• Intuitionistic propositional logic is polynomial-space complete
• Linear logic

Cited in

(17)

• The undecidability theorem for the Horn-like fragment of linear logic (revisited)
• scientific article; zbMATH DE number 7566060 (Why is no real title available?)
• Towards NP-P via proof complexity and search
• On the decision problem for MELL
• System NEL is undecidable
• Linear logic automata
• scientific article; zbMATH DE number 1841812 (Why is no real title available?)
• Petri nets, Horn programs, linear logic and vector games
• Direct encodings of NP-complete problems into Horn sequents of multiplicative linear logic
• scientific article; zbMATH DE number 408788 (Why is no real title available?)
• Collaborative planning with confidentiality
• scientific article; zbMATH DE number 5295720 (Why is no real title available?)
• 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)