Skip to main content

Research Repository

Advanced Search

Dynamic Neighbourhood Cellular Automata

Dantchev, Stefan

Dynamic Neighbourhood Cellular Automata Thumbnail



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.


Dantchev, S. (2011). Dynamic Neighbourhood Cellular Automata. The Computer Journal, 54(1), 26-30.

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
Keywords Cellular automata, Distributed algorithms, Syncronization, Firing squad problem.


Accepted Journal Article (124 Kb)

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

You might also like

Downloadable Citations