Dynamic Neighbourhood Cellular Automata

We propose a defi nition of Cellular Automaton in which links between cells can change during the computation. This is done locally by each cell, which can reach the neighbours of its neighbours in a single computational step. We suggest that Dynamic Neighbourhood Cellular Automata can serve as a theoretical model for studying Algorithmic and Computational Complexity issues in the are of Ubiquitous Computing.We illustrate this approach by giving an optimal logarithmic time solution of the Firing Squad Synchronisation problem in our model, which is an exponential speed-up over classical Cellular Automata.