Asynchronous simulation of Boolean networks by monotone Boolean networks

Abstract

We prove that the fully asynchronous dynamics of a Boolean network $f:\{0,1{\}}^n\to \{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\to \{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^{\frac{n}{2}}$ updates. This contrasts with the following known property: if $f:\{0,1{\}}^n\to \{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.

To appear in the proceedings of ACA 2016 (fourth International Workshop on Asynchronous Cellular Automata and Asynchronous Discrete Models)