Synchronizing Boolean networks asynchronously

DOI10.1016/J.JCSS.2023.04.001MaRDI QIDQ6098155zbMATH OpenOpenAlexFDO

Authors Julio Aracena, Adrien Richard, Lilian Salinas

Publication date 12 June 2023

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

asynchronous dynamicsBoolean networkinteraction graphpositive and negative cyclessynchronizing automaton

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: The {em asynchronous automaton} associated with a Boolean network $f:{0,1}^{n}o{0,1}^n$, considered in many applications, is the finite deterministic automaton where 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. These actions are extended to words in the natural way. A word is then {em synchronizing} if the result of its action is the same for every state. In this paper, we ask for the existence of synchronizing words, and their minimal length, for a basic class of Boolean networks called and-or-nets: given an arc-signed digraph $G$ on $[n]$, we say that $f$ is an {em and-or-net} on $G$ if, for every $iin[n]$, there is $a$ such that, for all state $x$, $f_i(x)=a$ if and only if $x_j=a$ ($x_{j}eqa$) for every positive (negative) arc from $j$ to $i$; so if $a=1$ ($a=0$) then $f_i$ is a conjunction (disjunction) of positive or negative literals. Our main result is that if $G$ is strongly connected and has no positive cycles, then either every and-or-net on $G$ has a synchronizing word of length at most $10(sqrt5+1{)}^n$, much smaller than the bound $(2^n-1{)}^2$ given by the well known v{C}ern'y's conjecture, or $G$ is a cycle and no and-or-net on $G$ has a synchronizing word. This contrasts with the following complexity result: it is coNP-hard to decide if every and-or-net on $G$ has a synchronizing word, even if $G$ is strongly connected or has no positive cycles.

Cites work

• A logical calculus of the ideas immanent in nervous activity
• A lower bound on the length of a sequence containing all permutations as subsequences
• Boolean monomial dynamical systems
• Complexity of fixed point counting problems in Boolean networks
• Computation with no memory, and rearrangeable multicast networks
• Computing in permutation groups without memory
• Determining a singleton attractor of an AND/OR Boolean network in \(O(n^{1.587})\) time
• Dimension reduction of large sparse AND-NOT network models
• Fixed points and maximal independent sets in AND-OR networks
• Fixed points in conjunctive networks and maximal independent sets in graph contractions
• Fixing monotone Boolean networks asynchronously
• From kernels in directed graphs to fixed points and negative cycles in Boolean networks
• scientific article; zbMATH DE number 50840 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• scientific article; zbMATH DE number 3354928 (Why is no real title available?)
• Itérations sur des ensembles finis et automates cellulaires contractants
• Maximum number of fixed points in regulatory Boolean networks
• 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
• Necessary conditions for multistationarity in discrete dynamical systems
• Negative circuits and sustained oscillations in asynchronous automata networks
• Network information flow
• Neural networks and physical systems with emergent collective computational abilities
• On the computation of fixed points in Boolean networks
• On the notion of balance of a signed graph
• Permanents, Pfaffian orientations, and even directed circuits
• Pólya's permanent problem
• Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability
• Synchronizing Automata and the Černý Conjecture

Cited in

(10)

• Asynchronous threshold networks
• Boolean networks: beyond generalized asynchronicity
• Asynchronous Boolean networks and hereditarily bijective maps
• Asynchronous threshold networks with multisorted signals
• Interconnection of asynchronous Boolean networks, asymptotic and transient dynamics
• Synchronization of Boolean networks with time delays
• Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions
• Generalising the maximum independent set algorithm via Boolean networks
• Trapping and commutative Boolean networks
• Negative circuits and sustained oscillations in asynchronous automata networks

This page was built for publication: Synchronizing Boolean networks asynchronously

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