Complexity of correctness for pomset logic proof nets

2019/12/23 by Lê Thành Dũng Nguyễn, Nguyên, Lê Thành Dũng
Computer Science · #Logic, programming, and type systems #Formal Methods in Verification #Advanced Database Systems and Queries

paper · pdf · doi:10.48550/arxiv.1912.10606

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).

Cited by

• Constrained path-finding and structure from acyclicity

Related

• A System of Interaction and Structure III: The Complexity of BV and Pomset Logic
• On paths-based criteria for polynomial time complexity in proof-nets
• On the role of connectivity in Linear Logic proofs
• Abstract p-time proof nets for MALL: Conflict nets
• MALL proof equivalence is Logspace-complete, via binary decision diagrams