toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Record Links
Author (up) Goles, E.; Maldonado, D.; Montealecre, P. doi  openurl
  Title On the complexity of asynchronous freezing cellular automata Type
  Year 2021 Publication Information and Computation Abbreviated Journal Inf. Comput.  
  Volume 281 Issue Pages 104764  
  Keywords Cellular automata; Computational complexity; Freezing dynamics  
  Abstract In this paper we study the family of freezing cellular automata (FCA) in the context of asynchronous updating schemes. A cellular automaton is called freezing if there exists an order of its states, and the transitions are only allowed to go from a lower to a higher state. A cellular automaton is asynchronous if at each time-step only one cell is updated. We define the problem ASYNCUNSTABILITY, which consists in deciding there exists a sequential updating scheme that changes the state of a given cell.

We begin showing that ASYNCUNSTABILITY is in NL for any one-dimensional FCA. Then we focus on the family of life-like freezing CA (LFCA). We study the complexity of ASYNCUNSTABILITY for all LFCA in the triangular and square grids, showing that almost all of them can be solved in NC, except for one rule for which the problem is NP-Complete. (C) 2021 Elsevier Inc. All rights reserved.
 
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0890-5401 ISBN Medium  
  Area 0890-5401 Expedition Conference  
  Notes WOS:000721215200020 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1490  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: