Proof equivalence in MLL is PSPACE-complete

DOI10.2168/LMCS-12(1:2)2016zbMath1448.03050OpenAlexW1800613700MaRDI QIDQ2790165

Willem Heijltjes, Robin Houston

Publication date: 3 March 2016

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2168/lmcs-12(1:2)2016

zbMATH Keywords

linear logicproof netsPSPACE-completenessconstraint logicproof equivalence

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Related Items

Fixed-parameter algorithms for graph constraint logic, Unnamed Item, Combinatorial flows as bicolored atomic flows, Unnamed Item, Unnamed Item, Homomorphism Reconfiguration via Homotopy, Unnamed Item