Coalescing Cellular Automata -- Synchronizing CA by Common Random Source and Varying Asynchronicity

Abstract : We say that a Cellular Automata (CA) is coalescing when its execution on two distinct (random) initial configurations in the same asynchronous mode (the same cells are updated in each configuration at each time step) makes both configurations become identical after a reasonable time. We prove coalescence for two elementary rules, non coalescence for two other, and show that there exists infinitely many coalescing CA. We then conduct an experimental study on all elementary CA and show that some rules exhibit a phase transition, which belongs to the universality class of directed percolation.
Type de document :
Pré-publication, Document de travail
2007
Liste complète des métadonnées

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00196635
Contributeur : Jean-Baptiste Rouquier <>
Soumis le : jeudi 13 décembre 2007 - 11:06:16
Dernière modification le : jeudi 12 juillet 2018 - 01:12:26

Lien texte intégral

Identifiants

  • HAL Id : ensl-00196635, version 1
  • ARXIV : 0712.1992

Citation

Jean-Baptiste Rouquier, Michel Morvan. Coalescing Cellular Automata -- Synchronizing CA by Common Random Source and Varying Asynchronicity. 2007. 〈ensl-00196635〉

Partager

Métriques

Consultations de la notice

445