146
views
0
recommends
+1 Recommend
1 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

      Dynamic Neighbourhood Cellular Automata

      Visions of Computer Science - BCS International Academic Conference (VOCS)

      BCS International Academic Conference

      22 - 24 September 2008

      Cellular Automata, Ubiquitous Computations, Algorithms, Computational Complexity

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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.

          Related collections

          Author and article information

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

          South Road, Durham, Co. Durham, DH1 3LE, UK
          Article
          10.14236/ewic/VOCS2008.6
          © 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
          Product
          Product Information: 1477-9358BCS Learning & Development
          Self URI (journal page): https://ewic.bcs.org/
          Categories
          Electronic Workshops in Computing

          Comments

          Comment on this article