Implicational Relevance Logic is 2-ExpTime-Complete - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue The Journal of Symbolic Logic Année : 2016

Implicational Relevance Logic is 2-ExpTime-Complete

Sylvain Schmitz
Laboratoire Spécification et Vérification [Cachan]
Verification in databases
CV

Résumé

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.

Domaines

Logique en informatique [cs.LO]

Sylvain Schmitz  : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-01340113

Soumis le : jeudi 30 juin 2016-14:04:43

Dernière modification le : vendredi 24 mars 2023-14:53:02

Consulter le texte intégral

Dates et versions

hal-01340113 , version 1 (30-06-2016)

Identifiants

Citer

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⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS INRIA ENS-CACHAN INRIA2 UNIV-PARIS-SACLAY ANR ENS-PARIS-SACLAY GS-COMPUTER-SCIENCE
64 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More