Paper: Correctness of Multiplicative Additive Proof Structures is NL-Complete (at LICS 2008)

Authors: Paulin Jacobé de Naurois Virgile Mogbil

Abstract

We revisit the correctness criterion for the multiplicative additive fragment of linear logic. We prove that deciding the correctness of corresponding proof structures is NL-complete.

BibTeX

  @InProceedings{deNauroisMogbil-CorrectnessofMultip,
    author = 	 {Paulin Jacobé de Naurois and Virgile Mogbil},
    title = 	 {Correctness of Multiplicative Additive Proof Structures is NL-Complete},
    booktitle =  {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)},
    year =	 {2008},
    month =	 {June}, 
    pages =      {476--485},
    location =   {Pittsburgh, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }