A System of Interaction and Structure III: The Complexity of BV and Pomset Logic
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929241312985088 |
|---|---|
| author | Nguyên, Lê Thành Dũng Straßburger, Lutz |
| author_facet | Nguyên, Lê Thành Dũng Straßburger, Lutz |
| contents | Pomset logic and BV are both logics that extend multiplicative linear logic (with Mix) with a third connective that is self-dual and non-commutative. Whereas pomset logic originates from the study of coherence spaces and proof nets, BV originates from the study of series-parallel orders, cographs, and proof systems. Both logics enjoy a cut-admissibility result, but for neither logic can this be done in the sequent calculus. Provability in pomset logic can be checked via a proof net correctness criterion and in BV via a deep inference proof system. It has long been conjectured that these two logics are the same.
In this paper we show that this conjecture is false. We also investigate the complexity of the two logics, exhibiting a huge gap between the two. Whereas provability in BV is NP-complete, provability in pomset logic is $Σ_2^p$-complete. We also make some observations with respect to possible sequent systems for the two logics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_07825 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A System of Interaction and Structure III: The Complexity of BV and Pomset Logic Nguyên, Lê Thành Dũng Straßburger, Lutz Logic in Computer Science Pomset logic and BV are both logics that extend multiplicative linear logic (with Mix) with a third connective that is self-dual and non-commutative. Whereas pomset logic originates from the study of coherence spaces and proof nets, BV originates from the study of series-parallel orders, cographs, and proof systems. Both logics enjoy a cut-admissibility result, but for neither logic can this be done in the sequent calculus. Provability in pomset logic can be checked via a proof net correctness criterion and in BV via a deep inference proof system. It has long been conjectured that these two logics are the same. In this paper we show that this conjecture is false. We also investigate the complexity of the two logics, exhibiting a huge gap between the two. Whereas provability in BV is NP-complete, provability in pomset logic is $Σ_2^p$-complete. We also make some observations with respect to possible sequent systems for the two logics. |
| title | A System of Interaction and Structure III: The Complexity of BV and Pomset Logic |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2209.07825 |