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.
Document type :
Journal articles
Complete list of metadatas
Contributor : Sylvain Schmitz <>
Submitted on : Thursday, June 30, 2016 - 2:04:43 PM
Last modification on : Thursday, February 7, 2019 - 5:29:33 PM

Links full text



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⟩



Record views