Computability over an Arbitrary Structure. Sequential and Parallel Polynomial Time. - Olivier Bournez; Felipe Cucker; Paulin Jacobé de Naurois; Jean-Yves Marion (FoSSaCS, 2003)

Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH. - Olivier Bournez; Felipe Cucker; Paulin Jacobé de Naurois; Jean-Yves Marion (ICC@LICS, 2003)

Tailoring Recursion to Characterize Non-Deterministic Complexity Classes over Arbitrary Structures. - Olivier Bournez; Felipe Cucker; Paulin Jacobé de Naurois; Jean-Yves Marion (IFIP TCS, 2004)

Completeness results and syntactic characterizations of complexity classes over arbitrary structures. (Résultats de complétude et caractérisations syntaxiques de classes de complexité sur des structures arbitraires). - Paulin Jacobé de Naurois (2004)

Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time. - Olivier Bournez; Felipe Cucker; Paulin Jacobé de Naurois; Jean-Yves Marion (J. Log. Comput., 2005)

A Measure of Space for Computing over the Reals. - Paulin Jacobé de Naurois (CiE, 2006)

The complexity of semilinear problems in succinct representation. - Peter Bürgisser; Felipe Cucker; Paulin Jacobé de Naurois (Comput. Complex., 2006)

Implicit complexity over an arbitrary structure: Quantifier alternations. - Olivier Bournez; Felipe Cucker; Paulin Jacobé de Naurois; Jean-Yves Marion (Inf. Comput., 2006)

Correctness of Multiplicative (and Exponential) Proof Structures is NL -Complete. - Paulin Jacobé de Naurois; Virgile Mogbil (CSL, 2007)

Correctness of Multiplicative Additive Proof Structures is NL-Complete. - Paulin Jacobé de Naurois; Virgile Mogbil (LICS, 2008)

Parallel Time and Quantifier Prefixes. - Felipe Cucker; Paulin Jacobé de Naurois (Comput. Complex., 2009)

Rewriting Systems for Reachability in Vector Addition Systems with Pairs. - Paulin Jacobé de Naurois; Virgile Mogbil (RP, 2010)

Correctness of linear logic proof structures is NL-complete. - Paulin Jacobé de Naurois; Virgile Mogbil (Theor. Comput. Sci., 2011)

Pointers in Recursion: Exploring the Tropics. - Paulin Jacobé de Naurois (DICE-FOPARA@ETAPS, 2019)

Parallelism in Soft Linear Logic. - Paulin Jacobé de Naurois (CSL, 2022)