A4 Refereed article in a conference publication
Computational Aspects of Cellular Automata on Countable Sofic Shifts
Authors: Ville Salo, Ilkka Törmä
Editors: Branislav Rovan, Vladimiro Sassone, Peter Widmayer
Publishing place: Berlin
Publication year: 2012
Journal: Lecture Notes in Computer Science
Book title : Mathematical Foundations of Computer Science 2012
Article number: 67
Series title: Lecture Notes in Computer Science
Volume: 7464
First page : 777
Last page: 788
Number of pages: 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(external)
Abstract
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.
UTU Research Portal