Sequentialization and Procedural Complexity in Automata Networks

03/01/2018
by   Florian Bridoux, et al.
0

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 > 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset