Dantchev, Stefan (2011) 'Dynamic neighbourhood cellular automata.', The computer journal., 54 (1). pp. 26-30.
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.
|Keywords:||Cellular automata, Distributed algorithms, Syncronization, Firing squad problem.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (122Kb)
|Publisher Web site:||https://doi.org/10.1093/comjnl/bxp019|
|Publisher 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.|
|Record Created:||15 Dec 2009 10:35|
|Last Modified:||06 Sep 2017 09:17|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|