Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor
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. 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 |
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.
Sherali-Adams and the binary encoding of combinatorial principles
(2020)
Presentation / Conference Contribution
Resolution and the binary encoding of combinatorial principles
(2019)
Presentation / Conference Contribution
Simplicial Complex Entropy
(2017)
Presentation / Conference Contribution
Sublinear-Time Algorithms for Tournament Graphs
(2009)
Presentation / Conference Contribution
Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
(2007)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search