论文标题
蜂窝自动机通用极限集的语言的算术复杂性
Arithmetical Complexity of the Language of Generic Limit Sets of Cellular Automata
论文作者
论文摘要
动态系统的通用限制集是从拓扑意义上吸引大多数空间的最小集合：它是最小的闭合套件，带有一个相当的吸引力盆地。由米尔诺（Milnor）引入的，已在Djenaoui和Guillon，Delacourt和Törmä的一维蜂窝自动机中进行了研究。在本文中，我们介绍了具有规定属性的蜂窝自动机的通用极限集的实现。我们表明，如果蜂窝自动机具有等准点，并且这些范围很紧。我们还证明，许多链条混合$π^0_2 $ subshifts和所有链混合$δ^0_2 $ subshifts都是可以将其视为通用限制集的。作为推论，我们将最小的子迁移表征为通用限制集。
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 $Π^0_2$ language if they are inclusion-minimal, a $Σ^0_1$ language if the cellular automaton has equicontinuous points, and that these bounds are tight. We also prove that many chain mixing $Π^0_2$ subshifts and all chain mixing $Δ^0_2$ subshifts are realizable as generic limit sets. As a corollary, we characterize the minimal subshifts that occur as generic limit sets.
