Fig. 2

An example of asynchronous automata network and its transition graph. Top: an asynchronous automata network composed of the 3 automata a, b and c. Automata are represented by labeled boxes, and their local states by circles identified with the ticks. For instance, the circle ticked 1 in the automaton a is the state 1 of a, noted a ₁. Local transitions are represented by directed labeled edges, where the labels indicate the set of conditions that have to be satisfied for firing the transition. The local states in blue represent a potential global state of the automata network: the state a ₀,b ₁,c ₀. Bottom: the transition graph of the asynchronous automata network, from the global initial state represented in blue. This graph represents all transitions that can be successively fired from the global initial state. For example, from the global initial state, it is possible to fire the transition labeled \(l_{a_{1}}\) or the transition labeled \(l_{\overline {b}}\). One of these two will be fired non-deterministically. Firing transition \(l_{a_{1}}\) will change the state of a from 0 to 1, hence replacing a ₀ with a ₁ in the global state of the network, becoming a ₁,b ₁,c ₀. Firing transition \(l_{\overline {b}}\) will change the state of b from 1 to 0, hence replacing b ₁ with b ₀ in the global state of the network, becoming 〈a ₀,b ₀,c ₀〉