This thesis aims to better represent a framework for asynchrony. Traditional asynchronous models, particularly those used to simulate cellular automata, have used stochasticity or randomness to generate update times. We claimthat, while they may make good representations of their application, such asynchronousmethods rid themodel of the essence of interesting asynchronous processes. Thus, we attempt to better harness the aspects internal to the decision process of such discretely dynamic cells as those in cellular automata.We propose the maxminm model as a suitable model for the asynchronous computation of cellular automata. The model uses maxminplus algebra, a special case of which is maxplus algebra. This algebra arises naturally from the cellular automaton requirement that a cell receives the state of its neighbours before updating. The maxminm model allows each cell to update after it receives m out of a possible n neighbours' states.The maxplus model shows that, while update times may be asynchronous in real time, there is no loss of information, since the corresponding asynchronous process is bijectively related to the synchronous model. In turn, the cellular automaton output, measured by the Shannon and word entropies, is shown to vary little from the synchronous model. Moreover, this type of asynchrony is simple, i.e. it is deterministically obtained due to the linearity of maxplus algebra.Indeed, the maxminm model is also shown to be deterministic and always reaches periodic behaviour. In the long time limit, this model is shown to be represented by a maxplus model, supporting its determinism further. Consequently, the complexity of such a model may be thought to be limited. However, we show through large scale experiments that the case where m is approximately n/2 generates most complex behaviour in terms of large periods and transients to the aforementioned periodic orbits. In particular, the complexity is empirically shown to obey a bell form as a function of m (where m ranges from 1 to n). The resulting cellular automaton simulations indicate a correspondence from the complexity of the update times. Therefore, cellular automaton behaviour may be predictable with the type of asynchrony employed in this thesis.
Date of Award  1 Aug 2012 

Original language  English 

Awarding Institution   The University of Manchester


Supervisor  David Broomhead (Supervisor) 

 maxplus
 cellular automata
 asynchrony
Maxminplus Models of Asynchronous Computation
Patel, E. (Author). 1 Aug 2012
Student thesis: Phd