Correctness of Multiplicative (and Exponential) Proof Structures is NL-Complete

DOI10.1007/978-3-540-74915-8_33MaRDI QIDQ3608429zbMATH OpenOpenAlexFDO

Authors Paulin Jacobé de Naurois, Virgile Mogbil

Publication date 5 March 2009

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74915-8_33

Mathematics Subject Classification ID

Structure of proofs (03F07) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Recommendations

• Correctness of linear logic proof structures is NL-complete
• A new correctness criterion for the proof nets of non-commutative multiplicative linear logics
• A new correctness criterion for multiplicative non-commutative proof nets
• Minimality of the correctness criterion for multiplicative proof nets
• A linear algorithm for MLL proof net correctness and sequentialization

Cited in

(9)

• Fast verification of MLL proof nets via IMLL
• A linear algorithm for MLL proof net correctness and sequentialization
• Correctness of linear logic proof structures is NL-complete
• On the decision problem for MELL
• A matrix characterization for multiplicative exponential linear logic
• Minimality of the correctness criterion for multiplicative proof nets
• scientific article; zbMATH DE number 786498 (Why is no real title available?)
• Proof nets for multiplicative cyclic linear logic and Lambek calculus
• Rewritings for polarized multiplicative and exponential proof structures

This page was built for publication: Correctness of Multiplicative (and Exponential) Proof Structures is NL-Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608429)