Fixing monotone Boolean networks asynchronously

Abstract

The asynchronous automaton associated with a Boolean network f : f0; 1gn ! f0; 1gn is considered in many applications. It is the nite deterministic automaton with set of states f0; 1gn, alphabet f1; : : : ; ng, where the action of letter i on a state x consists in either switching the ith component if fi(x) 6= xi or doing nothing otherwise. This action is extended to words in the natural way. We then say that a word w xes f if, for all states x, the result of the action of w on x is a xed point of f. In this paper, we ask for the existence of xing words, and their minimal length. Firstly, our main results concern the minimal length of words that x monotone networks. We prove that, for n suciently large, there exists a monotone network f with n components such that any word xing f has length (n2). For this rst result we prove, using Baranyai's theorem, a property about shortest supersequences that could be of independent interest: there exists a set of permutations of f1; : : : ; ng of size 2o(n) such that any sequence containing all these permutations as subsequences is of length (n2). Conversely, we construct a word of length O(n3) that xes all monotone networks with n components. Secondly, we rene and extend our results to dierent classes of xable networks, including networks with an acyclic interaction graph, increasing networks, conjunctive networks, monotone networks whose interaction graphs are contained in a given graph, and balanced networks.