2016/06/16 by Melliti, Tarek, Regnault, Damien, Richard, Adrien +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1606.05172
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.