Cellular automata classes: examples.

Marianne Delorme; Jacques Mazoyer

RAIRO - Theoretical Informatics and Applications (2008)

  • Volume: 42, Issue: 1, page 37-53
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Delorme, Marianne, and Mazoyer, Jacques. "Exemples de classes d'automates cellulaires." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 37-53. <http://eudml.org/doc/250334>.

@article{Delorme2008,
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]. },
author = {Delorme, Marianne, Mazoyer, Jacques},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Automates cellulaires; classification; auto-organisation; émergence},
language = {fre},
month = {1},
number = {1},
pages = {37-53},
publisher = {EDP Sciences},
title = {Exemples de classes d'automates cellulaires},
url = {http://eudml.org/doc/250334},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Delorme, Marianne
AU - Mazoyer, Jacques
TI - Exemples de classes d'automates cellulaires
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/1//
PB - EDP Sciences
VL - 42
IS - 1
SP - 37
EP - 53
AB - 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].
LA - fre
KW - Automates cellulaires; classification; auto-organisation; émergence
UR - http://eudml.org/doc/250334
ER -

References

top
  1. N. Boccara and M. Roger, Block transformations of one-dimensional deterministic cellulat automaton rules. J. Phys. A24 (1991) 1849–1865.  
  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.  
  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.  
  5. J.P. Crutchfield and J.E. Hanson, Attractor vicinity decay for a cellular automaton. Chaos3 (1993) 215–224.  
  6. J.P. Crutchfield and J.E. Hanson, Turbulent pattern bases for a cellular automata. Phys. D69 (1993) 279–301.  
  7. J.P. Crutchfield and J.E. Hanson, Computational mechanics of cellular automata: an example. Phys. D103 (1997) 169–189.  
  8. K. Eloranta, Partially permutive cellular automata. Nonlinearity6 (1993) 1009–1023.  
  9. K. Eloranta, Random walks in cellular automata. Nonlinearity6 (1993) 1025–1036.  
  10. K. Eloranta, The dynamics of defect ensembles in one-dimensional cellular automata. J. Statist. Phys.76 (1994) 1377–1398.  
  11. K. Eloranta, Cellular automata for contours dynamics. Phys. D89 (1995) 184–203.  
  12. K. Eloranta and E. Nummelin, The kind of cellular automaton rule 18 performs a random walk. J. Statist. Phys.69 (1992) 1131–1136.  
  13. P. Grassberger, Chaos and diffusion in deterministic cellular automata. Phys. D10 (1984) 52–58.  
  14. P. Grassberger, New mechanism for deterministic diffusion. Phys. Rev. A28 (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.  
  17. M. Hurley, Ergodic aspects of cellular automata. Ergod. Theor. Dyn. Syst.10 (1990) 671–685.  
  18. M. Hurley, Varieties of periodic attractors in cellular automata. T. Am. Math. Soc.326 (1991) 701–726.  
  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. D154 (2001) 240–258.  
  21. P. Kůrka, Languages, equicontinuity and attractors in cellular automata. Ergod. Theor. Dyn. Syst.17 (1997) 417–433.  
  22. P. Kůrka, Cellular automata with vanishing particles. Fund. Inform.58 (2003) 203–221.  
  23. P. Kůrka, On the measure attractor of a cellular automaton. Discret. Contin. Dyn. Syst. (2005) S524–S535.  
  24. P. Kůrka and A. Maass. Limit sets of cellular automata associated to probability measures. J. Statist. Phys.100 (2000) 1031–1047.  
  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.  
  26. B. Martin, A group interpretation of particles generated by one-dimensional cellular automata. Int. J. Mod. Phys. C11 (2000) 101–123.  
  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.  
  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.  
  30. H.V. McIntosh, A concordance for rule 110 (1999). mcintosh/comun  URIhttp://delta.cs.cinvestav.mx/
  31. H.V. McIntosh, Rule 110 as it relates to the presence of gliders (1999). mcintosh/comun/rule110.pdf  URIhttp://delta.cs.cinvestav.mx/
  32. H.V. McIntosh, Rule 110 is universal (1999). mcintosh/comun/texlet/texlet.pdf  URIhttp://delta.cs.cinvestav.mx/
  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. A44 (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.  
  36. N. Ollinger, The intrinsic universality problem of one-dimensional cellular automata, in Proceeding of STACS'03, Springer Verlag (2003) 632–641.  
  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.  
  39. M. Pivato, Algebraic invariants for crystallographics defects in cellular automata. Ergod. Theor. Dyn. Syst.27 (2007) 199–240.  
  40. M. Pivato, Defect particle kinematics in one-dimensional cellular automata. Theoret. Comput. Sci.377 (2007) 205–225.  
  41. M. Pivato, Spectral domain boundaries in cellular automata. Fund. Inform.78 (2007) 417–447.  
  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.  
  45. G. Theyssier, Captive cellular automata, in Proceeding of MFCS'04, Springer Verlag (2004) 427–438.  
  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).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.