A New Correctness Criterion for the Proof Nets of Non-Commutative Multiplicative Linear Logics

Nagayama, Misao; Okada, Mitsuhiro

J. Symbolic Logic, Tome 66 (2001) no. 1, p. 1524-1542 / Harvested from Project Euclid

Résumé

This paper presents a new correctness criterion for marked Danos-Reginer graphs (D-R graphs, for short) of Multiplicative Cyclic Linear Logic MCLL and Abrusci's non-commutative Linear Logic MNLL. As a corollary we obtain an affirmative answer to the open question whether a known quadratic-time algorithm for the correctness checking of proof nets for MCLL and MNLL can be improved to linear-time.

Publié le : 2001-12-14
Classification:

@article{1183746610,
     author = {Nagayama, Misao and Okada, Mitsuhiro},
     title = {A New Correctness Criterion for the Proof Nets of Non-Commutative Multiplicative Linear Logics},
     journal = {J. Symbolic Logic},
     volume = {66},
     number = {1},
     year = {2001},
     pages = { 1524-1542},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746610}
}

Nagayama, Misao; Okada, Mitsuhiro. A New Correctness Criterion for the Proof Nets of Non-Commutative Multiplicative Linear Logics. J. Symbolic Logic, Tome 66 (2001) no. 1, pp.  1524-1542. http://gdmltest.u-ga.fr/item/1183746610/