Annals of Pure and Applied Logic 142 (1):366-379 (2006)

Authors
Abstract
By a well-known result of Cook and Reckhow [S.A. Cook, R.A. Reckhow, The relative efficiency of propositional proof systems, Journal of Symbolic Logic 44 36–50; R.A. Reckhow, On the lengths of proofs in the propositional calculus, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1976], all Frege systems for the classical propositional calculus are polynomially equivalent. Mints and Kojevnikov [G. Mints, A. Kojevnikov, Intuitionistic Frege systems are polynomially equivalent, Zapiski Nauchnyh Seminarov POMI 316 129–146] have recently shown p-equivalence of Frege systems for the intuitionistic propositional calculus in the standard language, building on a description of admissible rules of IPC by Iemhoff [R. Iemhoff, On the admissible rules of intuitionistic propositional logic, Journal of Symbolic Logic 66 281–294]. We prove a similar result for an infinite family of normal modal logics, including K4, GL, S4, and
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2006.04.001
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 54,740
Through your library

References found in this work BETA

Modal Logic.Alexander Chagrov - 1997 - Oxford University Press.
Unification in Intuitionistic Logic.Silvio Ghilardi - 1999 - Journal of Symbolic Logic 64 (2):859-880.
Canonical Formulas for K4. Part I: Basic Results.Michael Zakharyaschev - 1992 - Journal of Symbolic Logic 57 (4):1377-1402.

View all 11 references / Add more references

Citations of this work BETA

Independent Bases of Admissible Rules.Emil Jerábek - 2008 - Logic Journal of the IGPL 16 (3):249-267.
Canonical Rules.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (4):1171 - 1205.
Proof Complexity of Intuitionistic Implicational Formulas.Emil Jeřábek - 2017 - Annals of Pure and Applied Logic 168 (1):150-190.
On Lengths of Proofs in Non-Classical Logics.Pavel Hrubeš - 2009 - Annals of Pure and Applied Logic 157 (2-3):194-205.
Rules with Parameters in Modal Logic I.Emil Jeřábek - 2015 - Annals of Pure and Applied Logic 166 (9):881-933.

View all 7 citations / Add more citations

Similar books and articles

Complexity of Admissible Rules.Emil Jeřábek - 2007 - Archive for Mathematical Logic 46 (2):73-92.
Abstract Modal Logics.Ramon Jansana - 1995 - Studia Logica 55 (2):273 - 299.
Some Multi-Conclusion Modal Paralogics.Casey McGinnis - 2007 - Logica Universalis 1 (2):335-353.
Term-Modal Logics.Melvin Fitting, Lars Thalmann & Andrei Voronkov - 2001 - Studia Logica 69 (1):133-169.
A First Approach to Abstract Modal Logics.Josep M. Font & Ventura Verdú - 1989 - Journal of Symbolic Logic 54 (3):1042-1062.
Four Simple Systems of Modal Propositional Logic.Gerald J. Massey - 1965 - Philosophy of Science 32 (3/4):342-355.

Analytics

Added to PP index
2013-12-31

Total views
17 ( #578,365 of 2,386,872 )

Recent downloads (6 months)
3 ( #262,029 of 2,386,872 )

How can I increase my downloads?

Downloads

My notes