958
views
0
recommends
+1 Recommend
1 collections
    0
    shares

      Celebrating 65 years of The Computer Journal - free-to-read perspectives - bcs.org/tcj65

      scite_
       
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

      Dynamic Neighbourhood Cellular Automata

      proceedings-article
      Visions of Computer Science - BCS International Academic Conference (VOCS)
      BCS International Academic Conference
      22 - 24 September 2008
      Cellular Automata, Ubiquitous Computations, Algorithms, Computational Complexity
      Bookmark

            Abstract

            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.

            Content

            Author and article information

            Contributors
            Conference
            September 2008
            September 2008
            : 61-68
            Affiliations
            [0001]Department of Computer Science, Durham University

            South Road, Durham, Co. Durham, DH1 3LE, UK
            Article
            10.14236/ewic/VOCS2008.6
            b93844c3-5bc5-41f4-b723-17e17107af9c
            © Stefan Dantchev. Published by BCS Learning and Development Ltd. Visions of Computer Science - BCS International Academic Conference

            This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

            Visions of Computer Science - BCS International Academic Conference
            VOCS
            Imperial College, London, UK
            22 - 24 September 2008
            Electronic Workshops in Computing (eWiC)
            BCS International Academic Conference
            History
            Product

            1477-9358 BCS Learning & Development

            Self URI (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/VOCS2008.6
            Self URI (journal page): https://ewic.bcs.org/
            Categories
            Electronic Workshops in Computing

            Applied computer science,Computer science,Security & Cryptology,Graphics & Multimedia design,General computer science,Human-computer-interaction
            Cellular Automata,Ubiquitous Computations,Algorithms,Computational Complexity

            Comments

            Comment on this article