Serge GRIGORIEFF                     Last update: March 23th 2016
Cool   Professor emeritus, Université Paris VII Denis Diderot
  Member of the IRIF (Institut de Recherche en Informatique Fondamentale)
                                  (team "Automates et Applications")

    Office: IRIF - Bureau 427, 4e étage   Bâtiment Sophie Germain   75013 PARIS
Address: IRIF     Université Paris Diderot   Case 7014   75205   Paris Cedex 13
  Phone: 01 57 27 94 41   (33 1 57 27 94 41 from abroad)
  E-mail: seg[at]irif.univ-paris-diderot.fr

  Mathematical genealogy     DBLP Bibliography  

 Publications             Slides of talks
  Computability and (genuine) theory of algorithms
  Topology and computer science
  Automata and rational relations
  Randomness
  Kolmogorov complexity
  Impredicativity "à la Poincaré"
  Number Theory
  Definability and decidability in logical theories
  Set theory     (long time ago...)

Publications (thematically ordered)

Computability and (genuine) theory of algorithms

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]
Register Cellular Automata in the Hyperbolic Plane
(with Maurice Margenstern). Fundamenta Informaticae, 61(1):19--27, 2004. [ps], [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]

Topology and computer science

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]

Automata and rational relations

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]
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* × 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]

Randomness

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 and halting probabilities
(with Verónica Becher, Santiago Figueira, Joseph S. Miller). Journal of Symbolic Logic, 71(4):1411--1430, 2006.
[pdf], [UpDate]
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]

Kolmogorov complexity

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]
Kolmogorov complexity and non determinism
(with Jean-Yves Marion). Theoretical Computer Science, 271:151--180, 2002. [ps], [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]

Number Theory

Characterizing congruence preserving functions Z/nZ → Z/mZ via rational polynomials
(with Patrick Cégielski, Irène Guessarian).
To appear in Integers [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]
On lattices of regular sets of natural integers closed under decrementation
(with Patrick Cégielski, Irène Guessarian).
Information Processing Letters, 114(4):197--202; March 2014. [pdf]

Definability and decidability in logical theories

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]
Logical theory of the additive monoid of subsets of natural integers
(with Christian Choffrut). Automata, universality, computation. Tribute to Maurice Margenstern, editor: Andrew Adamatsky, 39--74, 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]

Set theory         (long time ago...)

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).

Slides of talks

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]