Asynchronous simulation of Boolean networks by monotone Boolean networks

Description

We prove that the fully asynchronous dynamics of a Boolean network f : {0, 1}^n → {0, 1}^n without negative loop can be simulated, in a very specific way, by a monotone Boolean network with 2n components. We then use this result to prove that, for every even n, there exists a monotone Boolean network f : {0, 1}^n → {0, 1}^n , an initial configuration x and a fixed point y of f such that: (i) y can be reached from x with a fully asynchronous updating strategy, and (ii) all such strategies contains at least 2^{n/2} updates. This contrasts with the following known property: if f : {0, 1}^n → {0, 1}^n is monotone, then, for every initial configuration x, there exists a fixed point y such that y can be reached from x with a fully asynchronous strategy that contains at most n updates.

Abstract

International audience

Additional details