We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Dr Maximilien Gadouleau

Aracena, Julio, Gadouleau, Maximilien, Richard, Adrien & Salinas, Lilian (2020). Fixing monotone Boolean networks asynchronously. Information and Computation 104540.

Author(s) from Durham


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 re ne and
extend our results to di erent 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.