Complexity of correctness for pomset logic proof nets

Abstract

We show that it is coNP-complete to decide whether a given proof structure of pomset logic is a correct proof net, using the graph-theoretic used in a previous paper of ours (arXiv:1901.10247).

Fully subsumed by arXiv:2209.07825 (which contains a lot more material and has an additional coauthor)

References in corpus (2)

• On noncommutative extensions of linear logic
• Constrained path-finding and structure from acyclicity

Cited by in corpus (1)

• Unique perfect matchings, forbidden transitions and proof nets for linear logic with Mix