Archive for Mathematical Logic 46 (2):73-92 (2007)
| Authors | |
| 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
|
| Keywords | Admissible rules Computational complexity Modal logics Intermediate logics |
| Categories | (categorize this paper) |
| DOI | 10.1007/s00153-006-0028-9 |
| Options |
Mark as duplicate
Export citation
Request removal from index
|
Download options
PhilArchive copy
Upload a copy of this paper Check publisher's policy Papers currently archived: 70,091
External links
- From the Publisher via CrossRef (no proxy)
- link.springer.com (no proxy)
- link.springer.com [2] (no proxy)
- oldweb.math.cas.cz
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
- Sign in / register and customize your OpenURL resolver..
- Configure custom resolver
References found in this work BETA
One Hundred and Two Problems in Mathematical Logic.Harvey Friedman - 1975 - Journal of Symbolic Logic 40 (2):113-129.
Unification in Intuitionistic Logic.Silvio Ghilardi - 1999 - Journal of Symbolic Logic 64 (2):859-880.
On the Admissible Rules of Intuitionistic Propositional Logic.Rosalie Iemhoff - 2001 - Journal of Symbolic Logic 66 (1):281-294.
That All Normal Extensions of S4.3 Have the Finite Model Property.R. A. Bull - 1966 - Mathematical Logic Quarterly 12 (1):341-344.
View all 12 references / Add more references
Citations of this work BETA
Proof Theory for Admissible Rules.Rosalie Iemhoff & George Metcalfe - 2009 - Annals of Pure and Applied Logic 159 (1-2):171-186.
Admissible Rules in the Implication–Negation Fragment of Intuitionistic Logic.Petr Cintula & George Metcalfe - 2010 - Annals of Pure and Applied Logic 162 (2):162-171.
KD is Nullary.Philippe Balbiani & Çiğdem Gencer - 2017 - Journal of Applied Non-Classical Logics 27 (3-4):196-205.
A Syntactic Approach to Unification in Transitive Reflexive Modal Logics.Rosalie Iemhoff - 2016 - Notre Dame Journal of Formal Logic 57 (2):233-247.
Unification in Linear Temporal Logic LTL.Sergey Babenyshev & Vladimir Rybakov - 2011 - Annals of Pure and Applied Logic 162 (12):991-1000.
View all 17 citations / Add more citations
Similar books and articles
On the Rules of Intermediate Logics.Rosalie Iemhoff - 2006 - Archive for Mathematical Logic 45 (5):581-599.
Intermediate Logics and Visser's Rules.Rosalie Iemhoff - 2005 - Notre Dame Journal of Formal Logic 46 (1):65-81.
Metalogic of Intuitionistic Propositional Calculus.Alex Citkin - 2010 - Notre Dame Journal of Formal Logic 51 (4):485-502.
A Note on Admissible Rules and the Disjunction Property in Intermediate Logics.Alexander Citkin - 2012 - Archive for Mathematical Logic 51 (1-2):1-14.
Logical Equations and Admissible Rules of Inference with Parameters in Modal Provability Logics.V. V. Rybakov - 1990 - Studia Logica 49 (2):215 - 239.
Admissibility of Ackermann's Rule Δ in Relevant Logics.Gemma Robles - 2013 - Logic and Logical Philosophy 22 (4):411-427.
Criteria for Admissibility of Inference Rules. Modal and Intermediate Logics with the Branching Property.Vladimir V. Rybakov - 1994 - Studia Logica 53 (2):203 - 225.
On Self-Admissible Quasi-Characterizing Inference Rules.V. V. Rybakov, M. Terziler & C. Gencer - 2000 - Studia Logica 65 (3):417-428.
Best Unifiers in Transitive Modal Logics.Vladimir V. Rybakov - 2011 - Studia Logica 99 (1-3):321-336.
Intermediate Logics Preserving Admissible Inference Rules of Heyting Calculus.Vladimir V. Rybakov - 1993 - Mathematical Logic Quarterly 39 (1):403-415.
The Γ-Admissibility of Relevant Modal Logics II — The Method Using Metavaluations.Takahiro Seki - 2011 - Studia Logica 97 (3):351-383.
Construction of an Explicit Basis for Rules Admissible in Modal System S4.Vladimir V. Rybakov - 2001 - Mathematical Logic Quarterly 47 (4):441-446.
Analytics
Added to PP index
2013-11-23
Total views
436 ( #22,017 of 2,506,351 )
Recent downloads (6 months)
1 ( #416,997 of 2,506,351 )
2013-11-23
Total views
436 ( #22,017 of 2,506,351 )
Recent downloads (6 months)
1 ( #416,997 of 2,506,351 )
How can I increase my downloads?
Downloads
