Show simple item record

dc.contributor.authorKreslavskiy, Dmitry Michaelen_US
dc.date.accessioned2005-06-16T20:04:03Z
dc.date.available2005-06-16T20:04:03Z
dc.date.issued2003-11-26en_US
dc.identifier.urihttp://hdl.handle.net/1853/6423
dc.description.abstractThe present work consists of three parts. In the first part (chapters III and IV), the dynamics of Lorentz lattice gases (LLG) on graphs is analyzed. We study the fixed scatterer model on finite graphs. A tight bound is established on the size of the orbit for arbitrary graphs, and the model is shown to perform a depth-first search on trees. Rigidity models on trees are also considered, and the size of the resulting orbit is established. In the second part (chapter V), we give a complete description of dynamics for LLG on the one-dimensional integer lattice, with a particular interest in showing that these models are not capable of universal computation. Some statistical properties of these models are also analyzed. In the third part (chapter VI) we attempt to partition a pool of workers into teams that will function as independent TSS lines. Such partitioning may be aimed to make sure that all groups work at approximately the same rate. Alternatively, we may seek to maximize the rate of convergence of the corresponding dynamical systems to their fixed points with optimal production at the fastest rate. The first problem is shown to be NP-hard. For the second problem, a solution for splitting into pairs is given, and it is also shown that this solution is not valid for partitioning into teams composed of more than two workers.en_US
dc.format.extent627499 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectCellular automataen_US
dc.subjectLorentz Lattice gasen_US
dc.subjectLogic gatesen_US
dc.subjectDepth-first searchen_US
dc.subjectUniversal computationen_US
dc.subjectBucket brigadesen_US
dc.subjectTSS linesen_US
dc.titleLorentz Lattice Gases on Graphsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentAlgorithms, Combinatorics, and Optimizationen_US
dc.contributor.departmentMathematics
dc.description.advisorCommittee Chair: Leonid A. Bunimovich ; Committee Members: Mihai Ciucu ; Thomas Morley ; Dana Randall ; Prasad Tetalien_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record