Implicational Relevance Logic is 2-ExpTime-Complete

Sylvain Schmitz 1, 2
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We show that provability in the implicational fragment of relevance logic is complete for doubly exponential time, using reductions to and from coverability in branching vector addition systems.
Type de document :
Article dans une revue
The Journal of Symbolic Logic, Association for Symbolic Logic, 2016, 81 (2), pp.641--661. 〈10.1017/jsl.2015.7〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01340113
Contributeur : Sylvain Schmitz <>
Soumis le : jeudi 30 juin 2016 - 14:04:43
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14

Lien texte intégral

Identifiants

Citation

Sylvain Schmitz. Implicational Relevance Logic is 2-ExpTime-Complete. The Journal of Symbolic Logic, Association for Symbolic Logic, 2016, 81 (2), pp.641--661. 〈10.1017/jsl.2015.7〉. 〈hal-01340113〉

Partager

Métriques

Consultations de la notice

136