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

Snakes and Cellular Automata: Reductions and Inseparability Results

Jarkko Kari, Snakes and Cellular Automata: Reductions and Inseparability Results. In: Alexander Kulikov, Nikolay Vereshchagin (Eds.), Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings, Lecture Notes in Computer Science 6651, 223–232, Springer, 2011.

Abstract:

A careful analysis of an old undecidability proof reveals that periodicity and non-surjectivity of two-dimensional cellular automata are recursively inseparable properties. Analogously, Wang tile sets that admit tilings of arbitrarily long loops (and hence also infinite snakes) are recursively inseparable from the tile sets that admit no loops and no infinite snakes. The latter inseparability result actually implies the first one in a trivial way.

BibTeX entry:

@INPROCEEDINGS{inpKari_Jarkko11a,
  title = {Snakes and Cellular Automata: Reductions and Inseparability Results},
  booktitle = {Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg,  Russia, June 14-18, 2011. Proceedings},
  author = {Kari, Jarkko},
  volume = {6651},
  series = {Lecture Notes in Computer Science},
  editor = {Kulikov, Alexander and Vereshchagin, Nikolay},
  publisher = {Springer},
  pages = {223–232},
  year = {2011},
}

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

Publication Forum rating of this publication: level 1

Edit publication