Julio Aracena
Fixing monotone Boolean networks asynchronously
Aracena, Julio; Gadouleau, Maximilien; Richard, Adrien; Salinas, Lilian
Authors
Dr Maximilien Gadouleau m.r.gadouleau@durham.ac.uk
Associate Professor
Adrien Richard
Lilian Salinas
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, 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 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Article Number | 104540 |
DOI | https://doi.org/10.1016/j.ic.2020.104540 |
Files
Accepted Journal Article
(744 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright 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/
You might also like
Bent functions in the partial spread class generated by linear recurring sequences
(2022)
Journal Article
Expansive automata networks
(2020)
Journal Article
Elementary, finite and linear vN-regular cellular automata
(2020)
Journal Article
Complete Simulation of Automata Networks
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search