A4 Refereed article in a conference publication

Computational Aspects of Cellular Automata on Countable Sofic Shifts




AuthorsVille Salo, Ilkka Törmä

EditorsBranislav Rovan, Vladimiro Sassone, Peter Widmayer

Publishing placeBerlin

Publication year2012

JournalLecture Notes in Computer Science

Book title Mathematical Foundations of Computer Science 2012

Article number67

Series titleLecture Notes in Computer Science

Volume7464

First page 777

Last page788

Number of pages12

ISBN978-3-642-32588-5

eISBN978-3-642-32589-2

ISSN0302-9743

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


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.



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