Implicational Relevance Logic is 2-ExpTime-Complete
Author: Sylvain Schmitz
Paper Information
| Title: | Implicational Relevance Logic is 2-ExpTime-Complete |
| Authors: | Sylvain Schmitz |
| Proceedings: | RTA-TLCA 2014 LNCS Proceedings |
| Editor: | Gilles Dowek |
| Keywords: | relevance logic, branching VASS, focusing proofs, complexity |
| Abstract: | 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. |
| Pages: | 15 |
| Talk: | Jul 14 10:45 |
| Paper: |  |