Solutions to All-Colors Problem on Graph Cellular Automata
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2019/3164692 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832551387928461312 |
|---|---|
| author | Xiaoyan Zhang Chao Wang |
| author_facet | Xiaoyan Zhang Chao Wang |
| author_sort | Xiaoyan Zhang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-36c15e3d7ce240448412a16041d6c8c9 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-36c15e3d7ce240448412a16041d6c8c92025-02-03T06:01:33ZengWileyComplexity1076-27871099-05262019-01-01201910.1155/2019/31646923164692Solutions to All-Colors Problem on Graph Cellular AutomataXiaoyan Zhang0Chao Wang1School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Jiangsu 210023, ChinaCollege of Software, Nankai University, Tianjin 300350, ChinaThe 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.http://dx.doi.org/10.1155/2019/3164692 |
| spellingShingle | Xiaoyan Zhang Chao Wang Solutions to All-Colors Problem on Graph Cellular Automata Complexity |
| title | Solutions to All-Colors Problem on Graph Cellular Automata |
| title_full | Solutions to All-Colors Problem on Graph Cellular Automata |
| title_fullStr | Solutions to All-Colors Problem on Graph Cellular Automata |
| title_full_unstemmed | Solutions to All-Colors Problem on Graph Cellular Automata |
| title_short | Solutions to All-Colors Problem on Graph Cellular Automata |
| title_sort | solutions to all colors problem on graph cellular automata |
| url | http://dx.doi.org/10.1155/2019/3164692 |
| work_keys_str_mv | AT xiaoyanzhang solutionstoallcolorsproblemongraphcellularautomata AT chaowang solutionstoallcolorsproblemongraphcellularautomata |