Christian Choffrut; Loïc Colson

RAIRO - Theoretical Informatics and Applications (2008)

  • Volume: 42, Issue: 1, page 1-4
  • ISSN: 0988-3754

How to cite


Choffrut, Christian, and Colson, Loïc. "Preface." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 1-4. <>.

author = {Choffrut, Christian, Colson, Loïc},
journal = {RAIRO - Theoretical Informatics and Applications},
language = {eng},
month = {1},
number = {1},
pages = {1-4},
publisher = {EDP Sciences},
title = {Preface},
url = {},
volume = {42},
year = {2008},

AU - Choffrut, Christian
AU - Colson, Loïc
TI - Preface
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/1//
PB - EDP Sciences
VL - 42
IS - 1
SP - 1
EP - 4
LA - eng
UR -
ER -


  1. Random reals “à la Chaitin” with no prefix-freeness (with V. Becher), submitted.  
  2. From index sets to randomness in ∅n (Random reals and possibly infinite computations – Part II) (with V. Becher), submitted.  Zbl1163.03023
  3. Random reals and halting probabilities (with V. Becher, S. Figueira and J.S. Miller).  
  4. Random reals and possibly infinite computations – Part I: randomness in ∅ (with V. Becher). J. Symbolic Logic70 (2005) 891–913.  Zbl1089.03037
  5. Is randomness native to computer science? (with M. Ferbus), Curr. Trends Theor. Comput. Sci.2 (2004) 141–179. Preliminary version in Bull. EATCS74 (2001) 78–118.  
  6. Kolmogorov complexities Kmin, Kmax on computable partially ordered sets (with M. Ferbus). Theor. Comput. Sci.352 (2006) 159–180.  
  7. Kolmogorov complexity and set theoretical representations of integers (with M. Ferbus). Math. Logic Quart.52 (2006) 381–409.  
  8. Kolmogorov complexity and non determinism (with J.-Y. Marion). Theor. Comput. Sci.271 (2002) 151–180.  
  9. Logics for finite words on infinite alphabets (with C. Choffrut), submitted.  
  10. Decision problems among the main subfamilies of rational relations (with C. Choffrut and O. Carton). RAIRO-Theor. Inf. Appl.40 (2006) 255–275.  
  11. Separability of rational relations in A* x Nm by recognizable relations is decidable (with C. Choffrut). Inform. Process. Lett.99 (2006) 27–32.  
  12. Modelization of deterministic rational relations. Theor. Comput. Sci.281 (2002) 423–453.  Zbl0997.68072
  13. The theory of rational relations on transfinite strings (with C. Choffrut), in Words, Languages and Combinatorics III (Kyoto, March 2000), World Scientific (2004) 103–151.  
  14. Uniformization of rational relations (with C. Choffrut), in Jewels are forever, book in honor of Arto Salomaa, Springer (1999) 59–71.  
  15. Every recursive linear ordering has an isomorphic copy in DTIME-SPACE (n, log(n)). J. Symbolic Logic55 (1990) 260–276.  Zbl0708.03015
  16. Synchronization of a bounded degree graph of cellular automata with non uniform delays in time DlogmD. Theor. Comput. Sci.356 (2006) 170–185.  
  17. Register cellular automata in the hyperbolic plane (with M. Margenstern). Fund. Inform.61 (2004) 19–27.  
  18. Syntactical truth predicates for second order arithmetic (with L. Colson). J. Symbolic Logic66 (2001) 225–256.  Zbl0978.03044
  19. La théorie élémentaire de la fonction de couplage de Cantor des entiers naturels est décidable (with P. Cégielski and D. Richard). C. R. Acad. Sci. Sér. 1 331 (2000) 107–110.  
  20. Décidabilité et complexité des théories logiques. Collection Didactique INRIA8 (1991) 7–97.  
  21. Contribution à l'étude d'une conjecture de théorie des nombres par le codage ZBV (with Denis Richard). Enseign. Math.35 (1989) 125–189.  Zbl0685.03039
  22. Recursion and topology on 2≤ω for possibly infinite computations (with V. Becher). Theor. Comput. Sci.322 (2004) 85–136.  
  23. Intermediate submodels and generic extensions in set theory. Ann. Math.101 (1975) 447–490.  Zbl0308.02060
  24. Modéles intermédiaires et extensions génériques. C. R. Acad. Sci.276 (1973) 1635–1638.  Zbl0258.02059
  25. Minimalité des réels définis par forcing sur des familles d'arbres de suites finies d'entiers. C. R. Acad. Sci.281 (1975) 301–304.  Zbl0316.02062
  26. Combinatorics on ideals and forcing. Ann Math. Logic3 (1971) 363–394.  Zbl0328.02041
  27. Problème de la minimalité des réels définis par forcing à partir d'un ultrafiltre. C. R. Acad. Sci.270 (1970) 169–172.  Zbl0188.02003
  28. Détermination des jeux boréliens et problèmes logiques associés. Sém. Bourbaki478 (1976) 1–14.  
  29. La non-contradiction relative de l'axiome de Martin. Publ. Math. Univ. Paris VII5 (1979) 61–74. Séminaire GMS (Grigorieff, McAloon, Stern).  
  30. Le réel 0#&gt;. Publ. Math. Univ. Paris VII5 (1979) 149–162. Séminaire GMS (Grigorieff, McAloon, Stern).  
  31. 0# et les injections élémentaires de L dans L. Publ. Math. Univ. Paris VII5 (1979) 163–202. Séminaire GMS (Grigorieff, McAloon, Stern).  

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.