PAULIN DE NAUROIS

Publications

Research reports:

Paulin Jacobé de Naurois: Coverability in a NonFunctional Extension of BVASS. 2014. (download .pdf)

Journals:

Paulin Jacobé de Naurois, Virgile Mogbil: Correctness of linear logic proof structures is NL-complete. Theor. Comput. Sci. 412(20): 1941-1957 (2011)
Felipe Cucker, Paulin Jacobé de Naurois: Parallel Time and Quantifier Prefixes. Computational Complexity 18(4): 527-550 (2009)
Peter Bürgisser, Felipe Cucker, Paulin Jacobé de Naurois: The complexity of semilinear problems in succinct representation. Computational Complexity 15(3): 197-235 (2006) (download .pdf)
O. Bournez, F. Cucker, P. Jacobé de Naurois and J.-Y.Marion, Implicit Complexity over an Arbitrary Structure: Quantifier Alternations. Information and Computation, Volume 204, Issue 2, February 2006, Pages 210-230. (download .pdf)
O. Bournez, F. Cucker, P. Jacobé de Naurois and J. -Y. Marion, Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time, Journal of Logic and Computations, Volume 15, February 2005, Pages 41 - 58. (download .pdf)

Conferences:

Paulin Jacobé de Naurois, Virgile Mogbil: Rewriting Systems for Reachability in Vector Addition Systems with Pairs. RP 2010: 133-145
P. Jacobé de Naurois and V. Mogbil, Correctness of Multiplicative Additive Proof Structures is NL-Complete. LICS, pages 476–485. IEEE Computer Society, 2008. (télécharger .pdf)
P. Jacobé de Naurois and V. Mogbil, Correctness of Multiplicative (and Exponential) Proof Structures is NL-Complete. CSL, volume 4646 of Lecture Notes in Computer Science, pages 435–450. Springer, 2007. (télécharger .pdf)
P. Jacobé de Naurois, A Measure of Space for Computing over the Reals. In A. Beckmann, U. Berger, B. Löwe and J.V. Tucker, editors, CIE 2006: Logical Approaches to Computational Barriers, volume 3988 of Lecture Notes in Computer Science, pages 231-240, Springer.(download .pdf)
P. Bürgisser, F. Cucker and P. Jacobé de Naurois, The complexity of semilinear sets in succinct representation (Extended Abstract). In Maciej Liskiewicz and Rüdiger Reischuk, editors 15th International Symposium on Fundamentals of Computation Theory (FCT) 2005, volume 3623 of Lecture Notes in Computer Science, pages 479-490, Springer. (download .pdf)
O. Bournez, F. Cucker, P. Jacobé de Naurois and J. -Y. Marion, Logical Characterizations of Pk and NPk over an Arbitrary Structure K. CIE 2005: New Computational Paradigms. (download .pdf)
O. Bournez, F. Cucker, P. Jacobé de Naurois and J. -Y. Marion, Tailoring Recursion to Characterize Non-Deterministic Complexity Classes over Arbitrary Structures. In J-J. Levy, E. W. Mayr and J. C. Mitchell, editors, "Exploring new Frontiers of Theoretical Informatics", proceedings of the 3rd International Conference on Theoretical Computer Science (TCS'04), Kluwer Academic Publishers, 2004. (download .pdf)
O. Bournez, F. Cucker, P. Jacobé de Naurois and J. -Y. Marion, Computability over an Arbitrary Structure. Sequential and Parallel Polynomial Time. In Andrew D. Gordon, editor, Foundations of Software Science and Computational Structures, 6th International Conference (FOSSACS'2003), volume 2620 of Lecture Notes in Computer Science, pages 185--199, Springer. (download .pdf)

Laboratoire d'Informatique de l'Université Paris Nord (LIPN)
UMR CNRS 7030
Institut Galilée - Université Paris-Nord
99, avenue Jean-Baptiste Clément
93430 Villetaneuse
France

Email:
Tel:	+ [33] 1 49 40 44 43