The Closed Fragment of IL is PSPACE Hard

DOI10.1016/j.entcs.2011.10.005zbMath1347.03040arXiv2004.06398OpenAlexW2163979941WikidataQ113318202 ScholiaQ113318202MaRDI QIDQ2825406

Félix Bou, Joost J. Joosten

Publication date: 7 October 2016

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitynormal formsinterpretability logicclosed fragmentPSPACE-hardness

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Cut-elimination and normal-form theorems (03F05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Provability logics and related algebras (e.g., diagonalizable algebras) (03F45)

Related Items (2)

On the share of closed \(\mathsf {IL}\) formulas which are also in \(\mathsf {GL}\) ⋮ On the complexity of the closed fragment of Japaridze's provability logic

Cites Work

• A note on the normal form of closed formulas of interpretability logic
• The decision problem of provability logic with only one atom
• On the proof theory of the modal logic for arithmetic provability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Closed Fragment of IL is PSPACE Hard