Leader election on two-dimensional periodic cellular automata
type: Item
instance of: scholarly article
title: Leader election on two-dimensional periodic cellular automata
zbMATH Open document ID: 1358.68207
author: Nicolas Bacquey
published in: Theoretical Computer Science
publication date: 2016-12-23T00:00:00Z
review text: Two-dimensional cellular automata on states periodic in two directions (that is, on a finite torus) are studied from the viewpoint of computational power. A selection problem (`leader election') is defined, and an algorithm is presented to solve this problem. Other uses of the algorithm, and possible extensions to higher dimensions, are discussed.
Mathematics Subject Classification ID: 68Q80
zbMATH DE Number: 6668316
zbMATH Keywords: cellular automata
zbMATH Keywords: leader election
zbMATH Keywords: bi-periodical configuration
zbMATH Keywords: equivalence classes
zbMATH Keywords: uniform computation
reviewed by: Thomas B. Ward
MaRDI profile type: Publication
full work available at URL: j.tcs.2016.10.021
OpenAlex ID: W2553612887
cites work: Complexity classes on spatially periodic Cellular Automata
cites work: An 8-state minimal time solution to the firing squad synchronization problem
cites work: On translating one polyomino to tile the plane
cites work: Q3086926
cites work: Theory of cellular automata: a survey
cites work: A six-state minimal time solution to the Firing squad synchronization problem
cites work: Computations on one-dimensional cellular automata
cites work: Signals in one-dimensional cellular automata
cites work: Algorithms for leader election by cellular automata
cites work: Q3605708
cites work: Proving theorems by pattern recognition I
DOI: 10.1016/J.TCS.2016.10.021
description: scientific article; zbMATH DE number 6668316