σ-Automata And Low-Dimensional CA

Cellular automata(CA) are discrete dynamical systems which evolve on lattices or vertices of graphs according to some local rule. They are useful in many fields. Research on CA has been much active for several times abroad. In this thesis, we explore σ-automata on graphs, properties of low-dimensional CA, the application of CA to image encryption, and obtain some results. The outline of this thesis is as follows:(1) In the first chapter, we mainly discuss on σ-automata on graphs. We give, for any solution of a tree, a clear description on the elements in the solution, by introducing the concept of "Quasi-All-Ones Problem" after analyzing the algorithm created by Galvin to construct a solution to the All-Ones Problem for trees thoroughly. This leads to an enumeration for the number of solutions in a tree. As a product of this description, we also get two algorithms for finding solutions in a unicycle graph. These results are parts of [7].In the latter part of this chapter, we introduce two generalization forms of the All-Ones Problem: the Strong-All-Colors Problem and the Weak-All-Colors Problem. For the Strong-All-Colors Problem, we give a rule named "deleting a 3-connected path", and prove that a radioactive tree has solutions to the Strong-All-Colors Problem. For the Weak-All-Colors Problem, we give a rule named "adding a leaf, and prove that any tree has a solution to the Weak-All-Colors Problem. It's proved that circles and unicyclic graphs have solutions to the Weak-All-Colors Problem as well. We conjecture that there is a solution to the Weak-All-Colors Problem for any graph. Especially, any tree can have a solution containing only 0 and 1 to the Weak-All-Colors Problem on Z₃. Whether the similar result holds for trees on Z_m(m ≥ 4) or graphs, is put forward as conjectures. Finally, we introduce the k-Random WACP, which is connected tightly to the Erdos-Ginzburg-Ziv problem in combinatorial number theory. We have solved it partly by using the results in [15,43].(2) In the second chapter, we summarize various properties of low-dimensional CA, such as "injective for C", "surjective for C", "injective for C_F", "surjective for C_F", "without Garden-of-Eden", "mutually erasable", etc, and characterize their relations. Note that the first four properties are basic. Afterwards we represent three algorithms to determine whether a one-dimensional CA is injective for C, surjective for C, surjective for Cp, respectively. The former two algorithms are brought forward by S.Amoroso and Y.N.Patt. The algorithm to determine "surjective for C_f" is created by myself. At last we enumerate all the one-dimensional CA which have the four fundamental properties and list them in Appendix A,B,C with some comments.(3)After its appearance, CA have been used in many fields such as physics, chemistry, biology, medicine, etc. In the third chapter of this thesis, I will bring forth a new application of CA on the image encryption field that hasn't been mentioned before. We give an algorithm to use a two-dimensional CA to encrypt an image. This algorithm has some virtues such as large amount of keys, high efficiency, great speed, etc. After its theoretical proof having been given, it will become a promising image encryption algorithm.