Cellular Automata: Algorithms and Applications
Cellular automata (CA) are an interesting computation medium to study because of their simplicity and inherently parallel operation. These characteristics make them a useful and efficient computation tool for applications such as cryptography and physical systems modelling, particularly when impleme...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Text |
| Language: | English |
| Published: |
2009
|
| Subjects: | |
| Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.497.9168 http://qspace.library.queensu.ca/bitstream/1974/1724/1/Clarridge_Adam_G_200903_MSc.pdf |
| Summary: | Cellular automata (CA) are an interesting computation medium to study because of their simplicity and inherently parallel operation. These characteristics make them a useful and efficient computation tool for applications such as cryptography and physical systems modelling, particularly when implemented on specialized parallel hardware. In this dissertation, we study a number of applications of CA and develop new theoretical results used for them. We begin by presenting conditions which guar-antee that a composition of marker cellular automata has the same neighbourhood as each 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-key cryptosystem based on reversible cellular automata originally conceived by Kari. We also give an improvement to a CA algorithm which solves a version of the convex hull problem, ensuring that the algorithm does not require a global rule change and correcting the operation in a special case. Finally, we study a modified version of an established CA-based car traffic flow model for the single-lane highway case, and use CA as a modelling tool to investigate the coverage problem in wireless sensor network design. We developed functional software implementations for all of these experiments. i Acknowledgements First and foremost, I would like to thank my supervisor, Dr. Kai Salomaa, for all of his help, intuition, guidance, and support. The quality of this work would not have been nearly as high without all of his thoughtful and well-appreciated advice. Kiitos! I would also like to thank Jarkko Kari and Sami Torbey for their advice and answers to my questions, which made the extension of their work clearer and easier for me. Thanks to my family and friends for all of your support. ii |
|---|