Dynamic Neighbourhood Cellular Automata

Dantchev, Stefan

doi:10.1093/comjnl/bxp019

Dynamic Neighbourhood Cellular Automata

Dantchev, Stefan

Authors

Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor

Abstract

We propose a definition of cellular automaton in which each cell can change its neighbourhood during a computation. This is done locally by looking not farther than neighbours of neighbours and the number of links remains bounded by a constant throughout. We suggest that dynamic neighbourhood cellular automata can serve as a theoretical model in studying algorithmic and computational complexity issues of ubiquitous computations. We illustrate our approach by giving an optimal, logarithmic time solution of the Firing Squad Synchronization problem in this setting.

Citation

Dantchev, S. (2011). Dynamic Neighbourhood Cellular Automata. The Computer Journal, 54(1), 26-30. https://doi.org/10.1093/comjnl/bxp019

Journal Article Type	Article
Online Publication Date	Mar 28, 2009
Publication Date	Jan 1, 2011
Deposit Date	Dec 15, 2009
Publicly Available Date	Sep 6, 2017
Journal	The Computer Journal
Print ISSN	0010-4620
Electronic ISSN	1460-2067
Publisher	BCS, The Chartered Institute for IT
Peer Reviewed	Peer Reviewed
Volume	54
Issue	1
Pages	26-30
DOI	https://doi.org/10.1093/comjnl/bxp019
Keywords	Cellular automata, Distributed algorithms, Syncronization, Firing squad problem.

Files

Accepted Journal Article (124 Kb)
PDF

Copyright Statement
This is a pre-copyedited, author-produced version of an article accepted for publication in The Computer Journal following peer review. The version of record Dantchev, Stefan (2011). Dynamic Neighbourhood Cellular Automata. The Computer Journal 54(1): 26-30 is available online at https://doi.org/10.1093/comjnl/bxp019.