Publications

Modifié

23 février 2026

Preprints

  1. Jean-Michel Couvreur, Martin Delacourt, Nicolas Ollinger, Pierre Popoli, Jeffrey Shallit, and Manon Stipulanti. Effective Computation of Generalized Abelian Complexity for Pisot Type Substitutive Sequences, 2025

  2. Nicolas Ollinger and Jeffrey Shallit. The Repetition Threshold for Rote Sequences, 2024

Journal Articles

  1. Rodrigo Torres-Avilés, Anahí Gajardo, and Nicolas Ollinger. On relations between properties in transitive Turing machines. Nonlinearity, 36(12):6297, oct 2023

  2. Nicolas Ollinger and Guillaume Theyssier. Freezing, Bounded-Change and Convergent Cellular Automata. Discrete Mathematics & Theoretical Computer Science, 24(1):1–37, 2022

  3. Eric Goles, Diego Maldonado, Pedro Montealegre, and Nicolas Ollinger. On the complexity of the stability problem of binary freezing totalistic cellular automata. Information and Computation, 274:104535, 2020

  4. Julien Cassaigne, Nicolas Ollinger, and Rodrigo Torres-Avilés. A small minimal aperiodic reversible Turing machine. Journal of Computer and System Sciences, 84:288–301, 2017

  5. Anahı́ Gajardo, Nicolas Ollinger, and Rodrigo Torres-Avilés. Some undecidable problems about the trace-subshift associated to a Turing machine. Discrete Mathematics & Theoretical Computer Science, 17(2):267–284, 2015

  6. Marianne Delorme, Jacques Mazoyer, Nicolas Ollinger, and Guillaume Theyssier. Bulking I: an Abstract Theory of Bulking. Theoretical Computer Science, 412(30):3866–3880, 2011

  7. Marianne Delorme, Jacques Mazoyer, Nicolas Ollinger, and Guillaume Theyssier. Bulking II: Classifications of Cellular Automata. Theoretical Computer Science, 412(30):3881–3905, 2011

  8. Nicolas Ollinger and Gaétan Richard. Four states are enough! Theoretical Computer Science, 412(1–2):22–32, 2010

  9. Nicolas Ollinger and Gaétan Richard. Automata on the Plane vs Particles and Collisions. Theoretical Computer Science, 410(27–29):2767–2773, 2009

  10. Emmanuel Jeandel and Nicolas Ollinger. Playing with Conway’s Problem. Theoretical Computer Science, 409(3):557–564, 2008

  11. Christian Choffrut, Juhani Karhumäki, and Nicolas Ollinger. The commutation of finite sets: a challenging problem. Theoretical Computer Science, 273(1–2):69–79, 2002

Conference Papers

  1. Olivier Carton, Jean-Michel Couvreur, Martin Delacourt, and Nicolas Ollinger. Linear Recurrence Sequence Automata and the Addition of Abstract Numeration Systems. In Guilhem Gamard and Julien Leroy, editors, Combinatorics on Words - 15th International Conference, WORDS 2025, Nancy, France, June 30 - July 4, 2025, Proceedings, volume 15729 of Lecture Notes in Computer Science, pages 70–82. Springer, 2025

  2. Florent Becker, Diego Maldonado, Nicolas Ollinger, and Guillaume Theyssier. Universality in Freezing Cellular Automata. In Florin Manea, Russell G. Miller, and Dirk Nowotka, editors, Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30 - August 3, 2018, Proceedings, volume 10936 of Lecture Notes in Computer Science, pages 50–59. Springer, 2018

  3. Eric Goles, Diego Maldonado, Pedro Montealegre-Barba, and Nicolas Ollinger. Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata. In Giancarlo Mauri, Samira El Yacoubi, Alberto Dennunzio, Katsuhiro Nishinari, and Luca Manzoni, editors, Cellular Automata - 13th International Conference on Cellular Automata for Research and Industry, ACRI 2018, Como, Italy, September 17-21, 2018, Proceedings, volume 11115 of Lecture Notes in Computer Science, pages 406–415. Springer, 2018

  4. Nicolas Ollinger. On Aperiodic Reversible Turing Machines (Invited Talk). In Jarkko Kari and Irek Ulidowski, editors, Reversible Computation - 10th International Conference, RC 2018, Leicester, UK, September 12-14, 2018, Proceedings, volume 11106 of Lecture Notes in Computer Science, pages 61–64. Springer, 2018

  5. Martin Delacourt and Nicolas Ollinger. Permutive One-Way Cellular Automata and the Finiteness Problem for Automaton Groups. In Jarkko Kari, Florin Manea, and Ion Petre, editors, Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings, volume 10307 of Lecture Notes in Computer Science, pages 234–245. Springer, 2017

  6. Eric Goles, Diego Maldonado, Pedro Montealegre, and Nicolas Ollinger. On the Computational Complexity of the Freezing Non-strict Majority Automata. In Alberto Dennunzio, Enrico Formenti, Luca Manzoni, and Antonio E. Porreca, editors, Cellular Automata and Discrete Complex Systems - 23rd IFIP WG 1.5 International Workshop, AUTOMATA 2017, Milan, Italy, June 7-9, 2017, Proceedings, volume 10248 of Lecture Notes in Computer Science, pages 109–119. Springer, 2017

  7. Anahı́ Gajardo, Nicolas Ollinger, and Rodrigo Torres-Avilés. The Transitivity Problem of Turing Machines. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald Sannella, editors, Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I, volume 9234 of Lecture Notes in Computer Science, pages 231–242. Springer, 2015

  8. Bastien Le Gloannec and Nicolas Ollinger. Knight Tiles: Particles and Collisions in the Realm of 4-Way Deterministic Tilings. In Arseny M. Shur and Mikhail V. Volkov, editors, Developments in Language Theory - 18th International Conference, DLT 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings, volume 8633 of Lecture Notes in Computer Science, pages 227–238. Springer, 2014

  9. Bastien Le Gloannec and Nicolas Ollinger. Substitutions and Strongly Deterministic Tilesets. In S. Barry Cooper, Anuj Dawar, and Benedikt Löwe, editors, How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings, volume 7318 of Lecture Notes in Computer Science, pages 462–471. Springer, 2012

  10. Rodrigo Torres-Avilés, Nicolas Ollinger, and Anahı́ Gajardo. Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine. In Robert Glück and Tetsuo Yokoyama, editors, Reversible Computation, 4th International Workshop, RC 2012, Copenhagen, Denmark, July 2-3, 2012. Revised Papers, volume 7581 of Lecture Notes in Computer Science, pages 44–56. Springer, 2012

  11. Thomas Fernique and Nicolas Ollinger. Combinatorial substitutions and sofic tilings. In J. Kari, editor, Symposium on Cellular Automata Journées Automates Cellulaires (JAC’2010), pages 100–110. TUCS, Turku, 2010

  12. Fabien Givors, Gregory Lafitte, and Nicolas Ollinger. Infinite time cellular automata: a real computation model. In J. Kari, editor, Symposium on Cellular Automata Journées Automates Cellulaires (JAC’2010), pages 111–120. TUCS, Turku, 2010

  13. Nicolas Ollinger. Tiling the Plane with a Fixed Number of Polyominoes. In A. H. Dediu, A. M. Ionescu, and C. Martı́n-Vide, editors, Language and Automata Theory and Applications (LATA’2009), volume 5457 of Lecture Notes in Computer Science, pages 638–647. Springer, Berlin, 2009

  14. Jarkko Kari and Nicolas Ollinger. Periodicity and Immortality in Reversible Computing. In E. Ochmański and J. Tyszkiewicz, editors, Mathematical Foundations of Computer Science (MFCS’2008), volume 5162 of Lecture Notes in Computer Science, pages 419–430. Springer, Berlin, 2008

  15. Nicolas Ollinger. Two-by-two Substitution Systems and the Undecidability of the Domino Problem. In A. Beckmann, C. Dimitracopoulos, and B. Löwe, editors, Computability in Europe (CiE’2008), volume 5028 of Lecture Notes in Computer Science, pages 476–485, Berlin, 2008 . Springer

  16. Nicolas Ollinger. Universalities in Cellular Automata: a (short) survey. In B. Durand, editor, Symposium on Cellular Automata Journées Automates Cellulaires (JAC’2008), pages 102–118. MCCME Publishing House, Moscow, 2008

  17. Nicolas Ollinger and Gaétan Richard. Collisions and their Catenations: Ultimately Periodic Tilings of the Plane. In Proceedings of the Fifth IFIP Int. Conf. on TCS (IFIP-TCS’2008), volume 273/2008, pages 229–240, Boston, 2008 . Springer

  18. Nicolas Ollinger. The intrinsic universality problem of one-dimensional cellular automata. In H. Alt and M. Habib, editors, Symposium on Theoretical Aspects of Computer Science (STACS’2003), volume 2607 of Lecture Notes in Computer Science, pages 632–641, Berlin, 2003 . Springer

  19. Nicolas Ollinger. The quest for small universal cellular automata. In P. Widmayer, F. Triguero, R. Morales, M. Hennessy, S. Eidenbenz, and R. Conejo, editors, International Colloquium on Automata, languages and programming (ICALP’2002), volume 2380 of Lecture Notes in Computer Science, pages 318–329, Berlin, 2002 . Springer

  20. Nicolas Ollinger. Two-states bilinear intrinsically universal cellular automata. In R. Freivalds, editor, Fundamentals of computation theory (FCT’2001), volume 2138 of Lecture Notes in Computer Science, pages 396–399, Berlin, 2001 . Springer

Workshop Papers

  1. Eric Goles, Nicolas Ollinger, and Guillaume Theyssier. Introducing Freezing Cellular Automata. In Jarkko Kari, Ilkka Törmä, and Michal Szabados, editors, Cellular Automata and Discrete Complex Systems, 21st International Workshop, AUTOMATA 2015, Turku, Finland, June 8-10, 2015. Exploratory Papers, volume 24 of TUCS Lecture Notes, pages 65–73. Turku Centre for Computer Science, 2015

  2. Nicolas Ollinger. Intrinsically Universal Cellular Automata. In Turlough Neary, Damien Woods, Anthony Karel Seda, and Niall Murphy, editors, Proceedings International Workshop on The Complexity of Simple Programs, CSP 2008, Cork, Ireland, 6-7th December 2008., volume 1 of EPTCS, pages 199–204, 2009

  3. Nicolas Ollinger and G. Richard. A Particular Universal Cellular Automaton. In Turlough Neary, Damien Woods, Anthony Karel Seda, and Niall Murphy, editors, Proceedings International Workshop on The Complexity of Simple Programs, CSP 2008, Cork, Ireland, 6-7th December 2008., volume 1 of EPTCS, pages 205–214, 2009

Book Chapters

  1. Nicolas Ollinger. Le calcul numérique. In B. Martin and S. Riva, editors, Informatique Mathématique, une photographie en 2022, École Jeunes Chercheuses et Chercheurs en Informatique Mathématique (EJCIM 2022), pages 157–190. CNRS Éditions, 2022 . (sous licence CC-BY-NC-SA)

  2. Nicolas Ollinger. Universalities in Cellular Automata. In Grzegorz Rozenberg, Thomas Bäck, and Joost N. Kok, editors, Handbook of Natural Computing, pages 189–229. Springer, Berlin, 2012

Edited Volumes

  1. Nicolas Ollinger and Heribert Vollmer, editors. 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016 . (sous licence CC-BY)

  2. Ernst W. Mayr and Nicolas Ollinger, editors. 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015 . (sous licence CC-BY)

  3. Nicolas Ollinger, editor. Informatique Mathématique, une photographie en 2015, École Jeunes Chercheurs en Informatique Mathématique (EJCIM 2015). CNRS Éditions, 2015 . (sous licence CC-BY-NC-SA)

Thesis and Habilitation

  1. N. Ollinger. Programmation et indécidabilités dans les systèmes complexes. Habilitation thesis, Université de Nice Sophia Antipolis, 2008

  2. N. Ollinger. Automates cellulaires : structures. PhD thesis, École Normale Supérieure de Lyon, décembre 2002

Mis à jour le 23 février 2026