  In this article we consider finite automata networks (ANs) with two kinds of
update schedules: the parallel one (all automata are updated all together) and
the sequential ones (the automata are updated periodically one at a time
according to a total order w). The cost of sequentialization of a given AN h is
the number of additional automata required to simulate h by a sequential AN
with the same alphabet. We construct, for any n and q, an AN h of size n and
alphabet size q whose cost of sequentialization is at least n/3. We also show
that, if q $\ge$ 4, we can find one whose cost is at least n/2 -- log q (n). We
prove that n/2 + log q (n/2 + 1) is an upper bound for the cost of
sequentialization of any AN h of size n and alphabet size q. Finally, we
exhibit the exact relation between the cost of sequentialization of h and its
procedural complexity with unlimited memory and prove that its cost of
sequentialization is less than or equal to the pathwidth of its interaction
graph.
