NO CoST project
New tools for complexity: semantics and types
Nouveaux outils pour la complexité : sémantique et types

Navigation

Publications and reports

Latest addition : Thursday 28 September 2006. (English|français)

This section's articles

Thesis


-  Vincent Rahli. Réseaux de preuves et circuits booléens (Proof-nets and boolean circuits) . Master Thesis (MPRI), supervised by Virgile Mogbil, LIPN, 93 pp., in French, September 2006.

-  Patrick Baillot. Linear Logic, Types and Implicit Computational Complexity . Habilitation à diriger les recherches (HdR) en informatique, March 2008, Université Paris 13. See web page]


Prepublications


-  Poster: V. Atassi, P. Baillot, P. Boudes, P. Jacobé de Naurois, V. Mogbil, J.-Y. Moyen. Complexité implicite : des méthodes logiques et sémantiques pour garantir le temps de calcul, available as document below, Workshop for the 20th anniversary of LIPN, Université Paris 13, 16-17/11/2006.

-  Patrick Baillot, Ugo Dal Lago, Jean-Yves Moyen. On Quasi-Interpretations, Blind Abstractions and Implicit Complexity. preprint HAL ccsd-00023668, 23 pp., May 3 2006.

See Baillot’s publications page.

-  Vincent Atassi , Patrick Baillot, Kazushige Terui. Verification of Ptime reducibility for system F terms via Dual Light Affine Logic. preprint arXiv cs.LO/0603104 and HAL ccsd-00021834, march 2006.

See Baillot’s publications page.

-  Jean-Yves Moyen. Resource control graphs. preprint hal-00107145, october 2006. http://hal.archives-ouvertes.fr/ccs....

-  Daniel de Carvalho, Michele Pagani, Lorenzo Tortora De Falco, A semantic measure of the exectution time in linear logic.

See page

-  Patrick Baillot, Damiano Mazza. Linear Logic by Levels and Bounded Time Complexity. 49 pages, 12/2007, preprint arXiv:0801.1253.

See Baillot’s publications page.


Publications


-  Paulin Jacobé de Naurois. A Measure of Space for Computing over the Reals. Proceedings of Computability In Europe 2006, volume 3988 of LNCS, pp. 231-240, Springer, 2006.

See the home page of Jacobé de Naurois.

-  Ugo Dal Lago and Patrick Baillot. On Light Logics, Uniform Encodings and Polynomial Time. Mathematical Structures in Computer Science, 16(4):713-733, 2006.

See Baillot’s publications page.

-  Olivier Laurent and Lorenzo Tortora de Falco. Obsessional cliques: a semantic characterization of bounded time complexity. Proceedings of the twenty-first annual IEEE symposium on Logic In Computer Science (LICS ’06). IEEE Computer Society Press, August 2006.

See Laurent’s home page.

-  Vincent Atassi , Patrick Baillot, Kazushige Terui. Verification of Ptime reducibility for system F terms via Dual Light Affine Logic. in Proceedings of Computer Science Logic 2006 (CSL’06), volume 4207 of LNCS, pp.150-166, Springer, 2006. (also preprint HAL ccsd-00021834 )

See publications page of Baillot.

-  Virgile Mogbil, Vincent Rahli. Uniform circuits, & Boolean proof nets. in Proceedings of the Symposium on Logical Foundations of Computer Science (LFCS’07), Lecture Notes in Computer Science 4514, pp. 401-421, Springer, New York, U.S.A., June 4 - 7 2007. also preprint LIPN hal-00122980.

See publications page of Mogbil.

-  Patrick Baillot, Paolo Coppola, Ugo Dal Lago. Light Logics and Optimal Reduction: Completeness and Complexity. in Proceedings of the twenty-second annual IEEE symposium on Logic In Computer Science (LICS ’07), pp 421—430, IEEE Computer Society Press,

See publications page of Baillot.

- Patrick Baillot. From Proof-Nets to Linear Logic Type Systems for Polynomial Time Computing. Invited talk. Proceedings of International Conference on Typed Lambda Calculi and Applications (TLCA’07), volume 4583 of LNCS, pp. 2-7, 2007. Springer.

See publications page of Baillot.

-  Damiano Mazza. Edifices and Full Abstraction for the Symmetric Interaction Combinators. In Proceedings of Typed Lambda Calculi and Applications (TLCA’07), LNCS 4583, pp. 305—320, Springer, 2007.

See publications page of Mazza.

-  Paulin Jacobé de Naurois and Virgile Mogbil. Correctness of multiplicative (and exponential) proof structures is NL-complete. in Proceedings of the 16th EACSL Annual Conference on Computer Science and Logic (CSL’07), Lecture Notes in Computer Science 4646, pp. 435-450, September 11-15 2007.

See publications page of Mogbil.

-  Vincent Atassi, Patrick Baillot, Kazushige Terui. Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic. Logical Methods in Computer Science, 3(4:10), pp.1—32, Special issue on CSL’06, 2007.

See page

-  Paulin Jacobé de Naurois, Virgile Mogbil. Correctness of Multiplicative Additive Proof Structures is NL-Complete. to appear in Proceedings of the annual IEEE symposium on Logic In Computer Science (LICS ’08), IEEE Computer Society Press

-  Jean-Yves Moyen. ’’Resource control graphs’’. to appear in ACM Transactions on Computer Logic, special issue on Implicit computational complexity.