A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Arithmetical complexity of the language of generic limit sets of cellular automata
Tekijät: Esnay Solène J, Núñez Alonso, Törmä Ilkka
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2023
Journal: Journal of Computer and System Sciences
Tietokannassa oleva lehden nimi: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Lehden akronyymi: J COMPUT SYST SCI
Vuosikerta: 134
Aloitussivu: 20
Lopetussivu: 41
Sivujen määrä: 22
ISSN: 0022-0000
DOI: https://doi.org/10.1016/j.jcss.2023.01.002
Verkko-osoite: https://doi.org/10.1016/j.jcss.2023.01.002
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/179463124
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 Torma. 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 Pi(0)(2) language if they are inclusion-minimal, a Sigma(0)(1) language if the cellular automaton has equicontinuous points, and that these bounds are tight. We also prove that many chain mixing Pi(0)(2) subshifts and all chain mixing Delta(0)(2) subshifts are realizable as generic limit sets. As a corollary, we characterize the minimal subshifts that occur as generic limit sets. (c) 2023 Elsevier Inc. All rights reserved.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
