Abstract

In this article we study the minimum number kappa of additional automata that a Boolean automata network (BAN) associated with a given block-sequential update schedule needs in order to simulate a given BAN with a parallel update schedule. We introduce a graph that we call NECC graph built from the BAN and the update schedule. We show the relation between kappa and the chromatic number of the NECC graph. Thanks to this NECC graph, we bound kappa in the worst case between n/2 and 2n/3+2 (n being the size of the BAN simulated) and we conjecture that this number equals n/2. We support this conjecture with two results: the clique number of a NECC graph is always less than or equal to n/2 and, for the subclass of bijective BANs, kappa is always less than or equal to n/2+1.