Fixing monotone Boolean networks asynchronously

DOI10.1016/J.IC.2020.104540MaRDI QIDQ2201799zbMATH OpenOpenAlexFDO

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

Publication date 17 September 2020

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.02068, http://dro.dur.ac.uk/30375/1/30375.pdf

zbMATH Keywords

fixed pointBoolean networkasynchronous dynamics

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Symbolic dynamics (37B10) Dynamical systems involving maps of trees and graphs (37E25)

Abstract: The asynchronous automaton associated with a Boolean network $f:{0,1}^{n}o{0,1}^n$ is considered in many applications. It is the finite deterministic automaton with set of states ${0,1}^n$, alphabet $1,dots,n$, where the action of letter $i$ on a state $x$ consists in either switching the $i$th component if $f_i(x)eq{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, for $n$ sufficiently large, there exists a monotone network $f$ with $n$ components such that any word fixing $f$ has length $Omega(n^2)$. For this first 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 $1,dots,n$ of size $2^{o(n)}$, such that any sequence containing all these permutations as subsequences is of 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 fixable 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.

Recommendations

• On Fixable Families of Boolean Networks
• Asynchronous simulation of Boolean networks by monotone Boolean networks
• Fixed points of Boolean networks with small number of elementary circuits
• On the flora of asynchronous locally non-monotonic Boolean automata networks
• Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks

Cites work

• scientific article; zbMATH DE number 50840 (Why is no real title available?)
• A construction of short sequences containing all permutations of a set as subsequences
• A course in combinatorics.
• A guided tour of asynchronous cellular automata
• A logical calculus of the ideas immanent in nervous activity
• A lower bound on the length of a sequence containing all permutations as subsequences
• Asynchronous simulation of Boolean networks by monotone Boolean networks
• Asynchronous threshold networks
• Bounds of the number of leaves of spanning trees
• Computation with no memory, and rearrangeable multicast networks
• Computing in permutation groups without memory
• Computing issues of asynchronous CA
• Connectivity and dynamics for random subgraphs of the directed cube
• Discrete dynamical systems
• Fully asynchronous behavior of double-quiescent elementary cellular automata
• Itérations sur des ensembles finis et automates cellulaires contractants
• Memoryless computation: new results, constructions, and extensions
• Multistationarity, the basis of cell differentiation and memory. II: Logical analysis of regulatory networks in terms of feedback circuits
• Network information flow
• Neural networks and physical systems with emergent collective computational abilities
• On the convergence of Boolean automata networks without negative cycles
• Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability
• Short permutation strings
• Shorter strings containing all \(k\)-element permutations
• Transient length in sequential iteration of threshold functions
• m-asynchronous cellular automata: from fairness to quasi-fairness

Cited in

(4)

• Synchronizing Boolean networks asynchronously
• On Fixable Families of Boolean Networks
• Asynchronous simulation of Boolean networks by monotone Boolean networks
• scientific article; zbMATH DE number 3884098 (Why is no real title available?)

This page was built for publication: Fixing monotone Boolean networks asynchronously

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201799)