The complexity of Horn fragments of linear logic

DOI10.1016/0168-0072(94)90085-XzbMath0812.03007MaRDI QIDQ1337693

Max I. 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) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (9)

Petri nets, Horn programs, linear logic and vector games ⋮ Linear logic automata ⋮ RASP and ASP as a fragment of linear logic ⋮ Towards NP-P via proof complexity and search ⋮ On the decision problem for MELL ⋮ Collaborative planning with confidentiality ⋮ System NEL is Undecidable ⋮ Unnamed Item ⋮ Relating state-based and process-based concurrency through linear logic (full-version)

Cites Work

• Unnamed Item
• Unnamed Item
• Linear logic
• Computational interpretations of linear logic
• Bounded linear logic: A modular approach to polynomial-time computability
• Intuitionistic propositional logic is polynomial-space complete
• Efficient program synthesis: Semantics, logic, complexity

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