Complexity of the interpretability logic IL

DOI10.1093/JIGPAL/JZY015MaRDI QIDQ5241913zbMATH OpenOpenAlexWikidataFDO

Authors Luka Mikec, Mladen Vuković, Fedor N. Pakhomov

Publication date 4 November 2019

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.05599

zbMATH Keywords

complexitydecidabilityPSPACEinterpretability logicVeltman semantics

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Provability logics and related algebras (e.g., diagonalizable algebras) (03F45)

Abstract: We show that the decision problem for the basic system of interpretability logic IL is PSPACE-complete. For this purpose we present an algorithm which uses polynomial space with respect to the complexity of a given formula. The existence of such algorithm, together with the previously known PSPACE hardness of the closed fragment of IL, implies PSPACE-completeness.

Recommendations

• Complexity of the interpretability logics ILW and ILP
• scientific article; zbMATH DE number 1281983
• Decidability of interpretability logics \(\mathbf{IL}\mathtt{M}_0\) and \(\mathbf{IL}\mathtt{W}^*\)
• scientific article; zbMATH DE number 5147176
• Modal completeness of sublogics of the interpretability logic IL
• scientific article; zbMATH DE number 1215477
• scientific article; zbMATH DE number 218514
• Interpretability logics and generalised Veltman semantics
• scientific article; zbMATH DE number 218496
• scientific article; zbMATH DE number 806756

Cited in

(5)

• The closed fragment of IL is PSPACE hard
• Complexity of the interpretability logics ILW and ILP
• An overview of Verbrugge semantics, a.k.a. generalised Veltman semantics
• scientific article; zbMATH DE number 1515320 (Why is no real title available?)
• Modular sequent calculi for interpretability logics

This page was built for publication: Complexity of the interpretability logic IL

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