Serge GRIGORIEFF
Cool   Professor emeritus - Université Paris VII Denis Diderot
  Member of the LIAFA (Laboratoire d'Informatique Algorithmique: Fondements et Applications)
                                  (team "Automates et Applications")




    Office: LIAFA - Bureau 7A29, 7e étage   175 rue du Chevaleret   75013 PARIS
Address: LIAFA     Université Paris Diderot   Case 7014   75205   Paris Cedex 13
  Phone: 01 44 27 45 19   (33 1 44 27 45 19 from abroad)
  E-mail: seg[at]liafa.univ-paris-diderot.fr

Publications (thematically ordered)

Computability and (genuine) theory of algorithms

Functionals using Bounded Information and the Dynamics of Algorithms
(with Pierre Valarcher). LICS 2012.
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]
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]
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]

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

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]

Profinite words

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]

Automata and rational relations

Rational relations having a rational trace on each finite intersection of rational relations
(with Christian Choffrut). Theoretical Computer Science, in press, 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]

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]

Definability and decidability in logical theories

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


Last update: May 21st, 2012