• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Computational Aspects of Cellular Automata on Countable Sofic Shifts

Ville Salo, Ilkka Törmä, Computational Aspects of Cellular Automata on Countable Sofic Shifts . In: Branislav Rovan, Vladimiro Sassone, Peter Vidmayer (Eds.), Mathematical Foundations of Computer Science 2012, 777–788 , Springer, 2012.

http://dx.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 stability of the limit set, and the existence of a $\Pi^0_1$-complete limit set and a $\Sigma^0_3$-complete asymptotic set.

BibTeX entry:

@INPROCEEDINGS{inpSaTx12d,
  title = {Computational Aspects of Cellular Automata on Countable Sofic Shifts },
  booktitle = {Mathematical Foundations of Computer Science 2012},
  author = {Salo, Ville and Törmä, Ilkka},
  editor = {Rovan, Branislav and Sassone, Vladimiro and Vidmayer, Peter},
  publisher = {Springer},
  pages = {777–788 },
  year = {2012},
  keywords = {cellular automata, subshifts, nontransitivity, undecidability},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication