On Fixable Families of Boolean Networks

DOI10.1007/978-3-319-99813-8_36zbMATH Open1515.68162OpenAlexW2962771155MaRDI QIDQ6163607FDOQ6163607

Authors Maximilien Gadouleau, Adrien Richard 

Publication date 30 June 2023

Published in Developments in Language Theory (Search for Journal in Brave)

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

zbMATH Keywords

fixed pointsBoolean networksasynchronous dynamicsasynchronous graph

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Symbolic dynamics (37B10) Dynamical systems involving maps of trees and graphs (37E25)

Abstract: The asynchronous dynamics associated with a Boolean network $f:{0,1}^{n}o{0,1}^n$ is a finite deterministic automaton considered in many applications. The set of states is ${0,1}^n$, the alphabet is $[n]$, and 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$ {em fixes} $f$ if, for all states $x$, the result of the action of $w$ on $x$ is a fixed point of $f$. A whole family of networks is fixable if its members are all fixed by the same word, and the fixing length of the family is the minimum length of such a word. In this paper, we are interested in families of Boolean networks with relatively small fixing lengths. Firstly, we prove that fixing length of the family of networks with acyclic asynchronous graphs is $Theta(n{2}^n)$. Secondly, it is known that the fixing length of the whole family of monotone networks is $O(n^3)$. We then exhibit two families of monotone networks with fixing length $Theta(n)$ and $Theta(n^2)$ respectively, namely monotone networks with tree interaction graphs and conjunctive networks with symmetric interaction graphs.

Recommendations

• Fixing monotone Boolean networks asynchronously
• Asynchronous simulation of Boolean networks by monotone Boolean networks
• Fixed points of Boolean networks with small number of elementary circuits
• Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks
• Fixed points and connections between positive and negative cycles in Boolean networks

Cites Work

• Asynchronous simulation of Boolean networks by monotone Boolean networks
• Connectivity and dynamics for random subgraphs of the directed cube
• Digraphs
• Itérations sur des ensembles finis et automates cellulaires contractants
• On the convergence of Boolean automata networks without negative cycles

Cited In (5)

• Fixed points and maximal independent sets in AND-OR networks
• Fixed points and connections between positive and negative cycles in Boolean networks
• Asynchronous simulation of Boolean networks by monotone Boolean networks
• Title not available (Why is no real title available?)
• Fixing monotone Boolean networks asynchronously

This page was built for publication: On Fixable Families of Boolean Networks

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