A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Computational Aspects of Cellular Automata on Countable Sofic Shifts
Tekijät: Ville Salo, Ilkka Törmä
Toimittaja: Branislav Rovan, Vladimiro Sassone, Peter Widmayer
Kustannuspaikka: Berlin
Julkaisuvuosi: 2012
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Mathematical Foundations of Computer Science 2012
Artikkelin numero: 67
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 7464
Aloitussivu: 777
Lopetussivu: 788
Sivujen määrä: 12
ISBN: 978-3-642-32588-5
eISBN: 978-3-642-32589-2
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-642-32589-2_67
Tiivistelmä
We investigate the computational properties of cellular automata on countable (equivalently, zero entropy) sofic shifts with an emphasis on nilpotency, periodicity, and asymptotic behavior. As a tool for proving decidability results, we prove the Starfleet Lemma, which is of independent interest. We present computational results including the decidability of nilpotency and periodicity, the undecidability of stabil-
ity of the limit set, and the existence of a Π01 -complete limit set and a Σ03 -complete asymptotic set.
We investigate the computational properties of cellular automata on countable (equivalently, zero entropy) sofic shifts with an emphasis on nilpotency, periodicity, and asymptotic behavior. As a tool for proving decidability results, we prove the Starfleet Lemma, which is of independent interest. We present computational results including the decidability of nilpotency and periodicity, the undecidability of stabil-
ity of the limit set, and the existence of a Π01 -complete limit set and a Σ03 -complete asymptotic set.
Turun yliopiston Tutkimustietojärjestelmän portaali