Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Computational Aspects of Cellular Automata on Countable Sofic Shifts
verfasst von : Ville Salo, Ilkka Törmä
Erschienen in: Mathematical Foundations of Computer Science 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 stability of the limit set, and the existence of a
$\mathrm{\Pi}^0_1$
-complete limit set and a
$\mathrm{\Sigma}^0_3$
-complete asymptotic set.