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.  Zbl0724.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.  Zbl0941.37006
  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.  Zbl0892.58051
  5. J.P. Crutchfield and J.E. Hanson, Attractor vicinity decay for a cellular automaton. Chaos3 (1993) 215–224.  Zbl1055.37508
  6. J.P. Crutchfield and J.E. Hanson, Turbulent pattern bases for a cellular automata. Phys. D69 (1993) 279–301.  Zbl0794.68111
  7. J.P. Crutchfield and J.E. Hanson, Computational mechanics of cellular automata: an example. Phys. D103 (1997) 169–189.  Zbl1194.37022
  8. K. Eloranta, Partially permutive cellular automata. Nonlinearity6 (1993) 1009–1023.  Zbl0791.58051
  9. K. Eloranta, Random walks in cellular automata. Nonlinearity6 (1993) 1025–1036.  Zbl0791.58052
  10. K. Eloranta, The dynamics of defect ensembles in one-dimensional cellular automata. J. Statist. Phys.76 (1994) 1377–1398.  Zbl0837.60092
  11. K. Eloranta, Cellular automata for contours dynamics. Phys. D89 (1995) 184–203.  Zbl0900.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.  Zbl0891.68065
  13. P. Grassberger, Chaos and diffusion in deterministic cellular automata. Phys. D10 (1984) 52–58.  Zbl0562.68039
  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.  Zbl0182.56901
  17. M. Hurley, Ergodic aspects of cellular automata. Ergod. Theor. Dyn. Syst.10 (1990) 671–685.  Zbl0695.58019
  18. M. Hurley, Varieties of periodic attractors in cellular automata. T. Am. Math. Soc.326 (1991) 701–726.  Zbl0738.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. D154 (2001) 240–258.  Zbl0986.37013
  21. P. Kůrka, Languages, equicontinuity and attractors in cellular automata. Ergod. Theor. Dyn. Syst.17 (1997) 417–433.  Zbl0876.68075
  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.  Zbl1144.37303
  24. P. Kůrka and A. Maass. Limit sets of cellular automata associated to probability measures. J. Statist. Phys.100 (2000) 1031–1047.  Zbl0995.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.  Zbl1053.54046
  26. B. Martin, A group interpretation of particles generated by one-dimensional cellular automata. Int. J. Mod. Phys. C11 (2000) 101–123.  Zbl0940.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.  Zbl0564.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.  Zbl0893.68108
  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.  Zbl1056.68104
  36. N. Ollinger, The intrinsic universality problem of one-dimensional cellular automata, in Proceeding of STACS'03, Springer Verlag (2003) 632–641.  Zbl1035.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.  Zbl1072.37016
  39. M. Pivato, Algebraic invariants for crystallographics defects in cellular automata. Ergod. Theor. Dyn. Syst.27 (2007) 199–240.  Zbl1129.37007
  40. M. Pivato, Defect particle kinematics in one-dimensional cellular automata. Theoret. Comput. Sci.377 (2007) 205–225.  Zbl1115.68102
  41. M. Pivato, Spectral domain boundaries in cellular automata. Fund. Inform.78 (2007) 417–447.  Zbl1127.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.  Zbl0268.68044
  45. G. Theyssier, Captive cellular automata, in Proceeding of MFCS'04, Springer Verlag (2004) 427–438.  Zbl1096.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).  Zbl0609.68043

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.