@article { ,
title = {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.},
doi = {10.1016/j.ic.2020.104540},
issn = {0890-5401},
journal = {Information and Computation},
note = {EPrint Processing Status: Full text deposited in DRO},
publicationstatus = {Published},
publisher = {Elsevier},
url = {https://durham-repository.worktribe.com/output/1275121},
year = {2020},
author = {Aracena, Julio and Gadouleau, Maximilien and Richard, Adrien and Salinas, Lilian}
}