Exemples de classes d'automates cellulaires

Delorme, Marianne; Mazoyer, Jacques

doi:10.1051/ita:2007049

Delorme, Marianne ; Mazoyer, Jacques

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 37-53.

Résumé
Abstract

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

MR Zbl

DOI : 10.1051/ita:2007049

Classification : 68Q80, 37B15
Mot clés : automates cellulaires, classification, auto-organisation, émergence
Mots-clés : cellular automata, classification, self-organization, emergence

@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},
     pages = {37--53},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {1},
     year = {2008},
     doi = {10.1051/ita:2007049},
     mrnumber = {2382543},
     zbl = {1148.68407},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1051/ita:2007049/}
}

TY  - JOUR
AU  - Delorme, Marianne
AU  - Mazoyer, Jacques
TI  - Exemples de classes d'automates cellulaires
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 37
EP  - 53
VL  - 42
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007049/
DO  - 10.1051/ita:2007049
LA  - fr
ID  - ITA_2008__42_1_37_0
ER  -

%0 Journal Article
%A Delorme, Marianne
%A Mazoyer, Jacques
%T Exemples de classes d'automates cellulaires
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 37-53
%V 42
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007049/
%R 10.1051/ita:2007049
%G fr
%F 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) no. 1, pp. 37-53. doi : 10.1051/ita:2007049. http://www.numdam.org/articles/10.1051/ita:2007049/

Bibliographie
Cité par

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

[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

[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 | Zbl

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

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

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

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

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

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

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

[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 | Zbl

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

[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 | Zbl

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

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

[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 | Zbl

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

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

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

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

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

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

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

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

[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 | Zbl

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

[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 | Zbl

Cité par Sources :