Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-27T08:28:31.815Z Has data issue: false hasContentIssue false
  • English
  • Français

Exemples de classes d'automates cellulaires

Published online by Cambridge University Press:  18 January 2008

Marianne Delorme  and
Jacques Mazoyer
Marianne Delorme
Affiliation:
Laboratoire de l'Informatique du Parallélisme, École Normale Supérieure de Lyon, 46 allée d'Italie, 69634 Lyon, France; [email protected] Institut des Systèmes Complexes, IXXI, 5 rue du Vercors, Lyon 69007, France.
Jacques Mazoyer
Affiliation:
Laboratoire de l'Informatique du Parallélisme, École Normale Supérieure de Lyon, 46 allée d'Italie, 69634 Lyon, France; [email protected] Institut des Systèmes Complexes, IXXI, 5 rue du Vercors, Lyon 69007, France.
Get access

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

Keywords

Cellular automataclassificationself-organizationemergenceAutomates cellulairesclassificationauto-organisationémergence
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 42 , Issue 1: A nonstandard spirit among computer scientists:a tribute to Serge Grigorieff at the occasion of his 60th birthday , January 2008 , pp. 37 - 53
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Boccara, N. and Roger, M., Block transformations of one-dimensional deterministic cellulat automaton rules. J. Phys. A 24 (1991) 1849–1865. CrossRef
G. Cattaneo, E. Formenti, L. Margara and J. Mazoyer, Shift invariant distance on $s^{{\mathbb{Z}}}$ with non trivial topology, in Proceeding of MFCS'97, Springer Verlag (1997) 376–381.
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.
Crutchfield, J.P. and Hanson, J.E., The attractor basin portait of a cellular automaton. J. Statist. Phys. 66 (1992) 1415–1462.
Crutchfield, J.P. and Hanson, J.E., Attractor vicinity decay for a cellular automaton. Chaos 3 (1993) 215–224. CrossRef
Crutchfield, J.P. and Hanson, J.E., Turbulent pattern bases for a cellular automata. Phys. D 69 (1993) 279–301. CrossRef
Crutchfield, J.P. and Hanson, J.E., Computational mechanics of cellular automata: an example. Phys. D 103 (1997) 169–189.
Eloranta, K., Partially permutive cellular automata. Nonlinearity 6 (1993) 1009–1023. CrossRef
Eloranta, K., Random walks in cellular automata. Nonlinearity 6 (1993) 1025–1036. CrossRef
Eloranta, K., The dynamics of defect ensembles in one-dimensional cellular automata. J. Statist. Phys. 76 (1994) 1377–1398. CrossRef
Eloranta, K., Cellular automata for contours dynamics. Phys. D 89 (1995) 184–203. CrossRef
Eloranta, K. and Nummelin, E., The kind of cellular automaton rule 18 performs a random walk. J. Statist. Phys. 69 (1992) 1131–1136. CrossRef
Grassberger, P., Chaos and diffusion in deterministic cellular automata. Phys. D 10 (1984) 52–58. CrossRef
Grassberger, P., New mechanism for deterministic diffusion. Phys. Rev. A 28 (1984) 3666–3667. CrossRef
J.E. Hanson, Computational Mechnaics if Cellular Automata. Ph.D. Thesis, University of California, Ann Arbor, MI (1993). Published by University Microfilms.
Hedlund, G., Endomorphism and automorphism of the shift dynamical system. Math. Syst. Theor. 3 (1969) 320–375. CrossRef
Hurley, M., Ergodic aspects of cellular automata. Ergod. Theor. Dyn. Syst. 10 (1990) 671–685.
Hurley, M., Varieties of periodic attractors in cellular automata. T. Am. Math. Soc. 326 (1991) 701–726. CrossRef
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.
Hordijk, W., Crutchfield, J.P. and Shalizi, C.R., Upper bound of the products of particle interactions in cellular automata. Phys. D 154 (2001) 240–258. CrossRef
Kůrka, P., Languages, equicontinuity and attractors in cellular automata. Ergod. Theor. Dyn. Syst. 17 (1997) 417–433. CrossRef
Kůrka, P., Cellular automata with vanishing particles. Fund. Inform. 58 (2003) 203–221.
P. Kůrka, On the measure attractor of a cellular automaton. Discret. Contin. Dyn. Syst. (2005) S524–S535.
P. Kůrka and A. Maass. Limit sets of cellular automata associated to probability measures. J. Statist. Phys. 100 (2000) 1031–1047.
Maass, A., Host, B. and Martinez, S., Uniform Bernoulli measure in dynamics of permutive cellular automata with algebraic local rules. Discrete Contin. Dyn. Syst. 9 (2003) 1423–1446. CrossRef
Martin, B., A group interpretation of particles generated by one-dimensional cellular automata. Int. J. Mod. Phys. C 11 (2000) 101–123. CrossRef
B. Martin, Automates cellulaires, information et chaos. Ph.D. Thesis, École Normale Supérieure de Lyon (2001).
Martin, O., Odlysko, A. and Wolfram, S., Algebraic properties of cellular automata. Commun. Math. Phys. 93 (1984) 219–258. CrossRef
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.
H.V. McIntosh, A concordance for rule 110 (1999). http://delta.cs.cinvestav.mx/ mcintosh/comun
H.V. McIntosh, Rule 110 as it relates to the presence of gliders (1999). http://delta.cs.cinvestav.mx/ mcintosh/comun/rule110.pdf
H.V. McIntosh, Rule 110 is universal (1999). http://delta.cs.cinvestav.mx/ mcintosh/comun/texlet/texlet.pdf
Nasser, J., Boccara, N. and Roger, M., Particle-like structures and their interactions in spatiotemporal patterns generated ny one-dimentional cellular automata. Phys. Rev. A 44 (1991) 866–875. CrossRef
N. Ollinger, Automates cellulaires: structures. Ph.D. Thesis, École Normale Supérieure de Lyon (2002).
N. Ollinger, The quest for small universal cellular automata, in Proceeding of ICALP'02, 3 Springer Verlag (2002) 376–381.
N. Ollinger, The intrinsic universality problem of one-dimensional cellular automata, in Proceeding of STACS'03, Springer Verlag (2003) 632–641.
N. Ollinger and G. Richard, On the universality of rule 110, in Proceedings of DMTCS'04 (2004).
Pivato, M., Invariant measures for bipermutive cellular automata. Discret. Contin. Dyn. Syst. 12 (2005) 723–736. CrossRef
Pivato, M., Algebraic invariants for crystallographics defects in cellular automata. Ergod. Theor. Dyn. Syst. 27 (2007) 199–240. CrossRef
Pivato, M., Defect particle kinematics in one-dimensional cellular automata. Theoret. Comput. Sci. 377 (2007) 205–225. CrossRef
Pivato, M., Spectral domain boundaries in cellular automata. Fund. Inform. 78 (2007) 417–447.
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.
I. Rapaport, Ordre induit sur les automates cellulaires par l'opération de regroupement. Ph.D. Thesis, École Normale Supérieure de Lyon (1998).
Smith, A., Real time languages by one-dimensional cellular automata. J. Comput. Syst. Sci. 6 (1972) 233–253. CrossRef
G. Theyssier, Captive cellular automata, in Proceeding of MFCS'04, Springer Verlag (2004) 427–438.
G. Theyssier, Automates cellulaires : un modèle de complexité. Ph.D. Thesis, École Normale Supérieure de Lyon (2005).
S. Wolfram, Theory and applications of cellular automata. World Scientific, Singapore (1986).