Cellular Automata: Algorithms and Applications

dc.contributor.authorClarridge, Adamen
dc.contributor.departmentComputingen
dc.contributor.supervisorSalomaa, Kai Jren
dc.date2009-03-23 11:20:58.666
dc.date.accessioned2009-03-23T19:53:31Z
dc.date.available2009-03-23T19:53:31Z
dc.date.issued2009-03-23T19:53:31Z
dc.degree.grantorQueen's University at Kingstonen
dc.descriptionThesis (Master, Computing) -- Queen's University, 2009-03-23 11:20:58.666en
dc.description.abstractCellular 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.en
dc.description.degreeM.Sc.en
dc.format.extent2048524 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1974/1724
dc.language.isoengen
dc.relation.ispartofseriesCanadian thesesen
dc.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.en
dc.subjectCellular automataen
dc.subjectEncryptionen
dc.subjectPublic keyen
dc.subjectConvex hullen
dc.subjectWireless sensor networken
dc.subjectTrafficen
dc.titleCellular Automata: Algorithms and Applicationsen
dc.typethesisen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Clarridge_Adam_G_200903_MSc.pdf
Size:
1.95 MB
Format:
Adobe Portable Document Format