published_or_final_version / Physics / Master / Master of Philosophy

No description available.

published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy

published_or_final_version / Physics / Master / Master of Philosophy

Thesis (M. Phil.)--University of Hong Kong, 2000. / Includes bibliographical references (leaf 64).

Thesis (M. Phil.)--University of Hong Kong, 1996. / Includes bibliographical references (leaf 60-61).

Thesis (M.Phil.)--University of Hong Kong, 2000. / Includes bibliographical references (leaves 64) Also available in print.

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.