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 maxmin-m model as a suitable model for the asynchronous computation of cellular automata. The model uses maxmin-plus algebra, a special case of which is max-plus algebra. This algebra arises naturally from the cellular automaton requirement that a cell receives the state of its neighbours before updating. The maxmin-m model allows each cell to update after it receives m out of a possible n neighbours' states.The max-plus 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 max-plus algebra.Indeed, the maxmin-m 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 max-plus 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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:549349 |
| Date | January 2012 |
| Creators | Patel, Ebrahim |
| Contributors | Broomhead, David |
| Publisher | University of Manchester |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | https://www.research.manchester.ac.uk/portal/en/theses/maxminplus-models-of-asynchronous-computation(148d3056-2309-48c2-887f-42743949ae03).html |
Page generated in 0.0016 seconds