Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T02:13:36.775Z Has data issue: false hasContentIssue false

IMPLICATIONAL RELEVANCE LOGIC IS 2-EXPTIME-COMPLETE

Published online by Cambridge University Press:  22 January 2016

SYLVAIN SCHMITZ*
Affiliation:
ENS CACHAN & INRIA FRANCE E-mail: schmitz@lsv.ens-cachan.fr URL: http://www.lsv.ens-cachan.fr/∼schmitz
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2016