Type of Document	Dissertation
Author	Kreslavskiy, Dmitry Michael
Author's Email Address	dima@math.gatech.edu
URN	etd-11242003-160034
Title	Lorentz Lattice Gases on Graphs
Degree	Doctor of Philosophy
Department	Algorithms, Combinatorics and Optimization
Advisory Committee	Advisor Name Title Bunimovich, Leonid A. Committee Chair Ciucu, Mihai Committee Member Morley, Thomas Committee Member Randall, Dana Committee Member Tetali, Prasad Committee Member
Keywords	cellular automata Lorentz Lattice gas logic gates depth-first search universal computation bucket brigades TSS lines
Date of Defense	2003-11-13
Availability	unrestricted
Abstract The 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.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    kreslavskiy_dmitry_m_200312.pdf 627.50 Kb 00:02:54 00:01:29 00:01:18 00:00:39 00:00:03