Complexity of some problems in positive and related calculi

DOI10.1016/S0304-3975(02)00450-4MaRDI QIDQ1401362zbMATH OpenOpenAlexFDO

Authors L. L. Maksimova

Publication date 17 August 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(02)00450-4

zbMATH Keywords

complexityinterpolationpositive logicprojective Beth property

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Interpolation, preservation, definability (03C40) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Complexity of interpolation and related problems in positive calculi
• Computer Science Logic
• Decidable properties of logical calculi and of varieties of algebras
• Decidability of the interpolation problem and of related properties in tabular logics
• Strongly decidable properties of modal and intuitionistic calculi

Cites work

• A guide to completeness and complexity for modal logics of knowledge and belief
• scientific article; zbMATH DE number 1003731 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3609636 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 1746556 (Why is no real title available?)
• scientific article; zbMATH DE number 3417441 (Why is no real title available?)
• Intuitionistic logic and implicit definability
• Intuitionistic propositional logic is polynomial-space complete
• Propositional dynamic logic of regular programs
• The Computational Complexity of Provability in Systems of Modal Propositional Logic

Cited in

(9)

• On the complexity of the Leibniz hierarchy
• LC and its pretabular relatives
• Decidability of the interpolation problem and of related properties in tabular logics
• Strongly decidable properties of modal and intuitionistic calculi
• Complexity of interpolation and related problems in positive calculi
• The tabularity problem over the minimal logic
• Restricted positive quantification is not elementary
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Decidable properties of logical calculi and of varieties of algebras

This page was built for publication: Complexity of some problems in positive and related calculi

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