TY - JOUR

T1 - On the complexity of asynchronous freezing cellular automata

AU - Goles, Eric

AU - Maldonado, Diego

AU - Montealegre, Pedro

AU - Ríos-Wilson, Martín

N1 - Funding Information:
This research was partially supported by ANID via PAI + Convocatoria Nacional Subvención a la Incorporación en la Academia Año 2017 + PAI77170068 (P.M.), FONDECYT 11190482 (P.M.), FONDECYT 1200006 (E.G., P.M.), STIC- AmSud CoDANet project 88881.197456/2018-01 (E.G., P.M.), ANID via PFCHA / DOCTORADO NACIONAL/2018 – 21180910 + PIA AFB 170001 (M.R.W), French ANR project FANs ANR-18-CE40-0002 (M.R.W.) and ECOS project C19E02 (M.R.W.). Some of the results of this paper were presented in the 13th International Conference on Cellular Automata for Research and Industry (ACRI), Como, Italy, in September 2018.
Publisher Copyright:
© 2021 Elsevier Inc.

PY - 2021/12

Y1 - 2021/12

N2 - 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.

AB - 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.

KW - Cellular automata

KW - Computational complexity

KW - Freezing dynamics

UR - http://www.scopus.com/inward/record.url?scp=85105793680&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2021.104764

DO - 10.1016/j.ic.2021.104764

M3 - Article

AN - SCOPUS:85105793680

VL - 281

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 104764

ER -