Implicational Relevance Logic is 2-ExpTime-Complete

Sylvain Schmitz 1, 2, *
* Auteur correspondant
1 DAHU - Verification in databases
CNRS - Centre National de la Recherche Scientifique : UMR8643, Inria Saclay - Ile de France, ENS Cachan - École normale supérieure - Cachan, LSV - Laboratoire Spécification et Vérification [Cachan]
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 : mardi 5 février 2019 - 13:46:02

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

206