Dynamic Neighbourhood Cellular Automata

Dantchev, Stefan

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.
• Public URL: https://durham-repository.worktribe.com/output/1546698