The fractal structure of cellular automata on abelian groups

Abstract : It is a well-known fact that the spacetime diagrams of some cellular automata have a fractal structure: for instance Pascal's triangle modulo $2$ generates a Sierpinski triangle. Explaining the fractal structure of the spacetime diagrams of cellular automata is a much explored topic, but virtually all of the results revolve around a special class of automata, whose main features include irreversibility, an alphabet with a ring structure and a rule respecting this structure, and a property known as being (weakly) $p$-Fermat. The class of automata that we study in this article fulfills none of these properties. Their cell structure is weaker and they are far from being $p$-Fermat, even weakly. However, they do produce fractal spacetime diagrams, and we will explain why and how. These automata emerge naturally from the field of quantum cellular automata, as they include the classical equivalent of the Clifford quantum cellular automata, which have been studied by the quantum community for several reasons. They are a basic building block of a universal model of quantum computation, and they can be used to generate highly entangled states, which are a primary resource for measurement-based models of quantum computing.
Keywords :
Type de document :
Communication dans un congrès
Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.51-70, 2010, DMTCS Proceedings
Domaine :

Littérature citée [14 références]

https://hal.inria.fr/hal-01185495
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 14:16:39
Dernière modification le : mardi 7 mars 2017 - 15:06:56
Document(s) archivé(s) le : mercredi 26 avril 2017 - 09:44:16

Fichier

dmAL0105.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

• HAL Id : hal-01185495, version 1

Citation

Johannes Gütschow, Vincent Nesme, Reinhard F. Werner. The fractal structure of cellular automata on abelian groups. Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.51-70, 2010, DMTCS Proceedings. 〈hal-01185495〉

Métriques

Consultations de la notice

79

Téléchargements de fichiers