- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
The decision problem of provability logic with only one atom
Archive for Mathematical Logic 42 (8):763-768 (2003)
Abstract
The decision problem for provability logic remains PSPACE-complete even if the number of propositional atoms is restricted to oneMy notes
Similar books and articles
On the polynomial-space completeness of intuitionistic propositional logic.Vítězslav Švejdar - 2003 - Archive for Mathematical Logic 42 (7):711-716.
A propositional logic with explicit fixed points.Albert Visser - 1981 - Studia Logica 40 (2):155 - 175.
On the provability logic of bounded arithmetic.Rineke Verbrugge & Alessandro Berarducci - 1991 - Annals of Pure and Applied Logic 61 (1-2):75-93.
Explicit provability and constructive semantics.Sergei N. Artemov - 2001 - Bulletin of Symbolic Logic 7 (1):1-36.
On predicate provability logics and binumerations of fragments of Peano arithmetic.Taishi Kurahashi - 2013 - Archive for Mathematical Logic 52 (7-8):871-880.
Bimodal logics for extensions of arithmetical theories.Lev D. Beklemishev - 1996 - Journal of Symbolic Logic 61 (1):91-124.
All finitely axiomatizable subframe logics containing the provability logic CSM $_{0}$ are decidable.Frank Wolter - 1998 - Archive for Mathematical Logic 37 (3):167-182.
Realization of Intuitionistic Logic by Proof Polynomials.Sergei N. Artemov - 1999 - Journal of Applied Non-Classical Logics 9 (2-3):285-301.
On strong provability predicates and the associated modal logics.Konstantin N. Ignatiev - 1993 - Journal of Symbolic Logic 58 (1):249-290.
On Provability Logics with Linearly Ordered Modalities.Lev D. Beklemishev, David Fernández-Duque & Joost J. Joosten - 2014 - Studia Logica 102 (3):541-566.
Provability and Interpretability Logics with Restricted Realizations.Thomas F. Icard & Joost J. Joosten - 2012 - Notre Dame Journal of Formal Logic 53 (2):133-154.
Kripke semantics for provability logic GLP.Lev D. Beklemishev - 2010 - Annals of Pure and Applied Logic 161 (6):756-774.
Interpolation and implicit definability in extensions of the provability logic.Larisa Maksimova - 2008 - Logic and Logical Philosophy 17 (1-2):129-142.
The Closed Fragment of the Interpretability Logic of PRA with a Constant for.Joost J. Joosten - 2005 - Notre Dame Journal of Formal Logic 46 (2):127-146.
A Note on Bisimulation and Modal Equivalence in Provability Logic and Interpretability Logic.Vedran Čačić & Domagoj Vrgoč - 2013 - Studia Logica 101 (1):31-44.
Analytics
Added to PP
2013-12-01
Downloads
58 (#271,353)
6 months
13 (#184,769)
2013-12-01
Downloads
58 (#271,353)
6 months
13 (#184,769)
Historical graph of downloads
Citations of this work
Complete additivity and modal incompleteness.Wesley H. Holliday & Tadeusz Litak - 2019 - Review of Symbolic Logic 12 (3):487-535.
Complexity and expressivity of propositional dynamic logics with finitely many variables.Mikhail Rybakov & Dmitry Shkatov - 2018 - Logic Journal of the IGPL 26 (5):539-547.
Predicate counterparts of modal logics of provability: High undecidability and Kripke incompleteness.Mikhail Rybakov - forthcoming - Logic Journal of the IGPL.
Complexity of finite-variable fragments of propositional modal logics of symmetric frames.Mikhail Rybakov & Dmitry Shkatov - forthcoming - Logic Journal of the IGPL.
On the complexity of the closed fragment of Japaridze’s provability logic.Fedor Pakhomov - 2014 - Archive for Mathematical Logic 53 (7-8):949-967.
References found in this work
On the polynomial-space completeness of intuitionistic propositional logic.Vítězslav Švejdar - 2003 - Archive for Mathematical Logic 42 (7):711-716.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-7c76586df8-5tf24 uwo