Row subshifts and topological entropy of cellular automata
Pietro Di Lena, Luciano Margara · Archivio istituzionale della ricerca (Alma Mater Studiorum Università di Bologna) · 2007
Cellular Automata (CA) are symbolic dynamical systems often used in computer science as models of complex systems [9]. The topological entropy is often referred to as a measure of the complexity of a dynamical system [1]. The topological entropy of a CA (AZ, F ) is defined in terms of the entropy of its column subshifts Σk [4], H(F ) = limk→∞ H(Σk) k . Here we address the following question: is it true that for every cellular automaton (AZ, F ) there exists a number k > 0 such that H(F ) = H(Σk)? This property holds for some well known classes of CA and, in particular, it is always true for one-sided CA [2]. In order to investigate this problem, we attach to the dynamics of a cellular automaton (AZ, F ) a sequence of shift spaces (Ωt)t>0, we call row subshifts in contrast to column subshifts. We provide a strong characterization of the shift space sequence (Ωt)t>0 and we explore how it is related to the growth rate of different blocks of column subshifts.