dc.creatorAracena, Julio
dc.creatorGadouleau, Maximilien
dc.creatorRichard, Adrien
dc.creatorSalinas, Lilian
dc.date.accessioned2021-03-01T18:25:01Z
dc.date.available2021-03-01T18:25:01Z
dc.date.created2021-03-01T18:25:01Z
dc.date.issued2020
dc.identifierInformation and Computation Vol. 274, October 2020, 104540
dc.identifier10.1016/j.ic.2020.104540
dc.identifierhttps://repositorio.uchile.cl/handle/2250/178486
dc.description.abstractThe asynchronous automaton associated with a Boolean network f : {0, 1}(n) -> {0, 1}(n) is considered in many applications. It is the finite deterministic automaton with set of states {0,1}(n), alphabet {1, ..., n}, where the action of letter i on a state x consists in switching the ith component if f(i) (x) not equal x(i), or doing nothing otherwise. This action is extended to words in the natural way. We then say that a word w fixes f if, for all states x, the result of the action of w on x is a fixed point of f. In this paper, we ask for the existence of fixing words, and their minimal length. Firstly, our main results concern the minimal length of words that fix monotone networks. We prove that there exists a monotone network f with n components such that any word fixing f has length Omega(n(2)). Conversely, we construct a word of length O(n(3)) that fixes all monotone networks with n components. Secondly, we refine and extend our results to different classes of networks.
dc.languageen
dc.publisherElsevier
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
dc.sourceInformation and Computation
dc.subjectBoolean network
dc.subjectFixed point
dc.subjectAsynchronous dynamics
dc.titleFixing monotone Boolean networks asynchronously
dc.typeArtículo de revista


Este ítem pertenece a la siguiente institución