A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Complexity of Generic Limit Sets of Cellular Automata
Tekijät: Törmä Ilkka
Toimittaja: Hector Zenil
Konferenssin vakiintunut nimi: International Workshop on Cellular Automata and Discrete Complex Systems
Kustantaja: Springer Science and Business Media Deutschland GmbH
Julkaisuvuosi: 2020
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Cellular Automata and Discrete Complex Systems 26th IFIP WG 1.5 International Workshop, AUTOMATA 2020, Stockholm, Sweden, August 10–12, 2020, Proceedings
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 12286
Aloitussivu: 126
Lopetussivu: 138
ISBN: 978-3-030-61587-1
eISBN: 978-3-030-61588-8
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-030-61588-8_10
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/51158147
The generic limit set of a topological dynamical system is the smallest closed subset of the phase space that has a comeager realm of attraction. It intuitively captures the asymptotic dynamics of almost all initial conditions. It was defined by Milnor and studied in the context of cellular automata, whose generic limit sets are subshifts, by Djenaoui and Guillon. In this article we study the structural and computational restrictions that apply to generic limit sets of cellular automata. As our main result, we show that the language of a generic limit set can be at most Σ03-hard, and lower in various special cases. We also prove a structural restriction on generic limit sets with a global period.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
