Skip to main content

Research Repository

Advanced Search

Dynamic Neighbourhood Cellular Automata

Dantchev, Stefan

Dynamic Neighbourhood Cellular Automata Thumbnail


Authors



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

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.






You might also like



Downloadable Citations