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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,219

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.
Intuitionistic Completeness and Classical Logic.D. C. McCarty - 2002 - Notre Dame Journal of Formal Logic 43 (4):243-248.
A Closer Look at Some Subintuitionistic Logics.Ramon Jansana & Sergio Celani - 2001 - Notre Dame Journal of Formal Logic 42 (4):225-255.
A Closer Look at Some Subintuitionistic Logics.Sergio Celani & Ramon Jansana - 2001 - Notre Dame Journal of Formal Logic 42 (4):225-255.
Completeness and incompleteness for intuitionistic logic.Charles Mccarty - 2008 - Journal of Symbolic Logic 73 (4):1315-1327.
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.
Propositional Mixed Logic: Its Syntax and Semantics.Karim Nour & Abir Nour - 2003 - Journal of Applied Non-Classical Logics 13 (3-4):377-390.
Reverse Mathematics and Completeness Theorems for Intuitionistic Logic.Takeshi Yamazaki - 2001 - Notre Dame Journal of Formal Logic 42 (3):143-148.
Intuitionistic completeness for first order classical logic.Stefano Berardi - 1999 - Journal of Symbolic Logic 64 (1):304-312.
Towards intuitionistic dynamic logic.J. W. Degen & J. M. Werner - 2006 - Logic and Logical Philosophy 15 (4):305-324.
Irreflexive modality in the intuitionistic propositional logic and Novikov completeness.A. D. Yashin - 1999 - Journal of Philosophical Logic 28 (2):175-197.
On the complexity of propositional quantification in intuitionistic logic.Philip Kremer - 1997 - Journal of Symbolic Logic 62 (2):529-544.
The classification of propositional calculi.Alexander S. Karpenko - 2000 - Studia Logica 66 (2):253-271.

Analytics

Added to PP
2013-11-23

Downloads
89 (#184,948)

6 months
4 (#698,851)

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