Cellular Automata: Algorithms and Applications

Abstract Cellular automata (CA) are an interesting computation medium to study because oftheir simplicity and inherently parallel operation. These characteristics make thema useful and ecient computation tool for applications such as cryptography andphysical systems modelling, particularly when implemented on specialized parallelhardware. In this dissertation, we study a number of applications of CA and developnew theoretical results used for them. We begin by presenting conditions which guar-antee that a composition of marker cellular automata has the same neighbourhood aseach of the individual components. We show that, under certain technical assump-tions, a marker cellular automaton has a unique inverse with a given neighbourhood.We use these results to develop a working key generation algorithm for a public-keycryptosystem based on reversible cellular automata originally conceived by Kari. Wealso give an improvement to a CA algorithm which solves a version of the convexhull problem, ensuring that the algorithm does not require a global rule change andcorrecting the operation in a special case. Finally, we study a modi ed version ofan established CA-based car trac ow model for the single-lane highway case, anduse CA as a modelling tool to investigate the coverage problem in wireless sensornetwork design. We developed functional software implementations for all of theseexperiments.i