Skip to main content

Research Repository

Advanced Search

Fixing monotone Boolean networks asynchronously

Aracena, Julio; Gadouleau, Maximilien; Richard, Adrien; Salinas, Lilian

Fixing monotone Boolean networks asynchronously Thumbnail


Julio Aracena

Adrien Richard

Lilian Salinas


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.


Aracena, J., Gadouleau, M., Richard, A., & Salinas, L. (2020). Fixing monotone Boolean networks asynchronously. Information and Computation, Article 104540.

Journal Article Type Article
Online Publication Date Mar 3, 2020
Publication Date 2020-10
Deposit Date Mar 6, 2020
Publicly Available Date Mar 3, 2021
Journal Information and Computation
Print ISSN 0890-5401
Publisher Elsevier
Peer Reviewed Peer Reviewed
Article Number 104540


You might also like

Downloadable Citations