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 -