Publications (thematically ordered)

ASMs and Operational Algorithmic Completeness of Lambda Calculus
(with Marie Ferbus). Fields of Logic and Computation, Lecture Notes in Computer Science 6300:301--327, Nachum Dershowitz, Wolfgang Reisig editors, Springer, 2010. [pdf]

Evolving Multialgebras Unify All Usual Sequential Computation Models
(with Pierre Valarcher). STACS 2010, 301--327, Jean-Yves Marion, Thomas Schwentick, editors. Springer, 2010. [pdf]

Synchronization of a bounded degree graph of cellular automata with non uniform delays in time D log_mD
Theoretical Computer Science, 356:170--185, 2006. [pdf]

Register Cellular Automata in the Hyperbolic Plane
(with Maurice Margenstern). Fundamenta Informaticae, 61(1):19--27, 2004. [ps], [pdf]

Recursion and topology on 2^≤ω for possibly infinite computations
(with Verónica Becher). Theoretical Computer Science, 322:85--136, 2004. [pdf]

Every recursive linear ordering has an isomorphic copy in DTIME-SPACE(n,log(n))
Journal of Symbolic Logic, 55(1):260--276, March 1990. [pdf]

Is Randomness native to Computer Science? Ten Years Later
(with Marie Ferbus). Randomness Through Computation: Some Answers, More Questions, 243--263, Hector Zenil editor, World Scientific, 2011. [pdf], [Update]

From index sets to randomness in Øⁿ
(Random reals and possibly infinite computations - Part II)
(with Verónica Becher). Journal of Symbolic Logic, 74(1):124--156, March 2009. [pdf],

Random reals "à la Chaitin" with or without prefix-freeness
(with Verónica Becher). Theoretical Computer Science, 385(1-3):193--201, 2007. [pdf], [UpDate]

Random reals and halting probabilities
(with Verónica Becher), Santiago Figueira, Joseph S. Miller). Journal of Symbolic Logic, 71(4):1411--1430, 2006.
Download [pdf], [UpDate]

Random reals and possibly infinite computations - Part I: randomness in Ø'
(with Verónica Becher). Journal of Symbolic Logic, 70(3):891--913, 2005. [pdf]

Is Randomness native to Computer Science?
(with Marie Ferbus). Current Trends in Theoretical Computer Science, vol.2, 141--179, 2004.
Preliminary version in Bulletin EATCS, 74:78--118, June 2001. [pdf]

Kolmogorov complexities K_min , K_max on computable partially ordered sets
(with Marie Ferbus). Theoretical Computer Science, 352:159--180, 2006. [pdf]

Kolmogorov complexity and set theoretical representations of integers
(with Marie Ferbus). Math. Logic Quarterly, 52(4):381--409, 2006. [pdf]

Kolmogorov complexity and non determinism
(with Jean-Yves Marion). Theoretical Computer Science, 271:151--180, 2002. [ps], [pdf]

A Topological Approach to Recognition
(with Mai Gehrke, Jean-Eric Pin).
ICALP 2010. Lecture Notes in Computer Science 6199:151--162, Springer, 2010. [pdf]

Duality and equational theory of regular languages
(with Mai Gehrke, Jean-Eric Pin). Best paper award of ICALP 2008, Track B.
Lecture Notes in Computer Science 5126:246--257, Springer, 2008. [pdf]

Finite n-tape automata over possibly infinite alphabets: extending a theorem of Eilenberg et al.
(with Christian Choffrut). Theoretical Computer Science, 410(1):16--34, 2009. [pdf]

The decision problem for some logics for finite words on infinite alphabets
(with Christian Choffrut). Zapiski Nauchnyh Seminarov POMI (Notes of scientific seminars of POMI).
"Studies in Constructive Mathematics and Mathematical Logic. Part XI" (special volume dedicated to Yuri Matiyasevich's 60th birthday), editor M.A. Vsemirnov, 358:100--119, 2008. [pdf]

Decision problems among the main subfamilies of rational relations
(with Christian Choffrut, Olivier Carton). RAIRO-Informatique Théorique et Applications 40:255--275, 2006. [pdf]

Separability of rational relations in A* × N^m by recognizable relations is decidable
(with Christian Choffrut). Information Processing Letters 99:27--32, 2006. [pdf]

Modelization of deterministic rational relations
Theoretical Computer Science, 281:423--453, 2002. [ps], [pdf]

The theory of rational relations on transfinite strings
(with Christian Choffrut). In "Words, Languages and Combinatorics III (Kyoto, March 2000)", World Scientific, p.103--151, 2004. [pdf]

Uniformization of rational relations
(with Christian Choffrut). In "Jewels are forever", book in honor of Arto Salomaa, Springer, p.59--71, 1999. [pdf]

Syntactical truth predicates and second order arithmetic
(with Loïc Colson). Journal of Symbolic Logic, 66(1):225--256; March 2001. [pdf]

La théorie élémentaire de la fonction de couplage de Cantor des entiers naturels est décidable
(with Patrick Cégielski, Denis Richard). Comptes Rendus de l'Académie des Sciences, série 1, 331:107-110, 2000. [pdf]

Décidabilité et complexité des théories logiques
Collection Didactique, 8:7--97, INRIA, 1991.

Contribution a l'étude d'une conjecture de théorie des nombres par le codage ZBV
(with Denis Richard). L'Enseignement Mathématique, 35:125--189, 1989. [pdf]

Intermediate submodels and generic extensions in set theory
Annals of Mathematics, 101(3):447--490, May 1975. [pdf]

Combinatorics on ideals and forcing
Annals of Mathematical Logic, 3(4):363--394, 1971. [pdf]

Détermination des jeux boréliens et problèmes logiques associés
Séminaire Bourbaki, 478:1-14, 1976. [pdf]

Modèles intermédiaires et extensions génériques
Comptes Rendus de l'Académie des Sciences, 276:1635-1638, 1973.

Minimalité des réels définis par forcing sur des familles d'arbres de suites finies d'entiers
Comptes Rendus de l'Académie des Sciences, 281:301-304, 1975.

Problème de la minimalité des réels définis par forcing à partir d'un ultrafiltre
Comptes Rendus de l'Académie des Sciences, 270:169-172, 1970. [pdf]

La non-contradiction relative de l'axiome de Martin
Publications mathématiques Université Paris VII, 5:61-74, 1979. Séminaire GMS (Grigorieff, McAloon, Stern).

Le réel 0^#
Publications mathématiques Université Paris VII, 5:149-162, 1979. Séminaire GMS (Grigorieff, McAloon, Stern).

0^# et les injections élémentaires de L dans L
Publications mathématiques Université Paris VII, 5:163-202, 1979. Séminaire GMS (Grigorieff, McAloon, Stern).