Decidable properties of 2D cellular automata

Creators: Formenti, Enrico; Dennunzio, Alberto

Others:: Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe MC3 ; Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA); Dipartimento di Informatica Sistemistica e Comunicazione (DISCo) ; Università degli Studi di Milano-Bicocca = University of Milano-Bicocca (UNIMIB); Interlink/MIUR project "Cellular Automata: Topological Properties, Chaos and Associated Formal Languages", and by the PRIN/MIUR project "Formal Languages and Automata: Mathematical and Applicative Aspects".; M. Ito and M. Toyma; ANR-05-BLAN-0374,Sycomore,Systèmes complexes et modèles de calcul(2005)

Description

In this paper we study some decidable properties of twodimensional cellular automata (2D CA). The notion of closingness is generalized to the 2D case and it is linked to permutivity and openness. The major contributions of this work are two deep constructions which have been fundamental in order to prove our new results and we strongly believe it will be a valuable tool for proving other new ones in the near future.

Abstract

International audience

Decidable properties of 2D cellular automata

Description

Abstract

Additional details