Return to search

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 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. / Thesis (Master, Computing) -- Queen's University, 2009-03-23 11:20:58.666

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OKQ.1974/1724
Date23 March 2009
CreatorsClarridge, Adam
ContributorsQueen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.))
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
Format2048524 bytes, application/pdf
RightsThis 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.
RelationCanadian theses

Page generated in 0.0021 seconds