Fixing monotone Boolean networks asynchronously

DOI10.1016/J.IC.2020.104540zbMATH Open1455.68081arXiv1802.02068OpenAlexW3010073297MaRDI QIDQ2201799FDOQ2201799

Adrien Richard, Julio Aracena, Maximilien Gadouleau, Lilian Salinas

Publication date: 17 September 2020

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

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.

Full work available at URL: https://arxiv.org/abs/1802.02068

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)

Cites Work

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

Cited In (2)

• Synchronizing Boolean networks asynchronously
• Title not available (Why is that?)

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)