Implicational Relevance Logic is 2-ExpTime-Complete

Sylvain Schmitz 1, 2, *
* Auteur correspondant
1 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 :
Communication dans un congrès
Gilles Dowek. Joint 25th International Conference on Rewriting Techniques and Applications and 12th International Conference on Typed Lambda Calculi and Applications, Jul 2014, Vienna, Austria. Springer, 8560, pp.395--409, Lecture Notes in Comptuer Science. 〈10.1007/978-3-319-08918-8_27〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01076698
Contributeur : Sylvain Schmitz <>
Soumis le : mercredi 22 octobre 2014 - 18:51:50
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14

Lien texte intégral

Identifiants

Collections

Citation

Sylvain Schmitz. Implicational Relevance Logic is 2-ExpTime-Complete. Gilles Dowek. Joint 25th International Conference on Rewriting Techniques and Applications and 12th International Conference on Typed Lambda Calculi and Applications, Jul 2014, Vienna, Austria. Springer, 8560, pp.395--409, Lecture Notes in Comptuer Science. 〈10.1007/978-3-319-08918-8_27〉. 〈hal-01076698〉

Partager

Métriques

Consultations de la notice

165