Implicational Relevance Logic is 2-ExpTime-Complete

Sylvain Schmitz 1, 2, *
* Corresponding author
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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01076698
Contributor : Sylvain Schmitz <>
Submitted on : Wednesday, October 22, 2014 - 6:51:50 PM
Last modification on : Tuesday, February 5, 2019 - 1:46:02 PM

Links full text

Identifiers

Collections

Citation

Sylvain Schmitz. Implicational Relevance Logic is 2-ExpTime-Complete. Joint 25th International Conference on Rewriting Techniques and Applications and 12th International Conference on Typed Lambda Calculi and Applications, Jul 2014, Vienna, Austria. pp.395--409, ⟨10.1007/978-3-319-08918-8_27⟩. ⟨hal-01076698⟩

Share

Metrics

Record views

230