Introduction. Calculabilité, le quoi et le comment
Anthologie de la calculabilité.
Naissance et développements de la théorie de la calculabilité
des années 1920 à 1970.
Michel Bourdeau,
Jean Mosconi,
editors.
79 pages (in French).
To appear.
Functionals using Bounded Information
and the Dynamics of Algorithms
(with
Pierre Valarcher).
LICS 2012.
[pdf]
Classes of Algorithms: Formalization and Comparison
(with
Pierre Valarcher).
Bulletin EATCS, June 2012.
[pdf]
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]
Informatique théorique : calculabilité, décidabilité et logique
Informatique théorique : complexité, automates et au-delà
(with
Olivier Bournez,
Gilles Dowek,
Rémi Gilleron,
Jean-Yves Marion,
Simon Perdrix,
Sophie Tison).
L'intelligence artificielle : frontières et applications.
Volume 3, chapters 1 and 2, 989--1029 and 1031--1065 (in French).
Pierre Marquis,
Odile Papini,
Henri Prade,
editors.
Cépaduès publisher, 2014.
[pdf]
Synchronization of a bounded degree graph of cellular automata
with non uniform delays in time D logmD
Theoretical Computer Science, 356:170--185, 2006.
[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]
Borel and Hausdorff Hierarchies in Topological Spaces of Choquet Games
and their Effectivization
(with
Verónica Becher).
Mathematical Structures in Computer Science, 25(07):1490--1519, October 2015.
[pdf]
Wadge Hardness in Scott Spaces and its Effectivization
(with
Verónica Becher).
Mathematical Structures in Computer Science, 25(07):1520--1545, October 2015.
[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]
Recursion and topology on 2≤ω
for possibly infinite computations
(with
Verónica Becher).
Theoretical Computer Science, 322:85--136, 2004.
[pdf]
Rational relations having a rational trace on each finite intersection of rational relations
(with
Christian Choffrut).
Theoretical Computer Science, 454:88--94, 2012.
[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``equal last letter" predicate for words on infinite alphabets
and classes of multitape automata
(with
Christian Choffrut).
Theoretical Computer Science, 410(30-32):2870--2884, 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]
Separability of rational relations
in A* × Nm 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]
Random reals and possibly infinite computations - Part I:
randomness in Ø'
(with
Verónica Becher).
Journal of Symbolic Logic, 70(3):891--913, 2005.
[pdf]
From index sets to randomness in Øn
(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]
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]
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]
Kolomogorov complexity in perspective: information theory and randomness
(with Marie Ferbus).
Constructivity and computability in historical and philosophical perspective.
Logic, Epistemology and the unity of science 34:57--94,
Jacques Dubucs,
Michel Bourdeau editors, 2014.
[pdf]
Kolmogorov complexities Kmin , Kmax
on computable partially ordered sets
(with Marie Ferbus).
Theoretical Computer Science, 352(1-3):159--180, 2006.
[pdf]
Kolmogorov complexity and set theoretical representations
of integers
(with Marie Ferbus).
Math. Logic Quarterly, 52(4):381--409, 2006.
[pdf]
Impredicativity "à la Poincaré"
Syntactical truth predicates and second order arithmetic
(with Loïc Colson).
Journal of Symbolic Logic, 66(1):225--256; March 2001.
[pdf]
Arithmetical Congruence Preservation: From Finite to Infinite
(with
Patrick Cégielski,
Irène Guessarian).
Fields of Logic and Computation II.
Lecture Notes in Computer Science 9300:210--225, 2015.
[pdf]
Integral Difference Ratio Functions on Integers
(with
Patrick Cégielski,
Irène Guessarian).
Computing with New Resources.
Lecture Notes in Computer Science 8808:277--291, December 2014.
[pdf]
Newton representation of functions over natural integers having integral difference ratios
(with
Patrick Cégielski,
Irène Guessarian).
International Journal of Number Theory 11(7):2109--2139, 2015.
[pdf]
Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations
(with
Christian Choffrut).
Fields of Logic and Computation II,
Lecture Notes in Computer Science 9300:109--128, 2015.
[pdf]
Theory of the Monoid of Languages over a Non Tally Alphabet
(with
Christian Choffrut).
Fundamenta Informaticae, 138(1-2):159--177, 2015.
[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.
[pdf]
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).
Arithmetical congruence preserving functions
YuriFest 2015,
Berlin, September 11, 2015
[pdf]
Emergence des modèles du concept de calculabilité
Séminaire Epistémologie et histoire des idees mathématiques;
(responsable
Michel Serfati),
Paris, March 11, 2015
[pdf]
Quasi-Polish Spaces and Choquet Games
Topology and Informatic Days;
LIAFA, Université Paris-Diderot, March 21, 2013
[pdf]
Bounded information functionals and the dynamics of algorithms
LICS 2012; Dubrovnik (Croatia), June 26, 2012
[pdf]
A remaining issue after Turing's work:
formalize the notion of algorithm
Colloquium Polaris, Université Lille 1 & Inria, May 31, 2012
[pdf]
Borel determinacy
Groupe de travail
"Calculabilité, Complexité & Hasard",
LIAFA, Université Paris-Diderot, April 12 & 18, 2012
[pdf]