{'fraction_non_alphanumeric': 0.06607023140763345, 'fraction_numerical': 0.016552234320456806, 'mean_word_length': 3.4339893398933987, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 51, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quotients of probabilistic Boolean networks

A probabilistic Boolean network (PBN) is a discrete-time system composed of a collection of Boolean networks between which the PBN switches in a stochastic manner. This paper focuses on the study of quotients of PBNs. Given a PBN and an equivalence relation on its state set, we consider a probabilistic transition system that is generated by the PBN; the resulting quotient transition system then automatically captures the quotient behavior of this PBN. We therefore describe a method for obtaining a probabilistic Boolean system that generates the transitions of the quotient transition system. Applications of this quotient description are discussed, and it is shown that for PBNs, controller synthesis can be performed easily by first controlling a quotient system and then lifting the control law back to the original network. A biological example is given to show the usefulness of the developed results.


I. INTRODUCTION
Mathematical modeling of biological systems is a valuable avenue for understanding complex biological systems and their behaviors. One powerful approach to modeling biological systems is through a Boolean model, where each system component is characterized with a binary variable. Boolean network (BN) modeling can capture the system's behavior without the need for much kinetic detail, making it a practical choice for systems where enough kinetic information may not be at disposal [1]. A BN is typically placed in the form of a (deterministic) nonlinear system (with a finite state space); while interestingly, based on an algebraic state representation approach, the Boolean dynamics can be exactly mapped into the standard discretetime linear dynamics [2]. This formal simplicity makes it relatively easy to formulate and solve classical control-theoretic problems for BNs, and thereby has stimulated a great many interesting subsequent developments in this area [3]- [20]. For some recent work on the analysis and control of BNs based on other approaches, see, e.g., [21]- [23].
A probabilistic Boolean network (PBN) is a stochastic extension of the classical BN. It can be considered as a collection of BNs endowed with a probability structure describing the likelihood with which a constituent network is active. PBNs possess not only the appealing properties of BNs such as requiring few kinetic parameters, but also are able to cope with uncertainties, both in the experimental data and in the model selection [24]. The algebraic state representation has also proved a powerful framework for studying control-related problems in PBNs. Examples of recent studies based on the algebraic representation approach include investigations of network robustness and synchronization [25]- [27], controllability and stabilizability [28]- [32], observability and detectability [33]- [35], optimal control [36], just to quote a few. It is a well-known fact that the analysis of control systems and synthesis of controllers become increasingly difficult as the dimension of the system gets larger. It is then desirable to have a methodology that reduces the size of control systems while preserving the properties relevant for analysis or synthesis. Quotient systems can be seen as lower dimensional models that may still contain enough information about the original system. A stability analysis of BNs based on a quotient map was presented in [37] and [38], where it was shown that the stability of the original BN can be inferred from the analysis of a specific quotient dynamics. Our recent work described a process for obtaining quotients of BNs [39]. A relation-based transformation strategy was introduced, which is able to transform a BN expressed in algebraic form into a quotient Boolean system suited for use. The present paper focuses on the study of quotients of PBNs. Given a PBN, together with an equivalence relation on the state set, we consider a probabilistic transition system T that is generated by the PBN. The equivalence relation then naturally induces a partition of the state space of T , and the corresponding quotient system fully captures the quotient dynamics of the PBN concerned. We therefore develop a probabilistic Boolean system that produces the transitions of the quotient transition system. As an application of this quotient description, we apply the proposed technique to solve two typical control problems, namely the stabilization and optimal control problems. The results show us that through the use of an appropriately defined relation, the proposed quotient system can indeed preserve the system property relevant to control design. Consequently, synthesizing controllers for a PBN can be done easily by first designing control polices on the quotient and then inducing the control polices back to the original network.
The remainder of this paper is organized as follows. Section II contains the basic notation and briefly reviews PBNs and probabilistic transition systems. Section III details a process for generating quotients of PBNs given that the networks are represented in algebraic form. Section IV discusses the use of the proposed quotient systems for control design and presents applications to stabilization and optimal control problems. Section V gives a biological example illustrating the developed results. A summary of the paper is given in the last section.

A. Notation
The following notation is used throughout the paper. The symbol δ i k denotes the ith k × 1 canonical basis vector (all entries of δ i k are 0 except for the ith one, which is 1), ∆ k denotes the set consisting of the canonical vectors δ 1 k , . . . , δ k k , and L k×r denotes the set of all k × r matrices whose columns are canonical basis vectors of length k. Elements of L k×r are called logical matrices (of size k × r). A (0, 1)-matrix is a matrix with all entries either 0 or 1. The (i, j)entry of a matrix A is denoted by (A) ij . Given two (0, 1)-matrices A and B of the same size, by A ≤ B we mean that if (A) ij = 1 then (B) ij = 1 for every i and j. The meet of A and B, denoted by A ∧ B, is the (0, 1)-matrix whose (i, j)-entry is (A) ij ∧ (B) ij . The (left) semitensor product [2] of two matrices C and D of sizes k 1 × r 1 and k 2 × r 2 , respectively, denoted by C ⋉ D, is defined by where ⊗ is the Kronecker product of matrices, and I l/r 1 and I l/k 2 are the identity matrices of orders l/r 1 and l/k 2 , respectively, with l being the least common multiple of r 1 and k 2 .

B. Probabilistic Boolean Networks
A PBN is described by the following stochastic equation where To be more precise, we let x(t) = x 1 (t) ⋉ · · · ⋉ xn(t) and Then it is shown that the PBN (1) satisfies the following algebraic description . . , S, with N := 2 n and M := 2 m . For more information about obtaining the algebraic description, as well as the properties of the semitensor product, the reader is referred to, e.g., the monograph of Cheng et al. [2].

C. Probabilistic Transition Systems
Our discussion of quotients of PBNs will draw on the notion of probabilistic transition systems. Recall that a probability distribution over a finite set Q is a function µ : Q → [0, 1] such that q∈Q µ(q) = 1. The set of all probability distributions over Q is denoted by Dist(Q). We state the following definition.
Definition 1 (see, e.g., [40], [41]): A probabilistic transition system (or probabilistic automaton) is a tuple T = (Q, Act, →), where Q is a finite set of states, Act is a finite set of actions, and → ⊆ Q × Act × Dist(Q) is a probabilistic transition relation.
Intuitively, a transition (q, α, µ) ∈→ means that in the state q an action α can be executed after which the probability to move to a state q ′ ∈ Q is µ(q ′ ). Following standard conventions we denote q α − → µ if (q, α, µ) ∈→. A probabilistic transition system is reactive 1 if for any state q ∈ Q and any action α ∈ Act there exists a unique µ ∈ Dist(Q) such that q α − → µ [42]. As we will explain in the following section, every PBN corresponds naturally to a probabilistic transition system which is always reactive.
Recall that an equivalence relation R on Q is a reflexive, symmetric, and transitive binary relation on Q. Let Q/R be the quotient set of Q by R (i.e., the set of all equivalence classes [q] = {p ∈ Q : (q, p) ∈ R} for q ∈ Q). Then every µ ∈ Dist(Q) induces a probability distributionμ over Q/R given byμ([q]) = p∈[q] µ(p).
The following definition of a quotient transition system is taken from [43,Definition 12], but slightly adjusted to our notation.
Definition 2: Let T = (Q, Act, →) be a probabilistic transition system and let R be an equivalence relation on Q. The quotient transition system T /R is defined by T /R = (Q/R, Act, → R ), where the probabilistic transition relation → R is defined as follows: for any [q] ∈ Q/R and π ∈ Dist(Q/R), [q] α − → R π if and only if 1 We note that some authors use the terminology "reactive" for a probabilistic transition system where there is at most one (but perhaps no) transition on a given action from a given state.
for every p ∈ [q] there exists a µ ∈ Dist(Q) inducing π such that p α − → µ. It follows from the above definition that an action α can be executed in [q] just in case: (i) α can be executed in every state in [q], and (ii) all states in [q] have identical transition probabilities to each of the equivalence classes after the action α. Furthermore, the transition probability in T /R from [q] to [q ′ ] is simply the probability with which T transitions from q (or any other state belonging to [q]) to the equivalence class [q ′ ]. Note that T /R may not be reactive even if T is. Indeed, it is possible that there are two states in a class, say [q], which have different probabilities of transitioning to some equivalence class under a given action, say α, thus violating the above condition (ii). Then the action α is not executable in [q] and, consequently, the quotient transition system T /R is not reactive.
In the next section, we will use a similar framework to study quotients of a PBN.

III. CONSTRUCTION OF QUOTIENTS
Let us consider a PBN described by 2 As assumed above, {θ(t)} is an i.i.d. process taking finitely many values 1, . . . , S with associated probabilities p 1 , . . . , p S ; and F i ∈ L N ×N M for each 1 ≤ i ≤ S. We define a column-stochastic matrix 3 P = p 1 F 1 + p 2 F 2 + · · · + p S F S , and for each u ∈ ∆ M let The (i, j)-entry of P (u) then gives the transition probability of Σ from its state δ j N to state δ i N when input u is applied (see, e.g., [2]). The above matrix P is called the transition probability matrix of Σ [31]. Note that any column-stochastic matrix P of size N ×N M can be interpreted as the transition probability matrix of a PBN of the form (2). Indeed, since every column-stochastic matrix is a convex combination of logical matrices (cf. the algorithms in [44] and [45]), there exist logical matrices F 1 , . . . , F S and positive reals λ 1 , . . . , λ S such that P = S i=1 λ i F i and S i=1 λ i = 1. Let {θ(t)} be the i.i.d. process with the probability that θ(t) = i equal to λ i for all t ≥ 0. Then the PBN described in (2) has as its transition probability matrix the matrix P .
In order to investigate quotients of (2), we first recall that every equivalence relation R ⊆ ∆ N × ∆ N can be viewed as induced by a logical matrix C with N columns and full row rank, by saying The matrix C is easily derived from the matrix representation of R. Indeed, let A R be the N × N matrix with entries If C is a matrix having the same set of distinct rows as A R , but with no rows repeated, then it must be a logical matrix of full row rank and fulfilling condition (4) (see [46,Lemma 4.6] where it is shown that such a C is a logical matrix with no zero rows, hence of full row rank, and (4) holds for that C). Note that, for an equivalence relation R ⊆ ∆ N × ∆ N induced by a matrix C ∈ L N ×N of full row rank, the quotient set ∆ N /R has cardinality N , and the correspondence [x] → Cx gives a bijection between ∆ N /R and ∆ N .
We now consider quotients of (2). The PBN (2) naturally generates a probabilistic transition system T (Σ) = (∆ N , ∆ M , →), where the transition relation → is defined as follows: for a ∈ ∆ N , u ∈ ∆ M , and µ ∈ Dist(∆ N ), Here, x ⊤ P (u)a is just the transition probability of Σ moving from a to x under input u, since it coincides with the (i, j)-entry of P (u) when x = δ i N and a = δ j N . The above definition of → then says that, for each state a ∈ ∆ N and any u ∈ ∆ M , the probability of T (Σ) transitioning to the next state x is exactly the same as the probability of Σ transitioning from a to x. Clearly, the transition system T (Σ) generated in this way is reactive. In view of the following discussion, we mention that the converse of this fact is also true. Indeed, given a reactive transition system . Then P ′ is column-stochastic (since each P ′ (u) is), and the system T ′ can be considered as generated by a PBN whose transition probability matrix is P ′ .
Let R be an equivalence relation on ∆ N and consider the quotient For the analysis to remain in the Boolean context, we expect that the transitions of T (Σ)/R are also generated by a Boolean system 4 of the form (2). By the above argument, this is the case exactly when T (Σ)/R is reactive, or equivalently, when (that is, for any control action, states in the same class have the same transition probabilities to any equivalence class). We therefore restrict our attention to those R satisfying (5). The following theorem gives a method for constructing a probabilistic Boolean system that generates the transitions of T (Σ)/R. Theorem 1: Consider a PBN Σ as in (2) and let P (u) be as in (3). Suppose that R is an equivalence relation on ∆ N induced by a matrix C ∈ L N ×N of full row rank, and that property (5) holds. Let C ∈ L N × N be such that 5 C ≤ C ⊤ , and for each u ∈ ∆ M define P (u) to be the N × N matrix given by P (u) = CP (u) C. Then: be a probabilistic Boolean system that has P = P (δ 1 M ) P (δ 2 M ) · · · P (δ M M ) as its transition probability matrix. For any a, a ′ ∈ ∆ N and any u ∈ ∆ M , the transition probability of Σ R from Ca to Ca ′ under the input u is equal to the transition probability of Σ moving from a to the equivalence class [a ′ ] = {x ∈ ∆ N : Cx = Ca ′ } when u is applied. Proof: We first claim that for all u ∈ ∆ M and a, a ′ ∈ ∆ N we have where q = Ca and q ′ = Ca ′ . To see this, suppose that q = δ j N , The last equality follows since ( C) lj = 1 exactly when l = s. Noting the equivalence we get the above (7) equal to Since C ≤ C ⊤ and ( C) sj = 1, we have (C) js = 1. Thus, Cδ s N = δ j N = q = Ca and, hence, (δ s N , a) ∈ R. By (5), the right-hand side of (8) is then equal to x∈[a ′ ] x ⊤ P (u)a, and the claim is proved.
We can now prove (a) and (b). Let u ∈ ∆ M and 1 ≤ j ≤ N be fixed. It follows from (6) where 1 ≤ r ≤ N is such that Cδ r N = δ j N (such an r exists since C ∈ L N×N is of full row rank). Since ∆ N is the disjoint union of the sets x : Cx = δ i N , i = 1, . . . , N , the above (9) is equal (P (u)) kr = 1, where the final equality follows from the column-stochasticity of P (u). This shows that P (u) is column-stochastic, proving (a).
In order to prove part (b), we note that the right-hand side of (6) is exactly the transition probability of Σ R from q = Ca to q ′ = Ca ′ under input u. On the other hand, the left-hand side of (6) is the transition probability with which Σ moves from a to equivalence class [a ′ ] when control action u is applied. The assertion of part (b) then follows from (6).
Since, by the above theorem, Σ R generates the transitions of T (Σ)/R (recall that the assignment [x] → Cx is a bijection between ∆ N /R and ∆ N ), it can be interpreted as a quotient of the PBN Σ.
Remark 1: Note that for a given u ∈ ∆ M , the matrix P (u) introduced in Theorem 1 is a constant for all C ∈ L N × N such that C ≤ C ⊤ . Indeed, it follows from (7) and (8) that the (i, j)entry of P (u) is equal to the probability of Σ moving from the state Cδ j N ∈ ∆ N to the equivalence class x ∈ ∆ N : Cx = δ i N when input u is applied. It is easy to see that for any C ∈ L N × N satisfying C ≤ C ⊤ , Cδ j N belongs to the equivalence class x ∈ ∆ N : Cx =  5)), the (i, j)-entry of P (u) is constant for all logical matrices C such that Fig. 1. State transition diagram of the PBN in Example 1. A solid arrow represents the transition by the input δ 1 2 and a dashed arrow represents the transition by the input δ 2 2 . The number associated with each arrow denotes the probability of the state transition given the input. Example 1: As a simple illustration of Theorem 1, consider a PBN as in (2), with N = 8, M = 2, and the transition probability matrix given by The state transition diagram of the PBN is shown in Fig. 1. Let R be the equivalence relation on ∆ 8 produced by the partition exactly when x and x ′ belong to the same subset of the partition). It is easily checked that (5) is satisfied. The matrix representing R is where J k denotes the all-one matrix of size k × k. Collapsing the identical rows of A R yields a full row rank matrix which fulfills (4); and we take C = δ 1 8 δ 2 8 δ 4 8 δ 5 8 , which satisfies C ≤ C ⊤ . A calculation then yields The state transition diagram of Σ R whose transition probability matrix is given by P = P (δ 1 2 ) P (δ 2 2 ) is shown in Fig. 2. It is clear from the figure that Σ R is indeed a quotient of the original network which does not distinguish between states related by R.
Theorem 1 enables us to obtain a quotient Boolean system once an equivalence relation satisfying (5) is found. For the remainder of this section, we will discuss the issue of computing equivalence relations which allow the construction of quotient Boolean systems. More precisely we consider the following problem: given a PBN Σ and an equivalence relation S on ∆ N , determine the maximal (with respect to set inclusion) equivalence relation R ⊆ ∆ N × ∆ N such that R ⊆ S and condition (5) holds. Here, the relation S may be interpreted as a preliminary classification of the states of Σ; and we focus on finding the maximal equivalence relation since in many cases we want the size of a quotient system to be as small as possible. The following theorem suggests a way of deriving such an equivalence relation.
Theorem 2: Let Σ be a PBN described by (2) and let S be an equivalence relation on ∆ N . Define a sequence of relations R k by with the matrix P (u) given by (3). Then: (c) R k * is nonempty and is the maximal equivalence relation on ∆ N such that R k * ⊆ S and property (5) holds. Proof: We first note that, since R 1 = S is an equivalence relation, a simple inductive argument shows that for each k ≥ 1, R k is also an equivalence relation and the quotient ∆ N /R k in the definition of S u,k makes sense.
Part (a) is trivial. Part (b) follows from (a) and the finiteness of each R k . We proceed to the proof of (c). The relation R k * is clearly nonempty (since it contains the identity relation on ∆ N ) and is a subset of S. To show that (5) To prove the maximality of R k * , let R ⊆ ∆ N × ∆ N be another equivalence relation which is contained in S and satisfies (5). We show by induction that R ⊆ R k for all k. This, in particular, means that R ⊆ R k * , thus proving the maximality of R k * . The case k = 1 is trivial, so we take k > 1 and assume that R ⊆ R k−1 . Let (a, a ′ ) ∈ R and fix u ∈ ∆ M . Then we have x∈E x ⊤ P (u)a = x∈E x ⊤ P (u)a ′ for any equivalence class E of R. Since R ⊆ R k−1 , each equivalence class in R k−1 is a disjoint union of equivalence classes of R. It follows that ∈ ∆ N /R k−1 , and consequently (a, a ′ ) ∈ S u,k−1 by the definition of S u,k−1 . Since u ∈ ∆ M is arbitrary, we have (a, a ′ ) ∈ u∈∆ M S u,k−1 , and noting that (a, a ′ ) ∈ R ⊆ R k−1 we conclude (a, a ′ ) ∈ R k . This shows R ⊆ R k , and the theorem is proved.
Recall that a relation R ⊆ ∆ N × ∆ N can be represented by a (0, 1)-matrix of size N × N , whose (i, j)-entry is 1 if and only if (δ i N , δ j N ) ∈ R. For the sake of applications, it is convenient to reformulate the above theorem in terms of (0, 1)-matrices.
Corollary 1: Suppose that S is an equivalence relation on ∆ N represented by a matrix A S . For each u ∈ ∆ M let P (u) be as in (3). Define a sequence of (0, 1)-matrices by where B k,l (l = 1, 2, . . . , M ) are N × N (0, 1)-matrices whose (i, j)-entry is 1 if and only if the ith and jth columns of A k P (δ l M ) are identical. Then there is an integer k * such that A k * +1 = A k * , and A k * is the matrix representing the maximal equivalence relation on ∆ N that is contained in S and satisfies property (5).
Proof: We show that, for each k ≥ 1, the matrix A k represents the equivalence relation R k defined in Theorem 2; the result then follows by Theorem 2. We proceed by induction on k, with the case k = 1 being trivial. Suppose that R k−1 has the matrix representation A k−1 . For u ∈ ∆ M and 1 ≤ r, s ≤ N , the (r, s)-entry of the matrix and since R k−1 is represented by A k−1 , this equals Consequently, the ith and jth columns of A k−1 P (u) are the same exactly when for all 1 ≤ r ≤ N , and the latter is clearly equivalent to saying that and thus B k−1,l is the matrix representing S u,k−1 . Observe that the matrix representation of the intersection of relations is equal to the meet of the matrices representing these relations (see, e.g., [47,Section 9.3]). We conclude that the relation R k is represented by A k , and this completes the proof.
and a direct computation from Corollary 1 yields which is precisely the matrix representing the relation given in Example 1. Hence the relation R presented in Example 1 is the maximal equivalence relation contained in S which satisfies condition (5). We mention that here it is easy to check directly that the obtained R is indeed maximal. Specifically, note that any equivalence relation contained in S corresponds to a refinement of the partition  (5); thus it is the maximal equivalence relation which is contained in S and satisfies (5).
To conclude, we would like to point out that the proposed method for generating a quotient of a PBN is a natural extension of the approach presented in [39] for constructing a quotient of a deterministic BN. Recall that a deterministic BN described by can be seen as a special case of (2), with θ(t) having a constant value with probability one for all t ≥ 0. So the results of this section apply at once. For u ∈ ∆ M , let F (u) be defined as P (u) is in Theorem 1 with P (u) in place of F (u) := F ⋉ u. We note that F (u) has all nonnegative integer entries, and since it is column-stochastic by Theorem 1(a), every column contains exactly one nonzero entry and the nonzero entry equals 1, i.e., F (u) is a logical matrix. Also, recall that the (i, j)-entry of P (u) defined in Theorem 1 is equal to the probability with which the original network reaches the equivalence class x ∈ ∆ N : Cx = δ i N from an arbitrary but fixed state in x : Cx = δ j N when u is applied (cf. Remark 1). Translated to the deterministic setting, this means that ( F (u)) ij = 1 if and only if there is a one-step transition of Σ ′ from a state in x : Cx = δ j N to a state in x : Cx = δ i N under input u. The quotient system

IV. CONTROL DESIGN VIA QUOTIENTS
This section illustrates the application of quotient systems for control design. We consider two typical control problems in PBNs and show how the problems can be solved through the use of a quotient Boolean system.

A. Stabilization
Consider a PBN Σ as in (2) and let P (u) be as in (3), which gives the (one-step) transition probabilities of Σ under input u ∈ ∆ M . A (time-invariant) feedback controller is given by a map U : ∆ N → ∆ M so that if the present state is x ∈ ∆ N , then the controller selects the control input U(x) ∈ ∆ M , resulting in the matrix P (U(x)) that determines the one-step transition probabilities. Observe that when the present state is, say, δ i N , only the transition probabilities of leaving δ i N are relevant and are given by the ith column of the matrix P (U(δ i N )). We use P U to denote the matrix obtained by stacking such columns, i.e., the ith column of P U is the ith column of P (U(δ i N )). It is easy to see that the evolution of Σ under the control of the state feedback controller U : ∆ N → ∆ M is governed by the matrix P U , i.e., the transition probability from a ∈ ∆ N to b ∈ ∆ N after k steps is given by b ⊤ P k U a. Let M ⊆ ∆ N be a target set of states. The Boolean system Σ is stabilized to M with probability one by U : ∆ N → ∆ M , if for every initial state x 0 ∈ ∆ N , there exists an integer τ such that k ≥ τ implies x∈M x ⊤ P k U x 0 = 1 (see, e.g., [31], [48]). The following result shows that we can easily derive a stabilizing controller for Σ on the basis of a stabilizing controller for its quotient system. (b) If the controller x R → U R (x R ) stabilizes Σ R to M R with probability one, then the controller given by x → U(x) = U R (Cx) stabilizes Σ to M with probability one. For the proof of Proposition 1 we need the following lemma adapted from [49]. To make the paper self-contained, the proof of this lemma is given in the Appendix.
Lemma 1: Consider a PBN as in (2). Let M ⊆ ∆ N , and let M * be the last term of the sequence x∈M i−1 x ⊤ P (u)a = 1 for some u ∈ ∆ M }, and the value of ι is determined by the condition M ι+1 = Mι. Define the sequence Z j according to Then Z j ⊇ Z j−1 , and the PBN can be stabilized to M with probability one by a feedback U : ∆ N → ∆ M if, and only if, Z λ = ∆ N for some λ ≥ 1.
Proof of Proposition 1: (a) Let M i and Z j be as in Lemma 1. Let M * R be the last term of the sequence u ∈ ∆ M }, and the value of ι ′ is determined by the condition M ι ′ +1 = M ι ′ . Define the sequence Z j according to We show that for j ≥ 0, First, we claim that Indeed, if Cx ∈ M 0 , then there exists x ′ ∈ M such that Cx = Cx ′ , and hence (x, x ′ ) ∈ R ⊆ S, forcing x ∈ M since S is the equivalence relation yielded by the partition {M, ∆ N − M}. This shows that Cx ∈ M 0 ⇒ x ∈ M 0 . The converse implication is trivial. Assume by induction that x ∈ M i−1 ⇐⇒ Cx ∈ M i−1 .
Denoting I(z) = {x ∈ ∆ N : Cx = z} for z ∈ ∆ N , which is nonempty since C is supposed to have full row rank, then M i−1 can be partitioned as the disjoint union M i−1 = z∈ M i−1 I(z).
Indeed, the sets I(z), z ∈ M i−1 , are clearly mutually disjoint, and for any x ∈ ∆ N , x ∈ M i−1 if and only if Cx ∈ M i−1 , if and only if x ∈ I(z) for some z ∈ M i−1 . Suppose x ∈ ∆ N , u ∈ ∆ M , and let q = Cx. Then where the second equality follows from (6) in the proof of Theorem 1. This immediately implies that The proof of (10) is easily obtained by induction on j. It follows from (11) that x ∈ Z 0 if and only if Cx ∈ Z 0 , establishing the base step. The induction step is similar to that done in the proof of (11).
Since C is of full row rank, we conclude from (10) that Z j = ∆ N if and only if Z j = ∆ N , and the proof of (a) follows by Lemma 1.
(b) Define the matrix P U R for Σ R in the same way as P U is defined for Σ. We first prove that, for any a ∈ ∆ N , z ∈ ∆ N , and integer k ≥ 1, we have where I(z) = {x ∈ ∆ N : Cx = z} and q = Ca. The proof is by induction on k. Since P U a = P (U(a))a by the construction of P U , it follows from (6) in the proof of Theorem 1 that x ⊤ P (U(a))a = z ⊤ P (U(a))q, and since U(a) = U R (Ca) = U R (q), the above is equal to z ⊤ P (U R (q))q = z ⊤ P U R q. This gives (12) for k = 1. Assume as induction hypothesis that the statement holds for k −1. Decomposing the N × N identity matrix as b∈∆ N bb ⊤ , we have The last equality holds true since ∆ N is the disjoint union of the sets I(δ i , and the right-hand side of (13) is equal to the following expression: According to the induction hypothesis, we have for each and substituting this into (14) we get which is (12). From the proof of (a), we know that x ∈ M if and only if Cx ∈ M R , and consequently, we can write M as the disjoint union M = z∈M R I(z). The proof of part (b) is now obvious. Suppose x 0 ∈ ∆ N . Let x 0 R = Cx 0 . Then for each integer k ≥ 1 we have from which part (b) follows immediately.

B. Optimal Control
Let us consider the following optimal control problem, introduced in [50].
Problem 1: Consider a PBN as in (2). Given an initial state x 0 ∈ ∆ N and a finite time horizon T ∈ Z + , find a control policy, u(t) = U * (t, x(t)) for 0 ≤ t ≤ T − 1, that minimizes the cost functional where l(u, x) and g(x) are real-valued functions defined on ∆ M × ∆ N and ∆ N , respectively.
We show that the solution to Problem 1 can be found by considering the problem for a suitably chosen quotient system. To this end, let S be the equivalence relation on ∆ N given by We note that, if C ∈ L N ×N has full row rank, and if the equivalence relation R induced by C satisfies R ⊆ S, then every z ∈ ∆ N can be written as z = Cx for some x ∈ ∆ N and the function g is constant on the set I(z) = {x ∈ ∆ N : Cx = z}. Hence, the map g R : ∆ N → R, given by is well defined. For the same reason, the map l R : is also well defined. We can state the following proposition. Proposition 2: Let Σ be a PBN described by (2) and consider Problem 1 with given x 0 and T . Suppose that S is the equivalence relation given by (15), R ⊆ ∆ N × ∆ N is an equivalence relation induced by a full row rank matrix C ∈ L N ×N , R ⊆ S, and (5) holds. Let Σ R be the probabilistic Boolean system constructed in Theorem 1, and define J R = E g R (x R (T )) + T −1 t=0 l R (u(t), x R (t)) , where g R and l R are given by (16) and (17). Suppose that (t, x R ) → U * R (t, x R ) is an optimal control policy solving Problem 1 with Σ, x 0 , and J replaced by Σ R , x 0 R = Cx 0 , and J R , respectively. Then the control policy given by (t, x) → U * (t, x) = U * R (t, Cx) is an optimal control policy for Σ. Moreover, let J * be the optimal value of J given the initial state x 0 and let J * R be the optimal value of J R associated with x 0 R = Cx 0 . Then J * = J * R . The proof of the proposition follows from the following two lemmas.
Lemma 2: Consider Problem 1 with given x 0 and T . Let S, R, and C be as in Proposition 2. Then there exists an optimal control policy (t, x) → U(t, x) with the property that U(t, x) = U(t, x ′ ) for all 0 ≤ t ≤ T − 1 and all x, x ′ ∈ ∆ N such that Cx = Cx ′ .
Proof: Consider the following dynamic programming algorithm (adapted from [51, Proposition 1.3.1]; see also [50]): where P (u) is as in (3). If we let and define then the control law given by (t, x) → U (t, x) is optimal [50], [51]. We will show that for 0 ≤ t ≤ T − 1, Then we can find U(t, x) ∈ arg minu G(t, x, u) with the desired property. This will prove the lemma.
Fix u ∈ ∆ M and let x, x ′ ∈ ∆ N be such that Cx = Cx ′ . Since (x, x ′ ) ∈ R ⊆ S, it follows from (15) that For each z ∈ ∆ N , since H(T, ·) = g(·) is constant on the set I(z) = {ξ ∈ ∆ N : Cξ = z} (cf. the statement following (15)) and since Hence, since ∆ N is the disjoint union of I(z), z ∈ ∆ N . This together with (19) gives Note that if t ≤ T − 1 and if (18) is true for t, then for any ξ, ξ ′ ∈ ∆ N with Cξ = Cξ ′ , we have Thus with this t fixed, the function H(t, ·) is constant on each of the sets I(z) = {ξ : Cξ = z}. Then by an argument similar to that in the previous paragraph, we can show that (18) is true for t − 1 also, and so working by downward induction on t, we conclude that (18) holds true for all 0 ≤ t ≤ T − 1, as required. The proof is complete.
Lemma 3: Let the notation be as in the statement of Proposition 2. If the initial states of Σ and Σ R satisfy Cx 0 = x 0 R , and if the two control policies (t, x) → U(t, x) and (t, x R ) → U (t, x R ) satisfy U(t, x) = U(t, Cx) for all 0 ≤ t ≤ T − 1 and x ∈ ∆ N , then the cost functionals J and J R have the same value.
Proof: For each 0 ≤ t ≤ T − 1, let P t be the matrix whose ith column is the ith column of the matrix P (U(t, δ i N )), and let P t be the matrix in which the jth column is the jth column of P ( U (t, δ j N )). With a similar argument to that in proving (12), it is easy to see that for any a ∈ ∆ N , z ∈ ∆ N , and 1 ≤ t ≤ T , we have x∈I(z) x ⊤ P t−1 P t−2 · · · P 0 a = z ⊤ P t−1 P t−2 · · · P 0 q, where I(z) = {x ∈ ∆ N : Cx = z} and q = Ca.  ( U (t, Cx), Cx), it follows that x ∈ M(t, s) if and only if Cx ∈ M(t, s), and hence M(t, s) can be written as the disjoint union M(t, s) = z∈ M(t,s) I(z). Consequently, P l(U(t, x(t)), x(t)) = s = P x(t) ∈ M(t, s) Thus, we get The assertion of the lemma follows from the linearity of expectations.
Proof of Proposition 2: Let J(x 0 , U * ) be the value of J for the initial state x 0 and the control policy (t, x) → U * (t, x) = U * R (t, Cx), and let J R (x 0 R , U * R ) be the value of J R when the initial state is x 0 R = Cx 0 and the control policy (t, x) be the optimal control policy for Σ given by Lemma 2. Define a control policy for Σ R by (t, be the corresponding values of J and J R respectively. We have J R (x 0 R , U R ) = J(x 0 , U) = J * , by Lemma 3. Since U minimizes J given the initial state x 0 , it follows that J(x 0 , U) ≤ J(x 0 , U * ), and thus J * ≤ J * R . On the other hand, Thus, J * R ≤ J * and, hence, they are equal. It is also clear that U * is an optimal control law since J(x 0 , U * ) = J * R = J * . Example 3: To give an intuitive example of the proposed equivalence relation for solving the optimal control problem, consider again the PBN in Example 1. Suppose that the functions l(u, x) and g(x) are given by l(δ 1 2 , δ 1 8 ) = · · · = l(δ 1 2 , δ 4 8 ) = 1, l(δ 1 2 , δ 5 8 ) = · · · = l(δ 1 2 , δ 8 8 ) = 2, l(δ 2 2 , x) = 3, x ∈ ∆ 8 , g(δ 1 8 ) = 1, g(δ 2 8 ) = · · · = g(δ 8 8 ) = 2.
Then condition (15)  Let R be an equivalence relation which is contained in S and satisfies (5); for example, let R be the relation given in Example 1. It is easily checked that, for any x, x ′ in the same equivalence class of R and for either u ∈ ∆ 2 , we have g(x) = g(x ′ ), l(u, x) = l(u, x ′ ), and under the same input the (one-step) transition probability from x to any of the four equivalence classes of R is equal to that from x ′ to that class. For instance, if x = δ 2 8 , x ′ = δ 3 8 , and the input u = δ 1 2 , then g(x) = g(x ′ ) = 2, l(u, x) = l(u, x ′ ) = 1, and the transition probability from x to the equivalence class {δ 2 8 , δ 3 8 } or from x to {δ 1 8 } is 0.5, which is also the transition probability from x ′ to {δ 2 8 , δ 3 8 } or to {δ 1 8 } (cf. Fig. 1). This means that the states belonging to the same equivalence class of R have similar properties in terms of costs and transitions, and then can be amalgamated to form a quotient.
To conclude the section, we mention that the controller synthesized via Proposition 1 or 2 has a specific structure in which all states in the same equivalence class are assigned the same control action. There is therefore an underlying assumption when applying the quotient-based method, namely that such a controller exists for the original network. We do not explicitly mention this assumption in the statement of Propositions 1 and 2, since it is automatically implied by the conditions already stated in the propositions. Indeed, it follows from Proposition 1 that if a PBN Σ is stabilizable, then so is the quotient system Σ R , and by inducing a stabilizing controller for Σ R back to the original network, one can derive a feedback law that stabilizes Σ, showing for Σ the existence of a stabilizing controller with that specific structure. Similarly, we see from Lemma 2 that under the conditions of Proposition 2, there always exists for Σ an optimal controller having that structure. We should note, however, that these existence results do not ensure that we are always able to find a stabilizing (or optimal) controller for a PBN on the basis of another controller designed from a smaller network, since there may be situations in which there is no equivalence relation satisfying the hypotheses of Proposition 1 (or 2) except for the identity relation, yielding a quotient system the same as the original. Also, note that in the above discussion we do not require the equivalence relation to be maximal, although that will be the case in most applications. In practice, for a given PBN, we may apply Theorem 2 to find the maximal equivalence relation R that satisfies the hypotheses of Proposition 1 (or 2). Such a maximal R always exists: in the extreme case, one has R equal to the identity relation, which means that no other equivalence relations exist that satisfy the proposition's hypotheses. According to the preceding argument, if the PBN is stabilizable, then it can be stabilized by a feedback that assigns the same control to any two states related by R. Also, there exists an optimal controller where the control actions corresponding to different states related by R are the same.

V. A BIOLOGICAL EXAMPLE
The lac operon in Escherichia coli is the system responsible for the transport and metabolism of lactose. Although glucose is the preferred carbon source for E. coli, the lac operon allows for the effective digestion of lactose when glucose is not readily available. A Boolean model for the lac operon in E. coli was identified in [52]. The model consists of 13 variables (1 mRNA, 5 proteins, and 7 sugars) denoted by M lac , P lac , B, Cap, R, Rm, A, Am, L, Lm, Le, Lem and Ge. The Boolean functions of the model are given in Table I. We assume that the concentration of extracellular lactose (indicated by Le and Lem) can be either low or medium, 6 causing the model to appear random. We then arrive at a PBN consisting of two BNs. The first constituent BN is determined from Table I when Le = Lem = 0, and the second constituent BN is determined by setting Le = 0 and Lem = 1. The two constituent BNs are assumed to be equally likely. The concentration level of extracellular glucose (Ge) acts as the control input. The algebraic representation of the PBN is as in (2), with N = 1024, M = 2, and the selection probabilities given by p 1 = p 2 = 0.5. The matrices F 1 , F 2 ∈ L 1024×2048 are not presented explicitly due to their sizes. 1) Stabilization. When extracellular lactose is low, the lac operon model is known to exhibit two steady states [52], expressed in the canonical vector form as δ 912 1024 and δ 976 1024 . Let M = {δ 912 1024 } and let S be the equivalence relation produced by the partition {M, ∆ 1024 − M}. Then by following the procedure described in Section III, we obtain a quotient system Σ R with the transition probability matrix given by + 0.5δ 10 33 0.5δ 15 33 + 0.5δ 16 33 0.5δ 13 33 + 0.5δ 14 33 0.5δ 11 33 + 0.5δ 12 33 .
It is not hard to see that 7 the constant control u = δ 2 2 is optimal for Σ R , with the optimal cost J * R = 5.9063 (to which corresponds x 0 R = δ 25 25 ). Thus, by virtue of Proposition 2, this constant input also solves the optimal control problem for the original PBN, and the optimal cost corresponding to the initial state x 0 = δ 1 1024 is J * = J * R = 5.9063.

VI. SUMMARY
We considered quotients for PBNs in the exact sense that the notion is used in the control community. Specifically, we considered a probabilistic transition system generated by the PBN. The corresponding quotient transition system then captures the quotient dynamics of the PBN. We thus proposed a method of constructing a probabilistic Boolean system that generates the transitions of the quotient transition system. It is not surprising that the equivalence relation should satisfy certain constraints so that the quotient dynamics can indeed be generated from a Boolean system. We then developed a procedure converging in a finite number of iterations to a satisfactory equivalence relation. Finally, a discussion on the use of quotient systems for control design was given, and an application of the proposed results to stabilization and optimal control was presented. As a result, it is concluded that the control problems of the original PBN can be boiled down to those of the quotient systems. That is, instead of deriving control polices directly on the original network, which could be computationally expensive, one can design control polices on the quotient and subsequently induce the control polices back to the original PBN.

APPENDIX
Proof of Lemma 1: First, note that Z j ⊇ Z j−1 . In fact, since M * = Mι = Mι ∩A(Mι), we have Z 0 ⊆ Z 1 , and if Z j−1 ⊆ Z j , then for any a ∈ ∆ N such that x∈Z j−1 x ⊤ P (u)a = 1 for some u ∈ ∆ M , we have x∈Z j x ⊤ P (u)a = 1, and thus Z j ⊆ Z j+1 . Now, suppose that there exists a control law U : ∆ N → ∆ M that stabilizes the PBN to M with probability one. We first show that for every k ≥ 1, 7 Similarly as in the proof of Lemma 2, the optimal control problem for Σ R can be solved by the following dynamic programming algorithm, which proceeds backward in time from t = 10 to t = 0 (see, e.g., [50], [51]): where P (u) = P ⋉ u for u ∈ ∆ 2 . The optimal control law is obtained as U * R (t, x R ) = arg min u∈∆ 2 G(t, x R , u), and the optimal cost starting from the initial state x 0 R is given by H(0, x 0 R ). Clearly, different initial states may have different optimal values associated with them. For example, here a direct computation shows that H(0, δ 25 25 ) = 5.9063 and H(0, δ 1 25 ) = 6. Thus the optimal cost for the initial state x 0 R = δ 25 25 is 5.9063, while that for the initial state x 0 R = δ 1 25 is 6.
We use induction on k. The case k = 1 is trivial, so we proceed to the induction step. If x∈M * x ⊤ P k U x 0 = 1, then since and so by the induction hypothesis, b ∈ ∆ N and b ⊤ P U x 0 > 0 ⇒ b ∈ Z k−1 . Consequently, This shows that x 0 ∈ Z k . Let x 0 ∈ ∆ N . Since the feedback U : ∆ N → ∆ M stabilizes the PBN to M with probability one, there is τ ≥ 0 such that Hence, This implies that x∈M 1 x ⊤ P k U x 0 = 1, for any k ≥ τ . In the same way and by a simple induction argument, we obtain x∈M * x ⊤ P k U x 0 = 1 for k ≥ τ , and therefore, by (20) x 0 ∈ Z k for all k ≥ τ . This implies that Z λ = ∆ N for sufficiently large λ.
Conversely, suppose that Z λ = ∆ N for some λ ≥ 1. Let Z ′ 1 = Z 1 and Z ′ j = Z j − Z j−1 for j = 2, 3, . . . , λ. For every x ∈ ∆ N , we find a unique Z ′ j containing x and then pick ux ∈ ∆ M such that b∈Z j−1 b ⊤ P (ux)x = 1. We show that the feedback given by U : x → ux stabilizes the PBN to M with probability one. Since Z λ = ∆ N and M * ⊆ M, it suffices to show that for 1 ≤ j ≤ λ, x 0 ∈ Z j and k ≥ j ⇒ x∈M * x ⊤ P k U x 0 = 1.
We use induction on j. By the definition of U, we have x∈M * x ⊤ P U x 0 = 1 for all x 0 ∈ Z 1 . If k ≥ 2 and if x∈M * x ⊤ P k−1 U x 0 = 1 for all x 0 ∈ Z 1 , then for fixed x 0 we have Thus (21) holds for j = 1. To prove the induction step, assume that j ≥ 2 and (21) is true for j − 1. Let x 0 ∈ Z j , k ≥ j, and we show that x∈M * x ⊤ P k U x 0 = 1. This is clear if x 0 ∈ Z j−1 , by the induction hypothesis; so suppose x 0 ∈ Z ′ j . Then, by the definition of U, we obtain b∈Z j−1 b ⊤ P U x 0 = 1. Note that Since by the induction assumption x∈M * x ⊤ P k−1 U b = 1 for all b ∈ Z j−1 , the right-hand side of (22) is equal to b∈Z j−1 b ⊤ P U x 0 = 1. This completes the induction step and hence the proof.