Two-dimensional languages and cellular automata (Q2909191)

This article studies cellular automata (CA) through the new point of view of the picture language that they generate, that is, the set of blocks appearing in the half-planes that the evolution of bi-infinite configurations draw (space-time diagrams). The authors define the so-called factorial-local CA, whose language can be defined from a particular (finite) family of allowed blocks of some fixed size.NEWLINENEWLINEThey remark that this fixed size can always be taken to be the diameter, and that this class corresponds to the class of CA whose all (or one) sufficiently large traces (that is, sets of infinite words appearing in columns of the space-time diagrams) are subshifts of finite type. This class was studied in [\textit{P. Di Lena}, J. Cell. Autom. 2, No. 2, 121--129 (2007; Zbl 1135.68488)]. In particular, it includes nilpotent CA and is included in those having the shadowing property (see [\textit{P. Kůrka}, Topological and symbolic dynamics. Cours Spécialisés (Paris) 11. Paris: Société Mathématique de France (2003; Zbl 1038.37011)]); they give a counter-example to the converse, as well as one factorial-local CA with one trace not of finite type.NEWLINENEWLINEThe main result is the construction of a suitable (complicated) finite automaton that gives the decidability of whether a CA of a given radius corresponds to a given factorial-local language, from which is derived that the property of being factor-local is undecidable -thanks to the above characterization, this appears to be a particular case of [\textit{P. di Lena}, in: Proc. of the 4th IFIP Int. Conf. on Theor, Comput. Sci., 185--196 (2006)].