Computational Aspects of Cellular Automata on Countable Sofic Shifts



: Ville Salo, Ilkka Törmä

: Branislav Rovan, Vladimiro Sassone, Peter Widmayer

: Berlin

: 2012

: Lecture Notes in Computer Science

: Mathematical Foundations of Computer Science 2012

: 67

: Lecture Notes in Computer Science

: 7464

: 777

: 788

: 12

: 978-3-642-32588-5

: 978-3-642-32589-2

: 0302-9743

DOI: https://doi.org/10.1007/978-3-642-32589-2_67


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.



Last updated on 2024-26-11 at 11:13