Refereed article in conference proceedings (A4)
Complexity of Generic Limit Sets of Cellular Automata
List of Authors: Törmä Ilkka
Editors: Hector Zenil
Conference name: International Workshop on Cellular Automata and Discrete Complex Systems
Publisher: Springer Science and Business Media Deutschland GmbH
Publication year: 2020
Journal: Lecture Notes in Computer Science
Book title *: Cellular Automata and Discrete Complex Systems 26th IFIP WG 1.5 International Workshop, AUTOMATA 2020, Stockholm, Sweden, August 10–12, 2020, Proceedings
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Title of series: Lecture Notes in Computer Science
Volume number: 12286
Start page: 126
End page: 138
ISBN: 978-3-030-61587-1
eISBN: 978-3-030-61588-8
ISSN: 0302-9743
DOI: http://dx.doi.org/10.1007/978-3-030-61588-8_10
Self-archived copy’s web address: 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.
Downloadable publication This is an electronic reprint of the original article. |  |
