Visions of Computer Science - BCS International Academic Conference

Imperial College, London, UK - 22 - 24 September 2008

AUTHORS

Stefan Dantchev

ABSTRACT

We propose a definition 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.

PAPER FORMATS 

PDF Version of this Paper (220kb)

 

Other Papers in this Session
Other Sessions in this Conference