Complexity of admissible rules
type: Item
instance of: scholarly article
title: Complexity of admissible rules
zbMATH Open document ID: 1115.03010
author: Emil Jeřábek
published in: Archive for Mathematical Logic
publication date: 2007-03-06T00:00:00Z
review text: An inference rule is admissible in a logic \(L\) if the set of theorems of \(L\) is closed under the rule. V. Rybakov proved decidability of the problem od admissibility for many modal and superintuitionistic logics. The author provides complexity estimates for this problem which are optimal or close to optimal. Admissibility in ``typical'' extensions of K4 and superintuitionistic logics is co-NEXP-complete while derivability is P-SPACE-complete or even NP-complete. A co-NEXP decision procedure is given for admissibility in a class of logics including K4, GL, S4, S4Grz and Int. Admissibility is proved to be co-NEXP-hard in all superintuitionistic logics \(L\) such that every depth-3 tree is an \(L\)-frame and in similar normal modal extensions of K4.
Mathematics Subject Classification ID: 03B45
Mathematics Subject Classification ID: 03B55
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5131231
zbMATH Keywords: admissible rules
zbMATH Keywords: complexity
zbMATH Keywords: modal logic
zbMATH Keywords: intermediate logic
Wikidata QID: Q56474452
reviewed by: G. E. Mints
MaRDI profile type: Publication
full work available at URL: s00153-006-0028-9
OpenAlex ID: W2111570288
cites work: Modal logic
cites work: That All Normal Extensions of S4.3 Have the Finite Model Property
cites work: Q4723713
cites work: Decidable modal logic with undecidable admissibility problem
cites work: Q3128959
cites work: Q4058132
cites work: One hundred and two problems in mathematical logic
cites work: Unification in intuitionistic logic
cites work: Best solving modal equations
cites work: A Resolution/Tableaux Algorithm for Projective Approximations in IPC
cites work: On the admissible rules of intuitionistic propositional logic
cites work: Intermediate logics and Visser's rules
cites work: On the rules of intermediate logics
cites work: Admissible Rules of Modal Logics
cites work: Q4109648
cites work: The Computational Complexity of Provability in Systems of Modal Propositional Logic
cites work: Q4298260
cites work: Admissibility of logical inference rules
cites work: Q4833777
cites work: Intuitionistic propositional logic is polynomial-space complete
cites work: Canonical formulas for K4. Part II: Cofinal subframe logics
DOI: 10.1007/S00153-006-0028-9
description: scientific article; zbMATH DE number 5131231