- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Complexity of admissible rules
Archive for Mathematical Logic 46 (2):73-92 (2007)
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 systemsAuthor's Profile
Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
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):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
2013-11-23
Downloads
453 (#42,616)
6 months
14 (#175,970)
2013-11-23
Downloads
453 (#42,616)
6 months
14 (#175,970)
Historical graph of 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.
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.
Remarks about the unification type of several non-symmetric non-transitive modal logics.Philippe Balbiani - 2019 - Logic Journal of the IGPL 27 (5):639-658.
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.
On the admissible rules of intuitionistic propositional logic.Rosalie Iemhoff - 2001 - Journal of Symbolic Logic 66 (1):281-294.
Best solving modal equations.Silvio Ghilardi - 2000 - Annals of Pure and Applied Logic 102 (3):183-198.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-64dd777598-wg6s5 uwo