Arithmetical Complexity of the Language of Generic Limit Sets of Cellular Automata

DOI10.1016/J.JCSS.2023.01.002MaRDI QIDQ6396391arXivFDO

Authors Solène J. Esnay, A. Núñez, Ilkka A. Törmä

Publication date 13 April 2022

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.JCSS.2023.01.002

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

arXiv classification

cs.FLmath.DS

Abstract: 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"orm"a. 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 $P{i}_2^0$ language if they are inclusion-minimal, a $Sigm{a}_1^0$ language if the cellular automaton has equicontinuous points, and that these bounds are tight. We also prove that many chain mixing $P{i}_2^0$ subshifts and all chain mixing $Delt{a}_2^0$ subshifts are realizable as generic limit sets. As a corollary, we characterize the minimal subshifts that occur as generic limit sets.

This page was built for publication: Arithmetical Complexity of the Language of Generic Limit Sets of Cellular Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6396391)