Solutions to All‐Colors Problem on Graph Cellular Automata
Xiaoyan Zhang, Chao Wang · Complexity · 2019
The All‐Ones Problem comes from the theory of σ+‐automata, which is related to graph dynamical systems as well as the Odd Set Problem in linear decoding. In this paper, we further study and compute the solutions to the “All‐Colors Problem,” a generalization of “All‐Ones Problem,” on some interesting classes of graphs which can be divided into two subproblems: Strong‐All‐Colors Problem and Weak‐All‐Colors Problem, respectively. We also introduce a new kind of All‐Colors Problem, k‐Random Weak‐All‐Colors Problem, which is relevant to both combinatorial number theory and cellular automata theory.