Source author record

Adrien Richard

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO math.DS Information Theory math.IT Molecular Networks Computational Complexity Computational Engineering, Finance, and Science Logic in Computer Science

Catalog footprint

Research overview

11works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Interaction graphs of isomorphic automata networks I: complete digraph and minimum in-degree

An automata network with $n$ components over a finite alphabet $Q$ of size $q$ is a discrete dynamical system described by the successive iterations of a function $f:Q^n\to Q^n$ . In most applications, the main parameter is the interaction graph of $f$ : the digraph with vertex set $[n]$ that contains an arc from $j$ to $i$ if $f_i$ depends on input $j$ . What can be said on the set $\mathbb{G}(f)$ of the interaction graphs of the automata networks isomorphic to $f$ ? It seems that this simple question has never been studied. Here, we report some basic facts. First, we prove that if $n\geq 5$ or $q\geq 3$ and $f$ is neither the identity nor constant, then $\mathbb{G}(f)$ always contains the complete digraph $K_n$ , with $n^2$ arcs. Then, we prove that $\mathbb{G}(f)$ always contains a digraph whose minimum in-degree is bounded as a function of $q$ . Hence, if $n$ is large with respect to $q$ , then $\mathbb{G}(f)$ cannot only contain $K_n$ . However, we prove that $\mathbb{G}(f)$ can contain only dense digraphs, with at least $\lfloor n^2/4 \rfloor$ arcs.

preprint2022arXiv

Attractor separation and signed cycles in asynchronous Boolean networks

The structure of the graph defined by the interactions in a Boolean network can determine properties of the asymptotic dynamics. For instance, considering the asynchronous dynamics, the absence of positive cycles guarantees the existence of a unique attractor, and the absence of negative cycles ensures that all attractors are fixed points. In presence of multiple attractors, one might be interested in properties that ensure that attractors are sufficiently "isolated", that is, they can be found in separate subspaces or even trap spaces, subspaces that are closed with respect to the dynamics. Here we introduce notions of separability for attractors and identify corresponding necessary conditions on the interaction graph. In particular, we show that if the interaction graph has at most one positive cycle, or at most one negative cycle, or if no positive cycle intersects a negative cycle, then the attractors can be separated by subspaces. If the interaction graph has no path from a negative to a positive cycle, then the attractors can be separated by trap spaces. Furthermore, we study networks with interaction graphs admitting two vertices that intersect all cycles, and show that if their attractors cannot be separated by subspaces, then their interaction graph must contain a copy of the complete signed digraph on two vertices, deprived of a negative loop. We thus establish a connection between a dynamical property and a complex network motif. The topic is far from exhausted and we conclude by stating some open questions.

preprint2022arXiv

Complexity of fixed point counting problems in Boolean Networks

A Boolean network (BN) with $n$ components is a discrete dynamical system described by the successive iterations of a function $f:\{0,1\}^n \to \{0,1\}^n$ . This model finds applications in biology, where fixed points play a central role. For example, in genetic regulations, they correspond to cell phenotypes. In this context, experiments reveal the existence of positive or negative influences among components: component $i$ has a positive (resp. negative) influence on component $j$ meaning that $j$ tends to mimic (resp. negate) $i$ . The digraph of influences is called signed interaction digraph (SID), and one SID may correspond to a large number of BNs (which is, in average, doubly exponential according to $n$ ). The present work opens a new perspective on the well-established study of fixed points in BNs. When biologists discover the SID of a BN they do not know, they may ask: given that SID, can it correspond to a BN having at least/at most $k$ fixed points? Depending on the input, we prove that these problems are in $\textrm{P}$ or complete for $\textrm{NP}$ , $\textrm{NP}^{\textrm{NP}}$ , $\textrm{NP}^{\textrm{#P}}$ or $\textrm{NEXPTIME}$ . In particular, we prove that it is $\textrm{NP}$ -complete (resp. $\textrm{NEXPTIME}$ -complete) to decide if a given SID can correspond to a BN having at least two fixed points (resp. no fixed point).

preprint2022arXiv

Nilpotent dynamics on signed interaction graphs and weak converses of Thomas' rules

A finite dynamical system with $n$ components is a function $f:X\to X$ where $X=X_1\times\dots\times X_n$ is a product of $n$ finite intervals of integers. The structure of such a system $f$ is represented by a signed digraph $G$ , called interaction graph: there are $n$ vertices, one per component, and the signed arcs describe the positive and negative influences between them. Finite dynamical systems are usual models for gene networks. In this context, it is often assumed that $f$ is {\em degree-bounded}, that is, the size of each $X_i$ is at most the out-degree of $i$ in $G$ plus one. Assuming that $G$ is connected and that $f$ is degree-bounded, we prove the following: if $G$ is not a cycle, then $f^{n+1}$ may be a constant. In that case, $f$ describes a very simple dynamics: a global convergence toward a unique fixed point in $n+1$ iterations. This shows that, in the degree-bounded case, the fact that $f$ describes a complex dynamics {\em cannot} be deduced from its interaction graph. We then widely generalize the above result, obtaining, as immediate consequences, other limits on what can be deduced from the interaction graph only, as the following weak converses of Thomas' rules: if $G$ is connected and has a positive (negative) cycle, then $f$ may have two (no) fixed points.

preprint2022arXiv

Positive and negative cycles in Boolean networks

We review and discuss some results about the influence of positive and negative feedback cycles in asynchronous Boolean networks. These results merge several ideas of Thomas: positive and negative feedback cycles have been largely emphasized by Thomas, through the so called Thomas' rules, and asynchronous Boolean networks have been introduced by Thomas as a model for the dynamics of gene networks, which is nowadays very popular.

preprint2016arXiv

Asynchronous simulation of Boolean networks by monotone Boolean networks

We prove that the fully asynchronous dynamics of a Boolean network $f:\{0,1\}^n\to\{0,1\}^n$ without negative loop can be simulated, in a very specific way, by a monotone Boolean network with $2n$ components. We then use this result to prove that, for every even $n$ , there exists a monotone Boolean network $f:\{0,1\}^n\to\{0,1\}^n$ , an initial configuration $x$ and a fixed point $y$ of $f$ such that: (i) $y$ can be reached from $x$ with a fully asynchronous updating strategy, and (ii) all such strategies contains at least $2^{\frac{n}{2}}$ updates. This contrasts with the following known property: if $f:\{0,1\}^n\to\{0,1\}^n$ is monotone, then, for every initial configuration $x$ , there exists a fixed point $y$ such that $y$ can be reached from $x$ with a fully asynchronous strategy that contains at most $n$ updates.

preprint2016arXiv

Simple dynamics on graphs

Does the interaction graph of a finite dynamical system can force this system to have a "complex" dynamics ? In other words, given a finite interval of integers $A$ , which are the signed digraphs $G$ such that every finite dynamical system $f:A^n\to A^n$ with $G$ as interaction graph has a "complex" dynamics ? If $|A|\geq 3$ we prove that no such signed digraph exists. More precisely, we prove that for every signed digraph $G$ there exists a system $f:A^n\to A^n$ with $G$ as interaction graph that converges toward a unique fixed point in at most $\lfloor\log_2 n\rfloor+2$ steps. The boolean case $|A|=2$ is more difficult, and we provide partial answers instead. We exhibit large classes of unsigned digraphs which admit boolean dynamical systems which converge toward a unique fixed point in polynomial, linear or constant time.

preprint2015arXiv

A Genetically Modified Hoare Logic

An important problem when modeling gene networks lies in the identification of parameters, even if we consider a purely discrete framework as the one of René Thomas. Here we are interested in the exhaustive search of all parameter values that are consistent with observed behaviors of the gene network. We present in this article a new approach based on Hoare Logic and on a weakest precondition calculus to generate constraints on possible parameter values. Observed behaviors play the role of "programs" for the classical Hoare logic, and computed weakest preconditions represent the sets of all compatible parameterizations expressed as constraints on parameters. Finally we give a proof of correctness of our Hoare logic for gene networks as well as a proof of completeness based on the computation of the weakest precondition.

preprint2014arXiv

Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks

We are interested in fixed points in Boolean networks, {\em i.e.} functions $f$ from $\{0,1\}^n$ to itself. We define the subnetworks of $f$ as the restrictions of $f$ to the subcubes of $\{0,1\}^n$ , and we characterizes a class $\mathcal{F}$ of Boolean networks satisfying the following property: Every subnetwork of $f$ has a unique fixed point if and only if $f$ has no subnetwork in $\mathcal{F}$ . This characterization generalizes the fixed point theorem of Shih and Dong, which asserts that if for every $x$ in $\{0,1\}^n$ there is no directed cycle in the directed graph whose the adjacency matrix is the discrete Jacobian matrix of $f$ evaluated at point $x$ , then $f$ has a unique fixed point. Then, denoting by $\mathcal{C}^+$ (resp. $\mathcal{C}^-$ ) the networks whose the interaction graph is a positive (resp. negative) cycle, we show that the non-expansive networks of $\mathcal{F}$ are exactly the networks of $\mathcal{C}^+\cup \mathcal{C}^-$ ; and for the class of non-expansive networks we get a "dichotomization" of the previous forbidden subnetwork theorem: Every subnetwork of $f$ has at most (resp. at least) one fixed point if and only if $f$ has no subnetworks in $\mathcal{C}^+$ (resp. $\mathcal{C}^-$ ) subnetwork. Finally, we prove that if $f$ is a conjunctive network then every subnetwork of $f$ has at most one fixed point if and only if $f$ has no subnetwork in $\mathcal{C}^+$ .

preprint2014arXiv

Fixed points of Boolean networks, guessing graphs, and coding theory

In this paper, we are interested in the number of fixed points of functions $f:A^n\to A^n$ over a finite alphabet $A$ defined on a given signed digraph $D$ . We first use techniques from network coding to derive some lower bounds on the number of fixed points that only depends on $D$ . We then discover relationships between the number of fixed points of $f$ and problems in coding theory, especially the design of codes for the asymmetric channel. Using these relationships, we derive upper and lower bounds on the number of fixed points, which significantly improve those given in the literature. We also unveil some interesting behaviour of the number of fixed points of functions with a given signed digraph when the alphabet varies. We finally prove that signed digraphs with more (disjoint) positive cycles actually do not necessarily have functions with more fixed points.

preprint2014arXiv

Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations towards their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. The guessing number approach converts this problem to determining the number of fixed points of coding functions $f:A^n\to A^n$ over a finite alphabet $A$ (usually referred to as Boolean networks if $A = \{0,1\}$ ) with a given interaction graph, that describes which local functions depend on which variables. In this paper, we generalise the so-called reduction of coding functions in order to eliminate variables. We then determine the maximum number of fixed points of a fully reduced coding function, whose interaction graph has a loop on every vertex. Since the reduction preserves the number of fixed points, we then apply these ideas and results to obtain four main results on the linear network coding solvability problem. First, we prove that non-decreasing coding functions cannot solve any more instances than routing already does. Second, we show that triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing. This is the first classification result for the linear network coding solvability problem. Third, we exhibit a new class of non-linearly solvable graphs. Fourth, we determine large classes of strictly linearly solvable graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Adrien Richard

Research overview

Is this your work?

11 publications

Interaction graphs of isomorphic automata networks I: complete digraph and minimum in-degree

Attractor separation and signed cycles in asynchronous Boolean networks

Complexity of fixed point counting problems in Boolean Networks

Nilpotent dynamics on signed interaction graphs and weak converses of Thomas' rules

Positive and negative cycles in Boolean networks

Asynchronous simulation of Boolean networks by monotone Boolean networks

Simple dynamics on graphs

A Genetically Modified Hoare Logic

Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks

Fixed points of Boolean networks, guessing graphs, and coding theory

Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability

See the researcher in context

Building this map preview