| Automata is the model of automatic system, which is of considerable importance as an effective formal tool both in theory and in practice. Automata theory mainly studies the functions and the structure of discrete mathematical systems as well as the relationships between them. It is for the purpose of studying how to analyze and synthesize automata. With the rapid development of science and technology such as micro-electron and information, automata theory is getting to permeate into different fields and has already become the important foundations of theory and application for many subjects. A finite automation without outputs is called a state machine. State machine theory is a research direction of finite automata theory. Many domestic and international scholars have studied the theory of state machine with the help of distinct mathematical tools as differential equations, functional analysis, algebra and the theory of probability. What they have done promoted the development of the automata theory. In this paper, we study state machine theory by use of two algebraic methods. One is that defining a category for state machines over a fixed input set and discussing its property, the other is that characterizing linear cellular automatas over a finite communitive ring by matrix algebra and further analyzing their transition structure.The second part is our main work and is divided into four chapters.In chapter one the important position of automata in computer science and near concern with other science branches are showed briefly. We further emphasize the algebraic research background that introduced state machines and cellular automata. Finally the basic concepts and technical terms are given.In chapter two we study the properties of the category of complete state machines. Firstly we construct a category of complete state machines, besides, we discuss its initial objects, terminal objects and zero objects.Secondly, the homomorphism basic theorem of the category is given.Proposition 2.2.3 Let is a homomorphism from to in , and then is admissible on . If is an epimorphism, then is an isomorphism if and only if is a unit admission.Theorem 2.2.4 (1) If is a homomorphism in , is admissible on and , then there exist a unique homomorphism such that the following diagram of homomorphism is commutative: where by (2)If , then is a monomorphism. If is an epimorphism, then is onto. Furthermore, if and is onto, that is is an isomorphism.Corollary 2.2.5 Let are admissible on and , then Where exist .Lastly, the direct sums and products of finite complete state machines are given and it is proved that every complete state machine has a unique indecomposable decomposition. The results are as followsTheorem 2.3.1 Let are complete state machines, construct,whereby,,, then is the unique direct products of in . Theorem 2.3.2 Let, are complete state machines and let is the disjoint union , in other words, for , there exist a unique such that . Construct , where ,, if , then is a unique direct sum of in .Theorem 2.4.4 Let is complete state machine, then it is indecomposable if and only if its the state transition graph is connected.Theorem 2.4.5 every complete state machine has a unique indecomposable decomposition.Our main goal in chapter three is to discuss cellular automata, which is a specific state machine. Some theorems on homogenous linear cellular automata over a finite communitive ring are proved by using the theory of matrices, and further properties of evolution on some typical linear cellular automatas are given. At last we discuss the group property of non-homogenous linear cellular automata.Proposition 3.1.2 Let is N-dimensional homogenous linear cellular automata over a finite communitive ring, is its transition function and boundary conditions, then there exist such that for every state .Theorem 3.2.2 Let is the characteristic matrix of a ,...
|
PDF Full Text Request