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

DOI10.1007/978-3-540-74915-8_33zbMATH Open1179.03063OpenAlexW1810039454MaRDI QIDQ3608429FDOQ3608429

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

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

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• 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)