Complexity of interpolation and related problems in positive calculi

DOI10.2178/jsl/1190150051zbMath1037.03005OpenAlexW2169135069MaRDI QIDQ4532622

Larisa L. Maksimova

Publication date: 2002

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1190150051

zbMATH Keywords

interpolationNP-completenessdefinabilitycomplexity boundsPSPACE-completenesstabularitydecidable propertiespretabularityDP-hardnesspositive calculisuperintuitionistic calculi

Mathematics Subject Classification ID

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

Related Items (4)

LC and Its Pretabular Relatives ⋮ The tabularity problem over the minimal logic ⋮ Definability and interpolation in non-classical logics ⋮ Formal Properties of Modularisation

Cites Work

• Unnamed Item
• Unnamed Item
• A guide to completeness and complexity for modal logics of knowledge and belief
• Propositional dynamic logic of regular programs
• Intuitionistic propositional logic is polynomial-space complete
• Intuitionistic logic and implicit definability
• Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• A Remark on the Intersection of Tow Logics

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