Complexity of admissible rules
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.
- A Resolution/Tableaux Algorithm for Projective Approximations in IPC
- Admissibility of logical inference rules
- Admissible Rules of Modal Logics
- Best solving modal equations
- Canonical formulas for K4. Part II: Cofinal subframe logics
- Decidable modal logic with undecidable admissibility problem
- scientific article; zbMATH DE number 1003731 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3532920 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 3995647 (Why is no real title available?)
- scientific article; zbMATH DE number 757645 (Why is no real title available?)
- Intermediate logics and Visser's rules
- Intuitionistic propositional logic is polynomial-space complete
- Modal logic
- On the admissible rules of intuitionistic propositional logic
- On the rules of intermediate logics
- One hundred and two problems in mathematical logic
- That All Normal Extensions of S4.3 Have the Finite Model Property
- The Computational Complexity of Provability in Systems of Modal Propositional Logic
- Unification in intuitionistic logic
- Proof theory for admissible rules
- Criteria for admissibility of inference rules. Modal and intermediate logics with the branching property
- Rules with parameters in modal logic. II.
- Computability issues for adaptive logics in multi-consequence standard format
- Inference rules in Nelson's logics, admissibility and weak admissibility
- Rules with parameters in modal logic. I.
- Decidable modal logic with undecidable admissibility problem
- On rules
- A syntactic approach to unification in transitive reflexive modal logics
- A tableau method for checking rule admissibility in S4
- UNIFICATION IN INTERMEDIATE LOGICS
- Tutorial on admissible rules in Gudauri
- Admissible Rules of Lukasiewicz Logic
- Canonical rules
- Unification and admissible rules for paraconsistent minimal Johanssons' logic J and positive intuitionistic logic \(\mathbf{IPC}^+\)
- What is an inference rule?
- scientific article; zbMATH DE number 1746563 (Why is no real title available?)
- KD is nullary
- DECIDABILITY OF ADMISSIBILITY: ON A PROBLEM BY FRIEDMAN AND ITS SOLUTION BY RYBAKOV
- The complexity of admissible rules of Łukasiewicz logic
- Logic of Visibility, Perception, and Knowledge and Admissible Inference Rules
- Preservation of admissible rules when combining logics
- Proof complexity of non-classical logics
- Rules admissible in transitive temporal logic \(\mathrm{T}_{\mathrm{S}4}\), sufficient condition
- Admissible rules in the implication-negation fragment of intuitionistic logic
- Universal proof theory: feasible admissibility in intuitionistic modal logics
- Investigating definability in propositional logic via sheaves on Grothendieck topologies
- On the universal theory of the free pseudocomplemented distributive lattice
- Undecidability of admissibility in the product of two \textbf{Alt} logics
- Unification in linear temporal logic LTL
- About the unification type of modal logics between \(\mathbf{KB}\) and \(\mathbf{KTB} \)
This page was built for publication: Complexity of admissible rules
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868660)
