Abstract
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.