Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Fixing monotone Boolean networks asynchronously.

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

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(727Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.ic.2020.104540
Publisher statement:© 2020 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:No date available
Date deposited:06 March 2020
Date of first online publication:03 March 2020
Date first made open access:03 March 2021

Save or Share this output

Export:
Export
Look up in GoogleScholar