Cellular Automata: Algorithms and Applications
Loading...
Authors
Clarridge, Adam
Date
2009-03-23T19:53:31Z
Type
thesis
Language
eng
Keyword
Cellular automata , Encryption , Public key , Convex hull , Wireless sensor network , Traffic
Alternative Title
Abstract
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 guarantee that a composition of marker cellular automata has the same neighbourhood as each of the individual components. We show that, under certain technical assumptions, 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.
Description
Thesis (Master, Computing) -- Queen's University, 2009-03-23 11:20:58.666
Citation
Publisher
License
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.