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.MFCS.2020.22
URN: urn:nbn:de:0030-drops-126903
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12690/
Chatterjee, Krishnendu ;
Ibsen-Jensen, Rasmus ;
Jecker, Ismaël ;
Svoboda, Jakub
Simplified Game of Life: Algorithms and Complexity
Abstract
Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A configuration is a mapping of the vertices to the types. An update rule describes how the type of a vertex is updated given the types of its neighbors. In every round, all vertices are updated synchronously, which leads to a configuration update. While in general, Game of Life allows a broad range of update rules, we focus on two simple families of update rules, namely, underpopulation and overpopulation, that model several interesting dynamics studied in the literature. In both settings, a dead vertex requires at least a desired number of live neighbors to become alive. For underpopulation (resp., overpopulation), a live vertex requires at least (resp. at most) a desired number of live neighbors to remain alive. We study the basic computation problems, e.g., configuration reachability, for these two families of rules. For underpopulation rules, we show that these problems can be solved in polynomial time, whereas for overpopulation rules they are PSPACE-complete.
BibTeX - Entry
@InProceedings{chatterjee_et_al:LIPIcs:2020:12690,
author = {Krishnendu Chatterjee and Rasmus Ibsen-Jensen and Isma{\"e}l Jecker and Jakub Svoboda},
title = {{Simplified Game of Life: Algorithms and Complexity}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {22:1--22:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12690},
URN = {urn:nbn:de:0030-drops-126903},
doi = {10.4230/LIPIcs.MFCS.2020.22},
annote = {Keywords: game of life, cellular automata, computational complexity, dynamical systems}
}
|
Keywords: |
|
game of life, cellular automata, computational complexity, dynamical systems |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
