TY - JOUR

T1 - Mining a class of decision problems for one-dimensional cellular automata

AU - Lobos, Fabiola

AU - Goles, Eric

AU - Ruivo, Eurico L.P.

AU - De Oliveira, Pedro P.B.

AU - Montealegre, Pedro

N1 - Funding Information:
This work was supported in Chile by FONDECYT 1140090 (EG, FL) and BASAL-CMM (EG, PM), and in Brazil, by MackPesquisa and CNPq.
Publisher Copyright:
© 2018 Old City Publishing, Inc.

PY - 2018

Y1 - 2018

N2 - Cellular automata are locally defined, homogeneous dynamical systems, discrete in space, time and state variables. Within the context of one-dimensional, binary, cellular automata operating on cyclic configurations of odd length, we consider the general decision problem: if the initial configuration satisfies a given property, the lattice should converge to the fixed-point of all 1s (1),orto 0, otherwise. Two problems in this category have been widely studied in the literature, the parity problem [1] and the density classification task [4]. We are interested in determining all cellular automata rules with neighborhood sizes of 2, 3, 4 and 5 cells (i.e., radius r of 0.5, 1, 1.5 and 2.5) that solve decision problems of the previous type. We have demonstrated a theorem that, for any given rule in those spaces, ensures the non existence of fixed points other than 0 and 1 for configurations of size larger than 22r, provided that the rule does not support different fixed points for any configuration with size smaller than or equal to 22r. In addition, we have a proposition that ensures the convergence to only 0 or 1 of any initial configuration, if the rule complies with given conditions. By means of theoretical and computational approaches, we determined that: for the rule spaces defined by radius 0.5 and r = 1, only 1 and 2 rules, respectively, converge to 1 or 0, to any initial configuration, and both recognize the same language, and for the rule space defined by radius r = 1.5, 40 rules satisfy this condition and recognize 4 different languages. Finally, for the radius 2 space, out of the 4,294,967,296 different rules, we were able to significantly filter it out, down to 40,941 candidate rules. We hope such an extensive mining should unveil new decision problems of the type widely studied in the literature.

AB - Cellular automata are locally defined, homogeneous dynamical systems, discrete in space, time and state variables. Within the context of one-dimensional, binary, cellular automata operating on cyclic configurations of odd length, we consider the general decision problem: if the initial configuration satisfies a given property, the lattice should converge to the fixed-point of all 1s (1),orto 0, otherwise. Two problems in this category have been widely studied in the literature, the parity problem [1] and the density classification task [4]. We are interested in determining all cellular automata rules with neighborhood sizes of 2, 3, 4 and 5 cells (i.e., radius r of 0.5, 1, 1.5 and 2.5) that solve decision problems of the previous type. We have demonstrated a theorem that, for any given rule in those spaces, ensures the non existence of fixed points other than 0 and 1 for configurations of size larger than 22r, provided that the rule does not support different fixed points for any configuration with size smaller than or equal to 22r. In addition, we have a proposition that ensures the convergence to only 0 or 1 of any initial configuration, if the rule complies with given conditions. By means of theoretical and computational approaches, we determined that: for the rule spaces defined by radius 0.5 and r = 1, only 1 and 2 rules, respectively, converge to 1 or 0, to any initial configuration, and both recognize the same language, and for the rule space defined by radius r = 1.5, 40 rules satisfy this condition and recognize 4 different languages. Finally, for the radius 2 space, out of the 4,294,967,296 different rules, we were able to significantly filter it out, down to 40,941 candidate rules. We hope such an extensive mining should unveil new decision problems of the type widely studied in the literature.

KW - Decision problems

KW - Density classification

KW - One-dimensional cellular automata

KW - Parity problem

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

M3 - Article

AN - SCOPUS:85049358657

VL - 13

SP - 393

EP - 405

JO - Journal of Cellular Automata

JF - Journal of Cellular Automata

SN - 1557-5969

IS - 5-6

ER -