A one-dimensional linear hybrid cellular automaton (CA) is a specialised form of linear finite state machine. These machines are of interest, both for their theoretical properties and for their applications in VLSI built-in-self-test, random number generation, cryptography, coding theory, and other areas. This work is a study of the algebraic properties of the characteristic polynomials of CA, primarily for machines defined over GF(2). Several problems, previously open, are solved: the efficient synthesis of a CA from an irreducible polynomial, the existence and uniqueness of CA for irreducible polynomials, the reducibility of the characteristic polynomial of a cyclic-boundary CA, and the form of a similarity transform between CA and linear feedback shift registers. A probabilistic algorithm for the synthesis of CA over finite fields other than GF(2) is presented. Various other results concerning the characteristic polynomial of CA are derived, and possible directions for future research are discussed. / Graduate

M.Sc. (Computer Science) / Astudy of one- and two-dimensional cellular automata was made. Two research projects were undertaken; these are discussed in depth. One- and two-dimensional cellular automata are defined. These automata are discussed with respect to the various characteristics which they exhibit. Practical applications for one- and two-dimensional cellular automata are given, as well as examples of existing systems. These systems make use of the theory on which cellular automata is based to solve practical problems. An overview of work done in the field of one- and two-dimensional cellular automata and formal languages. is given. Equivalence of cellular automata and other formal languages is discussed. As a first research project, the possible equivalence of two-dimensional cellular automata and array automata, and two-dimensional cellular automata and table matrix L-systems. are investigated. Another research project suggests a methodology for the shrinking of two-dimensional cellular automata. A software system called S.O.S. was developed to simulate cellular automata. and support the research done in this field. In the last part of this thesis, an in depth discussion of the S.O.S. system is given.

Cellular automata (CA) are discrete dynamical systems comprised of a lattice of finite-state cells. At each time step, each cell updates its state as a function of the previous state of itself and its neighbours. Fuzzy cellular automata (FCA) are a real-valued extension of Boolean cellular automata which "fuzzifies" Boolean logic in the transition function using real values between zero and one (inclusive). To date, FCA have only been studied in disjunctive normal form (DNF). In this thesis, we study FCA in conjunctive normal form (CNF). We classify FCA in CNF both analytically and empirically. We compare these classes to their DNF counterparts. We prove that certain FCA exhibit chaos in CNF, in contrast to the periodic behaviours of DNF FCA. We also briefly explore five different forms of fuzzy logic, and suggest further study. In support of this research, we introduce novel methods of simulating and visualizing FCA.

Cellular automata (CA) are discrete dynamical systems comprised of a lattice of finite-state cells. At each time step, each cell updates its state as a function of the previous state of itself and its neighbours. Fuzzy cellular automata (FCA) are a real-valued extension of Boolean cellular automata which "fuzzifies" Boolean logic in the transition function using real values between zero and one (inclusive). To date, FCA have only been studied in disjunctive normal form (DNF). In this thesis, we study FCA in conjunctive normal form (CNF). We classify FCA in CNF both analytically and empirically. We compare these classes to their DNF counterparts. We prove that certain FCA exhibit chaos in CNF, in contrast to the periodic behaviours of DNF FCA. We also briefly explore five different forms of fuzzy logic, and suggest further study. In support of this research, we introduce novel methods of simulating and visualizing FCA.

Cellular automata (CA) are discrete dynamical systems comprised of a lattice of finite-state cells. At each time step, each cell updates its state as a function of the previous state of itself and its neighbours. Fuzzy cellular automata (FCA) are a real-valued extension of Boolean cellular automata which "fuzzifies" Boolean logic in the transition function using real values between zero and one (inclusive). To date, FCA have only been studied in disjunctive normal form (DNF). In this thesis, we study FCA in conjunctive normal form (CNF). We classify FCA in CNF both analytically and empirically. We compare these classes to their DNF counterparts. We prove that certain FCA exhibit chaos in CNF, in contrast to the periodic behaviours of DNF FCA. We also briefly explore five different forms of fuzzy logic, and suggest further study. In support of this research, we introduce novel methods of simulating and visualizing FCA.

Cellular automata (CA) are discrete dynamical systems comprised of a lattice of finite-state cells. At each time step, each cell updates its state as a function of the previous state of itself and its neighbours. Fuzzy cellular automata (FCA) are a real-valued extension of Boolean cellular automata which "fuzzifies" Boolean logic in the transition function using real values between zero and one (inclusive). To date, FCA have only been studied in disjunctive normal form (DNF). In this thesis, we study FCA in conjunctive normal form (CNF). We classify FCA in CNF both analytically and empirically. We compare these classes to their DNF counterparts. We prove that certain FCA exhibit chaos in CNF, in contrast to the periodic behaviours of DNF FCA. We also briefly explore five different forms of fuzzy logic, and suggest further study. In support of this research, we introduce novel methods of simulating and visualizing FCA.

Cellular automata are systems of interconnected cells which are discrete in space, time and state. Cell states are updated synchronously according to a local rule which is dependent upon the current state of the given cell and those of its neighbours in a pre-defined neighbourhood. The local rule is common to all cells. Fuzzy cellular automata extend this notion to systems which are discrete in space and time but not state. In this thesis, we explore fuzzy cellular automata which are created from the extension of Boolean rules in disjunctive normal form to continuous functions. Motivated by recent results on the classification of these rules from empirical evidence, we set out first to show that fuzzy cellular automata can shed some light on classical cellular automata and then to prove that the observed results are mathematically correct. The main results of this thesis can be divided into two categories. We first investigate the links between fuzzy cellular automata and their Boolean counter-parts. We prove that number conservation is preserved by this transformation. We further show that Boolean additive cellular automata have a definable property in their fuzzy form which we call self-oscillation. We then give a probabilistic interpretation of fuzzy cellular automata and show that homogeneous asymptotic states are equivalent to mean field approximations of Boolean cellular automata. We then turn our attention the asymptotic behaviour of fuzzy cellular automata. In the second half of the thesis we investigate the observed behaviours of the fuzzy cellular automata derived from balanced Boolean rules. We show that the empirical results of asymptotic behaviour are correct. In fuzzy form, the balanced rules can be categorized as one of three types: weighted average rules, self-averaging rules, and local majority rules. Each type is analyzed in a variety of ways using a range of tools to explain their behaviours.

Cellular automata are systems of interconnected cells which are discrete in space, time and state. Cell states are updated synchronously according to a local rule which is dependent upon the current state of the given cell and those of its neighbours in a pre-defined neighbourhood. The local rule is common to all cells. Fuzzy cellular automata extend this notion to systems which are discrete in space and time but not state. In this thesis, we explore fuzzy cellular automata which are created from the extension of Boolean rules in disjunctive normal form to continuous functions. Motivated by recent results on the classification of these rules from empirical evidence, we set out first to show that fuzzy cellular automata can shed some light on classical cellular automata and then to prove that the observed results are mathematically correct. The main results of this thesis can be divided into two categories. We first investigate the links between fuzzy cellular automata and their Boolean counter-parts. We prove that number conservation is preserved by this transformation. We further show that Boolean additive cellular automata have a definable property in their fuzzy form which we call self-oscillation. We then give a probabilistic interpretation of fuzzy cellular automata and show that homogeneous asymptotic states are equivalent to mean field approximations of Boolean cellular automata. We then turn our attention the asymptotic behaviour of fuzzy cellular automata. In the second half of the thesis we investigate the observed behaviours of the fuzzy cellular automata derived from balanced Boolean rules. We show that the empirical results of asymptotic behaviour are correct. In fuzzy form, the balanced rules can be categorized as one of three types: weighted average rules, self-averaging rules, and local majority rules. Each type is analyzed in a variety of ways using a range of tools to explain their behaviours.

Cellular automata are systems of interconnected cells which are discrete in space, time and state. Cell states are updated synchronously according to a local rule which is dependent upon the current state of the given cell and those of its neighbours in a pre-defined neighbourhood. The local rule is common to all cells. Fuzzy cellular automata extend this notion to systems which are discrete in space and time but not state. In this thesis, we explore fuzzy cellular automata which are created from the extension of Boolean rules in disjunctive normal form to continuous functions. Motivated by recent results on the classification of these rules from empirical evidence, we set out first to show that fuzzy cellular automata can shed some light on classical cellular automata and then to prove that the observed results are mathematically correct. The main results of this thesis can be divided into two categories. We first investigate the links between fuzzy cellular automata and their Boolean counter-parts. We prove that number conservation is preserved by this transformation. We further show that Boolean additive cellular automata have a definable property in their fuzzy form which we call self-oscillation. We then give a probabilistic interpretation of fuzzy cellular automata and show that homogeneous asymptotic states are equivalent to mean field approximations of Boolean cellular automata. We then turn our attention the asymptotic behaviour of fuzzy cellular automata. In the second half of the thesis we investigate the observed behaviours of the fuzzy cellular automata derived from balanced Boolean rules. We show that the empirical results of asymptotic behaviour are correct. In fuzzy form, the balanced rules can be categorized as one of three types: weighted average rules, self-averaging rules, and local majority rules. Each type is analyzed in a variety of ways using a range of tools to explain their behaviours.

This dissertation is devoted to the groups generated by automata. The first part of the dissertation deals with L-presentations for such groups. We describe the sufficient condition for an essentially free automaton group to have an L-presentation. We also find the L-presentation for several other groups generated by three-state automata, and we describe the defining relations in the Grigorchuk groups G_w. In case when the sequence w is almost periodic these relations provide an L-presentation for the group G_w. We also describe defining relations in the series of groups which contain Grigorchuk-Erschler group and the group of iterated monodromies of the polynomial z^2 + i. The second part of the dissertation considers groups generated by 3-state automata over the alphabet of 2 letters and 2-state automata over the 3-letter alphabet. We continue the classification work started by the research group at Texas A&M University ([BGK+07a, BGK+07b]) and further reduce the number of pairwise nonisomorphic groups generated by 3-state automata over the 2-letter alphabet. We also study the groups generated by 2-state automata over the 3-letter alphabet and obtain a number of classification results for this class of group.