2022/04/13 by Solène J. Esnay, Esnay, Solène J., Alonso Núñez +3
Computer Science · Mathematics · #37B15 #Cellular Automata and Applications #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2204.06215
openalex publication_date 2022/04/13 · openalex created_date 2022/04/19 · openalex updated_date 2026/07/28
The generic limit set of a dynamical system is the smallest set that attracts most of the space in a topological sense: it is the smallest closed set with a comeager basin of attraction. Introduced by Milnor, it has been studied in the context of one-dimensional cellular automata by Djenaoui and Guillon, Delacourt, and Törmä. In this article we present complexity bounds on realizations of generic limit sets of cellular automata with prescribed properties. We show that generic limit sets have a Π02 language if they are inclusion-minimal, a Σ01 language if the cellular automaton has equicontinuous points, and that these bounds are tight. We also prove that many chain mixing Π02 subshifts and all chain mixing Δ02 subshifts are realizable as generic limit sets. As a corollary, we characterize the minimal subshifts that occur as generic limit sets.