Publications
[T1]
Automates cellulaires et chaos : de la vision topologique à la vision algorithmique
Thèse soutenue le 23 octobre 1998 à lcole Normale Supérieure de Lyon
[T2]
De l'algorithmique du chaos dans les systèmes dynamiques discrets
Habilitation à diriger des recherches
[R1]
Transformations of the One-dimensional Cellular Automata Rule Space
Parallel Computing 23(11): 1593-1611, 1997
[R2]
On the Dynamical Behavior of Chaotic Cellular Automata
Theoretical Computer Science 217(1):31-51, 1999
[R3]
Ergodicity and Regularity for Linear Cellular Automata over Zm.
Theoretical Computer Science 233(1-2):147-164, 1999
[R4]
Cellular automata in Cantor, Besicovitch and Weyl topological spaces
Complex Systems 11(2):107-123, 1999
[R5]
Kolmogorov complexity and cellular automata classification
Theoretical Computer Science 259(1-2):271-285, 2001
[R6]
On the sensitivity of cellular automata in
Besicovitch spaces
Theoretical Computer Science 301(1-3):341-354, 2003
[R7]
Number conserving cellular automata I: decidability
Theoretical Computer Science 299(1-3):523-535, 2003
[R8]
Number conserving cellular automata II: dynamics
Theoretical Computer Science, 304(1-3):269-290, 2003
[R9]
Number conserving cellular automata: new results on decidability and dynamics
Discrete Mathematics and Theoretical Computer Science, AB:129-140, 2003
[R10]
On undecidability of equicontinuity classification for cellular automata
Discrete Mathematics and Theoretical Computer Science, AB:117-128, 2003
[R11]
A new dimension sensitive property for cellular automata
Theoretical Computer Science 345:243-247, 2005
[R12]
Some results about chaotic behavior of cellular automata
Theoretical Computer Science 349(3):318-336, 2005
[R13]
On computing the fixed points for generalized sandpiles
International Journal of Unconventional Computing, 2(1):13-25, 2005
[R14]
A note on fixed points of generalized ice piles models
International Journal of Unconventional Computing, 2(2):183-191, 2006
[R15]
Subshift attractors of cellular automata
Nonlinearity, 20:105-117, 2007
[R16]
Advances in symmetric sandpiles
Fundamenta Informaticae, 76(1-2):91-112, 2007
[R17]
From sandpiles to sand automata
Theoretical Computer Science, 381:1-28, 2007
[R18]
A search algorithm for subshift attractors of cellular automata
Theory of Computing Systems, 46:479-498, 2010
[R19]
Conservation of Some Dynamical Properties for Operations on Cellular Automata
Theoretical Computer Science, 410:3685-3693, 2009
[R20]
On the directional dynamics of additive cellular automata
Theoretical Computer Science, 410(47-49): 4823-4833, 2009
[R21]
On the hierarchy of conservation laws in a cellular automaton
Natural Computing 10(4): 1275-1294, 2011
[R22]
On the impact of the distance between two genes on their interaction curve
Journal of Mathematical Biology 64: 131-147, 2012
[R23]
Foreword: asynchronous cellular automata and nature-inspired computation
Natural Computing 11(2): 267-268 (2012)
[R24]
Non-Uniform Cellular Automata: classes, dynamics, and decidability
Information and Computation, 215: 32-46 (2012)
[R25]
Computational Complexity of Avalanches in the Kadanoff Sandpile Model
Fundamenta Informaticae 115(1): 107-124 (2012)
[R26]
Computational Issues of Asynchronous Cellular Automata
Fundamenta Informaticae 120:1-17 (2012)
[R27]
Local rule distributions, language complexity and non-uniform cellular automata
Theoretical Computer Science 504:38-51 (2013)
[R28]
Surjective Multidimensional Cellular Automata Are Non-Wandering: A Combinatorial Proof
Information Processing Letters 113(5-6):156-159 (2013)
[R29]
Special Issue: Cellular Automata and Models of Computation
Fundamenta Informaticae 126(2-3):i-ii (2013)
[R30]
Periodic orbits and dynamical complexity in Cellular Automata
Fundamenta Informaticae 126(2-3): 183-199 (2013)
[R31]
Forewords: cellular automata and applications
Natural Computing, 12(3): 305 (2013)
[R32]
Forewords: asynchronous cellular automata and applications
Natural Computing, 12(4): 537-538 (2013)
[R33]
m-Asynchronous cellular automata: from fairness to quasi-fairness
Natural Computing 12(4): 561-572 (2013)
[R34]
Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
Theoretical Computuer Science, 516: 40-59 (2014)
[R35]
Three research directions in non-uniform cellular automata
Theoretical Computuer Science, 559: 73-90 (2014)
[R36]
Non-uniform Cellular Automata
Theoretical Computuer Science, 559: 1-2 (2014)
[R37]
Fixed-point forms of the parallel symmetric sandpile model
Theoretical Computuer Science, 533: 1-14 (2014)
[R38]
Limit Properties of Doubly Quiescent m-Asynchronous Elementary Cellular Automata
J. Cellular Automata, 9(5-6): 341-355 (2014)
[R39]
Reaction systems and extremal combinatorics properties
Theoretical Computuer Science, 598: 138-149 (2015)
[R40]
Ancestors, descendants, and gardens of Eden in reaction systems
Theoretical Computuer Science, 608: 16-26 (2015)
[R41]
Foreword: asynchronous behavior of cellular automata and discrete models
Natural Computing 14(4): 505-506 (2015)
[R42]
On the complexity of occurrence and convergence problems in reaction systems
Natural Computing 14(1): 185-191 (2015)
[R43]
Computing the periods of preimages in surjective cellular automata
Natural Computing 16(3): 367-381 (2017)
[R44]
From Tetris to polyominoes generation
Electronic Notes in Discrete Mathematics 59: 79-98 (2017)
[R45]
Computational complexity of finite asynchronous cellular automata
Theoretical Computer Science 664: 131-143 (2017)
[R46]
More decision algorithms for global properties of 1D CA
Journal of Cellular Automata 13(1-2): 1-14 (2018)
[R47]
Computational Complexity of the Avalanche Problem for One Dimensional Decreasing Sandpiles
Journal of Cellular Automata 13(3): 215-228 (2018)
[R48]
An Iterated Local Search to find many solutions of the 6-states Firing Squad Synchronisation Problem
Appl. Soft Computing 66 : 449-461 (2018)
[R49]
On the dynamical behavior of linear higher-order cellular automata and its decidability
Information Sciences 486: 7387 (2019)
[R50]
Complexity of the dynamics of reaction systems
Information & Computation 267 : 96-109 (2019)
[R51]
Hard is to Predict Sandpiles on Lattices ? A Survey
Fundamenta Informaticae 171(1-4) : 189-219 (2020)
[R52]
Mutually orthogonal latin squares based on cellular automata
Design Codes and Cryptography 88(2) : 391-411 (2020)
[R53]
Preface
Nat. Comput. 19(1): 1-2 (2020)
[R54]
Preface
Inf. Comput. 274: 104530 (2020)
[R55]
Preface
Nat. Comput. 19(2): 271 (2020)
[R56]
Chaos and ergodicity are decidable for linear cellular automata over (Z/mZ)n
Inf. Sci. 539: 136-144 (2020)
[R57]
Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption
Inf. Sci. 563: 183-195 (2021)
[R58]
An efficiently computable characterization of stability and instability for linear cellular automata
J. Comput. Syst. Sci. 122: 63-71 (2021)
[R59]
Non-maximal sensitivity to synchronism in elementary cellular automata: Exact asymptotic measures
Theor. Comput. Sci. 926: 21-50 (2022)
[R60]
Preface
Nat. Comput. 22(3): 409-410 (2023)
[R61]
An algorithmic pipeline for solving equations over discrete dynamical systems modelling hypothesis on real phenomena
J. Comput. Sci. 66: 101932 (2023)
[R62]
A topology for P-systems with active membranes
J. Membr. Comput. 5(4): 193-204 (2023)
[R63]
An Easy to Check Characterization of Positive Expansivity for Additive Cellular Automata Over a Finite Abelian Group
IEEE Access 11: 121246-121255 (2023)
[R64]
Decomposition and factorisation of transients in functional graphs
Theor. Comput. Sci. 999: 114514 (2024)
[R65]
An efficient algorithm deciding chaos for linear cellular automata over (Z/mZ)n with applications to data encryption
Inf. Sci. 657: 119942 (2024)
[C1]
Rule Space Transfromations and One-dimensional Cellular Automata
Developments in Language Theory (DLT'95), pag. 409-419, Magdeburg, 1995. World Scientific Publishing Co
[C2]
Essential Transformations of the One-dimensional Cellular Automata Rule Space and Endomorphisms of Compact Abelian Groups
In G. Mauri and S. Bandini, editors, Cellular Automata for Research and Industry (ACRI'96), pag. 42-56, Milan, 1996. Springer-Verlag
[C3]
On Ergodic Linear Cellular Automata Over Zm
In Symposium on Theoretical Aspects of Computer Science (STACS'97), Volume 1200 of Lecture Notes in Computer Science, pag. 427-438, Hansestadt Lübeck (Germany), 1997. Springer-Verlag
[C4]
A Shift-invariant Metric on SZ Inducing a Non-trivial Topology
In Mathematical Foundations of Computer Science (MFCS'97), Volume 1295 of Lectures Notes in Computer Science, pag. 179-188, Bratislava, 1997. Springer-Verlag
[C5]
Algorithmic information theory and cellular automata dynamics
In Mathematical Foundations of Computer Science (MFCS'01), volume 2136 of Lectures Notes in Computer Science, pag. 248-259, Marianske Lazne, Czech Republic (2001). Springer-Verlag
[C6]
On sand automata
In Symposium on Theoretical Aspects of Computer Science (STACS'03), volume 2607 of Lecture Notes in Computer Science, pag. 642-653, Berlin (Allemagne) (2003). Springer-Verlag
[C7]
Periodicity and transitivity for cellular automata in Besicovitch topologies
In Mathematical Foundations of Computer Science (MFCS'03), volume 2747 of Lecture Notes in Computer Sciences, pag. 228-238, August 25-29, Bratislava, 2003
[C8]
On the dynamics of PB systems: a Petri net view
Proceedings of Workshop on membrane computing (WMC 2003), Carlos Martin-Vide, Gheorghe Paun, Grzegorz Rozenberg and Arto Salomaa editors. Volume 2933 of Lecture Notes in Computer Sciences, pag. 153-167, Tarragona (Spain), 2003
[C9]
A new dimension sensitive property for cellular automata
In Mathematical Foundations of Computer Science (MFCS'04), volume 3153 of Lecture Notes in Computer Sciences, pag. 416-426, August 22-27, Prague (Czech Rep.), 2004
[C10]
Basic properties for sand automata
In Mathematical Foundations of Computer Science (MFCS'05), volume 3618 of Lecture Notes in Computer Sciences, pag. 192-211, August 29- September 2, Gdansk (Poland), 2005
[C11]
On symmetric sandpiles
In S. El Yacouby and B. Chopard, editors, Cellular automata for research and industry (ACRI'06), volume 4173 of Lecture Notes in Computer Sciences, pag. 676-685, September 20-23, Perpignan (France), 2006
[C12]
A search algorithm for the maximal attractor of a cellular automaton
In Symposium on Theoretical Aspects of Computer Science (STACS'07), volume 4393 of Lecture Notes in Computer Sciences, pag. 356-366, February 22-24, Aachen (Germany), 2007
[C13]
Shifting and lifting of cellular automata
In S. Barry Cooper and B. Loewe and A. Sorbi, editors, Computation and Logic in the Real World. Third Conference on Computability in Europe (CiE 2007), volume 4497 of Lecture Notes in Computer Sciences, pag. 1-10, June 18-23, Siena (Italy), 2007
[C14]
Sofic trace subshift of a cellular automaton
In S. Barry Cooper and B. Loewe and A. Sorbi, editors, Computation and Logic in the Real World. Third Conference on Computability in Europe (CiE 2007), volume 4497 of Lecture Notes in Computer Sciences, pag. 152-161, June 18-23, Siena (Italy), 2007
[C15]
Classification of directional dynamics for additive cellular automata
In B. Durand (editor), Proceedings of Journées Automates Cellulaires (JAC 2008), pag. 40-53, April 21-25, Uzes (France), 2008
[C16]
The most general conservation law for a cellular automaton
In Computer Science Symposium in Russia (CSR 2008), volume 5010 of Lecture Notes in Computer Sciences, pag. 194-203, June 7-12, Moscow (Russia), 2008
[C17]
Decidable properties of 2D cellular automata
In M. Ito and M. Toyma Eds, Developments in Language Theory (DLT 2008), volume 5257 of Lecture Notes in Computer Sciences, pag. 264-275, September 16-19, Kyoto (Japan), 2008
[C18]
Non-uniform cellular automata
In A. Horia Dediu, A.-M. Ionescu, and C. Martin-Vide, editors, Language and Automata Theory and Applications, Third International Conference (LATA 2009), volume 5457, pages 302-313, Tarragon (Spain), 2009
[C19]
Ultimate traces for cellular automata
In Symposium on Theoretical Aspects of Computer Science (STACS'10), in Leibniz International Proceedings in Informatics, pag. 155-166, March 4-6, Nancy (France), 2010
[C20]
Gene regulatory networks: the impact of distance between genes
In 19th International Symposium in Mathematical Theory of Networks and Systems (MTNS'10), pag. xxx-xxx, July 5-9, Budapest (Hungary), 2010
[C21]
2D Cellular Automata: dynamics and undecidability
In Computability in Europe 2010, pag. xxx-xxx, June 30-July 4, Ponta Delgada, Azores (Portugal), 2010
[C22]
Computational Aspects of Asynchronous Cellular Automata
In Developments in Language Theory - DLT 2011, volume 6795 of Lecture Notes in Computer Sciences, pag. 466-468, July 19-22, Milan (Italy), 2011
[C23]
Asymptotic distribution of entry times in a cellular automaton with annihilating particles
In Nazim Fatès, Eric Goles, Alejandro Maass and Ivan Rapaport, editors, Automata 2011, Discrete Mathematics and Theorectical Computer Science AP: 47-58, 2011
[C24]
Computational Complexity of Rule Distributions of Non-uniform Cellular Automata
In Adrian Horia Dediu and C. Martin-Vide, editors, Language and Automata Theory and Applications, Sixth International Conference (LATA 2012), volume 7183 of Lectures Notes in Computer Science, page 204--215, La Coruna (Spain), 2012
[C25]
Acceptance conditions for Omega languages
In Hsu-Chun Yen and Oscar H. Ibarra, editors, Developments in Language Theory - DLT 2012, volume 7410 of Lectures Notes in Computer Science, pag. 320-331, Taipei, Taiwan, August 14-17, 2012
[C26]
$m$-Asynchronous Cellular Automata
In ACA 2012 (satellite of conference ACRI 2012), volume 7495 of Lecture Notes in Computer Sciences, pag. 653-662, September 24-26, Santorini (Greece), 2012
[C27]
A Survey on m-Asynchronous Cellular Automata
In Jarkko Kari, Martin Kutrib and Andreas Malcher (Eds.): Unconventional Computation and Natural Computation (UCNC 2013), volume 8155 of Lecture Notes in Computer Sciences, pag. 46-66, September 17-19, Giessen (Germany), 2013
[C28]
Asymptotic Dynamics of (Some) Asyncronous Cellular Automata - (Abstract)
In Giancarlo Mauri, Alberto Dennunzio, Luca Manzoni, Antonio Enrico Porreca (Eds.): Unconventional Computation and Natural Computation (UCNC 2013), volume 7956 of Lecture Notes in Computer Sciences, pag. 1-2, July 1-5, Milan (Italy), 2013
[C29]
Extremal combinatorics of reaction systems
In Adrian Horia Dediu, Carlos Martin-Vide, José-Louis Sierra and Bianca Truthe, editors, Language and Automata Theory and Applications, Eighth International Conference (LATA 2014), volume 8370 of Lectures Notes in Computer Science, pag. 297-307, Madrid (Spain), 2014
[C30]
ω-rational languages: high complexity classes vs. Borel Hierarchy
In Adrian Horia Dediu, Carlos Martin-Vide, José-Louis Sierra and Bianca Truthe, editors, Language and Automata Theory and Applications, Eighth International Conference (LATA 2014), volume 8370 of Lectures Notes in Computer Science, pag. 372-383, Madrid (Spain), 2014
[C31]
Cycles and Global Attractors of Reaction Systems
In Helmut Jürgensen, Juhani Karhumäki and Alexander Okhotin, editors, Descriptional Complexity of Formal Systems - 16th International Workshop (DCFS) 2014, volume 8614 of Lectures Notes in Computer Science, pag. 114-125, Turku (Finland), 2014
[C32]
Fixed Points and Attractors of Reaction Systems
In Arnold Beckmann, Erzsébet Csuhaj-Varju and Klaus Meer, editors, Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, volume 8493 of Lectures Notes in Computer Science, pag. 194-203, Budapest (Budapest), 2014
[C33]
Advances on Random Sequence Generation by Uniform Cellular Automata
In Cristian S. Calude, Rusins Freivalds and Kazuo Iwamar, editors, Computing with New Resources - Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday, volume 8808 of Lectures Notes in Computer Science, pag. 56-70, Budapest (Budapest), 2014
[C34]
Computational Complexity of the Avalanche Problem on One Dimensional Kadanoff Sandpiles
In Teijiro Isokawa, Katsunobu Imai, Nobuyuki Matsui, Ferdinand Peper and Hiroshi Umeo, editors, Cellular Automata and Discrete Complex Systems - 20th International Workshop, {AUTOMATA} 2014, volume 8996 of Lectures Notes in Computer Science, pag. 21-30, Himeji (Japan), 2014
[C35]
Non Uniform Cellular Automata Description of Signed Partition Versions of Ice and Sand Pile Models
In Jaroslaw Was, Georgios Ch. Sirakoulis and Stefania Bandini, editors, Cellular Automata - 11th International Conference on Cellular Automata for Research and Industry, {ACRI} 2014, volume 8751 of Lectures Notes in Computer Science, pag. 115-124, Krakow (Poland), 2014
[C36]
Preimage Problems for Reaction Systems
In Adrian Horia Dediu, Enrico Formenti, Carlos Martin-Vide and Bianca Truthe, editors, Language and Automata Theory and Applications - 9th International
Conference, {LATA} 2015, volume 8977 of Lectures Notes in Computer Science, pag. 537-548, Nice (France), 2015
[C37]
Reachability in Resource-Bounded Reaction Systems
In Adrian Horia Dediu, Jan Janousek, Carlos Martin-Vide and Bianca Truthe, editors, Language and Automata Theory and Applications - 10th International
Conference, {LATA} 2016, volume 9618 of Lectures Notes in Computer Science, pag. 592-602, Prague (Czech Republic), 2016
[C38]
Enumerating Orthogonal Latin Squares Generated by Bipermutive Cellular Automata
In AUTOMATA 2017, vol. 10248 of Lectures Notes in Computer Science, pag. 151-164, Milan (Italy), 2017
[C39]
On the generation of 2-Polyominoes
DFCS 2018, vol. 10952 of Lecture Notes in Computer Science, pag. 101-113, Halifax (Canada), 2018
[C40]
Polynomial Equation over Finite, Discrete-Time Dynamical Systems
ACRI 2018, vol. 11115 of Lectures Notes in Computer Science, pag. 298-306, Como (Italy), 2018
[C41]
Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties
Mathematical Foundations of Computer Science (MFCS) 2019, vol. 138 of LIPIcs, pag. 68:1-68:15, 2019
[C42]
Decidability of Sensitivity and Equicontinuity for Linear Higher-Order Cellular Automata
Language and Automata Theory and Applications - 13th International Conference (LATA), vol. 11417 of Lectures Notes iii Computer Science, pag. 95-107, 2019
[C44]
Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties
Mathematical Foundations of Computer Science (MFCS 2019): 68:1-68:15
[C45]
Solving Equations on Discrete Dynamical Systems
Computational Intelligence Methods for Bioinformatics and Biostatistics - 16th International Meeting (CIBB). Lecture Notes in Computer Science, 12313:119-132, 2019
[C46]
From Linear to Additive Cellular Automata
47th International Colloquium on Automata, Languages, and Programming, (ICALP) 2020, LIPIcs:168-125:1--125:13
[C47]
Non-maximal Sensitivity to Synchronism in Periodic Elementary Cellular Automata: Exact Asymptotic Measures
Cellular Automata and Discrete Complex Systems - 26th (IFIP WG 1.5) International Workshop, (AUTOMATA 2020), Lecture Notes in Computer Science, 12286:14--28, 2020
[C48]
High Order Cellular Automata for Edge Detection: A Preliminary Study
Cellular Automata - 14th International Conference on Cellular Automata for Research and Industry (ACRI 2020), Lecture Notes in Computer Science, vol. 12599, pp. 80-89, Springer, 2020
[C49]
MDDs Boost Equation Solving on Discrete Dynamical Systems
Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 18th International Conference, (CPAIOR 2021), Lecture Notes in Computer Science, vol. 12735, pp. 196-213, Springer, 2021
[C50]
Complexity of Local, Global and Universality Properties in Finite Dynamical Systems
Machines, Computations, and Universality - 9th International Conference (MCU 2022), Lecture Notes in Computer Science, vol. 13419, pp. 1-11, Springer, 2022
[C51]
On Elementary Second Order Cellular Automata
Cellular Automata Technology - Third Asian Symposium (ASCAT 2024), Communications in Computer and Information Science, vol. 2021, pp. 204-218, Springer, 2024
[L1]
Topological definitions of chaos: applications to cellular automata dynamics
In Jacques Mazoyer editor, Cellular Automata, chapter 8, Series in Mathematics and its Applications, Kluwer, 1999
[L2]
Dynamics of cellular automata in non-compact spaces
In Robert Meyer editor, Encyclopedia of Complexity and System Science, Springer-Verlag, 2009
[L3]
Chaotic behavior of cellular automata
In Robert Meyer editor, Encyclopedia of Complexity and System Science, Springer-Verlag, 2009
[L4]
Algorithmic complexity and cellular automata
In Robert Meyer editor, Encyclopedia of Complexity and System Science, Springer-Verlag, 2009
[L5]
Cellular automata dynamical systems
In In Grzegorz Rozenberg, Thomas Bäck et Joost N. Kok editors, Handbook of Natural Computing, 25-75, Springer, 2012
[L6]
Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires (AUTOMATA & JAC) 2012, La Marana, Corsica, September 19-21, 2012
EPTCS 90, 2012
[L7]
Pattern Recognition in Bioinformatics - 8th IAPR International Conference, PRIB 2013, Nice, France, June 17-20, 2013. Proceedings
Lecture Notes in Computer Science 7986, Springer 2013
[L8]
Computational Intelligence Methods for Bioinformatics and Biostatistics - 10th International Meeting, {CIBB} 2013, Nice, France, June 20-22, 2013, Revised Selected Papers
Lecture Notes in Computer Science 8452, Springer, 2014
[L9]
Language and Automata Theory and Applications - 9th International Conference, (LATA 2015), Proceedings
Lecture Notes in Computer Science 8977, Springer, 2015
[L10]
Cellular Automata and Discrete Complex Systems - 23rd IFIP WG 1.5 International Workshop (AUTOMATA 2017), Lecture Notes in Computer Science, Proceedings
Lecture Notes in Computer Science, vol. 10248, Springer, 2017
[L11]
From Additive Flowers to Additive Automata Networks. Automata and Complexity - Essays Presented to Eric Goles on the Occasion of His 70th Birthday
vol. 42, pp. 323-343, Springer, 2022
[L12]
Cellular Automata Technology - Third Asian Symposium (ASCAT 2024), Proceedings
Communications in Computer and Information Science, vol. 2021, Springer, 2024
[L13]
Reachability Problems - 17th International Conference (RP 2023), Proceedings
Lecture Notes in Computer Science, vol. 14235, Springer, 2023
[P1]
Fixed points of generalized ice pile models
In Posters proceedings of European Conference on Complex Systems (ECCS'05), Paris (november 2005)
[P2]
A New Heuristic for Rectilinear Crossing Minimization
Poster accepted at Graph Drawing and Network Visualization (GD 2021), 2021