On the polynomial-space completeness of intuitionistic propositional logic

Archive for Mathematical Logic 42 (7):711-716 (2003)
  Copy   BIBTEX

Abstract

We present an alternative, purely semantical and relatively simple, proof of the Statman's result that both intuitionistic propositional logic and its implicational fragment are PSPACE-complete

Categories

Keywords

Reprint years

DOI

10.1007/s00153-003-0179-x

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 106,756

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The decision problem of provability logic with only one atom.Vítězslav Švejdar - 2003 - Archive for Mathematical Logic 42 (8):763-768.
Complexity of intuitionistic propositional logic and its fragments.Mikhail Rybakov - 2008 - Journal of Applied Non-Classical Logics 18 (2):267-292.
Negational Fragment of Intuitionistic Control Logic.Anna Glenszczyk - 2015 - Studia Logica 103 (6):1101-1121.
Propositional Mixed Logic: Its Syntax and Semantics.Karim Nour & Abir Nour - 2003 - Journal of Applied Non-Classical Logics 13 (3-4):377-390.
On the computational content of intuitionistic propositional proofs.Samuel R. Buss & Pavel Pudlák - 2001 - Annals of Pure and Applied Logic 109 (1-2):49-64.
The classification of propositional calculi.Alexander S. Karpenko - 2000 - Studia Logica 66 (2):253-271.
A Syntactic Embedding of Predicate Logic into Second-Order Propositional Logic.Morten H. Sørensen & Paweł Urzyczyn - 2010 - Notre Dame Journal of Formal Logic 51 (4):457-473.
Linearizing intuitionistic implication.Patrick Lincoln, Andre Scedrov & Natarajan Shankar - 1993 - Annals of Pure and Applied Logic 60 (2):151-177.
A secondary semantics for Second Order Intuitionistic Propositional Logic.Mauro Ferrari, Camillo Fiorentini & Guido Fiorino - 2004 - Mathematical Logic Quarterly 50 (2):202-210.
A correct polynomial translation of s4 into intuitionistic logic.Rajeev Goré & Jimmy Thomson - 2019 - Journal of Symbolic Logic 84 (2):439-451.

Analytics

Added to PP
2013-11-23

Downloads
104 (#218,262)

6 months
7 (#633,574)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The decision problem of provability logic with only one atom.Vítězslav Švejdar - 2003 - Archive for Mathematical Logic 42 (8):763-768.
Proof Compression and NP Versus PSPACE II.Lew Gordeev & Edward Hermann Haeusler - 2020 - Bulletin of the Section of Logic 49 (3):213-230.

Add more citations

References found in this work

No references found.

Add more references