Skip to Main content Skip to Navigation
New interface
Journal articles

Implicational Relevance Logic is 2-ExpTime-Complete

Sylvain Schmitz 1, 2 
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], Inria Saclay - Ile de France
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 metadata
Contributor : Sylvain Schmitz Connect in order to contact the contributor
Submitted on : Thursday, June 30, 2016 - 2:04:43 PM
Last modification on : Friday, July 8, 2022 - 10:09:42 AM

Links full text



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



Record views