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.

Department dc:contributor.department

Computing

Year dc:date.issued

2009

Author dc:creator

• Clarridge, Adam

Advisor dc:contributor.supervisor

• Salomaa, Kai Jr

• Cellular automata
• Encryption
• Public key
• Convex hull
• Wireless sensor network
• Traffic

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1974/1724

OAI identifier oai:identifier

oai:queensu.scholaris.ca:1974/1724