Exemples de classes d'automates cellulaires
Delorme, Marianne ; Mazoyer, Jacques
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 37-53 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Lorsqu'on observe des orbites de certains automates cellulaires, on peut penser qu'elles apparaissent comme des mélanges d'orbites d'autres automates (composants). Dans cet article, nous tentons de comprendre ce phénomène en construisant un hybride de deux automates au moyen d'un troisième. Deux types d'automates cellulaires sont introduits : les captifs et les foulards. Nous comparons des propriétés de ces hybrides dans le cadre des classifications algébriques introduites par [B. Martin (2001) ; N. Ollinger (2002) ; I. Rapaport (1998) ; G. Teyssier (2005) : PhD. Thesis, École Normale Supérieure de Lyon].

Observing orbits of some cellular automata may lead to think that they are results of evolutions of other cellular automata, which could be considered as sort of components. In this paper, we try to understand this phenomenon by constructing a hybrid of two cellular automata by means of a third one. Two types of cellular automata are introduced: “captifs” and “foulards” cellular automata. We compare properties of hybrids in the framework of algebraic classifications introduced in [B. Martin (2001); N. Ollinger (2002); I. Rapaport (1998); G. Teyssier (2005): PhD. Thesis, École Normale Supérieure de Lyon].

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2007049
Classification:  68Q80,  37B15
Mots clés: automates cellulaires, classification, auto-organisation, émergence 
@article{ITA_2008__42_1_37_0,
     author = {Delorme, Marianne and Mazoyer, Jacques},
     title = {Exemples de classes d'automates cellulaires},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {42},
     year = {2008},
     pages = {37-53},
     doi = {10.1051/ita:2007049},
     mrnumber = {2382543},
     zbl = {1148.68407},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_1_37_0}
}

Delorme, Marianne; Mazoyer, Jacques. Exemples de classes d'automates cellulaires. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 37-53. doi : 10.1051/ita:2007049. http://gdmltest.u-ga.fr/item/ITA_2008__42_1_37_0/

[1] N. Boccara and M. Roger, Block transformations of one-dimensional deterministic cellulat automaton rules. J. Phys. A 24 (1991) 1849-1865. | MR 1117605 | Zbl 0724.68069

[2] G. Cattaneo, E. Formenti, L. Margara and J. Mazoyer, Shift invariant distance on s ℤ with non trivial topology, in Proceeding of MFCS'97, Springer Verlag (1997) 376-381. | MR 1640219

[3] G. Cattaneo, E. Formenti, L. Margara and G. Mauri, Topological chaos and cellular automata. in Cellular Automata: a parallel model, edited by Delorme and Mazoyer, Springer Verlag (1999) 213-259.

[4] J.P. Crutchfield and J.E. Hanson, The attractor basin portait of a cellular automaton. J. Statist. Phys. 66 (1992) 1415-1462. | MR 1156410 | Zbl 0892.58051

[5] J.P. Crutchfield and J.E. Hanson, Attractor vicinity decay for a cellular automaton. Chaos 3 (1993) 215-224. | MR 1222990 | Zbl 1055.37508

[6] J.P. Crutchfield and J.E. Hanson, Turbulent pattern bases for a cellular automata. Phys. D 69 (1993) 279-301. | MR 1251266 | Zbl 0794.68111

[7] J.P. Crutchfield and J.E. Hanson, Computational mechanics of cellular automata: an example. Phys. D 103 (1997) 169-189. | MR 1464247

[8] K. Eloranta, Partially permutive cellular automata. Nonlinearity 6 (1993) 1009-1023. | MR 1251255 | Zbl 0791.58051

[9] K. Eloranta, Random walks in cellular automata. Nonlinearity 6 (1993) 1025-1036. | MR 1251256 | Zbl 0791.58052

[10] K. Eloranta, The dynamics of defect ensembles in one-dimensional cellular automata. J. Statist. Phys. 76 (1994) 1377-1398. | MR 1298107 | Zbl 0837.60092

[11] K. Eloranta, Cellular automata for contours dynamics. Phys. D 89 (1995) 184-203. | MR 1366820 | Zbl 0900.82112

[12] K. Eloranta and E. Nummelin, The kind of cellular automaton rule 18 performs a random walk. J. Statist. Phys. 69 (1992) 1131-1136. | MR 1192037 | Zbl 0891.68065

[13] P. Grassberger, Chaos and diffusion in deterministic cellular automata. Phys. D 10 (1984) 52-58. | MR 762653 | Zbl 0562.68039

[14] P. Grassberger, New mechanism for deterministic diffusion. Phys. Rev. A 28 (1984) 3666-3667.

[15] J.E. Hanson, Computational Mechnaics if Cellular Automata. Ph.D. Thesis, University of California, Ann Arbor, MI (1993). Published by University Microfilms.

[16] G. Hedlund, Endomorphism and automorphism of the shift dynamical system. Math. Syst. Theor. 3 (1969) 320-375. | MR 259881 | Zbl 0182.56901

[17] M. Hurley, Ergodic aspects of cellular automata. Ergod. Theor. Dyn. Syst. 10 (1990) 671-685. | MR 1091421 | Zbl 0695.58019

[18] M. Hurley, Varieties of periodic attractors in cellular automata. T. Am. Math. Soc. 326 (1991) 701-726. | MR 1073773 | Zbl 0738.58030

[19] W. Hordijk, J.P. Crutchfield and M. Mitchell, Mechanisms of emergent computation in cellular automata. in Parallel Problem Solving in Nature V, edited by M. Schoenaur, A.E. Eiben, T. Bäck and K.-P. Schwefel. Lect. Notes Comput. Sci. (1998) 613-622.

[20] W. Hordijk, J.P. Crutchfield and C.R. Shalizi, Upper bound of the products of particle interactions in cellular automata. Phys. D 154 (2001) 240-258. | MR 1841063 | Zbl 0986.37013

[21] P. Kůrka, Languages, equicontinuity and attractors in cellular automata. Ergod. Theor. Dyn. Syst. 17 (1997) 417-433. | MR 1444061 | Zbl 0876.68075

[22] P. Kůrka, Cellular automata with vanishing particles. Fund. Inform. 58 (2003) 203-221. | MR 2073077 | Zbl 1111.68521

[23] P. Kůrka, On the measure attractor of a cellular automaton. Discret. Contin. Dyn. Syst. (2005) S524-S535. | MR 2192711 | Zbl 1144.37303

[24] P. Kůrka and A. Maass. Limit sets of cellular automata associated to probability measures. J. Statist. Phys. 100 (2000) 1031-1047. | MR 1798552 | Zbl 0995.37008

[25] A. Maass, B. Host and S. Martinez, Uniform Bernoulli measure in dynamics of permutive cellular automata with algebraic local rules. Discrete Contin. Dyn. Syst. 9 (2003) 1423-1446. | MR 2017675 | Zbl 1053.54046

[26] B. Martin, A group interpretation of particles generated by one-dimensional cellular automata. Int. J. Mod. Phys. C 11 (2000) 101-123. | MR 1755082 | Zbl 0940.82044

[27] B. Martin, Automates cellulaires, information et chaos. Ph.D. Thesis, École Normale Supérieure de Lyon (2001).

[28] O. Martin, A. Odlysko and S. Wolfram, Algebraic properties of cellular automata. Commun. Math. Phys. 93 (1984) 219-258. | MR 742194 | Zbl 0564.68038

[29] J. Mazoyer and I. Rapaport, Inducing an order on cellular automata by a grouping operation, in Proceeding of STACS'98, Springer Verlag (1998) 128-227. | MR 1650789 | Zbl 0893.68108

[30] H.V. Mcintosh, A concordance for rule 110 (1999). http://delta.cs.cinvestav.mx/ mcintosh/comun

[31] H.V. Mcintosh, Rule 110 as it relates to the presence of gliders (1999). http://delta.cs.cinvestav.mx/ mcintosh/comun/rule110.pdf

[32] H.V. Mcintosh, Rule 110 is universal (1999). http://delta.cs.cinvestav.mx/ mcintosh/comun/texlet/texlet.pdf

[33] J. Nasser, N. Boccara and M. Roger, Particle-like structures and their interactions in spatiotemporal patterns generated ny one-dimentional cellular automata. Phys. Rev. A 44 (1991) 866-875.

[34] N. Ollinger, Automates cellulaires: structures. Ph.D. Thesis, École Normale Supérieure de Lyon (2002).

[35] N. Ollinger, The quest for small universal cellular automata, in Proceeding of ICALP'02, 3 Springer Verlag (2002) 376-381. | MR 2062468 | Zbl 1056.68104

[36] N. Ollinger, The intrinsic universality problem of one-dimensional cellular automata, in Proceeding of STACS'03, Springer Verlag (2003) 632-641. | MR 2066789 | Zbl 1035.68066

[37] N. Ollinger and G. Richard, On the universality of rule 110, in Proceedings of DMTCS'04 (2004).

[38] M. Pivato, Invariant measures for bipermutive cellular automata. Discret. Contin. Dyn. Syst. 12 (2005) 723-736. | MR 2129368 | Zbl 1072.37016

[39] M. Pivato, Algebraic invariants for crystallographics defects in cellular automata. Ergod. Theor. Dyn. Syst. 27 (2007) 199-240. | MR 2297094 | Zbl 1129.37007

[40] M. Pivato, Defect particle kinematics in one-dimensional cellular automata. Theoret. Comput. Sci. 377 (2007) 205-225. | MR 2323397 | Zbl 1115.68102

[41] M. Pivato, Spectral domain boundaries in cellular automata. Fund. Inform. 78 (2007) 417-447. | MR 2346874 | Zbl 1127.68063

[42] M. Mitchell, R. Das and J.P. Crutchfield, A genetic algorithm discovers particle-based computation in cellular automata, in Parallel Problem Solving in Nature III, edited by K.-P. Schwefel, Y. Davidor and R. Männer. Lect. Notes Comput. Sci. (1994) 244-353.

[43] I. Rapaport, Ordre induit sur les automates cellulaires par l'opération de regroupement. Ph.D. Thesis, École Normale Supérieure de Lyon (1998).

[44] A. Smith, Real time languages by one-dimensional cellular automata. J. Comput. Syst. Sci. 6 (1972) 233-253. | MR 309383 | Zbl 0268.68044

[45] G. Theyssier, Captive cellular automata, in Proceeding of MFCS'04, Springer Verlag (2004) 427-438. | MR 2143159 | Zbl 1096.68100

[46] G. Theyssier, Automates cellulaires : un modèle de complexité. Ph.D. Thesis, École Normale Supérieure de Lyon (2005).

[47] S. Wolfram, Theory and applications of cellular automata. World Scientific, Singapore (1986). | MR 857608 | Zbl 0609.68043