Charles Explorer logo
🇬🇧

Subshift attractors in cellular automata

Publication |
2007

Abstract

A subshift attractor is a two-sided subshift which is an attractor of a cellular automaton. We prove that each subshift attractor is chain-mixing, contains a configuration which is both F-periodic and shift-periodic and the complement of its language is recursively enumerable.

We prove that a subshift of finite type is an attractor of a cellular automaton iff it is mixing. We identify a class of chain-mixing sofic subshifts which are not subshift attractors