License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.4
URN: urn:nbn:de:0030-drops-57054
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5705/
Go to the corresponding LIPIcs Volume Portal

Kari, Jarkko

Tutorial on Cellular Automata and Tilings (Tutorial)

pdf-format:
5.pdf (0.3 MB)

Abstract

Cellular automata (CA) are massively parallel systems where a regular grid of finite symbols is updated according to a synchronous application of the same local update rule everywhere. A closely related concept is that of Wang tiles where a local relation between neighboring symbols determines allowed combinations of symbols in the grid. In this tutorial we start with classical results on cellular automata, such as the Garden-of-Eden theorems, the Curtis-Hedlund-Lyndon-theorem and the balance property of surjective cellular automata. We then discuss Wang tiles and, in particular, the concept of aperiodicity and the undecidability of the domino problem. The domino problem is the decision problem to determine if a given Wang tile set admits any valid tilings of the grid. We relate Wang tiles to cellular automata, and establish a number of undecidability results for cellular automata.

BibTeX - Entry

@InProceedings{kari:LIPIcs:2016:5705,
  author =	{Jarkko Kari},
  title =	{{Tutorial on Cellular Automata and Tilings (Tutorial)}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5705},
  URN =		{urn:nbn:de:0030-drops-57054},
  doi =		{10.4230/LIPIcs.STACS.2016.4},
  annote =	{Keywords: cellular automata, wang tiles, decision problems, dynamics}
}

Keywords: cellular automata, wang tiles, decision problems, dynamics
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI