Fixing monotone Boolean networks asynchronously

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

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.

Citation

Aracena, J., Gadouleau, M., Richard, A., & Salinas, L. (2020). Fixing monotone Boolean networks asynchronously. Information and Computation, 274, Article 104540. https://doi.org/10.1016/j.ic.2020.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
• Electronic ISSN: 1090-2651
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 274
• Article Number: 104540
• DOI: https://doi.org/10.1016/j.ic.2020.104540
• Public URL: https://durham-repository.worktribe.com/output/1275121