Complexity of admissible rules

Archive for Mathematical Logic 46 (2):73-92 (2007)
  Copy   BIBTEX

Abstract

We investigate the computational complexity of deciding whether a given inference rule is admissible for some modal and superintuitionistic logics. We state a broad condition under which the admissibility problem is coNEXP-hard. We also show that admissibility in several well-known systems (including GL, S4, and IPC) is in coNE, thus obtaining a sharp complexity estimate for admissibility in these systems

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,154

External links

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

Through your library

Similar books and articles

Proof theory for admissible rules.Rosalie Iemhoff & George Metcalfe - 2009 - Annals of Pure and Applied Logic 159 (1-2):171-186.
Intermediate Logics and Visser's Rules.Rosalie Iemhoff - 2005 - Notre Dame Journal of Formal Logic 46 (1):65-81.
On the rules of intermediate logics.Rosalie Iemhoff - 2006 - Archive for Mathematical Logic 45 (5):581-599.
Description of modal logics inheriting admissible rules for S4.V. Rybakov - 1999 - Logic Journal of the IGPL 7 (5):655-664.
Canonical Rules.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (4):1171 - 1205.

Analytics

Added to PP
2013-11-23

Downloads
462 (#60,517)

6 months
7 (#673,909)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Proof theory for admissible rules.Rosalie Iemhoff & George Metcalfe - 2009 - Annals of Pure and Applied Logic 159 (1-2):171-186.
Canonical Rules.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (4):1171 - 1205.
On Rules.Rosalie Iemhoff - 2015 - Journal of Philosophical Logic 44 (6):697-711.
KD is nullary.Philippe Balbiani & Çiğdem Gencer - 2017 - Journal of Applied Non-Classical Logics 27 (3-4):196-205.

View all 19 citations / Add more citations

References found in this work

Unification in intuitionistic logic.Silvio Ghilardi - 1999 - Journal of Symbolic Logic 64 (2):859-880.
One hundred and two problems in mathematical logic.Harvey Friedman - 1975 - Journal of Symbolic Logic 40 (2):113-129.
Best solving modal equations.Silvio Ghilardi - 2000 - Annals of Pure and Applied Logic 102 (3):183-198.

View all 10 references / Add more references