Chaotic Subshifts and Related Languages Applications to one-dimensional Cellular Automata

Issue title: Cellular Automata

Article type: Research Article

Authors: Cattaneo, Gianpiero | Dennunzio, Alberto | Margara, Luciano

Affiliations: Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy | Dipartimento di Scienze dell'Informazione, Università di Bologna, Via Mura Anteo Zamboni 7, Bologna, Italy

Abstract: Subshift behaviors of one-dimensional (1D) bi-infinite Cellular Automata are studied. In particular the conditions under which subshifts generated by CA 1D dynamical systems exhibit some components of the chaotic behavior (in particular transitivity, topological mixing and strong transitivity) are investigated. A complete classification of all elementary (Boolean radius one) CA with respect to subshifts is given.

Keywords:

Journal: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 39-80, 2002