Directional Dynamics along Arbitrary Curves in Cellular Automata - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2011

Directional Dynamics along Arbitrary Curves in Cellular Automata

Résumé

This paper studies directional dynamics on one-dimensional cellular automata, a formalism previously introduced by the third author. The central idea is to study the dynamical behavior of a cellular automaton through the conjoint action of its global rule (temporal action) and the shift map (spacial action): qualitative behaviors inherited from topological dynamics (equicontinuity, sensitivity, expansivity) are thus considered along arbitrary curves in space-time. The main contributions of the paper concern equicontinuous dynamics which can be connected to the notion of consequences of a word. We show that there is a cellular automaton with an equicontinuous dynamics along a parabola, but which is sensitive along any linear direction. We also show that real numbers that occur as the slope of a limit linear direction with equicontinuous dynamics in some cellular automaton are exactly the computably enumerable numbers.
Fichier principal
Vignette du fichier
dpst.pdf (2.24 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00451729 , version 1 (29-01-2010)
hal-00451729 , version 2 (19-08-2010)
hal-00451729 , version 3 (28-06-2013)

Identifiants

Citer

Martin Delacourt, Victor Poupet, Mathieu Sablik, Guillaume Theyssier. Directional Dynamics along Arbitrary Curves in Cellular Automata. Theoretical Computer Science, 2011, 412, pp.3800-3821. ⟨10.1016/j.tcs.2011.02.019⟩. ⟨hal-00451729v3⟩
440 Consultations
367 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More