Printer Friendly

A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks.

1 Introduction

A function f from [{0,1}.sup.n] to itself is often seen as a Boolean network with n components. On on hand, the dynamics of the network is described by the iterations of f; for instance, with the synchronous iteration scheme, the dynamics is described by the recurrence [x.sup.t+1] = f([x.sup.t]). On the other hand, the "structure" of the network is described by a directed graph G(f): the vertices are the n components, and there exists an arc from j to i when the evolution of the ith component depends on the evolution of the jth one.

Boolean networks have many applications. In particular, from the seminal works of Kauffman (1969) and Thomas (1973), they are extensively used to model gene networks. In most cases, fixed points are of special interest. For instance, in the context of gene networks, they are often seen as stable patterns of gene expression at the basis of particular biological processes.

In this paper, we are interested in sufficient conditions for the existence and the uniqueness of a fixed point for f. Such a condition was first obtained by Robert (1980), who proved that if G(f) has no directed cycle, then f has a unique fixed point. This result was then generalized by Shih and Dong (2005). They associated to each point x in [{0,1}.sup.n] a local interaction graph G f(x), which is a subgraph of G(f) defined as the directed graph whose the adjacency matrix is the discrete Jacobian matrix of f evaluated at point x, and they proved that if G f(x) hasno directed cycle for all x in [{0,1}.sup.n], then f has a unique fixed point. Up to our knowledge, this is the weakest condition known to be sufficient for the presence and the uniqueness of a fixed point.

In this paper, we establish a sufficient condition for the existence and the uniqueness of a fixed point that is not expressed in terms of directed cycles. In Section 2, we defined, in a natural way, the subnetworks of f as the restrictions of f to the hypercubes contained in [{0,1}.sup.n], and we introduce the class F of even and odd self-dual networks. In Section 3, we prove the main result: if f has no subnetworks in F, then it has a unique fixed point. The rest of the paper discusses this "forbidden subnetworks theorem". In section 4, we show that it generalizes the fixed point theorem of Shih and Dong mentioned above. In section 5, we study the effect of the absence of subnetwork in F on the asynchronous state graph of f, which is a directed graph on [{0,1}.sup.n] constructed from the asynchronous iterations of f and proposed by Thomas (1973) as a model for the dynamics of gene networks. Finally, in Section 6, we compare F with the well-known class F' of networks f whose the interaction graph G(f) is a directed cycle. Mainly, we show that F' [subset or equal to] F and that the absence of subnetwork in F' is not sufficient for the existence and the uniqueness of a fixed point.

2 Definitions and notations

In this section, we introduce the definitions needed to state and prove the main result. Let B = {0,1}, let n be a positive integer, let [n] = {1, ..., n}, and let i [member of] [n]. The ith unit vector of [B.sup.n] is denoted [e.sub.i] (all the components are 0, excepted the ith one which is 1). The sum modulo two is denoted [direct sum]. It is applied componentwise on elements of [B.sup.n]: for all x, y [member of] [B.sup.n],

x [direct sum] y = ([x.sub.1] [direct sum] [y.sub.1], ..., [x.sub.n] [direct sum] [y.sub.n]) and x [direct sum] 1 = ([x.sub.1] [direct sum] 1, ..., [x.sub.n] [direct sum] 1).

Hence, x [direct sum] 1 may be seen as the negation of x. The number of ones that x contains is denoted [parallel]x[parallel], i.e. [parallel] x [parallel] = [[summation].sup.n.sub.i=1] [x.sub.i]. Thus [parallel] x [direct sum] y [parallel] gives the Hamming distance between two points x and y of [B.sup.n]. We say that x is even (odd) if [parallel]x[parallel] is even (odd) (there exists [2.sup.n-1] even (odd) points in [B.sup.n]). The point of [B.sup.n] obtained from x by assigning the ith component to [alpha] [member of] B is denoted [x.sup.i[alpha]], i.e.

[x.sup.i[alpha]] = ([x.sub.1], ..., [x.sub.i-1], [alpha], [x.sub.i+1], ..., [x.sub.n]).

If n > 1, the point of [B.sup.n-1] obtained from x be removing the ith component is denoted [x.sub.-i], i.e.

[x.sub.-i] = ([x.sub.1], ..., [x.sub.i-1], [alpha], [x.sub.i+1], ..., [x.sub.n]).

We call (n-dimensional Boolean) networks any function f from [B.sup.n] to itself.

Definition 1 (Conjugate) The conjugate of f : [B.sup.n] [right arrow] [B.sup.n] is the following n-dimensional network:

[??]: [B.sup.n] [right arrow] [B.sup.n], [??](x)= x [direct sum] f(x) [for all]x [member of] [B.sup.n].

Remark that [??](x) = 0 if and only if x is a fixed point of f, i.e. f(x) = x.

Definition 2 (Self-dual networks and even/odd networks) f is self-dual if

f(x) = f(x [direct sum] 1) [direct sum] 1 [for all]x [member of] [B.sup.n].

f is even (odd) if the image of [??] is the set of even points of [B.sup.n], i.e.

{[??](x) | x [member of] [B.sup.n]} = {x | x [member of] [B.sup.n] and [parallel]x[parallel] is even (odd)}.

We say that f is even (odd) self-dual if it is both even (odd) and self-dual. Note that f(x) = f (x [direct sum] 1)[direct sum] 1 if and only if f (x [direct sum] 1) = [??](x). Note also that if f is even (odd) self-dual, then for each even (odd) point x [member of] [B.sup.n], the preimage of x by f is of cardinality two, i.e. there exists exactly two distinct points y, z [member of] [B.sup.n] such that [??](y) = [??](z) = x. Since [??](x) =0 if and only if f(x) = x, we deduce that if f is even self-dual, then it has exactly two fixed points (obviously, if f is odd self-dual, then it has no fixed point).

Definition 3 (Immediate subnetworks) If n > 1, [alpha] [member of] B and i [member of] [n], we call immediate subnetwork of f (obtained by fixing the ith component to [alpha]) the following (n - 1)-dimensional network:

[f.sup.i[alpha]]: [B.sup.n-1] [right arrow] [B.sup.n-1], [f.sup.i[alpha]]([x.sub.-i]) = f[([x.sup.i[alpha]]).sub.-i] [for all]x [member of] [B.sup.n].

Remark that conjugate of [f.sup.i[alpha]] is equal to the immediate subnetwork [[??].sup.i[alpha]] of the conjugate [??] of f:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Definition 4 (Subnetworks) The subnetworks of f are inductively defined by: (1) if n = 1, then f has a unique subnetwork, which is f itself; and (2) if n > 1, the subnetworks of f are f and the subnetworks of the immediate subnetworks off. A strict subnetwork off is a subnetwork off different than f.

3 Main result

Theorem 1 (Forbidden subnetworks theorem) If a network f : [B.sup.n] [right arrow] [B.sup.n] has no even or odd self-dual subnetwork, then the conjugate off is a bijection, and in particular, f has a unique fixed point.

The proof of Theorem 1 needs the following two lemmas.

Lemma 1 Let X be a non-empty subset of [B.sup.n] and V(X) = {x [direct sum] [e.sub.i] | x [member of] X, i [member of] [n]}. If X and V(X) are disjoint and [absolute value of X] [greater than or equal to] [absolute value of V(X)], then X is either the set of even points of [B.sup.n] or the set of odd points of [B.sup.n].

Proof: by induction on n. The case n = 1 is obvious. So suppose that n > 1 and that the lemma holds for the dimensions less than n. Let X be a non-empty subset of [B.sup.n] satisfying the conditions of the statement. Let [alpha] [member of] B, and consider the following subsets of [B.sup.n-1]:

[X.sup.[alpha]] = {[x.sub.-n] | x [member of] X, [x.sub.n] = [alpha]}, V[(X).sup.[alpha]] = {[x.sub.-n] | x [member of] V(X), [x.sub.n] = a}.

We first prove that V([X.sup.[alpha]]) [subset or equal to] V[(X).sup.[alpha]] and [X.sup.[alpha]] [intersection] V([X.sup.[alpha]]) = 0. Let x [member of] [B.sup.n] with [x.sub.n] = [alpha] be such that [x.sub.-n] [member of] V([X.sup.[alpha]]). To prove that V([X.sup.[alpha]]) [subset or equal to] V[(X).sup.[alpha]], it is sufficient to prove that [x.sub.-n] [member of] V[(X).sup.[alpha]]. Since [x.sub.-n] [member of] V([X.sup.[alpha]]), there exists y [member of] [B.sup.n] with [y.sub.n] = [alpha] and i [member of] [n - 1] such that [y.sub.-n] [member of] [X.sup.[alpha]] and [x.sub.-n] = [y.sub.-n] [direct sum] [e.sub.i]. So x = y [direct sum] [e.sub.i], and since [y.sub.n] = [alpha], we have y [member of] X. Hence x [member of] V(X) and since [x.sub.n] = [alpha], we have [x.sub.-n] [member of] V[(X).sup.[alpha]]. We now prove that [X.sup.[alpha]] [intersection] V([X.sup.[alpha]]) = 0. Indeed, otherwise, there exists x [member of] [B.sup.n] with [x.sub.n] = [alpha] such that [x.sub.-n] [member of] [X.sup.[alpha]] [intersection] V([X.sup.[alpha]]). Since V([X.sup.[alpha]]) [subset or equal to] V[(X).sup.[alpha]], we have [x.sub.-n] [member of] [X.sup.[alpha]] [intersection] V[(X).sup.[alpha]] and since [x.sub.n] = [alpha], we deduce that x [member of] X [intersection] V(X), a contradiction.

Now, since V([X.sup.[alpha]]) [subset or equal to] V[(X).sup.[alpha]], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

So [absolute value of [X.sup.0]] [greater than or equal to] [absolute value of V([X.sup.0])] or [absolute value of [X.sup.1]] [greater than or equal to] [absolute value of V([X.sup.1])]. Suppose that [absolute value of [X.sup.0]] [greater than or equal to Since [X.sup.0] [intersection] V([X.sup.0]) = 0, by induction hypothesis [X.sup.0] is either the set of even points of [B.sup.n-1] or the set of odd points of [B.sup.n-1]. So in both cases, we have [absolute value of [X.sup.0]] = [absolute value of V([X.sup.0])] = [2.sup.n-1]. We deduce that [absolute value of [X.sup.1]] [greater than or equal to] [absolute value of V([X.sup.1])] and so, by induction hypothesis, [X.sup.1] is either the set of even points of [B.sup.n-1] or the set of odd points of [B.sup.n-1]. But [X.sup.0] and [X.sup.1] are disjointed: for all x [member of] [B.sup.n], if [x.sup.-n] [member of] [X.sup.0] [intersection] [X.sup.1], then [x.sub.n0] and [x.sub.n1] are two points of X, and [x.sub.n1] = [x.sub.n0] [direct sum] [e.sub.n] [member of] V(X), a contradiction. So if [X.sup.0] is the set of even (odd) points of [B.sup.n-1], then [X.sup.1] is the set of odd (even) points of [B.sup.n-1], and we deduce that X is the set of even (odd) points of [B.sup.n].

Lemma 2 Let f : [B.sup.n] [member of] [B.sup.n]. Suppose that the conjugate of every immediate subnetwork of f is a bijection. If the conjugate of f is not a bijection, then f is even or odd self-dual.

Proof: Suppose that f satisfies the conditions of the statement, and that the conjugate [??] of f is not a bijection. Let [??] [subset or equal to] [B.sup.n] be the image of [??], and let X = [B.sup.n] \ [??]. Since [??] is not a bijection, X is not empty. We first prove the following property:

(*) For every x [member of] X and i [member of] [n], the preimage of x [direct sum] [e.sub.i] by [??] is of cardinality two.

Let x [member of] X and i [member of] [n]. By hypothesis, the conjugate of [f.sup.i0] is a bijection, so there exists a unique point in [B.sup.n-1] whose the image by [f.sup.i0] is [x.sub.-i]. We deduce that there exists a unique point y [member of] [B.sup.n] such that [y.sub.i] = 0 and [[??].sup.i0]([y.sub.-i]) = [x.sub.-i]. Then, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We deduce that either [??](y) = x or [??](y) = x [direct sum] [e.sub.i]. Since x [member of] X we have f(y) [not equal to] x so [??](y) = x [direct sum] ei. Hence, we have proved that there exists a unique point y [member of] [B.sup.n] such that [y.sub.i] =0 and [??](y) = x [direct sum] [e.sub.i], and we prove with similar arguments that there exists a unique point z [member of] [B.sup.n] such that [z.sub.i] = 1 and [??](z) = x [direct sum] [e.sub.i]. This proves (*).

We are now in position to prove that f is even or odd. Let V(X) = {x [direct sum] [e.sub.i] | x [member of] X, i [member of] [n]}. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Following (*), we have [absolute value of [[??].sup.-1](V(X))] = 2[absolute value of V(X)] and V(X) [subset or equal to] [??], so

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Therefore, [absolute value of X] [greater than or equal to] [absolute value of V(X)], and since V(X) [subset or equal to] [??] = [B.sup.n] \ X, we have X [intersection] V(X) = 0. So according to Lemma 1, X is either the set of even points of [B.sup.n] or the set of odd points of [B.sup.n]. We deduce that in the first (second) case, X is the set of odd (even) points of [B.sup.n]. Thus, f is even or odd.

It remains to prove that f is self-dual. Let x [member of] [B.sup.n]. For all i [member of] [n], since [parallel][??] (x)[parallel] and [parallel][??](x) [direct sum] [e.sub.i][parallel] have not the same parity, and since f is even or odd, we have [??](x) [direct sum] [e.sub.i] [member of] X. Thus, according to (*), the preimage of ([??](x) [direct sum] [e.sub.i]) [direct sum] [e.sub.i] = [??](x) by f is of cardinality two. Consequently, there exists a point y [member of] [B.sup.n], distinct from x, such that [??](y) = f(x). Let us proved that x = y [direct sum] 1. Indeed, if [x.sub.i] = [y.sub.i] = 0 for some i [member of] [n], then [f.sup.i0]([x.sub.-i]) = f[(x).sub.-i] = f[(y).sub.-i] = [[??].sup.i0]([y.sub.-i]). Since x [not equal to] y, we deduce that [f.sup.i0] is not a bijection, a contradiction. We show similarly that if [x.sub.i] = [y.sub.i] = 1, then [f.sup.i1] is not a bijection. So x = y [direct sum] 1. Consequently, [??](x [direct sum] 1) = [??](x), and we deduce that f is self-dual.

Proof of Theorem 1: by induction on n. The case n = 1 is obvious. So suppose that n > 1 and that the theorem holds for the dimensions less than n. Suppose that f has no even or odd self-dual subnetwork. Under this condition, f is neither even self-dual nor odd self-dual (since f is a subnetwork of f), and every immediate subnetwork of f has no even or odd self-dual subnetwork. So, by induction hypothesis, the dual of every strict subnetwork of f is a bijection, and we deduce from Lemma 2 that the dual of f is a bijection. Thus, in particular, there exists a unique point x [member of] [B.sup.n] such that [??](x) = 0, and since [??](x) = 0 if and only if f(x) = x, this point x is the unique fixed point of f.

Clearly, if f has no even or odd self-dual subnetwork, then every subnetwork of f has no even or odd self-dual subnetwork, and according to Theorem 1, the conjugate of every subnetwork of f is a bijection. Conversely, if the conjugate of every subnetwork of f is a bijection, then f has no even or odd self-dual subnetwork, since the conjugate of an even or odd self-dual network is not a bijection. Consequently, we have the following characterization:

Corollary 1 The conjugate of each subnetwork of f is a bijection if and only if f has no even or odd self-dual network.

Example 1 f : [B.sup.3] [right arrow] [B.sup.3] is defined by:

f([x.sub.1], [x.sub.2], [x.sub.3]) = ([bar.[x.sub.2]] [conjunction] [x.sub.3], [bar.[x.sub.3]] [conjunction] [x.sub.1], [bar.[x.sub.1]] [conjunction] [x.sub.2]).

Remark that f is not self-dual, since f(000) = f(111) = 000. The immediate subnetworks of f are:

[f.sup.10]([x.sub.2], [x.sub.3]) = (0, [x.sub.2])

[f.sub.11]([x.sub.2], [x.sup.3]) = ([bar.[x.sub.3]], 0)

[f.sup.20]([x.sub.1], [x.sub.3]) = ([x.sub.3], 0)

[f.sub.21]([x.sub.1], [x.sub.3]) = (0, [bar.[x.sub.1]])

[f.sub.30]([x.sub.1], [x.sub.2]) = (0, [x.sub.1])

[f.sub.31]([x.sub.1], [x.sub.2]) = ([bar.[x.sub.2]], 0)

So each immediate subnetwork [f.sup.i[alpha]] of f has one component fixed to zero, and so is not self-dual. Furthermore, each immediate subnetwork of [f.sup.i[alpha]] is the one dimensional network h defined by h(0) = h(1) = 0, which is not self-dual. So f has no self-dual subnetwork, and we deduce from Theorem 1 that the conjugate of [??] of f is a bijection, and that f has a unique fixed point. Indeed:
x       f (x)   [??] (x)

000     000     000
001     100     101
010     001     011
011     001     010
100     010     110
101     100     001
110     010     100
111     000     111


4 Remarks on the theorem of Shih and Dong

In this section, we show that Theorem 1 implies a fixed point theorem due to Shih and Dong (2005). In order to state this theorem, we need additional definitions. Let

f : [B.sup.n] [right arrow] [B.sup.n], f(x) = ([f.sub.1](x), ..., [f.sub.n](x)).

Definition 5 (Discrete Jacobian matrix) The discrete Jacobian matrix of f evaluated at point x [member of] [B.sup.n] is the following n x n Boolean matrix

f'(x) = ([f.sub.ij](x)), [f.sub.ij](x) = [f.sub.i]([x.sup.j1]) [direct sum] [f.sub.i]([x.sup.j0]) (i, j [member of] [n]).

In the next definition, we represent f'(x) under the form of a directed graph, in order to use graph theoretic notions instead of matrix theoretical notions. In fact, we mainly focus on elementary directed cycles, that we simply call cycles in the following.

Definition 6 (Local interaction graph) The local interaction graph of f evaluated at point x [member of] [B.sup.n] is the directed graph Gf(x) defined by: the vertex set is [n], and for all i, j [member of] [n], there exists an arc j [right arrow] i if and only if [f.sub.ij](x) = 1.

The discrete Jacobian matrix of f was first defined by Robert (1983), who also introduced the notion of Boolean eigenvalue. This material allowed Shih and Ho (1999) to state a combinatorial analog of the Jacobian conjecture: if f has the property that, for each x [member of] [B.sup.n], all the boolean eigenvalues of f'(x) are zero, then f has a unique fixed point. This conjecture was proved by Shih and Dong (2005). Since Robert proved that all the boolean eigenvalues of f'(x) are zero if and only if G f(x) has no cycle, the theorem of Shih and Dong can be stated as follows.

Theorem 2 (Shih and Dong (2005)) If G f(x) has no cycle [for all]x [member of] [B.sup.n], then f has a unique fixed point.

A short prove of this theorem, independent of Theorem 1, is given in appendix. In the following of this section, we show, using Theorem 1, that the condition "if G f(x) has no cycle for all x" can be weakened into a condition of the form "if there exists "few" point x such that G f(x) has a "short" cycle". The exact statement is given after the following proposition.

Proposition 1 If f is even or odd, then for every x [member of] [B.sup.n] the out-degree of each vertex of G f(x) is odd. In particular, G f(x) has a cycle.

Proof: The out-degree [d.sup.+.sub.j] of any vertex j of G f(x), which equals the number of ones in the jth column of f'(x), is [d.sup.+.sub.j] = [parallel]f ([x.sup.j1]) [direct sum] f ([x.sup.j0])[parallel] = [parallel]f(x) [direct sum] f(x [direct sum] [e.sub.j])[parallel]. Since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

the parity of [d.sup.+.sub.j] is the parity of [parallel]f(x)[parallel] + [parallel][??](x) [direct sum] [e.sub.j]) [parallel] + 1. Hence, if f is even or odd, then [parallel][??](x)[parallel] + [parallel]f(x) [direct sum] [e.sub.j])[parallel] is even, and [d.sup.+.sub.j] is odd.

Corollary 2 (Extension of Shih-Dong's fixed point theorem) If for k = 1, ..., n, there exists at most [2.sup.k] - 1 points x [member of] [B.sup.n] such that G f(x) has a cycle of length at most k, then the conjugate of f is a bijection. In particular, f has a unique ixed point.

Proof: According to Theorem 1, it is sufficient to prove, by induction on n, that if f satisfies the conditions of the statement, then f has no even or odd self-dual subnetwork. The case n = 1 is obvious. Suppose that n > 1 and that f satisfies the conditions of the statement. Let i, j [member of] [n - 1]. For each x [member of] [B.sup.n] such that [x.sub.n] = 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

So G [f.sup.n0]([x.sub.-n]) is the subgraph of G f(x) induced by [n-1], and we deduce that [f.sup.n[alpha]] satisfies the condition of the theorem (for every k [member of] [n - 1], there exists at most [2.sup.k] - 1 points x [member of] [B.sup.n-1] such that G [f.sup.n0](x) has a cycle of length at most k). Thus, by induction hypothesis, [f.sup.n0] has no even or odd self-dual subnetwork. More generally, we prove with similar arguments, that for all i [member of] [n], [f.sup.i0] and [f.sup.i1] have no even or odd self-dual subnetwork. So f has no odd or even self-dual strict subnetwork. If f is itself even or odd self-dual, then by Proposition 1, G f(x) has a cycle for every x [member of] [B.sup.n], so f does not satisfy that conditions of the statement (for k = n). Therefore, f has no even or odd self-dual subnetwork.

Example 2 (Continuation of Example 1) Take again

f([x.sub.1], [x.sub.2], [x.sub.3]) = ([bar.[x.sub.2]] [conjunction] [x.sub.3], [bar.[x.sub.3]] [conjunction] [x.sub.1], [bar.[x.sub.1]] [conjunction] [x.sub.2]).

We have seen that f has no self-dual subnetwork. So it satisfies the conditions of Theorem 1, but not the conditions of Shih-Dong's theorem, since G f(000) and G f(111) have a cycle:

[ILLUSTRATION OMITTED]

However, f satisfies the condition of Corollary 2 (there is 0 < [2.sup.1] point x with a cycle of length at most 1; 0 < [2.sup.2] point x such that G f(x) has a cycle of length at most 2, and 2 < [2.sup.3] points x such that G f(x) has a cycle of length at most 3).

Now, consider the following "extension" h : [B.sup.5] [right arrow] [B.sup.5] of f :

h([x.sub.1], [x.sub.2], [x.sub.3], [x.sub.4], [x.sub.5]) = ([bar.[x.sub.2]] [conjunction] [x.sub.3], [bar.[x.sub.3]] [conjunction] [x.sub.1], [bar.[x.sub.1]] [conjunction] [x.sub.2], 0,0) = (f([x.sub.1], [x.sub.2], [x.sub.3]), 0,0)

Using the fact that f has no self-dual subnetwork, it's easy to see that h has no self-dual subnetwork. So h satisfies the conditions of Theorem 1. But it does not satisfy the conditions of Corollary 2. Indeed, there exists 23 points x such that Gh(x) has a cycle of length at most 3:

[ILLUSTRATION OMITTED]

5 Remarks on asynchronous state graphs

In the following definition, we associate with f: [B.sup.n] [right arrow] [B.sup.n] a directed graph on [B.sup.n], called the asynchronous state graph of f, which has been proposed by Thomas (1973) as a model for the dynamics of gene networks; see also Thomas and d'Ari (1990).

Definition 7 (Asynchronous state graphs) The asynchronous state graph of f is the directed graph [GAMMA](f) defined by: the vertex set is [B.sup.n], and for every x, y [member of] [B.sup.n], there exists an arc x [right arrow] y if and only if there exists i [member of] [n] such that y = x [direct sum] [e.sub.i] and [f.sub.i](x) [not equal to] [x.sub.i].

Remark that [GAMMA](f) and f share the same information. Remark also that for every i [member of] [n] and [alpha] [member of] B, [GAMMA]([f.sup.i[alpha]]) is isomorphic to the subgraph of [GAMMA](f) induced by the set of points x [member of] [B.sup.n] such that [x.sub.i] = [alpha]. Indeed: for every x, y [member of] [B.sup.n],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (*)

Corollary 3 If f has no even or odd self-dual subnetwork, then f has a unique fixed point x, and for all y [member of] [B.sup.n], [GAMMA](f) contains a directed path from y to x of length [parallel]x [direct sum] y[parallel].

By the definition of [GAMMA](f), apath from x to y cannot be of length strictly less than [parallel]x [direct sum] y[parallel]; a path from x to y of length [parallel]x [direct sum] y[parallel] can thus be seen has a shortest path.

Proof of Corollary 3: by induction on n. The case n = 1 is obvious, so suppose that n > 1 and that the corollary holds for the dimensions less than n. Let f : [B.sup.n] [right arrow] [B.sup.n], and suppose that f has no even or odd self-dual subnetwork. By Theorem 1, f has a unique fixed point x. Let y [member of] [B.sup.n]. Suppose first that there exists i [member of] [n] such that [x.sub.i] = [y.sub.i] = 0. Then [x.sub.-i] is the unique fixed point of [f.sup.i0]. So, by induction hypothesis, [GAMMA]([f.sup.i0]) has apath from [y.sub.-i] to [x.sub.-i] of length [parallel][x.sub.-i] [direct sum] [y.sub.-i][parallel]. Since [x.sub.i] = [y.sub.i] = 0, we deduce from (*) that [GAMMA](f) has a path from y to x of length [parallel][x.sub.-i] [direct sum] [y.sub.-i][parallel] = [parallel]x [direct sum] y[parallel]. The case [x.sub.i] = [y.sub.i] = 1 is similar. So, finally, suppose that y = x [direct sum] 1. Since y is not a fixed point, there exists i [member of] [n] such that [f.sub.i](y) [not equal to] [y.sub.i]. Then, [GAMMA](f) has an arc from y to z = y [direct sum] [e.sub.i]. So [z.sub.i] = [x.sub.i], and as previously, we deduce that [GAMMA](f) has a path from z to x of length [parallel]x [direct sum] z[parallel]. This path together with the arc y [right arrow] z forms a path from y to x of length [parallel]x [direct sum] z[parallel] + 1 = [parallel]x [direct sum] y[parallel]. []

According to (*), the asynchronous state graph of each subnetwork of f is a subgraph of asynchronous state graph of f induced by an hypercube contained in [B.sup.n]. Hence, one can see the asynchronous state graphs of the subnetworks of f as "dynamical modules" of asynchronous state graph of f. The previous corollary shows that if f has no even or odd self-dual subnetwork, then the asynchronous state graph of f is "simple": it describes a "weak convergence" toward a unique fixed point. An interpretation is then that the asynchronous state graphs of even and odd self-dual networks are "dynamical modules" that are necessary for the "emergence" of "complex" asynchronous behaviors.

Example 3 (Continuation of Example 1) Take again the 3-dimensional network f defined in Example 1, which has no self-dual subnetwork. The asynchronous state graph [GAMMA](f) of f is the following:
  x     f (x)   f (x)

 000     000     000
 001     100     101
 010     001     011
 011     001     010
 100     010     110
 101     100     001
 110     010     100
 111     000     111


[ILLUSTRATION OMITTED]

In agreement with Corollary 3, there exists, from any initial point, a shortest path leading to the unique fixed point of f (the point 000): the asynchronous state graph describes a "weak asynchronous convergence" (by shortest paths) toward a unique fixed point. However, [GAMMA](f) has a cycle (of length 6), so every path does not lead to the unique fixed point: the condition "has no even or odd self-dual subnetworks" does no ensure a "strong asynchronous convergence" toward a unique fixed point.

6 Remarks on positive and negative cycles

In this section, we show that positive (negative) circular networks, i.e. Boolean networks whose the global interaction graph reduces to a positive (negative) cycle, are simple instances of even (odd) circular networks. From this fact and existing results about positive and negative cycles, we will see that natural ideas of generalizations of Theorem 1 arise, but that none of these generalizations is true.

Let us begin with additional definitions. A signed directed graph is a directed graph in which each arc is either positive, negative or unsigned. In such a graph, a cycle is positive (negative) if it contains an unsigned arc or an even (odd) number of negative arcs (a directed cycle may be both positive and negative).

Definition 8 (Global interaction graph) The global interaction graph of f : [B.sup.n] [right arrow] [B.sup.n] is the signed directed graph G(f) defined by: the vertex set is [n], and for all i, j [member of] [n], there exists an arc i [right arrow] j if and only if [f.sub.i]([x.sup.j1]) = [f.sub.i]([x.sup.j0]) for at least one x [member of] [B.sup.n]; and an arc j [right arrow] i of G(f) is: positive if [f.sub.i]([x.sup.j1]) > [f.sub.i]([x.sup.j0]) for all x [member of] [B.sup.n]; negative if [f.sub.i]([x.sup.j1]) [less than or equal to] [f.sub.i]([x.sup.j0]) for all x [member of] [B.sup.n]; and unsigned in the other cases.

Remark that G(f) has an arc j [right arrow] i if and only if [f.sub.i] depends on the jth variable [x.sub.j] (and that [f.sub.i]([x.sup.j1]) [not equal to] [f.sub.i]([x.sup.j0]) if and only if [f.sub.ij](x) = 1).

Definition 9 (Positive and negative circular networks) f is a positive (negative) circular network if G(f) is a positive (negative) cycle.

The dynamics of positive and negative circular networks has been widely studied; see Remy et al. (2003) and Demongeot et al. (2010). Here, we prove that they are simple instances of even and odd self-dual networks.

Proposition 2 Every positive (negative) circular network is even (odd) and self-dual.

Proof: Let f be a circular network. Without loss of generality, suppose that the n arcs of G(f) are i + 1 [right arrow] i for all i [member of] [n]; n +1 being identified to 1 (here and in the rest of the proof). Then [f.sub.i] depends only on [x.sub.i+1], so either [f.sub.i](x) = [x.sub.i+1] (and i + 1 [right arrow] i is positive), or [f.sub.i](x) = [x.sub.i+1] [direct sum] 1 (and i + 1 [right arrow] i is negative); in the first case, we set [s.sub.i] = 0, and in the second case, we set [s.sub.i] = 1 (so that [f.sub.i](x) = [x.sub.i+1] [direct sum] [s.sub.i] in both cases). Let s = ([s.sub.1], ..., [s.sub.n]) [member of] [B.sup.n]. By construction, f is positive if [parallel]s[parallel] is even, and negative if [parallel]s[parallel] is odd. Furthermore,

f(x) = ([x.sub.2], [x.sub.3], ..., [x.sub.n], [x.sub.1]) [direct sum] s [for all]x [member of] [B.sup.n].

Hence

f(x [direct sum] 1) = ([x.sub.2] [direct sum] 1, ..., [x.sub.n] [direct sum] 1, [x.sub.1] [direct sum] 1) [direct sum] s = ([x.sub.2], ..., [x.sub.n], [x.sub.1]) [direct sum] 1 [direct sum] s = f (x) [direct sum] 1.

So f is self-dual. Also, we have [??](x) = x [direct sum] ([x.sub.2], ..., [x.sub.n], [x.sub.1]) [direct sum] s so the parity of [??](x) is the parity of [parallel]x[parallel] + [parallel]([x.sub.2], ..., [x.sub.n], [x.sub.1])[parallel] + [parallel]s[parallel]. Since [parallel]x[parallel] = [parallel]([x.sub.2], ..., [x.sub.n], [x.sub.1]) [parallel], we deduce that the parity of [??](x) is the parity of [parallel]s[parallel]. So if f is positive (negative) then the image of f only contains even (odd) points.

It remains to prove that if f is positive (negative) then each even (odd) point is in the image of [??]. Suppose that f is positive (negative), and let z be an even (odd) point of [B.sup.n]. Let x g [B.sup.n] be recursively defined by

[x.sub.1] = [z.sub.n], [x.sub.i+1] = [z.sub.i] [direct sum] [s.sub.i] [direct sum] [x.sub.i] for all i [member of] [n - 1].

Then, for every i [member of] [n - 1], we have

[[??].sub.i](x) = [x.sub.i] [direct sum] [f.sub.i](x) = [x.sub.i] [direct sum] [x.sub.i+1] [direct sum] [s.sub.i] = [x.sub.i] [direct sum] ([z.sub.i] [direct sum] [s.sub.i] [direct sum] [x.sub.i]) [direct sum] [s.sub.i] = [z.sub.i].

If remains to prove that [[??].sub.n](x) = [z.sub.n]. By the definition of x, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

So z and ([s.sub.1], [s.sub.2], ..., [s.sub.n-1], [x.sub.n]) have the same parity, and since z and s have the same parity, we deduce that [x.sub.n] = [s.sub.n]. Thus [f.sub.n](x) = [x.sub.n] [direct sum] [f.sub.n](x) = [s.sub.n] [direct sum] [x.sub.1] [direct sum] [s.sub.n] = [x.sub.1] = [z.sub.n], and we deduce that [??](x) = z. So f is even (odd) self-dual.

Remark 1 There are [2.sup.n-1]! n-dimensional even (odd) self-dual networks, but "only" (n - 1)![2.sup.n-1] n-dimensional positive (negative) circular networks. Since [2.sup.n-1]! = (n - 1)![2.sup.n-1] for n = 1, 2, we deduce that every one or two-dimensional even (odd) self-dual network is a positive (negative) circular network.

Since the class of positive and negative circular networks is contained in the class of even and odd self-dual networks, it is natural to think about the following generalization of Theorem 1: iff has no positive or negative circular networks, then f has a unique fixed point. However, this is false, as showed by the following example. Hence, Theorem 1 becomes false if "has no even or odd self-dual subnetwork" is replaced by "has no positive or negative circular subnetwork".

Example 4 f : [B.sup.4] [right arrow] [B.sup.4] is defined by

[f.sub.1](x) = ([bar.[x.sub.2]] [conjunction] [x.sub.3] [conjunction] [bar.[x.sub.4]]) [disjunction] (([bar.[x.sub.2]] [disjunction] [x.sub.3]) [conjunction] [x.sub.4])

[f.sub.2](x) = ([bar.[x.sub.3]] [conjunction] [x.sub.1] [conjunction] [bar.[x.sub.4]]) [disjunction] (([bar.[x.sub.3]] [disjunction] [x.sub.1]) [conjunction] [x.sub.4])

[f.sub.3](x) = ([bar.[x.sub.1]] [conjunction] [x.sub.2] [conjunction] [bar.[x.sub.4]]) [disjunction] (([bar.[x.sub.1]] [disjunction] [x.sub.2]) [conjunction] [x.sub.4])

[f.sub.4](x) = ([x.sub.2] [conjunction] [x.sub.3] [conjunction] [bar.[x.sub.1]]) [disjunction] (([x.sub.2] [disjunction] [x.sub.3]) [conjunction] [x.sub.1])

The table of f and [??], and the asynchronous state graph of f are as follow:
x       f (x)   f (x)

0000    0000    0000
0010    1000    1010
0100    0010    0110
0110    0011    0101
1000    0100    1100
1010    1001    0011
1100    0101    1001
1110    0001    1111
0001    1110    1111
0011    1010    1001
0101    0110    0011
0111    1011    1100
1001    1100    0101
1011    1101    0110
1101    0111    1010
1111    1111    0000


[ILLUSTRATION OMITTED]

One can see that f is even self-dual. The immediate subnetworks off are the following:

[f.sup.10]([x.sub.2], [x.sub.3], [x.sub.4]) = ([bar.[x.sub.3]] [conjunction] [x.sub.4], [x.sub.2] [disjunction] [x.sub.4], [x.sub.2] [conjunction] [x.sub.3])

[f.sub.11]([x.sub.2], [x.sub.3], [x.sub.4]) = ([bar.[x.sub.3]] [disjunction] [x.sub.4], [x.sub.2] [conjunction] [x.sub.4], [x.sub.2] [disjunction] [x.sub.3])

[f.sub.20]([x.sub.1], [x.sub.3], [x.sub.4]) = ([x.sub.3] [disjunction] [x.sub.4], [bar.[x.sub.1]] [conjunction] [x.sub.4], [x.sub.3] [disjunction] [x.sub.1])

[f.sup.21]([x.sub.1], [x.sub.3], [x.sub.4]) = ([x.sub.3] [disjunction] [x.sub.4], [bar.[x.sub.1]] [disjunction] [x.sub.4], [x.sub.3] [disjunction] [x.sub.1])

[f.sup.30]([x.sub.1], [x.sub.2], [x.sub.4]) = ([bar.[x.sub.2]] [disjunction] [x.sub.4], [x.sub.1] [disjunction] [x.sub.4], [x.sub.2] [conjunction] [x.sub.1])

[f.sup.31]([x.sub.1], [x.sub.2], [x.sub.4]) = ([bar.[x.sub.2]] [disjunction] [x.sub.4], [x.sub.1] [conjunction] [x.sub.4], [x.sub.2] [disjunction] [x.sub.1])

[f.sup.40]([x.sub.1], [x.sub.2], [x.sub.3]) = ([bar.[x.sub.2]] [disjunction] [x.sub.3], [bar.[x.sub.3]] [conjunction] [x.sub.1], [bar.[x.sub.1]] [conjunction] [x.sub.2])

[f.sup.41]([x.sub.1], [x.sub.2], [x.sub.3]) = ([bar.[x.sub.2]] [disjunction] [x.sub.3], [bar.[x.sub.3]] [disjunction] [x.sub.1], [bar.[x.sub.1]] [disjunction] [x.sub.2])

(as in Examples 1-3)

Proceeding as in Example 1, one can check that none immediate subnetwork of f has a self-dual subnetwork (actually, it is sufficient to check this for each [f.sup.i0] since [f.sup.i1](x) = [f.sup.i0](x [direct sum] 1) [direct sum] 1, 1 [less than or equal to] i [less than or equal to] 4). So f has no circular strict subnetwork, and since f is not circular, f has no circular subnetwork, but it has not a unique fixed points. Note that for 1 [less than or equal to] i [less than or equal to] 4, the 4-dimensional network h defined by h(x) = f (x) [direct sum] [e.sub.i] is odd self-dual, has no circular subnetwork, and no fixed point.

Now, consider the following three fundamental theorems about cycles and fixed points (the last two theorems result from two conjectures of Thomas; see Remy et al. (2008); Richard (2010) and the references therein).

Theorem 3 (Robert (1980)) If G(f) has no cycle, then f has a unique fixed point.

Remark 2 Clearly, each local interaction graph G f(x) is a subgraph of the (unsigned version of the) global interaction graph G(f). Hence, the condition "G(f) has no cycle" of Robert's theorem is (much more) stronger than the condition "G f(x) has no cycle for every x" of Shih-Dong's Theorem. Consequently, Shih-Dong's theorem is a generalization of Robert's theorem. Thus, Theorem 1 is also a generalization of Robert's theorem.

Remark 3 Actually, Robert proved, in Robert (1980) and Robert (1995), that if G(f) has no cycle, then f has a unique fixed point x and: (1) the synchronous iteration [x.sup.t+1] = f([x.sup.t]) converges toward x in at most n steps for every initial point [x.sup.0] [member of] [B.sup.n]; (2) every path of r(f) leads to x in at most n steps ("strong asynchronous convergence by shortest paths toward a unique fixed points"). These results shows the necessity of cycles for obtaining "complex" synchronous or asynchronous behaviors (e.g. multiple fixed points, cyclic attractors, long transient phases...).

Theorem 4 (Remy et al. (2008)) If G(f) has no positive cycle, then f has at most one fixed point.

Remark 4 Actually, by saying that an arc j [right arrow] i of G f(x) is positive if [f.sub.i]([x.sup.j1]) > [f.sub.i]([x.sup.j0]) and negative if [f.sub.i]([x.sup.ji]) < [f.sub.i]([x.sup.j0]), Remy et al. (2008) proved the following more general statement: if G f(x) has no positive cycle for all x [member of] [B.sup.n], then f has at most one fixed point.

Theorem 5 (Richard (2010)) If G(f) has no negative cycle, then f has at least one fixed point.

Hence, Theorems 4 and 5 give a nice proof "by dichotomy" of Robert's theorem: the absence of positive cycle gives the uniqueness, and absence of negative cycle gives the existence. Seeing the relationship between positive (negative) circular networks and even (odd) self-dual networks, one may ask if a "proof by dichotomy" occurs for Theorem 1, i.e., if the absence of even self-dual subnetwork gives the uniqueness, and if the absence of odd self-dual network gives the existence. The following example shows that both cases are false. Hence: if f has no even (odd) self-dual subnetworks, than it has not necessarily at most (at least) one fixed point.

Example 5 f : [B.sup.3] [right arrow] [B.sup.3] is defined by

[f.sub.1](x) = ([bar.[x.sub.1]] [conjunction] ([x.sub.2] [disjunction] [x.sub.3])) [disjunction] ([x.sub.2] [conjunction] [x.sub.3])

[f.sup.2](x) = ([bar.[x.sub.2]] [conjunction] ([x.sub.3] [disjunction] [x.sub.1])) [disjunction] ([x.sub.3] [conjunction] [x.sub.1])

[f.sub.3](x) = ([bar.[x.sub.3]] [conjunction] ([x.sub.1] [disjunction] [x.sub.2])) [disjunction] ([x.sub.1] [disjunction] [x.sub.2])

The table of f and [??], and the asynchronous state graph off are as follow:
 x    f (x)   f (x)

000    000     000
001    110     111
010    101     111
011    100     111
100    011     111
101    010     111
110    001     111
111    111     000


[ILLUSTRATION OMITTED]

f is self-dual, but not even since [parallel]f(001)[parallel] is odd. The immediate subnetworks of f are:

[f.sup.10]([x.sub.2], [x.sub.3]) = ([bar.[x.sub.2]] [disjunction] [x.sub.3], [bar.[x.sub.3]] [disjunction] [x.sub.2])

[f.sup.11]([x.sub.2], [x.sub.3]) = ([bar.[x.sub.2]] [disjunction] [x.sub.3], [bar.[x.sub.3]] [disjunction] [x.sub.2])

[f.sup.20]([x.sub.1], [x.sub.3]) = ([bar.[x.sub.1]] [conjunction] [x.sub.3], [bar.[x.sub.3]] [disjunction] [x.sub.1])

[f.sup.21]([x.sub.1], [x.sub.3]) = ([bar.[x.sub.1]] [disjunction] [x.sub.3], [bar.[x.sub.3]] [disjunction] [x.sub.1])

[f.sup.30]([x.sub.1], [x.sub.2]) = ([bar.[x.sub.1]] [conjunction] [x.sub.2], [bar.[x.sub.2]] [conjunction] [x.sub.1])

[f.sup.31]([x.sub.1], [x.sub.2]) = ([bar.[x.sub.1]] [disjunction] [x.sub.2], [bar.[x.sub.2]] [disjunction] [x.sub.1])

So each [f.sup.i[alpha]] is not circular, and according to Remark 1, it is not even and self-dual. Furthermore, each strict subnetwork h of [f.sup.i[alpha]] is either constant or defined by h(0) = 1 and h(1) = 0 (in the second case, h is odd and self-dual). So [f.sup.i[alpha]] has no strict even self-dual subnetwork. We deduce that f has no even self-dual subnetwork. But it has two fixed points.

Now consider the network f : [B.sup.3] [right arrow] [B.sup.3] is defined by

[f.sup.1](x) = [bar.[x.sub.2]]

[f.sub.2](x) = [bar.[x.sub.3]]

[f.sub.3](x) = ([x.sub.3] [conjunction] ([bar.[x.sub.1]] [disjunction] [x.sub.2])) [disjunction] ([bar.[x.sub.1]] [conjunction] [x.sub.2])

The table of f and [??], and the asynchronous state graph off are as follow:
x     f (x)   f (x)

000    110     110
001    101     100
010    011     001
011    001     010
100    110     010
101    100     001
110    010     100
111    001     110


[ILLUSTRATION OMITTED]

f is self-dual, but not odd since [parallel]f(000)[parallel] is even. The immediate subnetworks off are:

[f.sup.10]([x.sub.2], [x.sub.3]) = ([bar.[x.sub.3]], [x.sub.3] [disjunction] [x.sub.2])

[f.sup.11]([x.sub.2], [x.sub.3]) = ([x.sub.3], [x.sub.3] [conjunction] [x.sub.2])

[f.sup.20]([x.sub.1], [x.sub.3]) = (1, [x.sub.3] [conjunction] [bar.[x.sub.1]])

[f.sup.21]([x.sub.1], [x.sub.3]) = (0, [x.sub.3] [disjunction] [bar.[x.sub.1]])

[f.sub.30]([x.sub.1], [x.sub.2]) = ([bar.[x.sub.2]], 1)

[f.sup.31]([x.sub.1], [x.sub.2]) = ([bar.[x.sub.2]], 0)

So each [f.sup.i[alpha]] is not circular, and according to Remark 1, it is not odd and self-dual. Furthermore, each strict subnetwork h of [f.sup.i[alpha]] is either constant or defined by h(0) = 0 and h(1) = 1 (in the second case, h is even and self-dual). So [f.sup.i[alpha]] has no strict odd self-dual subnetwork. We deduce that f has no odd self-dual subnetwork. But it has no fixed point.

Acknowledgements

I wish to thank Julie Boyon and Sebastien Brun for interesting discussions. This work has been partially supported by the French National Agency for Reasearch (ANR-10-BLANC-0218 BioTempo project).

A A short proof of the theorem of Shih and Dong

The "trick" consists in proving, by induction on n, the following more general statement:

(*) If G f(x) has no cycle for all x [member of] [B.sup.n], then the conjugate of f is a bijection (so that f has a unique fixed point).

The case n =1 is obvious, so suppose that n > 1 and that (*) holds for the dimensions less than n. Suppose that G f(x) has no cycle for all x [member of] [B.sup.n]. Let i, j [member of] [n - 1], and x [member of] [B.sup.n] such that [x.sub.n] = 0. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

So G [f.sup.n0]([x.sub.-n]) is the subgraph of G f(x) induced by [n - 1], and thus, it has no cycle. We deduce that [f.sup.n0] satisfies the conditions of (*). Thus, by induction hypothesis, the conjugate of [f.sup.n0] is a bijection. We prove with similar arguments that [[??].sup.i0] and [[??].sup.i1] are bijections for all i [member of] [n].

Now, suppose, by contradiction, that [??] is not a bijection. Then, there exists two distinct points x, y [member of] [B.sup.n] such that [??](x) = [??](y). Let us proved that x = y [direct sum] 1. Indeed, if [x.sub.i] = [y.sub.i] = [alpha] for some i [member of] [n], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus [[??].sup.i[alpha]] is not a bijection, a contradiction. So x = y [direct sum] 1. Since G f(x) has no cycle, it contains at least one vertex of out-degree 0. In other words, there exists i [member of] [n] such that f([x.sup.i1]) = f([x.sup.i0]). Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence, setting [alpha] = [y.sub.i], we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

So [[??].sup.i[alpha]] is not a bijection, a contradiction. Thus [??] is a bijection and (*) is proved.

References

J. Demongeot, M. Noual, and S. Sene. On the number of attractors of positive and negative Boolean automata circuits. In Proceedings of WAINA'10, pages 782-789. IEEE press, 2010.

S. A. Kauffman. Metabolic stability and epigenesis in randomly connected nets. Journal of Theoretical Biology, 22:437-167, 1969.

E. Remy, B. Mosse, C. Chaouiya, and D. Thieffry. A description of dynamical graphs associated to elementary regulatory circuits. Bioinformatics, 19:172-178,2003.

E. Remy, P. Ruet, and D. Thieffry. Graphic requirements for multistability and attractive cycles in a boolean dynamical framework. Advances in Applied Mathematics, 41(3):335-350, 2008. ISSN 0196-8858.

A. Richard. Negative circuits and sustained oscillations in asynchronous automata networks. Advances in Applied Mathematics, 44(4):378-392, 2010. ISSN 0196-8858.

F. Robert. Iterations sur des ensembles finis et automates cellulaires contractants. Linear Algebra and its Applications, 29:393-412, 1980.

F. Robert. Derivee discrete et convergence locale d'une iteration Booleenne. Linear Algebra Appl., 52: 547-589, 1983.

F. Robert. Les systemes dynamiques discrets, volume 19 of Mathematiques et Applications. Springer, 1995.

M.-H. Shih and J.-L. Dong. A combinatorial analogue of the Jacobian problem in automata networks. Advances in Applied Mathematics, 34:30-46, 2005.

M.-H. Shih and J.-L. Ho. Solution of the Boolean Markus-Yamabe problem. Advances in Applied Mathematics, 22:60-102, 1999.

R. Thomas. Boolean formalization of genetic control circuits. Journal of Theoretical Biology, 42(3): 563-585, 1973. ISSN 0022-5193.

R. Thomas and R. d'Ari. Biological Feedback. CRC Press, 1990.

Adrien Richard ([dagger])

Laboratoire I3S, CNRS & Universite de Nice-Sophia Antipolis, France

([dagger]) Email: richard@unice.fr.
COPYRIGHT 2012 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2012 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Richard, Adrien
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUFR
Date:Jan 1, 2012
Words:8657
Previous Article:On the monotone hook hafnian conjecture.
Next Article:On the set of fixed points of the parallel symmetric sand pile model.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters