The purpose of this study was to estimate the drivers' travel time with the occurrence of an incident on freeway. Three approaches, which were shock wave analysis, queuing theory and cellular automata models, were initially considered, however, the first two macroscopic models were indicated to underestimate travel time by previous literature. A microscopic simulation model based on cellular automata was developed to attain the goal. The model incorporated driving behaviors on the freeway with the presence of on-ramps, off-ramps, shoulder lanes, bottlenecks and incidents. The study area was a 16 mile eastbound section of I-66 between US-29 and I-495 in northern Virginia. The data for this study included loop detector data and incident data for the road segment for the year 2007. Flow and speed data from the detectors were used for calibration using quantitative and qualitative techniques. The cellular automata model properly reproduced the traffic flow under normal conditions and incidents. The travel time information was easily obtained from the model. The system is promising for travel time estimation in near real time. / Master of Science

No description available.

published_or_final_version / Physics / Master / Master of Philosophy

New tools are available for reconstructing the attractor basins of discrete dynamical networks where state-space is linked according the network's dynamics. In this thesis the computer software "Discrete Dynamics Lab" is applied to examine simple networks ranging from cellular automata (CA) to random Boolean networks (RBN), that have been widely applied as idealised models of physical and biological systems, to search for general principles underlying their dynamics. The algorithms and methods for generating pre-images for both CA and RBN, and reconstructing and representing attractor basins are described, and also considered in the mathematical context of random directed graphs. RBN and CA provide contrasting notions of self-organisation. RBN provide models of hierarchical categorisation in biology, for example memory in neural and genomic networks. CA provide models at the lower level of emergent complex pattern. New measures and results are presented on CA attractor basins and how they relate to measures on local dynamics and the Z parameter, characterising ordered to "complex" to chaotic behaviour. A method is described for classifying CA rules by an entropy-variance measure which allows glider rules and related complex rules to be found automatically giving a virtually unlimited sample for further study. The dynamics of RBN and intermediate network architectures are examined in the context of memory, where categorisation occurs at the roots of subtrees as well as at attractors. Learning algorithms are proposed for "sculpting" the basin of attraction field. RBN are proposed as a possible neural network model, and also discussed as a model of genomic regulatory networks, where cell types have been explained as attractors

The creation and use of models is critical not only to the scientific process, but also to life in general. Selected features of a system are abstracted into a model that can then be used to gain knowledge of the workings of the observed system and even anticipate its future behaviour. A key feature of the modelling process is the identification of commonality. This allows previous experience of one model to be used in a new or unfamiliar situation. This recognition of commonality between models allows standards to be formed, especially in areas such as measurement. How everyday physical objects are measured is built on an ingrained acceptance of their underlying commonality. Complex systems, often with their layers of interwoven interactions, are harder to model and, therefore, to measure and predict. Indeed, the inability to compute and model a complex system, except at a localised and temporal level, can be seen as one of its defining attributes. The establishing of commonality between complex systems provides the opportunity to find common metrics. This work looks at two dimensional cellular automata, which are widely used as a simple modelling tool for a variety of systems. This has led to a very diverse range of systems using a common modelling environment based on a lattice of cells. This provides a possible common link between systems using cellular automata that could be exploited to find a common metric that provided information on a diverse range of systems. An enhancement of a categorisation of cellular automata model types used for biological studies is proposed and expanded to include other disciplines. The thesis outlines a new metric, the C-Value, created by the author. This metric, based on the connectedness of the active elements on the cellular automata grid, is then tested with three models built to represent three of the four categories of cellular automata model types. The results show that the new C-Value provides a good indicator of the gathering of active cells on a grid into a single, compact cluster and of indicating, when correlated with the mean density of active cells on the lattice, that their distribution is random. This provides a range to define the disordered and ordered state of a grid. The use of the C-Value in a localised context shows potential for identifying patterns of clusters on the grid.

by Siu Chi Sang Obadiah. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 66-68). / Abstracts in English and Chinese. / Chapter 1 --- Pseudorandom Number Generator --- p.5 / Chapter 1.1 --- Introduction --- p.5 / Chapter 1.2 --- Statistical Indistingushible and Entropy --- p.7 / Chapter 1.3 --- Example of PNG --- p.9 / Chapter 2 --- Basic Knowledge of Cellular Automata --- p.12 / Chapter 2.1 --- Introduction --- p.12 / Chapter 2.2 --- Elementary and Totalistic Cellular Automata --- p.14 / Chapter 2.3 --- Four classes of Cellular Automata --- p.17 / Chapter 2.4 --- Entropy --- p.20 / Chapter 3 --- Theoretical analysis of the CA PNG --- p.26 / Chapter 3.1 --- The Generator --- p.26 / Chapter 3.2 --- Global Properties --- p.27 / Chapter 3.3 --- Stability Properties --- p.31 / Chapter 3.4 --- Particular Initial States --- p.33 / Chapter 3.5 --- Functional Properties --- p.38 / Chapter 3.6 --- Computational Theoretical Properties --- p.42 / Chapter 3.7 --- Finite Size Behaviour --- p.44 / Chapter 3.8 --- Statistical Properties --- p.51 / Chapter 3.8.1 --- statistical test used --- p.54 / Chapter 4 --- Practical Implementation of the CA PNG --- p.56 / Chapter 4.1 --- The implementation of the CA PNG --- p.56 / Chapter 4.2 --- Applied to the set of integers --- p.58 / Chapter 5 --- Application to Cryptography --- p.61 / Chapter 5.1 --- Stream Cipher --- p.61 / Chapter 5.2 --- One Time Pad --- p.62 / Chapter 5.3 --- Probabilistic Encryption --- p.63 / Chapter 5.4 --- Probabilistic Encryption with RSA --- p.64 / Chapter 5.5 --- Prove yourself --- p.65 / Bibliography

This thesis presents a model of Quantum Cellular Automata (QCA). The presented formalism is a natural quantization of the classical Cellular Automata (CA). It is based on a lattice of qudits, and an update rule consisting of local unitary operators that commute with their own lattice translations. One purpose of this model is to act as a theoretical model of quantum computation, similar to the quantum circuit model. The main advantage that QCA have over quantum circuits is that QCA make considerably fewer demands on the underlying hardware. In particular, as opposed to direct implementations of quantum circuits, the global evolution of the lattice in the QCA model does not assume independent control over individual \emph{qudits}. Rather, all qudits are to be addressed collectively in parallel. The QCA model is also shown to be an appropriate abstraction for space-homogeneous quantum phenomena, such as quantum lattice gases, spin chains and others. Some results that show the benefits of basing the model on local unitary operators are shown: computational universality, strong connections to the circuit model, simple implementation on quantum hardware, and a series of applications. A detailed discussion will be given on one particular application of QCA that lies outside either computation or simulation: single-spin measurement. This algorithm uses the techniques developed in this thesis to achieve a result normally considered hard in physics. It serves well as an example of why QCA are interesting in their own right.

This thesis presents a model of Quantum Cellular Automata (QCA). The presented formalism is a natural quantization of the classical Cellular Automata (CA). It is based on a lattice of qudits, and an update rule consisting of local unitary operators that commute with their own lattice translations. One purpose of this model is to act as a theoretical model of quantum computation, similar to the quantum circuit model. The main advantage that QCA have over quantum circuits is that QCA make considerably fewer demands on the underlying hardware. In particular, as opposed to direct implementations of quantum circuits, the global evolution of the lattice in the QCA model does not assume independent control over individual \emph{qudits}. Rather, all qudits are to be addressed collectively in parallel. The QCA model is also shown to be an appropriate abstraction for space-homogeneous quantum phenomena, such as quantum lattice gases, spin chains and others. Some results that show the benefits of basing the model on local unitary operators are shown: computational universality, strong connections to the circuit model, simple implementation on quantum hardware, and a series of applications. A detailed discussion will be given on one particular application of QCA that lies outside either computation or simulation: single-spin measurement. This algorithm uses the techniques developed in this thesis to achieve a result normally considered hard in physics. It serves well as an example of why QCA are interesting in their own right.

published_or_final_version / Physics / Master / Master of Philosophy

Quantum-Dot Cellular Automata (QCA) is being investigated as a possible alternative for encoding and processing binary information in an attempt to realize dramatic improvements in device density and processing speed over conventional CMOS design. The binary information is encoded in the locations of two excess electrons in a system of four quantum dots. The dots are arranged with each on a corner of a square, and electrons are able to quantum-mechanically tunnel between dots. Each set of four dots and two excess electrons constitutes a QCA cell. Coulomb repulsion ensures that the electrons will tend to occupy antipodal sites, giving two possible polarizations, or lowest energy ground states for a QCA cell. The electrons would tend to align along one diagonal or the other. Arrangements of QCA cells can be used to pass along input binary information and perform necessary logic operations on the input signal.When electrons tunnel back and forth between dots, it is possible they will occupy excited states in the dots. Two undesirable effects result from this: 1) Energy will be dissipated to the environment and cause thermal heating, and 2) it is possible a cell could become locked in a metastable state, which may be a local energy minimum, but is not one of the ground state polarizations we desire. Through the modulation of the heights of the inter-dot potential barriers, it would be possible to allow electrons to more easily tunnel between dots. This would help prevent the system from reaching excited states. The time variance in the heights of the potential barriers must be greater than the time it takes for the electrons to tunnel between dots, thus, effectively clocking the QCA device.We present theoretical studies of controlling the inter-dot potential barriers in a QCA device using an electric field due to electrostatically charged rods. The amount of charge on the rods is varied in time to increase and decrease the electric field, which will raise and lower the inter-dot potential barriers as desired. Different arrangements of rods provide different time-dependent behavior in the electric field, which may be useful depending on the arrangements of QCA cells required to make a logic device. / Department of Physics and Astronomy