Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Most cellular automata are defined as being updated synchronously. I am interested in asynchronous automata, where they do not all have to update simultaneously. I am restricting myself to cellular automata on a graph (e.g. lattice) where the cellular automata is a FSM and all of the automata on the graph are identical.

I have seen some representations of asynchronously updated networks as synchronous updating of the automata with probabilistic updating of the cells, i.e. at each time step, each cell has probability $p$ of possibly updating its state.

I have seen asynchronous models where there is a single ordered list of the individual cells with each cell firing one after the other, with the same ordering maintained over multiple cycles, or with a different ordering being generated each time after all of the cells have fired. In this scheme, a cell is guaranteed to fire at most $3$ times in $2*n$ time-steps if there are $n$ total cells or at most $x+1$ times in $x*n$ time-steps ($x$ cycles of $n$ timesteps). (Example, it fires at time $n$ in the first cycle, at any time $n+s, (0 \le s \le n)$ in the second cycle, and at time $2n+1$ in the third cycle, meaning it fires 3 times during the $n+2$ steps from $t=n$ to $t=2n+1$.

I have also seen sequential firing, where at each time step a single cell is chosen to be updated, with no restrictions on firing all of the cells before starting over. This schema also averages a cell firing once every $n$ time-steps, but does not restrict it from firing more frequently.

Are there other better ways to mathematically model asynchronous cellular automata? What are the pitfalls and benefits of these particular schemes? I also agree at the outset that the type of firing scheme to be used for an asynchronous system depends on the particular system being modeled; I am asking for general answers or references for algorithms to model asynchronicity.

share|improve this question
add comment

2 Answers

There is also the possibility that the "firing" of the cellular automaton is also controlled by the states of its neighbors. For example, CA models of cardiac-cells (biological cells) have three states which they may be in: quiescent but excitable (relaxed and stretched, but capable of being activated), firing (currently activated and contracting their muscle fibers and getting shorter), and refractory (after having fired, and not being able to be activated). Firing times of a cell are affected by the firing time and firing sequence of neighboring cells.

Cardiac cells also have "automaticity" in that they will fire spontaneously, even if not triggered to do so by neighboring cells.

The neighborly pushing and automaticity can all be modeled by a synchronous cellular automaton model in this case. The synchronized cellular automaton keeps track of asynchronous firing by keeping track of the "phase" of each cell as an extra state: i.e. there could be 200 states which are quiescent leading to firing even without an external stimulus (but an external stimulus immediately jumps to the first firing stte), 10 firing states during which the cell can induce neighboring cells to also fire, and 30 refratory states during which the cell is neither firing nor induceable into firing, after which it cycles back to the first step of the quiscent phases.

Such a cellular automaton can be started with all cells in a randomly picked state out of those 240=200+10+30 possible states, and will end up firing in an organized manner after a few cycles (few in this case is probably multiple rounds of the maximum number of states).

share|improve this answer
add comment

Some of the schema you listed and some others are at http://en.wikipedia.org/wiki/Asynchronous_cellular_automaton. It also comments on how asynchronous cellular automata can be generated so that they can perform the same functions as synchronous cellular automata.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.