diaporama

An automata network (AN) can be seen as a directed graph where each node has a state in an alphabet A and an update function which will change this state depending on the values of the incoming neighbors of the node. We call update schedule a sequence of updates. In particular, if we update all nodes at once, it is the parallel update schedule and if we update all node one at a time, it is a sequential one.
We will say that a scheduled AN of size m simulates another one of size
n<=m if, with their respective sequences of updates, they compute the
same function with their n first nodes.
In this presentation, we will study the cost of sequentialisation of a
parallel AN. This cost is the minimum number of additional automata required for any sequential AN with the same alphabet to simulate the parallel AN. We will introduce the concept of a confusion graph to prove that this cost is always less than n/2+log(n). Furthermore, we will prove that in the worst case, the cost is above n/3 if the alphabet size is at least 2 and above n/2 - log(n) if the alphabet size is at least 4.
Finally, we will show that this number can be bounded using the pathwidth of the interaction graph.