Fixing monotone Boolean networks asynchronously

Abstract

The asynchronous automaton associated with a Boolean network f : {0, 1}(n) -> {0, 1}(n) is considered in many applications. It is the finite deterministic automaton with set of states {0,1}(n), alphabet {1, ..., n}, where the action of letter i on a state x consists in switching the ith component if f(i) (x) not equal x(i), or doing nothing otherwise. This action is extended to words in the natural way. We then say that a word w fixes f if, for all states x, the result of the action of w on x is a fixed point of f. In this paper, we ask for the existence of fixing words, and their minimal length. Firstly, our main results concern the minimal length of words that fix monotone networks. We prove that there exists a monotone network f with n components such that any word fixing f has length Omega(n(2)). Conversely, we construct a word of length O(n(3)) that fixes all monotone networks with n components. Secondly, we refine and extend our results to different classes of networks.