scientific article; zbMATH DE number 785051

zbMATH Open0828.03004MaRDI QIDQ4842540FDOQ4842540

Authors Andre Scedrov

Publication date 14 August 1995

zbMATH Keywords

surveycomplexity classesproof searchPSPACE-hardnessfragments of linear logic

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Subsystems of classical logic (including intuitionistic logic) (03B20)

Recommendations

• scientific article; zbMATH DE number 1231522
• First-order linear logic without modalities is NEXPTIME-hard
• Soft linear logic and polynomial complexity classes
• Decision problems for propositional linear logic
• Bounded linear logic: A modular approach to polynomial-time computability

Cited in

(18)

• RASP and ASP as a fragment of linear logic
• scientific article; zbMATH DE number 1231523 (Why is no real title available?)
• Encoding linear logic with interaction combinators
• On the computational complexity of cut-elimination in linear logic.
• Linear logic with fixed resources
• scientific article; zbMATH DE number 1361538 (Why is no real title available?)
• A PSPACE-complete fragment of second-order linear logic
• Bounded linear logic: A modular approach to polynomial-time computability
• PSPACE-completeness of a thread criterion for circular proofs in linear logic with least and greatest fixed points
• scientific article; zbMATH DE number 786487 (Why is no real title available?)
• scientific article; zbMATH DE number 786490 (Why is no real title available?)
• Linear logic as a logic of computations
• scientific article; zbMATH DE number 1231531 (Why is no real title available?)
• The complexity of Horn fragments of linear logic
• First-order linear logic without modalities is NEXPTIME-hard
• scientific article; zbMATH DE number 7441265 (Why is no real title available?)
• scientific article; zbMATH DE number 2120362 (Why is no real title available?)
• Constant-only multiplicative linear logic is NP-complete

This page was built for publication:

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