Nicolas Bacquey
GREYC, Université de Caen Normandie
https://www.researchgate.net/scientific-contributions/Nicolas-Bacquey-2078941943
Date(s) : 05/04/2016 iCal
11 h 00 min - 12 h 00 min
La configuration d’un automate cellulaire peut être considérée comme une image de dimension quelconque, qui subit des transformations au cours du temps.
Par définition du modèle, cette image est infinie. Toutefois, lorsqu’on considère un automate comme un modèle de calcul, il est commun de traiter des configurations à support fini, car les données à traiter sont elles-mêmes finies.
Le cas des configurations périodiques est un cas particulier de configurations à support fini. Dans ce contexte, on s’intéresse aux automates cellulaires comme reconnaisseurs de langages, et on étudie les contraintes imposées par la structure de l’entrée sur les langages qu’il est possible de reconnaître.
Dans le cas des automates de dimension 1, ces langages sont connus : ce sont les langages cycliques. On étendra cette notion en dimension supérieure, pour aboutir à la notion de « motif primitif » d’une image de dimension quelconque.
On étudiera particulièrement ces motifs en dimension 2 : on en présentera une caractérisation exhaustive et on discutera de certaines de leurs propriétés.
Primitive patterns in any dimension: a strict constraint on the recognition capacities of cellular automata with periodic input
The configuration of a cellular automaton can be considered as an image of any dimension, which undergoes transformations over time. By definition of the model, this image is infinite. However, when considering an automaton as a computational model, it is common to deal with finite support configurations, because the data to be processed is itself finite. The case of periodic configurations is a special case of finite support configurations. In this context, we are interested in cellular automata as language recognizers, and we study the constraints imposed by the structure of the input on the languages that it is possible to recognize. In the case of 1-dimensional automata, these languages are known: they are cyclic languages. We will extend this notion in higher dimension, to end up with the notion of « primitive pattern » of an image of any dimension. We will particularly study these patterns in dimension 2: we will present an exhaustive characterization and we will discuss some of their properties.
https://tel.archives-ouvertes.fr/tel-01261424
Catégories