Can I read Fixing monotone Boolean networks asynchronously on EtoBox?

Fixing monotone Boolean networks asynchronously by Aracena, Julio; Gadouleau, Maximilien; Richard, Adrien; Salinas, Lilian is a scholarly article available to read on EtoBox.

What is Fixing monotone Boolean networks asynchronously about?

The asynchronous automaton associated with a Boolean network $f:\{0,1\}^n\to\{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)\neq 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

Author

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

Published

2018

Language

EN