On the complexity of asynchronous freezing cellular automata
Goles
E
author
Maldonado
D
author
Montealecre
P
author
2021
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.
Cellular automata
Computational complexity
Freezing dynamics
WOS:000721215200020
exported from refbase (show.php?record=1490), last updated on Tue, 07 Dec 2021 14:26:26 -0300
text
10.1016/j.ic.2021.104764
Goles_etal2021
Information and Computation
Inf. Comput.
2021
continuing
periodical
academic journal
281
104764
0890-5401