Complexity of intuitionistic propositional logic and its fragments

Journal of Applied Non-Classical Logics 18 (2):267-292 (2008)
  Copy   BIBTEX

Abstract

In the paper we consider complexity of intuitionistic propositional logic and its natural fragments such as implicative fragment, finite-variable fragments, and some others. Most facts we mention here are known and obtained by logicians from different countries and in different time since 1920s; we present these results together to see the whole picture.

Categories

Keywords

Reprint years

DOI

10.3166/jancl.18.267-292

Links

PhilArchive



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

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

Interpolation in fragments of intuitionistic propositional logic.Gerard R. Renardel de Lavalette - 1989 - Journal of Symbolic Logic 54 (4):1419-1430.
Interpolation in Fragments of Intuitionistic Propositional Logic.Gerard R. Renardel De Lavalette - 1989 - Journal of Symbolic Logic 54 (4):1419 - 1430.
On the complexity of propositional quantification in intuitionistic logic.Philip Kremer - 1997 - Journal of Symbolic Logic 62 (2):529-544.
Intuitionistic Completeness and Classical Logic.D. C. McCarty - 2002 - Notre Dame Journal of Formal Logic 43 (4):243-248.
The degrees of maximality of the intuitionistic propositional logic and of some of its fragments.Wiesław Dziobiak - 1981 - Studia Logica 40 (2):195 - 198.
The logic of bunched implications.Peter W. O'Hearn & David J. Pym - 1999 - Bulletin of Symbolic Logic 5 (2):215-244.
Doing logic by computer: interpolation in fragments of intuitionistic propositional logic.Lex Hendriks - 2000 - Annals of Pure and Applied Logic 104 (1-3):97-112.
A characterization of fragments of the intuitionistic propositional logic.M. T. Porebska & A. Wronski - 1974 - Bulletin of the Section of Logic 3 (2):19-20.
Irreflexive modality in the intuitionistic propositional logic and Novikov completeness.A. D. Yashin - 1999 - Journal of Philosophical Logic 28 (2):175-197.
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.
On the polynomial-space completeness of intuitionistic propositional logic.Vítězslav Švejdar - 2003 - Archive for Mathematical Logic 42 (7):711-716.
The Expressive Force of Some Fragments of Intuitionistic Propositional Logic with Regard to Kripke Frames.P. H. Rodenburg - 1991 - Mathematical Logic Quarterly 37 (23‐24):357-362.
Absolute probability functions for intuitionistic propositional logic.Peter Roeper & Hugues Leblanc - 1999 - Journal of Philosophical Logic 28 (3):223-234.
The Separation Theorem for Fragments of the Intuitionistic Propositional Calculus.G. Rousseau - 1970 - Mathematical Logic Quarterly 16 (8):469-474.
A proof-search procedure for intuitionistic propositional logic.R. Alonderis - 2013 - Archive for Mathematical Logic 52 (7-8):759-778.

Analytics

Added to PP
2013-12-29

Downloads
31 (#501,295)

6 months
8 (#352,434)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Transitive primal infon logic.Carlos Cotrini & Yuri Gurevich - 2013 - Review of Symbolic Logic 6 (2):281-304.

View all 6 citations / Add more citations

References found in this work

Modal logic.Alexander Chagrov - 1997 - New York: Oxford University Press. Edited by Michael Zakharyaschev.
Modal Logic.Yde Venema, Alexander Chagrov & Michael Zakharyaschev - 2000 - Philosophical Review 109 (2):286.
Semantical Investigations in Heyting's Intuitionistic Logic.Dov M. Gabbay - 1986 - Journal of Symbolic Logic 51 (3):824-824.

View all 19 references / Add more references