Structural Properties of Invariant Dual Subspaces of Boolean Networks *** This
work is supported by Key Programs in Shaanxi Province of China under Grant
2021JZ-12.

Dongyao Bi†, Lijun Zhang∗†, Kuize Zhang‡

†School of Marine Science and Technology, Northwestern Polytechnical
University, Xi’an 710072, P.R. China

∗E-mail<EMAIL_ADDRESS>
‡Department of Computer Science, University of Surrey, GU2 7XH, Guildford, UK

Abstract: In this paper, we obtain the following results on dual subspaces of
Boolean networks (BNs). For a BN, there is a one-to-one correspondence between
partitions of its state-transition graph (STG) and its dual subspaces (i.e.,
the subspaces generated by a number of Boolean functions of the BN’s
variables). Moreover, a dual subspace is invariant if and only if the
corresponding partition is equitable, i.e., for every two (not necessarily
different) cells of the partition, every two states in the former have equally
many out-neighbors in the latter. With the help of equitable partitions of an
STG, we study the structural properties of the smallest invariant dual
subspaces containing a number of Boolean functions. And then, we give
algorithms for computing the equitable partition corresponding to the smallest
invariant dual subspace containing a given dual subspace. Moreover, we reveal
that the unobservable subspace of a BN is the smallest invariant dual subspace
containing the output function. We analyze properties of the unobservable
subspace by using the obtained structural properties. The graphical
representation provides an easier and more intuitive way to characterizing the
(smallest) invariant dual subspaces of a BN.

Keywords: Boolean network, equitable partition, quotient graph, unobservable
subspace.

##  1 Introduction

Boolean networks (BNs) were firstly proposed by Kauffman in 1969 [1]. From
then on it has proven to be a very efficient way to modeling and analyzing
genetic regulatory networks. The semi-tensor product (STP) of matrices was
proposed by Cheng in 2001 [2, 3] which makes BNs be dealt with by algebraic
methods. Recently Cheng et al. [4] considered the problem of finding the
smallest “$M$-invariant” (called “invariant dual” in the current paper)
subspace of a BN containing a given set of Boolean functions. Furthermore, we
study the structural properties of invariant dual subspaces from a graphical
perspective in this paper.

When a BN (BCN) is large-scale, the structure matrix of the overall BN (BCN)
will be of huge size and cannot be computed in a reasonable amount of time.
However, the dual systems of a BN generated by its invariant dual subspaces
are usually small and still can carry useful information of the original BN.
For example, in a BN with output (observation), the dynamic equation of the
smallest invariant dual subspace containing the given output function is
called the minimum realization of the BN. In the dual dynamics, part of the
structure of the original BN can be revealed [4]. Hence, dual dynamic systems
may provide a promising way to overcoming the high computational complexity of
dealing with large-scale BN in some sense. An algorithm for computing the
smallest invariant dual subspace containing a given set of Boolean functions
has been given in [4].

To study the properties of invariant dual subspaces, we first establish a one-
to-one correspondence between partitions of state-transition graphs (STGs) and
dual subspaces of BNs. In graph theory, a definition of equitable partition of
a directed graph (digraph) was given and the relationship between partition
cells was described by the quotient digraph of the diagraph [5]. We prove that
a dual subspace of a BN is invariant if and only if the corresponding
partition is equitable. Furthermore, we discuss the structural features of the
invariant dual subspaces of BNs with loops or cycles, respectively. These
properties provide a different way to determining whether a BN is observable.
Compared to the STP representation of the (smallest) invariant dual subspaces
used in [4], the graphical representation adopted in the current paper
provides an easier and more intuitive way to characterizing the (smallest)
invariant dual subspaces of a BN, and results in more concrete conclusions on
the invariant dual subspaces.

The rest of this paper is organized as follows. Section 2 is a survey for
necessary results in graph theory and STP. The main results of the current
paper are shown in Section 3 and Section 4. Structural properties of the
smallest invariant dual subspace containing a given set of Boolean functions
are obtained in Section 3. Section 4 discloses the fact that in a given BN,
its unobservable subspace is the smallest invariant dual subspace containing
its output functions. We get some methods for establishing output functions to
make a given BN observable by using the structural properties.

##  2 Preliminaries

###  2.1 Basic knowledge in graph theory

####  2.1.1 Basic concepts and notation

A digraph is denoted by ${\cal G}=(V,E)$, where
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and $E\subseteq V\times V$ represent the
vertex set and the edge set, respectively. If $e_{ij}=(v_{i},v_{j})$ is an
edge of ${\cal G}$, $v_{i}$ and $v_{j}$, two ends of $e_{ij}$, are called the
tail and the head of $e_{ij}$, respectively. If $e_{ij}\in E$, $v_{i}$
($v_{j}$) is an in-neighbor (out-neighbor) of $v_{j}$ ($v_{i}$). With each
digraph ${\cal G}$, we associate an undirected graph on the same vertex set;
corresponding to each directed edge of ${\cal G}$ there is an undirected edge
with the same ends. This graph is called the underlying graph of ${\cal G}$. A
path from $v_{1}$ to $v_{k+1}$ of length $k$ is a digraph with vertex set
$\\{v_{1},v_{2},\ldots,v_{k+1}\\}$ and edge set
$\\{(v_{i},v_{i+1})|~{}i=1,\ldots,k\\}$. Likewise, a cycle of length $k$ is a
path $v_{1}\cdots v_{k+1}$ such that $v_{1}=v_{k+1}$; a cycle on a single
vertex is called a loop. If there exists a path from $v_{i}$ to $v_{j}$,
vertex $v_{j}$ is said to be reachable from $v_{i}$. A digraph is said weakly
connected if for any pair of vertices there exists an undirected path in its
underlying graph between them. Every digraph may be expressed uniquely (up to
order) as a disjoint union of maximal weakly connected digraphs. These
digraphs are called the components of ${\cal G}$. The distance from $v_{i}$ to
$v_{j}$ is the length of a shortest path from $v_{i}$ to $v_{j}$, denoted by
$\operatorname{dist}(v_{i}\rightarrow v_{j})$ (we set
$\operatorname{dist}(v_{i}\rightarrow v_{i})=0$ and
$\operatorname{dist}(v_{i}\rightarrow v_{j})=\infty$ if $v_{j}$ is not
reachable from $v_{i}$). The largest in-distance (out-distance)
$\operatorname{dist}_{in}(v_{i})$ ($\operatorname{dist}_{out}(v_{i})$) of
$v_{i}$ is the maximum $\operatorname{dist}(v_{j}\rightarrow v_{i})$
($\operatorname{dist}(v_{i}\rightarrow v_{j})$) over all vertices reachable to
(from) $v_{i}$. We use $N_{in}(v_{i},k)$ ($N_{out}(v_{i},k)$) to denote the
vertex set $\\{v_{j}|\operatorname{dist}(v_{j}\rightarrow v_{i})=k\\}$
($\\{v_{j}|\operatorname{dist}(v_{i}\rightarrow v_{j})=k\\}$), where
$k\in\\{0,1,\ldots,\operatorname{dist}_{in}(v_{i})(\operatorname{dist}_{out}(v_{i})),\infty\\}$.
The in-neighboring $N_{in}(v_{i})$ (out-neighboring $N_{out}(v_{i})$) set of
$v_{i}\in V$ is the set $N_{in}(v_{i},1)$ ($N_{out}(v_{i},1)$). The in-degree
(out-degree) of $v_{i}$, denoted by $d_{in}(v_{i})$ ($d_{out}(v_{i})$), is the
cardinality of $N_{in}(v_{i})$ ($N_{out}(v_{i})$). For a given vertex set $C$,
we denote by $N_{in}(C,\infty)$ the vertex set which are not reachable to any
vertex in $C$.

To model practical problems, one often needs to define a weighted digraph as a
digraph with a weight function $w$ that assigns to each edge $e\in E$ a weight
$w(e)\in\mathbb{R}$. For a given weighted digraph ${\cal G}$ (if ${\cal G}$ is
unweighted, then the weights of edges are all equal to 1), the adjacency
matrix $A({\cal G})$ is an $n\times n$ matrix defined as

$[A({\cal G})]_{ij}=\left\\{\begin{array}[]{ll}w(e_{ji}),&e_{ji}\in E,\\\
0,&\text{ otherwise. }\end{array}\right.$

####  2.1.2 Graph partitions

For a digraph ${\cal G}=(V,E)$ with $n$ vertices and a given constant $1\leq
k\leq n$, we call $\pi=\\{C_{1},C_{2},\ldots,C_{k}\\}$ a $k$-partition of $V$
if $\pi$ is a family of nonempty disjoint subsets of $V$ and
$\cup_{i=1}^{k}C_{i}=V$. Accordingly, $C_{i},~{}i=1,2,\ldots,k$. are called
partition cells. If a partition contains at least one cell with more than one
vertex, it is nontrivial; otherwise, it is trivial. The characteristic matrix
$P(\pi)\in\\{0,1\\}^{n\times k}$ of the partition $\pi$ is defined as follows.

$[P]_{ij}=\left\\{\begin{array}[]{l}1,\text{ if }~{}v_{i}\in C_{j},\\\
0,\text{ otherwise, }\end{array}\quad 1\leqslant i\leqslant n,1\leqslant
j\leqslant k.\right.$

######  Definition 2.1 ([6]).

Let ${\cal G}=(V,E)$ be a weighted digraph with adjacency matrix $A({\cal
G})$. A partition $\pi$ of $V$ is said to be equitable if for all pairs
$(C_{i},C_{j})$, $i,j=1,\ldots,k$, $\forall v_{s},v_{t}\in C_{i}$

$\sum_{v_{k}\in N_{out}(v_{s})\cap C_{j}}[A({\cal G})]_{ks}=\sum_{v_{k}\in
N_{out}(v_{t})\cap C_{j}}[A({\cal G})]_{kt}.$ (1)

Particularly, when ${\cal G}$ is unweighted, $(\ref{2.1.2-1})$ degenerates to

$|N_{out}(v_{s})\cap C_{j}|=|N_{out}(v_{t})\cap C_{j}|.$ (2)

For an equitable partition $\pi$ of $V$, the quotient digraph ${\cal G}/\pi$
of ${\cal G}$ over $\pi$ has the vertex set $V({\cal
G}/\pi)=\left\\{C_{1},C_{2},\ldots,C_{k}\right\\}$ and edge set $E({\cal
G}/\pi)=\left\\{(C_{i},C_{j})\mid N_{out}(v_{s})\cap
C_{j}\neq\emptyset,v_{s}\in C_{i}\right\\}$; and the weight of $(C_{i},C_{j})$
is $\sum_{v_{k}\in N_{out}(v_{s})\cap C_{j}}[A({\cal G})]_{ks},\forall
v_{s}\in C_{i}$. With slight abuse of notation, we call an equitable partition
of $V$ an equitable partition of ${\cal G}$.

######  Lemma 2.2 ([7]).

Let ${\cal G}$ be a digraph. A $k$-partition $\pi$ is equitable if and only if
there exists a matrix $H$ satisfying $P^{T}A=HP^{T}$, where $P$ is the
characteristic matrix of $\pi$ and $A$ is the adjacency matrix of ${\cal G}$.
Moreover, if $\pi$ is equitable, then $H$ is exactly the adjacency matrix of
${\cal G}/\pi$.

In Lemma 2.2, $[P^{T}A]_{ij}$ is the sum of the weights of the edges starting
from $v_{j}$ and going into $C_{i}$, i.e., $\sum_{v_{k}\in N_{out}(v_{j})\cap
C_{i}}[A({\cal G})]_{kj}$. And $[HP^{T}]_{ij}$ is equal to $[H]_{ik}$, where
$C_{k}$ is the cell containing $v_{j}$. For unweighted digraphs,
$P^{T}A=HP^{T}$ means that any two vertices in the same cell have the same
number of out-neighbors in any cells.

######  Definition 2.3.

A partition $\pi_{1}$ is said to be finer than $\pi_{2}$ if each cell of
$\pi_{2}$ is the union of some cells in $\pi_{1}$, denote by
$\pi_{2}\preceq\pi_{1}$. In this case, we also say $\pi_{2}$ is coarser than
$\pi_{1}$.

Denote the set of all the partitions of $V$ by $\Pi$. The trivial partition
$\\{\\{v_{1}\\},\\{v_{2}\\},\ldots,\\{v_{n}\\}\\}$ is finer than any partition
in $\Pi$. In this paper, we use $V({\cal G})$ to simply denote the trivial
partition.

######  Definition 2.4 ([3]).

Let $S$ be a subset of $\Pi$.

  * $(i)$

$\pi\in\Pi$ is an upper bound (a lower bound) of $S$ if
$\pi^{\prime}\preceq\pi$ ($\pi\preceq\pi^{\prime}$) for all $\pi^{\prime}\in
S$.

  * $(ii)$

$\pi\in\Pi$ is the least upper bound of $S$, also the join of $S$, (denoted by
$\pi=\sqcup S$), if $\pi$ is an upper bound of $S$, and for any other upper
bound $\pi^{\prime}$ of $S$, we have $\pi\preceq\pi^{\prime}$.

  * $(iii)$

$\pi\in\Pi$ is the greatest lower bound of $S$, also the meet of $S$, (denoted
by $\pi=\sqcap S$), if $\pi$ is a lower bound of $S$, and for any other lower
bound $\pi^{\prime}$ of $S$, we have $\pi^{\prime}\preceq\pi$.

######  Example 2.5.

A digraph with four vertices is shown in Fig. 1, where its three quotient
graphs is obtained according to equitable partitions
$\pi_{1}=\\{\\{v_{1},v_{2}\\},\\{v_{3}\\},\\{v_{4}\\}\\}$,
$\pi_{2}=\\{\\{v_{1},v_{2},v_{3}\\},\\{v_{4}\\}\\}$ and
$\pi_{3}=\\{\\{v_{1},v_{3}\\},\\{v_{2}\\},\\{v_{4}\\}\\}$. Since
$\\{v_{1},v_{2},v_{3}\\}=\\{v_{1},v_{2}\\}\cup\\{v_{3}\\}=\\{v_{1},v_{3}\\}\cup\\{v_{2}\\}$,
$\pi_{1}$ and $\pi_{3}$ are finer than $\pi_{2}$. The join of $\pi_{1}$ and
$\pi_{3}$ is $\\{\\{v_{1}\\},\\{v_{2}\\},\\{v_{3}\\},\\{v_{4}\\}\\}$ and their
meet is $\pi_{2}$. That is

$\pi_{2}\preceq\pi_{1}\quad\pi_{2}\preceq\pi_{3},$
$\pi_{1}\sqcup\pi_{3}=\\{\\{v_{1}\\},\\{v_{2}\\},\\{v_{3}\\},\\{v_{4}\\}\\},$
$\pi_{1}\sqcap\pi_{3}=\pi_{2}.$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$ (a) ${\cal G}$

$\\{v_{1},v_{2}\\}$$\\{v_{3}\\}$$\\{v_{4}\\}$ (b) ${\cal G}/\pi_{1}$

$\\{v_{1},v_{2},v_{3}\\}$$\\{v_{4}\\}$ (c) ${\cal G}/\pi_{2}$

$\\{v_{1},v_{3}\\}$$\\{v_{2}\\}$$\\{v_{4}\\}$ (d) ${\cal G}/\pi_{3}$

Figure 1: (a) Digraph ${\cal G}$.(b) Quotient digraph of $\pi_{1}$, where
$C_{1}=\\{v_{1},v_{2}\\}$, $C_{2}=\\{v_{3}\\}$, and $C_{3}=\\{v_{4}\\}$. (c)
Quotient digraph of $\pi_{2}$, where $C_{1}=\\{v_{1},v_{2},v_{3}\\}$ and
$C_{2}=\\{v_{4}\\}$. (d) Quotient digraph of $\pi_{3}$, where
$C_{1}=\\{v_{1},v_{3}\\}$, $C_{2}=\\{v_{2}\\}$, and $C_{3}=\\{v_{4}\\}$.

Let ${\cal G}$ be a digraph and $\pi$ an equitable partition over ${\cal G}$.
Let $\rho=\\{C^{\prime}_{1},\ldots,C^{\prime}_{l}\\}$ be an equitable
partition of the quotient graph ${\cal G}/\pi$. Define the partition
$\pi\rho=\\{\overline{C}_{1},\ldots,\overline{C}_{l}\\}$ of $V({\cal G})$ by
$\overline{C}_{j}:=\bigcup_{C_{i}\in C^{\prime}_{j}}C_{i}$ for
$j=1,2,\ldots,l$. Then $\pi\rho$ is also an equitable partition of ${\cal G}$.

###  2.2 The STP of matrices

To use the matrix expression of logic, we need the following notation.

  * •

$A\subseteq X$: set $A$ is contained in set $X$.

  * •

${\cal M}_{n\times m}$: the set of $n\times m$ real matrices.

  * •

$\mathbb{R}^{n}$: the set of $n$-dimensional real column vectors.

  * •

$\delta_{n}^{i}$: the $i$th column of the identity matrix $I_{n}$.

  * •

$\Delta_{n}=\left\\{\delta_{n}^{i}\mid i=1,2,\ldots,n\right\\}$.

  * •

$\operatorname{Col}(A)$: the set of columns of $A$.

  * •

${\cal R}(A)$: the row space of $A$.

  * •

A matrix $L\in{\cal M}_{n\times m}$ is called a logical matrix if
$\operatorname{Col}(L)\subseteq\Delta_{n}$. Denote the set of $n\times m$
logical matrices by $\mathcal{L}_{n\times m}$.

  * •

If $A\in\mathcal{L}_{n\times m}$, $A$ can be expressed as
$A=\left[\delta_{n}^{i_{1}},\ldots,\delta_{n}^{i_{m}}\right]$; for brevity,
$A$ is denoted as $A=\delta_{n}\left[i_{1},\ldots,i_{m}\right]$.

  * •

Identify binary logical values in ${\cal D}:=\\{0,1\\}$ with vectors in
$\Delta_{2}:$ $1\sim\delta_{2}^{1}$ and $0\sim\delta_{2}^{2}$.

  * •

$[n;m]$: the set of integers $x$ with $n\leq x\leq m$.

######  Definition 2.6 ([8, 3]).

Let $M\in{\cal M}_{m\times n}$, $N\in{\cal M}_{p\times q}$, and
$t=\operatorname{lcm}\\{n,p\\}$ be the least common multiple of $n$ and $p$.
The semi-tensor product (STP) of $M$ and $N$, denoted by $M\ltimes N$, is
defined as

$\displaystyle\left(M\otimes I_{t/n}\right)\left(N\otimes
I_{t/p}\right)\in{\cal M}_{mt/n\times qt/p},$ (3)

where $\otimes$ is the Kronecker product.

Note that when $n=p$, $M\ltimes N=MN$. That is, the semi-tensor product is a
generalization of the conventional matrix product. Moreover, it preserves many
properties of the conventional matrix product, including associativity [9],
distributivity, reverse-order laws, etc. [3]. Hence we can omit the symbol
$\ltimes$. Throughout this paper the matrix product is assumed to be STP, and
the symbol $\ltimes$ is mostly omitted.

Necessary properties of STP are shown as follows.

######  Proposition 2.7 ([8]).

Let $X\in{\mathbb{R}}^{m}$ and $M$ a matrix. Then

$\displaystyle X\ltimes M=\left(I_{m}\otimes M\right)X.$ (4)

######  Definition 2.8 ([8]).

A matrix $W_{[m,n]}\in{\cal M}_{mn\times mn}$, defined by

$\displaystyle
W_{[m,n]}:=\left[I_{n}\otimes\delta_{m}^{1},I_{n}\otimes\delta_{m}^{2},\ldots,I_{n}\otimes\delta_{m}^{m},\right],$
(5)

is called the $(m,n)$-th dimensional swap matrix.

The basic function of the swap matrix is to “swap” two vectors. That is,

######  Proposition 2.9 ([8]).

Let $X\in{\mathbb{R}}^{m}$ and $Y\in{\mathbb{R}}^{n}$ be two columns. Then

$\displaystyle W_{[m,n]}\ltimes X\ltimes Y=Y\ltimes X.$ (6)

######  Definition 2.10 ([8]).

Let $A\in\mathcal{M}_{p\times n}$ and $B\in\mathcal{M}_{q\times n}$. The
Khatri-Rao Product of $A$ and $B$ is defined as follows:

$\displaystyle\begin{array}[]{ll}A*B\\!\\!\\!\\!&=\\!\\![\operatorname{Col}_{1}(A)\\!\\!\ltimes\\!\\!\operatorname{Col}_{1}(B),\ldots,\operatorname{Col}_{n}(A)\\!\\!\ltimes\\!\\!\operatorname{Col}_{n}(B)]\\\
\\!\\!\\!\\!&\\!\\!\\!\\!\in\mathcal{M}_{pq\times n}.\end{array}$ (9)

###  2.3 Invariant dual subspaces of BNs

A BN can be expressed as

$\displaystyle\begin{cases}x_{1}(t+1)=f_{1}(x_{1}(t),\ldots,x_{n}(t)),\\\
x_{2}(t+1)=f_{2}(x_{1}(t),\ldots,x_{n}(t)),\\\ \vdots\\\
x_{n}(t+1)=f_{n}(x_{1}(t),\ldots,x_{n}(t)),\\\ \end{cases}$ (10)

where $t=0,1,2,\ldots,$ $x_{i}(t)\in{\cal D}$, and each $f_{i}:{\cal
D}^{n}\rightarrow{\cal D}$ is a Boolean function, $i\in[1;n]$.

A BN has its matrix form under the vector form expressions of logical
variables, called the algebraic state space representation (ASSR) of the BN.

######  Proposition 2.11 ([10]).

  * $(i)$

For a Boolean function $f:{\cal D}^{n}\rightarrow{\cal D}$, there exists a
unique logical matrix $M_{f}\in{\cal L}_{2\times 2^{n}}$, called the structure
matrix of $f$, such that $f$ is expressed in the vector form

$\displaystyle f(x_{1},x_{2},\ldots,x_{n})=M_{f}\ltimes_{i=1}^{n}x_{i},$ (11)

where $x_{i}\in\Delta_{2}$, $i\in[1;n].$

  * $(ii)$

Let $M_{i}$ be the structure matrix of $f_{i}$, $i\in[1;n]$. Then
$(\ref{2.2.1})$ is expressed as

$\displaystyle x_{i}(t+1)=M_{i}\ltimes_{j=1}^{n}x_{j}(t),\quad i\in[1;n].$
(12)

  * $(iii)$

Setting $x(t)=\ltimes_{i=1}^{n}x_{i}(t)$, based on $(\ref{2.2.3})$, the ASSR
of $(\ref{2.2.1})$ is as follows:

$\displaystyle x(t+1)=Mx(t),$ (13)

where

$M=M_{1}*M_{2}*\cdots*M_{n}\in{\cal L}_{2^{n}\times 2^{n}}$

is called the transition matrix of $(\ref{2.2.1})$.

######  Definition 2.12 ([11]).

Consider $(\ref{2.2.1})$.

  * $(i)$

Its state space ${\cal X}$ is defined as the set of all Boolean functions of
$x_{1},x_{2},\ldots,x_{n}$, denoted by ${\cal
F}_{\ell}\\{x_{1},x_{2},\ldots,x_{n}\\}$. That is,

$\displaystyle{\cal X}={\cal F}_{\ell}\\{x_{1},x_{2},\ldots,x_{n}\\}.$ (14)

  * $(ii)$

For $z_{1},z_{2},\ldots,z_{r}\in{\cal X}$, the dual subspace generated by
$z_{1},z_{2},\ldots,z_{r}$ is defined by ${\cal Z}:={\cal
F}_{\ell}\\{z_{1},z_{2},\ldots,z_{r}\\}=\\{f(z_{1}(x_{1},\ldots,x_{n}),\ldots,z_{r}(x_{1},\ldots,x_{n}))|f:{\cal
D}^{r}\rightarrow{\cal D}\\}$. Set $z=\ltimes_{i=1}^{r}z_{i}$ and
$x=\ltimes_{i=1}^{n}x_{i}$. Then

$z=Gx,$

where $G\in{\cal L}_{2^{r}\times 2^{n}}$ is called the structure matrix of
${\cal Z}$.

######  Definition 2.13 ([4]).

Consider $(\ref{2.2.1})$ with its ASSR $(\ref{2.2.4})$. A dual subspace ${\cal
Z}$ is invariant if there exists a logical matrix $H\in{\cal L}_{2^{r}\times
2^{r}}$ such that

$\displaystyle GM=HG.$ (15)

######  Theorem 2.14 ([4]).

A dual subspace ${\cal Z}$ is invariant if and only if its dynamics can be
expressed as

$\displaystyle z(t+1)=Hz(t),$ (16)

where $H\in{\cal L}_{2^{r}\times 2^{r}}$.

The dynamics (16) is called the dual dynamics of BN (10) with respect to
${\cal Z}$ and $H$ is the dual transition matrix.

For BN (10) and a given dual subspace ${\cal Z}$, Cheng et al. [4] gave
Algorithm 1 to find the smallest invariant dual subspace $\overline{{\cal Z}}$
containing ${\cal Z}$. We call $\overline{{\cal Z}}$ the invariant dual
subspace generated by ${\cal Z}$.

Algorithm 1  An algorithm for constructing the smallest invariant dual
subspace containing a given dual subspace.

Input: $M\in\mathcal{L}_{2^{n}\times 2^{n}}$ (the structure matrix of a given
BN), $z=Gx$ (a given dual subspace) with $G\in\mathcal{L}_{2^{r}\times
2^{n}}$, $1\leq r\leq n$.
Output: the smallest invariant dual subspace $G_{1}x$ containing $z=Gx$ with
$G_{1}\in\mathcal{L}_{2^{r_{1}}\times 2^{n}}$ for some positive integer
$r_{1}$.

1:$k\leftarrow 0$

2:$G_{1}\leftarrow G$

3:$G_{2}\leftarrow GM$

4:while $\operatorname{rank}(G_{1})<\operatorname{rank}(G_{1}*G_{2})$ do

5: $k\leftarrow k+1$

6: $G_{1}\leftarrow G_{1}*G_{2}$

7: $G_{2}\leftarrow G_{2}M$

8:end while

9:return $G_{1}$, $k$.

######  Remark 2.15.

It is worth emphasizing that E. F. Moore first used the same idea as in
Algorithm 1 to compute equivalence classes of indistinguishable states in the
proof of Theorem 6 in his article as early as 1956 [12].

######  Lemma 2.16 ([4]).

Assume ${\cal Z}_{i}$, $i=1,2$, are invariant dual subspaces. That is, there
exist $H_{1}\in{\cal L}_{2^{p}\times 2^{p}}$ and $H_{2}\in{\cal
L}_{2^{q}\times 2^{q}}$ such that

$\displaystyle G_{1}M=H_{1}G_{1},\quad G_{2}M=H_{2}G_{2}.$ (17)

Then

${\cal Z}={\cal Z}_{1}\cup{\cal Z}_{2}={\cal
F}_{\ell}\\{z^{1}_{1},\ldots,z^{1}_{p},z^{2}_{1},\ldots,z^{2}_{q}\\}$

is also invariant. Moreover, the structure matrix of ${\cal Z}$, denoted by

$\displaystyle G=G_{1}*G_{2},$ (18)

satisfies

$\displaystyle GM=HG,$ (19)

where

$\displaystyle H=H_{1}\otimes H_{2}.$ (20)

##  3 A graph representation of a BN and its invariant dual subspaces

It is well known that a BN can be uniquely represented by its STG. In other
words, the STG of a BN contains all its dynamic information. In this section
we investigate the invariant dual subspaces of a BN from a graphical
perspective. We will prove that the invariant dual subspaces of a BN
correspond to an equitable partition of its STG. Based on it, we proceed to
analyze the structural properties of invariant dual subspaces generated by
different Boolean functions, and design algorithms for constructing these
subspaces.

###  3.1 Invariant dual subspaces and equitable partitions

For BN (10), its state set $\Delta_{2^{n}}$ is the vertex set of its STG
${\cal G}$ and
$E:=\left\\{(\delta_{2^{n}}^{i},\delta_{2^{n}}^{j})\mid\delta_{2^{n}}^{j}=M\delta_{2^{n}}^{i}\right\\}$
is the edge set of ${\cal G}$. The state transition matrix $M$ of (10) is the
adjacency matrix of ${\cal G}$. For a set $\\{z_{1},\ldots,z_{r}\\}$ of
Boolean functions, we have $z=\ltimes_{i=1}^{r}z_{i}=Gx$ and $G\in{\cal
L}_{2^{r}\times 2^{n}}$. Without loss of generality we always suppose that $G$
is of full row rank. We define a partition
${\pi_{G}}:=\\{\\{x|Gx=\delta_{2^{r}}^{i}\\}|i\in[1;2^{r}]\\}$ according to
$G$, where $G^{T}$ is exactly the characteristic matrix of ${\pi_{G}}$. We
conclude that ${\pi_{G}}$ is only determined by ${\cal R}(G)$. In other words,
${\pi_{G}}={\pi_{G^{\prime}}}$ if and only if ${\cal R}(G)={\cal
R}({G^{\prime}})$.

######  Definition 3.1.

Let $z_{1},\ldots,z_{r}:{\cal D}^{r}\rightarrow{\cal D}$ be Boolean functions.
For a dual subspace ${\cal Z}={\cal F}_{\ell}\\{z_{1},\ldots,z_{r}\\}$, we
define a partition ${\cal P}({\cal Z})$ where two states $x,x^{\prime}\in{\cal
D}^{n}$ are in the same cell of ${\cal P}({\cal Z})$ if and only if
$f(x)=f(x^{\prime})$ for any Boolean function $f\in{\cal Z}$.

For example, if ${\cal Z}={\cal X}$, then ${\cal P}({\cal
Z})=\\{\\{\delta_{2^{n}}^{1}\\},\\{\delta_{2^{n}}^{2}\\},\ldots,\\{\delta_{2^{n}}^{2^{n}}\\}\\}$.

######  Lemma 3.2.

For a dual subspace ${\cal Z}={\cal F}_{\ell}\\{z_{1},\ldots,z_{r}\\}$ with
structure matrix $G\in{\cal L}_{2^{r}\times 2^{n}}$, ${\cal P}({\cal
Z})={\pi_{G}}$. Moreover, ${\cal P}:{\cal X}^{*}\rightarrow\Pi$ is a
bijection, where ${\cal X}^{*}$ is the set of dual subspaces over
$\Delta_{2^{n}}$ and $\Pi$ is the set of all partitions of $\Delta_{2^{n}}$.

###### Proof.

For any Boolean function $f\in{\cal Z}$, it is a Boolean function over
$\\{z_{1},\ldots,z_{r}\\}$. There exists a structure matrix $F\in{\cal
L}_{2\times 2^{r}}$ over $\\{z_{1},\ldots,z_{r}\\}$. Moreover $FG$ is the
structure matrix of
$f(z_{1}(x_{1},\ldots,x_{n}),\ldots,z_{r}(x_{1},\ldots,x_{n}))$ over
$\Delta_{2^{n}}$. According to definition of ${\cal P}({\cal Z})$, states
$x,x^{\prime}\in\Delta_{2^{n}}$ are in the same cell of ${\cal P}({\cal Z})$
if and only if $FGx=FGx^{\prime}$ for any $F\in{\cal L}_{2\times 2^{r}}$.

For any $x,x^{\prime}\in\Delta_{2^{n}}$, they are in the same cell of
${\pi_{G}}$ if and only if $Gx=Gx^{\prime}$. Then $FGx=FGx^{\prime}$ for any
$F\in{\cal L}_{2\times 2^{r}}$, that is, they are in the same cell of ${\cal
P}({\cal Z})$. It follows that ${\cal P}({\cal Z})\preceq{\pi_{G}}$.

On the other hand, suppose that $x,x^{\prime}\in\Delta_{2^{n}}$ satisfy
$FGx=FGx^{\prime}$ for any $F\in{\cal L}_{2\times 2^{r}}$. Then the equation
holds for every
$F_{i}=\delta_{2}[\underbrace{2,\ldots,2}_{i-1},1,2,\ldots,2]$,
$i\in[1;2^{n}]$. It follows $Gx=Gx^{\prime}$. Consequently
${\pi_{G}}\preceq{\cal P}({\cal Z})$. Thus ${\cal P}({\cal Z})={\pi_{G}}$.

Before proceeding further, we remark that a dual subspace is also only
determined by the row space of its structure matrix. If $G\in{\cal
L}_{2^{r}\times 2^{n}}$ and $G^{\prime}\in{\cal L}_{2^{l}\times 2^{n}}$ have
the same row space, then $\\{FG\in{\cal L}_{2\times 2^{n}}|F\in{\cal
L}_{2\times 2^{r}}\\}=\\{FG^{\prime}\in{\cal L}_{2\times 2^{n}}|F\in{\cal
L}_{2\times 2^{l}}\\}$. That is, dual subspaces with $G$ and $G^{\prime}$ as
structure matrices are equal. Note that here $G$ and $G^{\prime}$ are not
necessarily of full row rank.

It remains to show that ${\cal P}$ is a bijection. (1) For any partition
$\pi\in\Pi$ with characteristic matrix $G^{T}$, we construct a dual subspace
whose structure matrix has row space ${\cal R}(G)$. (2) If two dual subspaces
${\cal Z}_{1},{\cal Z}_{2}$ satisfying ${\cal P}({\cal Z}_{1})={\cal P}({\cal
Z}_{2})$, then the row spaces of their structure matrices are same. Thus
${\cal Z}_{1}={\cal Z}_{2}$. The proof is completed. ∎

######  Lemma 3.3.

Given ${\cal Z}_{1},{\cal Z}_{2}\in{\cal X}^{*}$, ${\cal P}({\cal
Z}_{1})\preceq{\cal P}({\cal Z}_{2})$ if and only if ${\cal
Z}_{1}\subseteq{\cal Z}_{2}$.

###### Proof.

Suppose that $G_{1}$ and $G_{2}$ are the structure matrices of ${\cal Z}_{1}$
and ${\cal Z}_{2}$, respectively. It can easy to see that
${\pi_{G_{1}}}\preceq{\pi_{G_{2}}}$ if and only if ${\cal
R}(G_{1})\subseteq{\cal R}(G_{2})$. Moreover, ${\cal Z}_{1}\subseteq{\cal
Z}_{2}$ if and only if ${\cal R}(G_{1})\subseteq{\cal R}(G_{2})$. Thus, ${\cal
P}({\cal Z}_{1})\preceq{\cal P}({\cal Z}_{2})$ if and only if ${\cal
Z}_{1}\subseteq{\cal Z}_{2}$. ∎

Since ${\cal P}$ is a bijection, ${\cal P}^{-1}$ exists. From Lemma 3.3,
${\cal P}$ and ${\cal P}^{-1}$ are order-preserving. Thus two lattices $({\cal
X}^{*},\subseteq)$ and $(\Pi,\preceq)$ are isomorphic according to [3, Theorem
14.2]. It is straightforward to show the following proposition.

######  Proposition 3.4.

Consider ${\cal Z}_{1},{\cal Z}_{2}\in{\cal X}^{*}$.

  * $(i)$

${\cal P}({\cal Z}_{1}\cap{\cal Z}_{2})={\cal P}({\cal Z}_{1})\sqcap{\cal
P}({\cal Z}_{2})$.

  * $(ii)$

${\cal P}({\cal Z}_{1}\cup{\cal Z}_{2})={\cal P}({\cal Z}_{1})\sqcup{\cal
P}({\cal Z}_{2})$.

######  Remark 3.5.

From Proposition 3.4, we obtain the following properties.

  * $(i)$

Since ${\cal Z}\subseteq{\cal X}$ is always true, we have ${\cal P}({\cal
Z})\preceq{\cal P}({\cal X})$. In other words, ${\cal P}({\cal X})$ is the
finest partition of ${\cal G}$. Moreover ${\cal P}({\cal
X})=\\{\\{\delta_{2^{n}}^{1}\\},\\{\delta_{2^{n}}^{2}\\},\ldots,\\{\delta_{2^{n}}^{2^{n}}\\}\\}$.

  * $(ii)$

For the dual subspace ${\cal Z}={\cal F}_{\ell}\\{z\\}$ where $z\in{\cal X}$,
${\cal P}({\cal Z})$ is a 2-partition with cells
$\\{C,\Delta_{2^{n}}\backslash C\\}$, where
$C:=\\{x\in\Delta_{2^{n}}~{}|~{}z(x)=\delta_{2}^{1}\\}$. In this case we
express ${\cal P}({\cal Z})$ as ${\cal P}(z)$ for simplicity of presentation.

  * $(iii)$

Given ${\cal Z}$, ${\cal P}(z)\preceq{\cal P}({\cal Z})$ for all $z\in{\cal
Z}$.

  * $(iv)$

If ${\cal Z}={\cal F}_{\ell}\\{z_{1},z_{2},\ldots,z_{r}\\}$, then ${\cal
P}({\cal Z})={{\cal P}(z_{1})}\sqcup{{\cal P}(z_{2})}\sqcup\cdots\sqcup{{\cal
P}(z_{r})}$.

######  Theorem 3.6.

For BN $(\ref{2.2.1})$, a dual subspace ${\cal Z}$ is invariant if and only if
${\cal P}({\cal Z})$ is equitable in ${\cal G}$. Moreover, the dual transition
matrix $H$ of ${\cal Z}$ is exactly the adjacency matrix of ${\cal G}/{\cal
P}({\cal Z})$.

###### Proof.

Suppose that a dual subspace ${\cal Z}$ is invariant. By Definition 2.13,
there exists a logical matrix $H$ such that $GM=HG$. Since $G^{T}$ is the
characteristic matrix of ${\cal P}({\cal Z})$, ${\cal P}({\cal Z})$ is
equitable in ${\cal G}$ according to Lemma 2.2. The inverse implications are
also true.

From the proof of the first part of this theorem, it is trivial to conclude
that $H$ is also the adjacency matrix of the quotient digraph ${\cal G}/{\cal
P}({\cal Z})$. ∎

For any dual subspace ${\cal Z}$, recall that $\overline{{\cal Z}}$ is the
smallest invariant dual subspace containing ${\cal Z}$. Thus for any invariant
dual subspace ${\cal Z}_{1}$ containing ${\cal Z}$, $\overline{{\cal
Z}}\subseteq{\cal Z}_{1}$. By Lemma 3.4, ${\cal P}(\overline{{\cal
Z}})\preceq{\cal P}({\cal Z}_{1})$. And by Theorem 3.6, ${\cal P}({\cal
Z}_{1})$ and ${\cal P}(\overline{{\cal Z}})$ are equitable. Therefore, ${\cal
P}(\overline{{\cal Z}})$ is the coarsest equitable partition finer than ${\cal
P}({\cal Z})$.

######  Example 3.7.

Consider the following BN:

$\displaystyle\\!\\!\\!\\!\begin{cases}x_{1}(t+1)\\!\\!=&\\!\\!\\!\\!(x_{1}(t)\wedge
x_{2}(t)\wedge\neg x_{4}(t))\\\ &\vee(\neg x_{1}(t)\wedge x_{2}(t)),\\\
x_{2}(t+1)\\!\\!=&\\!\\!\\!\\!x_{2}(t)\vee(x_{3}(t)\leftrightarrow
x_{4}(t)),\\\ x_{3}(t+1)\\!\\!=&\\!\\!\\!\\!(x_{1}(t)\wedge\neg
x_{4}(t))\\!\\!\vee\\!\\!(\neg x_{1}(t)\wedge x_{2}(t))\\\ &\vee(\neg
x_{1}(t)\wedge\neg x_{2}(t)\wedge x_{4}(t)),\\\
x_{4}(t+1)\\!\\!=&\\!\\!\\!\\!x_{1}(t)\wedge\neg x_{2}(t)\wedge
x_{4}(t).\end{cases}$ (21)

Its ASSR is calculated as

$\displaystyle x(t+1)=Mx(t),$ (22)

where

$M=\delta_{16}[11,\\!1,\\!11,\\!1,\\!11,\\!13,\\!15,\\!9,\\!1,\\!2,\\!1,\\!2,\\!9,\\!15,\\!13,\\!11].$

Given an invariant dual subspace ${\cal Z}$ whose structure matrix is

$G=\delta_{2}[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1],$

its dual transition matrix is $H=\delta_{2}[2,2]$ satisfying $GM=HG$. Its dual
dynamics is

$\displaystyle z(t+1)=Hz(t).$ (23)

For the partition ${\cal P}({\cal Z})=\\{C_{1},C_{2}\\}$ where
$C_{1}=\\{x|Gx=\delta_{2}^{1}\\}=\\{\delta_{16}^{16}\\}$ and
$C_{2}=\Delta_{16}\backslash C_{1}$, each vertex $(\delta_{16}^{16})$ in
$C_{1}$ has single in-neighbor $(\delta_{16}^{11})$ in $C_{2}$ and each vertex
in $C_{2}$ has single in-neighbor in $C_{2}$. Thus ${\cal P}({\cal Z})$ is an
equitable partition of the STG ${\cal G}$ of BN $(\ref{3.1.8})$. And ${\cal
G}$ and the quotient digraph ${\cal G}/{\cal P}({\cal Z})$ are shown in Figure
2 $(a)$ and $(b)$. The characteristic matrix of ${\cal P}({\cal Z})$ is
exactly $G^{T}$. Lemma 2.2 illustrates the fact that $H$ is the adjacency
matrix of the quotient digraph ${\cal G}/{\cal P}({\cal Z})$.

$1$$2$$3$$4$$5$$6$$7$$8$$9$${10}$${11}$${12}$${13}$${14}$${15}$${16}$ (a) STG
${\cal G}$ of BN (22), whose adjacency matrix is $M$. In ${\cal G}$ each
vertex $i$ represents state $\delta_{16}^{i}$.

$C_{1}$$C_{2}$ (b) STG ${\cal G}/{\cal P}({\cal Z})$ of BN (23) with adjacency
matrix is $H$, where $C_{1}=\\{\delta_{16}^{16}\\}$ and
$C_{2}=\Delta_{16}\backslash C_{1}$.

Figure 2: STG ${\cal G}$ of BN (22) and its quotient digraph ${\cal G}/{\cal
P}({\cal Z})$. ${\cal G}/{\cal P}({\cal Z})$ is also the STG of BN (23).

###  3.2 Structural properties of invariant dual subspaces

Different smallest invariant dual subspaces generated by different dual
subspaces may have different properties. With the help of the correspondence
between invariant dual subspaces and equitable partitions obtained in the
previous section, in this section we reveal relationships between dual
subspaces and their generated smallest invariant dual subspaces. Without loss
of generality, we divide the STG of a BN (8) into four cases: (1) a path with
a single loop; (2) a tree with a single loop; (3) a single cycle; (4) a
connected graph with a single cycle. With respect to each of the four cases,
we characterize the smallest invariant dual subspace generated by a dual
subspace of BN (8) via the notion of equitable partition.

Since there are only finitely many nodes in a BN, a trajectory eventually
converges to a cycle, where particularly a fixed point is a cycle of length 1
[3].

In graph theory, a connected acyclic undirected graph is called a tree. On the
other hand, an undirected graph with $n$ vertices is a tree if and only if it
is connected and has exactly $n-1$ edges [5]. A rooted tree $T(v_{r})$ is a
tree $T$ with a specified vertex $v_{r}$, called the root of $T$. An
orientation of a rooted tree in which every vertex but the root has out-degree
one is called a branching. We refer to a rooted branching with root $v_{r}$ as
$v_{r}$-branching. Observe, also, that its root is reachable from any other
vertex of a branching via a unique directed path. (We point out that the
directions of all edges of a rooted branching defined here is opposite to that
of the rooted branching as usual. That is, every vertex but the root has in-
degree one in a rooted branching generally). A branching in a digraph is a
spanning branching if it includes all vertices of the digraph.

######  Lemma 3.8.

For any given BN, each component of its STG ${\cal G}$ is unicyclic and
contains at least one spanning branching.

###### Proof.

Without loss of generality, we assume ${\cal G}$ is connected. Since each
vertex has out-degree 1, ${\cal G}$ has the same number of vertices and edges.
By this reason, the underlying graph of ${\cal G}$ contains exactly one
undirected cycle ${\cal C}$.

Suppose that $e$ is an edge in ${\cal C}$ and $v$ is the tail of $e$.
According to that ${\cal G}$ contains a directed cycle such that every
trajectory will eventually converge to and ${\cal C}$ is the only cycle in
${\cal G}$, we will prove ${\cal G}\setminus\\{e\\}$ is a spanning branching
of ${\cal G}$. 1) If the length of ${\cal C}$ is 1, that is, $v$ is the only
vertex in ${\cal C}$, each state in ${\cal G}$ converges to $v$ without
passing through edge $e$. 2) If the length is larger than 1, a state not in
${\cal C}$ reach some state in ${\cal C}$ (otherwise, ${\cal G}$ is not
connected), and all states in the cycle can reach $v$ without passing through
edge $e$. Therefore, all states in ${\cal G}\setminus\\{e\\}$ can reach $v$ by
a unique directed path. And ${\cal G}\setminus\\{e\\}$ is a spanning branching
of ${\cal G}$ with root $v$ irrespective of the length of ${\cal C}$. ∎

Without loss of generality, we focus on connected ${\cal G}$ in this paper.
The following two subsections provide structural properties according to the
cases that the cycle has length 1 or greater than 1. In the following a cycle
on a single vertex is called a loop. As mentioned before, for any equitable
partition $\pi$ of ${\cal G}$, the quotient digraph ${\cal G}/\pi$ is the STG
of its dual dynamics. Thus ${\cal G}/\pi$ is also a unicyclic digraph by Lemma
3.8.

Before proceeding further, let us introduce an operation of shrinking. Let
${\cal G}$ be a digraph and let $C$ be a proper subset of $V({\cal G})$. To
shrink $C$ is to merge the vertices of $C$ into a single vertex and then add a
loop to the new vertex if there exists an edge between these vertices. We
denote the resulting digraph by ${\cal G}/C$ and new vertex as $C$. In ${\cal
G}/C$ the edges between the new vertex $C$ and vertices in $V({\cal
G})\setminus C$ are inherited from the edges of ${\cal G}$. Note that in
general ${\cal G}/C$ might have multiple edges. We replace a set of multiple
edges by a single edge of weight $k$, where $k$ is the sum of the weights of
the multiple edges. The operation of shrinking is illustrated in Figure 3.

We can extend this shrinking operation to partitions of $V$, as follows. Given
any partition $\pi=\\{C_{1},\ldots,C_{k}\\}$, we shrink $\pi$ by shrinking
each cell $C_{i}$, $i\in[1;k]$ and we denote the resulting $k$-vertex digraph
by ${\cal G}/\pi$. Note that if $\pi$ is equitable, then ${\cal G}/\pi$ is the
quotient digraph of $\pi$ as defined in 2.1.2.

More generally, to shrink a subset $C_{1}\subseteq C$ in $C$ is to merge the
elements in $C_{1}$ into one element. We denote the resulting set by
$C/C_{1}$.

In the following, we discuss the simple case that the dual subspace ${\cal Z}$
is generated by a single Boolean function. As mentioned earlier, the dual
subspace ${\cal Z}$ generated by Boolean function $z=G_{0}x$ with
$G_{0}\in{\cal L}_{2\times 2^{n}}$ corresponds to a 2-partition ${\cal
P}({\cal Z})=\\{C^{0},\Delta_{2^{n}}\setminus C^{0}\\}$, where the states in
$C^{0}$ produce the value $\delta_{2}^{1}$, and the states in
$\Delta_{2^{n}}\setminus C^{0}$ produce the value $\delta_{2}^{2}$. For
convenience of expression, we use ${\cal Z}_{C^{0}}$ to denote the subspace
satisfying the above condition. Recall that $\overline{{\cal Z}}_{C^{0}}$ is
the smallest invariant dual subspace generated by ${\cal Z}_{C^{0}}$. Then
${\cal P}(\overline{{\cal Z}}_{C^{0}})$ is equitable by Theorem 3.6. We call
${\cal P}(\overline{{\cal Z}}_{C^{0}})$ the equitable partition generated by
set $C^{0}$.

In Algorithm 1 the structure matrix of $\overline{{\cal Z}}$ is
$G_{0}*G_{1}*\cdots*G_{k}$, where $G_{i}=G_{0}M^{i}$, $i\in[1;k]$. Then two
states produce different values in $G_{0}*G_{1}*\cdots*G_{k}$ if and only if
they produce different values in some $z_{i}(x)=G_{i}x$, $i\in[0;k]$. Without
loss of generality, we suppose $G_{0}\in{\cal L}_{2\times 2^{n}}$ in the
sequel. Let $C^{i}$, $i\in[0;k-1]$ be the state subset that produce
$\delta_{2}^{1}$ in $z_{i}(x)=G_{i}x$. Since $G_{i+1}=G_{i}M$,

$\displaystyle\operatorname{Col}_{k}(G_{i+1})=\left\\{\begin{array}[]{l}\delta_{2}^{1},\text{
if }~{}M\delta_{2^{n}}^{k}\in C^{i},\\\ \delta_{2}^{2},\text{ otherwise.
}\end{array}\right.$ (26)

That is, the out-neighbors of $C^{i+1}$ are in $C^{i}$, $i\in[0;k-1]$.

######  Lemma 3.9.

  * $(i)$

Consider the STG ${\cal G}$ of a given BN. For any given vertex set
$C^{0}\subseteq V({\cal G})$, if $C_{1}=N_{in}(C^{0},\infty)$ is nonempty,
then it is a cell of ${\cal P}(\overline{{\cal Z}}_{C^{0}})$.

  * $(ii)$

If $C_{2}=\\{v_{1},\ldots,v_{r}\\}$ is a cell of ${\cal P}(\overline{{\cal
Z}}_{C^{0}})$, then ${\cal P}({\cal Z}_{C_{2}})\preceq{\cal P}(\overline{{\cal
Z}}_{C^{0}})\preceq\\{C_{2},\\{v_{r+1}\\},\ldots,\\{v_{2^{n}}\\}\\}:=\Delta_{2^{n}}/C_{2}$.

  * $(iii)$

If ${\cal P}({\cal Z}_{C_{2}})\preceq{\cal P}(\overline{{\cal Z}}_{C^{0}})$,
then ${\cal P}(\overline{{\cal Z}}_{C_{2}})\preceq{\cal P}(\overline{{\cal
Z}}_{C^{0}})$. Moreover, if ${\cal P}({\cal Z}_{C_{2}})\preceq{\cal P}({\cal
Z}_{C^{0}})$, then ${\cal P}(\overline{{\cal Z}}_{C_{2}})\preceq{\cal
P}(\overline{{\cal Z}}_{C^{0}})$.

  * $(iv)$

If $C_{2}\subseteq C^{0}$ and $\\{C_{2},C^{0}\setminus
C_{2},\Delta_{2^{n}}\setminus C^{0}\\}\preceq{\cal P}(\overline{{\cal
Z}}_{C^{0}})$, then ${\cal P}(\overline{{\cal Z}}_{C^{0}})={\cal
P}(\overline{{\cal Z}}_{C_{2}})\sqcup{\cal P}(\overline{{\cal
Z}}_{C^{0}\setminus C_{2}})$.

###### Proof.

  * $(i)$

Suppose that $G_{0}\in{\cal L}_{2\times 2^{n}}$ is the structure matrix of
${\cal Z}_{C^{0}}$. Recall from Algorithm 1 that the structure matrix of
$\overline{{\cal Z}}_{C^{0}}$ can be $G_{0}*G_{1}*\cdots*G_{k}$, where
$G_{i}=G_{0}M^{i}$, $i\in[1;k]$. Since only vertices in $C_{1}$ always produce
$\delta_{2}^{2}$ in $z_{i}(x)=G_{i}x$ for all $i\in[0;k]$, $C_{1}$ is a cell
of ${\cal P}(\overline{{\cal Z}}_{C^{0}})$.

  * $(ii)$

The proof is straightforward.

  * $(iii)$

As illustrated above, ${\cal P}(\overline{{\cal Z}}_{C_{2}})$ is the coarsest
equitable partition among the ones that are finer than ${\cal P}({\cal
Z}_{C_{2}})$. Since ${\cal P}(\overline{{\cal Z}}_{C^{0}})$ is equitable and
${\cal P}({\cal Z}_{C_{2}})\preceq{\cal P}(\overline{{\cal Z}}_{C^{0}})$,
${\cal P}(\overline{{\cal Z}}_{C_{2}})\preceq{\cal P}(\overline{{\cal
Z}}_{C^{0}})$.

Moreover, if ${\cal P}({\cal Z}_{C_{2}})\preceq{\cal P}({\cal Z}_{C^{0}})$,
then ${\cal P}({\cal Z}_{C_{2}})\preceq{\cal P}(\overline{{\cal Z}}_{C^{0}})$.
We get ${\cal P}(\overline{{\cal Z}}_{C_{2}})\preceq{\cal P}(\overline{{\cal
Z}}_{C^{0}})$.

  * $(iv)$

If $C_{2}\subseteq C^{0}$ and $\\{C_{2},C^{0}\setminus
C_{2},\Delta_{2^{n}}\setminus C^{0}\\}\preceq{\cal P}(\overline{{\cal
Z}}_{C^{0}})$, then ${\cal P}({\cal Z}_{C_{2}})\preceq{\cal P}(\overline{{\cal
Z}}_{C^{0}})$ and ${\cal P}({\cal Z}_{C^{0}\setminus C_{2}})\preceq{\cal
P}(\overline{{\cal Z}}_{C^{0}})$. Moreover ${\cal P}(\overline{\cal
Z}_{C_{2}})\preceq{\cal P}(\overline{{\cal Z}}_{C^{0}})$, ${\cal
P}(\overline{\cal Z}_{C^{0}\setminus C_{2}})\preceq{\cal P}(\overline{{\cal
Z}}_{C^{0}})$ and ${\cal P}(\overline{\cal Z}_{C_{2}})\sqcup{\cal
P}(\overline{\cal Z}_{C^{0}\setminus C_{2}})\preceq{\cal P}(\overline{{\cal
Z}}_{C^{0}})$.

On the other hand, ${\cal P}({\cal Z}_{C^{0}})\preceq{\cal P}({\cal
Z}_{C_{2}})\sqcup{\cal P}({\cal Z}_{C^{0}\setminus C_{2}})\preceq{\cal
P}(\overline{\cal Z}_{C_{2}})\sqcup{\cal P}(\overline{\cal Z}_{C^{0}\setminus
C_{2}})$. According to Lemma 2.16, dual subspace $\overline{\cal
Z}_{C_{2}}\cup\overline{\cal Z}_{C^{0}\setminus C_{2}}$ is invariant. Thus
${\cal P}(\overline{\cal Z}_{C_{2}}\cup\overline{\cal Z}_{C^{0}\setminus
C_{2}})={\cal P}(\overline{\cal Z}_{C_{2}})\sqcup{\cal P}(\overline{\cal
Z}_{C^{0}\setminus C_{2}})$ is equitable. We get ${\cal P}(\overline{{\cal
Z}}_{C^{0}})\preceq{\cal P}(\overline{\cal Z}_{C_{2}})\sqcup{\cal
P}(\overline{\cal Z}_{C^{0}\setminus C_{2}})$. In conclusion, ${\cal
P}(\overline{{\cal Z}}_{C^{0}})={\cal P}(\overline{\cal Z}_{C_{2}})\sqcup{\cal
P}(\overline{\cal Z}_{C^{0}\setminus C_{2}})$.

∎

####  3.2.1 BNs with loops

In this subsection, we discuss BNs with connected STGs which contain loops. We
start from STGs with paths as spanning branchings. Next we analyze the more
general STGs with loops. The obtained results are given in the form of
algorithms.

In any connected STG ${\cal G}$ with a loop $e$, each trajectory will
eventually converge to $e$. We denote the vertex in the loop $e$ by $v_{1}$.
Since ${\cal G}\setminus\\{e\\}$ is the unique spanning branching of ${\cal
G}$ and every vertex reaches $v_{1}$, we call $v_{1}$ the root of ${\cal G}$.

######  Lemma 3.10.

Consider BN $(\ref{2.2.1})$. Suppose that its STG ${\cal G}$ is connected and
has a loop $e$, where $v_{1}$ is the root. Given a dual subspace ${\cal
Z}_{C^{0}}$ where $v_{1}\in C^{0}$, if there are in-neighbors of $v_{1}$ in
$C^{0}$, then $v_{1}$ and these in-neighbors are in the same cell of ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$. Otherwise, $v_{1}$ forms a singleton cell.

###### Proof.

Suppose that $G_{0}\in{\cal L}_{2\times 2^{n}}$ is the structure matrix of
${\cal Z}_{C^{0}}$. Like in the proof of Lemma 3.9, let the structure matrix
of $\overline{{\cal Z}}_{C^{0}}$ be $G_{0}*G_{1}*\cdots*G_{k}$, where
$G_{i}=G_{0}M^{i}$, $i\in[1;k]$. Since $v_{1}$ produces $\delta_{2}^{1}$ in
$z_{0}(x)=G_{0}x$, $v_{1}$ always produces value $\delta_{2}^{1}$ in
$z_{i}(x)=G_{i}x$, $i\in[0;k]$ according to (26). By the same reason if
$v_{2}\in N_{in}(v_{1})\cap C^{0}$, $v_{2}$ always produces value
$\delta_{2}^{1}$ in $z_{i}(x)=G_{i}x$, $i\in[0;k]$. That is, $v_{2}$ and
$v_{1}$ are in the same cell of ${\cal P}(\overline{{\cal Z}}_{C^{0}})$. Then
$v_{1}$ and all states in $N_{in}(v_{1})\cap C^{0}$ are in the same cell of
${\cal P}(\overline{{\cal Z}}_{C^{0}})$.

If $N_{in}(v_{1})\cap C^{0}=\emptyset$, we will prove $v_{1}$ is the only
vertex which always produces value $\delta_{2}^{1}$ in $z_{i}(x)=G_{i}x$,
$i\in[0;k]$, and $v_{1}$ forms a singleton cell. Suppose that $v_{i}\in
C^{0}\setminus v_{1}$ always produces value $\delta_{2}^{1}$ in
$z_{i}(x)=G_{i}x$, $i\in[0;k]$. As illustrated in (26), the out-neighbors of
$C^{i+1}$ are in $C^{i}$. We get that the state in $N_{out}(v_{i},1)$ always
produces $\delta_{2}^{1}$ in $z_{i}(x)=G_{i}x$, $i\in[0;k]$. That is, the out-
neighbor of $v_{i}$ is a subset of $C^{0}$ and always produces
$\delta_{2}^{1}$ in $z_{i}(x)=G_{i}x$, $i\in[0;k]$. By repeating this
procedure we get that all the vertices in the path from $v_{i}$ to $v_{1}$ are
contained in $C_{0}$, which is contradicted to the assumption that $C^{0}$
contains no in-neighbor of $v_{1}$.

In conclusion, if $N_{in}(v_{1})\cap C^{0}\neq\emptyset$, then
$(\\{v_{1}\\}\cup N_{in}(v_{1}))\cap C^{0}$ is a subset of one cell of ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$. Otherwise, $\\{v_{1}\\}\in{\cal
P}(\overline{{\cal Z}}_{C^{0}})$. ∎

Case 1. STG ${\cal G}$ has a path as its spanning branching

Since ${\cal G}$ has a path as its spanning branching, we write ${\cal G}$ as
$v_{2^{n}}v_{2^{n}-1}\cdots v_{1}$, where $v_{1}$ is the root. Recall that the
root is the vertex with out-degree 0 in the current paper.

We first consider $|C^{0}|=1$. (1) If $C^{0}=\\{v_{1}\\}$, then we can get
from (26) that $C^{i+1}=\\{v_{i+2}\\}\cup C^{i}$ for $i\in[0;k-1]$. Each
vertex forms a singleton cell of ${\cal P}(\overline{{\cal Z}}_{C^{0}})$. Thus
${\cal P}(\overline{{\cal Z}}_{C^{0}})$ is trivial. (2) If
$C^{0}=\\{v_{r}\\}$, $r\neq 1$, then $C_{1}=N_{in}(C^{0},\infty)$ is a cell of
${\cal P}(\overline{{\cal Z}}_{C^{0}})$ and ${\cal P}({\cal
Z}_{C_{1}})\preceq{\cal P}(\overline{{\cal Z}}_{C^{0}})$ according to Lemma
3.9. It follows that ${\cal P}(\overline{{\cal Z}}_{C_{1}})\preceq{\cal
P}(\overline{{\cal Z}}_{C^{0}})$. Since the equitable partition generated by
the root $C_{1}$ of ${\cal G}/C_{1}$ is trivial, that is, ${\cal
P}(\overline{{\cal
Z}}_{C_{1}})=\\{C_{1},\\{v_{r}\\},\ldots,\\{v_{2^{n}}\\}\\}$, we get ${\cal
P}(\overline{{\cal
Z}}_{C^{0}})=\\{C_{1},\\{v_{r}\\},\ldots,\\{v_{2^{n}}\\}\\}$.

Assume, inductively, that ${\cal P}(\overline{\cal Z}_{C^{0}})$ is known when
$|C^{0}|<m$, $2\leq m\leq 2^{n-1}$. For the case $|C^{0}|=m$, (1) if
$v_{1},v_{2}\in C^{0}$, then they are in the same cell of ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$ according to Lemma 3.10. We can get ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$ from ${\cal P}(\overline{{\cal
Z}}_{C^{0}/C})$ in quotient digraph ${\cal G}/C$, where $C=\\{v_{1},v_{2}\\}$.
(2) If $v_{1}\in C^{0}$ but $v_{2}\notin C^{0}$, then $v_{1}$ forms a
singleton cell. Then we get ${\cal P}({\cal Z}_{\\{v_{1}\\}})\preceq{\cal
P}(\overline{{\cal Z}}_{C^{0}})$ and ${\cal P}(\overline{{\cal
Z}}_{\\{v_{1}\\}})\preceq{\cal P}(\overline{{\cal Z}}_{C^{0}})$ from Lemma
3.9. Since ${\cal P}(\overline{{\cal Z}}_{\\{v_{1}\\}})$ is trivial, ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$ is trivial. (3) If $v_{1}\notin C^{0}$, then
$C_{1}=N_{in}(C^{0},\infty)$ is nonempty and a cell of ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$. Because ${\cal P}(\overline{\cal
Z}_{C_{1}})$ is a trivial partition for vertex set of ${\cal G}/{C_{1}}$, we
get ${\cal P}(\overline{{\cal Z}}_{C^{0}})={\cal P}(\overline{\cal
Z}_{C_{1}})$.

Case 2. STG ${\cal G}$ has a general spanning branching

Case 2.1. First consider the case where $C^{0}$ contains a single vertex. (1)
If $C^{0}=\\{v_{1}\\}$, then $C^{i+1}=N_{in}(v_{1},i+1)\cup C^{i}$ in (26).
Thus ${\cal P}(\overline{{\cal
Z}}_{C^{0}})=\\{\\{v_{1}\\},N_{in}(v_{1},1),\ldots,N_{in}(v_{1},\operatorname{dist}_{in}(v_{1}))\\}$
and the quotient digraph is a path. (2) If $C^{0}=\\{v_{r}\\}$ and $r\neq 1$,
then $C_{1}=N_{in}(C^{0},\infty)$ is a cell of ${\cal P}(\overline{{\cal
Z}}_{C^{0}})$ and a root of ${\cal G}/{C_{1}}$. Moreover, $v_{r}$ is the only
vertex adjacent to $C_{1}$. Then ${\cal P}(\overline{{\cal
Z}}_{C_{1}})=\\{C_{1},C^{0},N_{in}(v_{r},1),\ldots,N_{in}(v_{r},\operatorname{dist}_{in}(v_{r}))\\}$.
It follows that ${\cal P}({\cal Z}_{C^{0}})\preceq{\cal P}(\overline{{\cal
Z}}_{C_{1}})\preceq{\cal P}(\overline{{\cal Z}}_{C^{0}})$. It is easy to get
${\cal P}(\overline{{\cal Z}}_{C^{0}})={\cal P}(\overline{{\cal Z}}_{C_{1}})$.

Case 2.2. Assume, inductively, that ${\cal P}(\overline{{\cal Z}}_{C^{0}})$ is
known when $|C^{0}|<m$, $2\leq m\leq 2^{n-1}$. For the case $|C^{0}|=m$, (1)
we first assume $v_{1}\in C^{0}$. 1) if $N_{in}(v_{1})\cap
C^{0}\neq\emptyset$, then $(\\{v_{1}\\}\cup N_{in}(v_{1}))\cap C^{0}$ is a
subset of one cell of ${\cal P}(\overline{{\cal Z}}_{C^{0}})$. We shrink
$C:=\\{v_{1}\\}\cup N_{in}(v_{1})$ in ${\cal G}$. And ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$ can be obtained by the equitable partition
generated by $C^{0}/C$ in quotient digraph ${\cal G}/C$. 2) If
$N_{in}(v_{1})\cap C^{0}=\emptyset$, then $v_{1}$ forms a singleton cell of
${\cal P}(\overline{{\cal Z}}_{C^{0}})$, that is, $\\{v_{1}\\}$ and
$C^{0}\setminus\\{v_{1}\\}$ are in different cells of ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$. Then ${\cal P}(\overline{{\cal
Z}}_{C^{0}})={\cal P}(\overline{{\cal
Z}}_{C^{0}\setminus\\{v_{1}\\}})\sqcup{\cal P}(\overline{{\cal
Z}}_{\\{v_{1}\\}})$ according to Lemma 3.9.

(2) In the case $v_{1}\notin C^{0}$, that is, $C_{1}:={\cal
N}_{in}(C^{0},\infty)$ is nonempty. Then $C_{1}$ is a cell of ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$ and ${\cal P}(\overline{{\cal
Z}}_{C_{1}})=\\{C_{1},N_{in}(C_{1},1),\ldots,N_{in}(C_{1},\operatorname{dist}_{in}(C_{1}))\\}$.
Moreover, $N_{in}(C_{1},1)\subseteq C^{0}$. 1) If $N_{in}(C_{1},1)=C^{0}$,
then ${\cal P}({\cal Z}_{C^{0}})\preceq{\cal P}(\overline{{\cal Z}}_{C_{1}})$.
According to ${\cal P}(\overline{{\cal Z}}_{C_{1}})\preceq{\cal
P}(\overline{{\cal Z}}_{C^{0}})$, it follows that ${\cal P}(\overline{{\cal
Z}}_{C_{1}})={\cal P}(\overline{{\cal Z}}_{C^{0}})$. 2) If
$N_{in}(C_{1},1)\subsetneq C^{0}$, then $N_{in}(C_{1},1)\subseteq C^{0}$ and
$C^{0}\setminus N_{in}(C_{1},1)$ are in different cells of ${\cal
P}(\overline{{\cal Z}}_{C_{1}})$. According to ${\cal P}(\overline{{\cal
Z}}_{C_{1}})\preceq{\cal P}(\overline{{\cal Z}}_{C^{0}})$, $N_{in}(C_{1},1)$
and $C^{0}\setminus N_{in}(C_{1},1)$ are in different cells of ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$. Thus ${\cal P}(\overline{{\cal
Z}}_{C^{0}})={\cal P}(\overline{{\cal Z}}_{N_{in}(C_{1},1)})\sqcup{\cal
P}(\overline{{\cal Z}}_{C^{0}\setminus N_{in}(C_{1},1)})$.

In conclusion, the algorithm for finding ${\cal P}(\overline{{\cal
Z}}_{C^{0}})$ in the connected STG which has a loop as follows.

Algorithm 2  An algorithm for computing the smallest invariant dual subspace
containing a given dual subspace when the STG is connected and have a loop.

Input: STG ${\cal G}$, state set $C^{0}\subseteq\Delta_{2^{n}}$
Output: $\pi$

1:$v_{1}$ is the root

2:${\cal G}$ is connected

3:function Partition1(${\cal G}$, $C^{0}$)

4: $C_{1}\leftarrow N_{in}(C^{0},\infty)$

5: if $|C^{0}|=1$ then

6: if $C_{1}=\emptyset$ then

7:
$\pi\leftarrow\\{C^{0},N_{in}(C^{0},1),\ldots,N_{in}(C^{0},\operatorname{dist}_{in}(C^{0}))\\}$

8: else

9:
$\pi\leftarrow\\{C_{1},C^{0},N_{in}(C^{0},1),\ldots,N_{in}(C^{0},\operatorname{dist}_{in}(C^{0}))\\}$

10: end if

11: else if $C_{1}=\emptyset$ then $\triangleright$ $v_{1}\in C^{0}$.

12: if $N_{in}(v_{1})\cap C^{0}\neq\emptyset$ then

13: $C_{2}\leftarrow(\\{v_{1}\\}\cup N_{in}(v_{1}))\cap C^{0}$

14: $\pi\leftarrow\textsc{Partition1}({\cal G}/C_{2},C^{0}/C_{2})$

15: else$\triangleright$ $v_{1}$ forms a singleton cell.

16: $\pi\leftarrow\textsc{Partition1}({\cal
G},C^{0}\setminus{\\{v_{1}\\}})\sqcup\textsc{Partition1}({\cal
G},\\{v_{1}\\})$

17: end if

18: else$\triangleright$ $C_{1}$ is a cell.

19: ${\cal G}\leftarrow{\cal G}/C_{1}$

20: $C_{2}\leftarrow N_{in}(C_{1})$ $\triangleright$ $C_{2}\subseteq C^{0}$.

21: if $C_{2}=C^{0}$ then

22: $\pi\leftarrow\textsc{Partition1}({\cal G},C_{1})$

23: else

24: $\pi\leftarrow\textsc{Partition1}({\cal G},C^{0}\setminus
C_{2})\sqcup\textsc{Partition1}({\cal G},C_{2})$

25: end if

26: end if

27: return $\pi$

28:end function

######  Example 3.11.

Let us illustrate Algorithm 2 by a simple example. Suppose that the STG of a
BN is shown in Fig.3 and $C^{0}=\\{v_{1},v_{4},v_{5}\\}$, where $v_{1}$ is the
root. Since $v_{1}$ and $v_{4}$ are adjacent, $C_{1}=\\{v_{1},v_{4}\\}$ is a
subset of one cell of ${\cal P}(\overline{\cal Z}_{C^{0}})$ and ${\cal
G}/C_{1}$ is shown in Fig.3 $(b)$. In ${\cal G}/C_{1}$, $C_{1}$ is the root
but $v_{5}$ is not adjacent to it. Then $C_{1}$ and $\\{v_{5}\\}$ are in
different cell of ${\cal P}(\overline{\cal Z}_{C^{0}})$ according to Lemma
3.10. Thus we get ${\cal P}(\overline{\cal Z}_{C^{0}})={\cal P}(\overline{\cal
Z}_{C_{1}})\sqcup{\cal P}(\overline{\cal Z}_{\\{v_{5}\\}})$ from Lemma 3.9 and
${\cal P}(\overline{\cal Z}_{C_{1}})$ and ${\cal P}(\overline{\cal
Z}_{\\{v_{5}\\}})$ are shown in Fig. 3 $(c)$ and $(d)$. And Fig. 3 $(c)$ is
also the quotient digraph of ${\cal P}(\overline{\cal Z}_{C^{0}})$.

$1$$2$$3$$4$$5$$6$$7$$8$ (a) ${\cal G}$ and $C^{0}=\\{v_{1},v_{4},v_{5}\\}$.
Since $v_{1}$ is the root and $v_{4}$ is adjacent to $v_{1}$,
$C_{1}=\\{v_{1},v_{4}\\}$ is a cell of ${\cal P}(\overline{\cal Z}_{C^{0}})$
according to Lemma 3.10.

$C_{1}$$2$$3$$5$$6$$7$$8$ (b) ${\cal G}/C_{1}$, where
$C_{1}=\\{v_{1},v_{4}\\}$ and $C/C_{1}=\\{C_{1},v_{5}\\}$. In ${\cal
G}/C_{1}$, $C_{1}$ is the root and $v_{5}$ is not adjacent to it, ${\cal
P}(\overline{\cal Z}_{C})={\cal P}(\overline{\cal Z}_{C_{1}})\sqcup{\cal
P}(\overline{\cal Z}_{\\{v_{5}\\}})$.

$C_{1}$$C_{2}$$5$$C_{3}$$8$ (c) ${\cal P}(\overline{\cal
Z}_{C_{1}})=\\{C_{1},C_{2}=\\{v_{2},v_{3}\\},\\{v_{5}\\},C_{3}=\\{v_{6},v_{7}\\},\\{v_{8}\\}\\}=\\{\\{v_{1},v_{4}\\},\\{v_{2},v_{3}\\},\\{v_{5}\\},\\{v_{6},v_{7}\\},\\{v_{8}\\}\\}$.

$C_{4}$$5$$C_{3}$$8$ (d) ${\cal P}(\overline{\cal
Z}_{\\{v_{5}\\}})=\\{C_{4}=\\{C_{1},v_{2},v_{3}\\},\\{v_{5}\\},\\{C_{3}\\},\\{v_{8}\\}\\}=\\{\\{v_{1},v_{2},v_{3},v_{4}\\},\\{v_{5}\\},\\{v_{6},v_{7}\\},\\{v_{8}\\}\\}$.

Figure 3: An example of the Algorithm 2 and ${\cal P}(\overline{\cal
Z}_{C^{0}})=\\{\\{v_{1},v_{4}\\},\\{v_{2},v_{3}\\},\\{v_{5}\\},\\{v_{6},v_{7}\\},\\{v_{8}\\}\\}$.

####  3.2.2 BNs with cycles

Now we consider the case that the STG contains a cycle ${\cal C}$. We need the
following lemma.

######  Lemma 3.12.

Assume that ${\cal C}$ is a directed cycle with length $l$ ($l$-cycle) and
$v_{1}\in V({\cal C})$, a partition $\pi$ of ${\cal C}$ is equitable if and
only if there exists a factor $q$ of $l$ such that
$\pi=\\{\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow v_{1})\equiv
j(\\!\\!\\!\\!\mod q)\\}|j\in[0:q-1]\\}$. And the quotient digraph ${\cal
C}/\pi$ is a directed $q$-cycle.

###### Proof.

Suppose that $\pi=\\{C_{1},C_{2},\ldots,C_{q}\\}$ is a nontrivial equitable
partition for ${\cal C}$. Let $v_{1}\in C_{1}$. If $N_{out}(v_{1})\subseteq
C_{1}$, then $C_{1}=V({\cal C})$. If $C_{1}\neq V({\cal C})$, then any $u,v\in
C_{i}$, $i\in[1;q-1]$ are non-adjacent and $N_{out}(u)$ and $N_{out}(v)$ are
subsets of the same cell of $\pi$, denoted by $C_{i+1}$. For $C_{q}$, the out-
neighbors of vertices in $C_{q}$ are contained in $C_{1}$ since ${\cal C}$ is
a directed $l$-cycle. Therefore ${\cal C}/\pi$ is a directed cycle and
$|C_{1}|=|C_{2}|=\cdots=|C_{q}|=l/q$. And $N_{out}(v_{1},q)$ is also a subset
of $C_{1}$. By repeating this procedure we get
$\pi=\\{\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow v_{1})\equiv
j(\\!\\!\\!\\!\mod p)\\}|j\in[0;q-1]\\}$. It follows that $q|l$.

On the contrary, it is easy to show that
$\pi=\\{\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow v_{1})\equiv
j(\\!\\!\\!\\!\mod q)\\}|j\in[0;q-1]\\}$ is equitable for any $q|l$. ∎

Case 1. STG ${\cal G}$ is a single cycle

For dual subspace ${\cal Z}$ with 2-partition ${\cal P}({\cal Z}_{C^{0}})$, if
${\cal P}(\overline{{\cal Z}}_{C^{0}})$ is nontrivial, there exists a proper
factor $q$ of $l$ such that ${\cal P}(\overline{{\cal
Z}}_{C^{0}})=\\{\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow v_{1})\equiv
j(\\!\\!\\!\\!\mod q)\\}|j\in[0;q-1]\\}$. Since ${\cal P}({\cal
Z}_{C^{0}})\preceq{\cal P}(\overline{{\cal Z}}_{C^{0}})$, $C^{0}=\cup_{j\in
S}\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow v_{1})\equiv
j(\\!\\!\\!\\!\mod q)\\}\text{ for some }S\subseteq[0;q-1]$. If there is no
such a proper factor, ${\cal P}(\overline{{\cal Z}}_{C^{0}})$ is trivial.

On the other hand, if there exists a proper factor $q$ of $l$ such that
$C^{0}=\cup_{j\in S}\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow v_{1})\equiv
j(\\!\\!\\!\\!\mod q)\\}\text{ for some }S\subseteq[0;q-1]$, then ${\cal
P}({\cal
Z}_{C^{0}})\preceq\pi:=\\{\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow
v_{1})\equiv j(\\!\\!\\!\\!\mod q)\\}|j\in[0;p-1]\\}$ and ${\cal
P}(\overline{{\cal Z}}_{C^{0}})\preceq\pi$ is nontrivial. We can continue
finding the equitable partition generated by $C^{0}$ in ${\cal G}/\pi$ until
it is trivial. Figure 4 is an example of this case.

$1$$2$$3$$4$$5$$6$$7$$8$ (a) ${\cal G}$ is a cycle and
$C^{0}=\\{v_{1},v_{2},v_{5},v_{6}\\}$. Since
$\operatorname{dist}(v_{5}\rightarrow
v_{1})=\operatorname{dist}(v_{6}\rightarrow v_{2})=4$, ${\cal
P}(\overline{{\cal
Z}}_{C^{0}})\preceq\pi:=\\{\\{v_{1},v_{5}\\},\\{v_{2},v_{6}\\},\\{v_{3},v_{7}\\},\\{v_{4},v_{8}\\}\\}$.

$C_{1}$$\\{v_{1},v_{5}\\}$$C_{2}$$\\{v_{2},v_{6}\\}$$C_{3}$$\\{v_{3},v_{7}\\}$$C_{4}$$\\{v_{4},v_{8}\\}$
(b) ${\cal G}/\pi$ is a 4-cycle. Since $C^{0}=\\{C_{1},C_{2}\\}$ generate a
trivial equitable partition in ${\cal G}/\pi$, ${\cal P}(\overline{{\cal
Z}}_{C^{0}})=\pi$.

Figure 4: An equitable partition of an 8-cycle.

Case 2. STG ${\cal G}$ is not a cycle

Let ${\cal C}$ be the only cycle in ${\cal G}$.

(1) If $C^{0}=V({\cal C})$, then only the vertices in ${\cal C}$ always
produce $\delta_{2}^{1}$ in $z_{i}(x)=G_{i}x$, $i\in[0;k]$. Thus $C^{0}$ is a
cell of ${\cal P}(\overline{{\cal Z}}_{C^{0}})$. Since ${\cal G}/V({\cal C})$
is a connected digraph with a loop and $V({\cal C})$ is the root with this
loop, the original problem can be reduced to finding the equitable partition
generated by the root in ${\cal G}/V({\cal C})$ which coincides with the case
in subsection 3.2.1. Figure 5 is an example of this case.

$1$$2$$3$$4$$5$$6$$7$$8$ (a) ${\cal G}$ with 6-cycle ${\cal C}$ and
$C^{0}=V({\cal C})$.

$C^{0}$$7$$8$ (b) ${\cal G}/V({\cal C})$ has root $C^{0}$. The equitable
partition generated by $C^{0}$ in ${\cal G}/V({\cal C})$ is trivial, that is,
${\cal P}(\overline{{\cal Z}}_{C^{0}})=\\{C^{0},\\{v_{7}\\},\\{v_{8}\\}\\}$.

Figure 5: STG ${\cal G}$ with 6-cycle ${\cal C}$ and its quotient graph, where
$C^{0}=V({\cal C})$.

(2) If $C^{0}\subseteq V({\cal G})\backslash V({\cal C})$, then $V({\cal
C})\subseteq N_{in}(C^{0},\infty)$. Thus $C_{1}:=N_{in}(C^{0},\infty)$ is
nonempty and a cell of ${\cal P}(\overline{{\cal Z}}_{C^{0}})$ according to
Lemma 3.9. We can simplify the original problem to finding the equitable
partition generated by $C^{0}$ in ${\cal G}/C_{1}$ which has a loop.

(3) In the case $C^{0}\subsetneq V({\cal C})$, let $v_{1}\in C^{0}$ and $e$ be
the out-edge of $v_{1}$.

1) If $|C^{0}|=1$, then $v_{1}$ forms a singleton cell of ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$. Since ${\cal G}\backslash e$ is a spanning
branching of ${\cal G}$ according to Lemma 3.8, we can obtain ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$ in digraph ${\cal G}^{\prime}$ which is
constructed from ${\cal G}\backslash e$ by adding a loop to $v_{1}$.

2) Assume, inductively, that ${\cal P}(\overline{{\cal Z}}_{C^{0}})$ is known
when $|C^{0}|<m$, $2\leq m\leq 2^{n-1}$. Consider $|C^{0}|=m$. If $C^{0}$ can
generate a nontrivial equitable partition $\pi_{1}$ of ${\cal C}$, we shrink
the cells of $\pi_{1}$ in ${\cal G}$ and denote by $\widetilde{{\cal G}}$ the
resulting digraph. And $\widetilde{{\cal G}}$ also has a cycle. We can reduce
the original problem to finding the equitable partition generated by $C^{0}$
in $\widetilde{{\cal G}}$. Since $C^{0}$ may be partitioned into some cells of
$\pi_{1}$, $C^{0}$ in $\widetilde{{\cal G}}$ may be a vertex subset. Figure 6
is an example of this case.

If the equitable partition generated by $C^{0}$ in ${\cal C}$ is trivial, then
vertices in $C^{0}$ are in different cells of ${\cal P}(\overline{{\cal
Z}}_{C^{0}})$ and ${\cal P}(\overline{{\cal Z}}_{C^{0}})=\sqcup_{v_{i}\in
C^{0}}{\cal P}(\overline{{\cal Z}}_{\\{v_{i}\\}})$ according to Lemma 3.9.

$1$$2$$3$$4$$5$$6$$7$$8$ (a) ${\cal G}$ with 6-cycle ${\cal C}$ and
$C^{0}=\\{v_{2},v_{4},v_{6}\\}$. And $C^{0}$ generates a nontrivial partition
$\pi_{1}:=\\{\\{v_{1},v_{3},v_{5}\\},\\{v_{2},v_{4},v_{6}\\}\\}$ in ${\cal
C}$.

$C^{\prime}$$\\{v_{1},v_{3},v_{5}\\}$$C^{0}$$7$$8$$e$ (b) $\widetilde{\cal G}$
is obtained by shrinking cells in $\pi_{1}$. The original problem is reduced
to finding the equitable partition generated by $C^{0}$ in $\widetilde{\cal
G}$.

$C^{\prime}$$C^{0}$$7$$8$$e^{\prime}$ (c) Moreover, the original problem is
reduced to finding the equitable partition generated by $C^{0}$ in
$\widetilde{\cal G}-e+e^{\prime}$.

$C^{0}$$\\{v_{2},v_{4},v_{6}\\}$$C_{2}$$\\{v_{1},v_{3},v_{5},v_{7}\\}$$8$$e^{\prime}$
(d) ${\cal G}/{\cal P}(\overline{{\cal Z}}_{C^{0}})$, where ${\cal
P}(\overline{{\cal
Z}}_{C^{0}})=\\{\\{v_{1},v_{3},v_{5},v_{7}\\},\\{v_{2},v_{4},v_{6}\\},\\{v_{8}\\}\\}$.

Figure 6: STG ${\cal G}$ with 6-cycle ${\cal C}$ and its quotient graph (d),
where $C^{0}=\\{v_{2},v_{4},v_{6}\\}$.

(4) The most difficult case is that $C^{0}$ consists of both vertices in
$V({\cal C})$ and $V({\cal G})\backslash V({\cal C})$. We denote
$C^{0}=C^{\prime}\cup C^{\prime\prime}$, where $C^{\prime}\subseteq V({\cal
C})$ and $C^{\prime\prime}\subseteq V({\cal G})\backslash V({\cal C})$.

1) Consider the case $|C^{\prime}|=1$ and $|C^{\prime\prime}|=1$. For
$z_{i}(x)=G_{i}x$, $i\in[0;k]$ which are defined in the proof of Lemma 3.9,
$v_{1}\in C^{\prime}$ produces value $\delta_{2}^{1}$ in a cycle of length
$l:=|V({\cal C})|$. Then $C^{0}$ is a cell of ${\cal P}(\overline{{\cal
Z}}_{C^{0}})$ if and only if the distance from $v^{\prime}$ to $v_{1}$ is $l$,
where $v^{\prime}\in C^{\prime\prime}$. In the case that $C^{0}$ is a cell of
${\cal P}(\overline{{\cal Z}}_{C^{0}})$, we denote the induced subgraph on
vertices $\\{v^{\prime}\\}\cup\widetilde{C}$ by ${\cal G}_{1}$, where
$\widetilde{C}$ is the vertex set reachable from $v^{\prime}$. In ${\cal
G}_{1}$, the equitable partition generated by $C^{0}$ is
$\pi_{1}:=\\{\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow v_{1})\equiv
j(\\!\\!\\!\\!\mod l)\\}|j\in[0;l-1]\\}$ which contains $C^{0}$ as a cell. The
quotient graph ${\cal G}_{1}/\pi_{1}$ is a directed $l$-cycle and has $C^{0}$
as a vertex.

We shrink the cells of $\pi_{1}$ in the original digraph ${\cal G}$ and denote
the new digraph by $\widetilde{\cal G}$. And ${\cal P}(\overline{{\cal
Z}}_{C^{0}})$ can be generated by $C^{0}$ in $\widetilde{\cal G}$. Figure 7 is
an example of this case.

2) Assume, inductively, that $C^{\prime}=\\{v_{1}\\}$ and ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$ is known when $|C^{\prime\prime}|<m$, $2\leq
m\leq 2^{n-1}$. Consider the case $|C^{\prime\prime}|=m$. We will discuss
whether there exists $u\in C^{\prime\prime}$ such that $u$ and $v_{1}$ are in
the same cell of ${\cal P}(\overline{{\cal Z}}_{C^{0}})$.

Before proceeding further, let us define the vertex set $S\subseteq
C^{\prime\prime}$ closest to ${\cal C}$. For $u\in C^{\prime\prime}$, if there
exists no other vertex in $C^{\prime\prime}$ that is reachable from $u$ then
$u\in S$.

If there exists $u\in S$ such that $\operatorname{dist}(u\rightarrow
v_{1})=l$, then $u$ and $v_{1}$ are in the same cell of ${\cal
P}(\overline{{\cal Z}}_{C^{0}})$. Like the above discussion, we consider the
induced subgraph on vertices $\\{u\\}\cup\widetilde{C}$, denoted by ${\cal
G}_{1}$, where $\widetilde{C}$ is the vertex set reachable from $u$. In ${\cal
G}_{1}$, we denote the equitable partition generated by $\\{u,v_{1}\\}$ by
$\pi_{1}$. We can obtain ${\cal P}(\overline{{\cal Z}}_{C^{0}})$from the
equitable partition generated by $C^{0}/\\{u,v_{1}\\}$ in $\widetilde{\cal
G}$, which is obtained from ${\cal G}$ by shrinking the cells of $\pi_{1}$.

If there exists no such $u\in S$, then $v_{1}$ forms a singleton cell in
${\cal P}(\overline{{\cal Z}}_{C^{0}})$. Thus ${\cal P}(\overline{{\cal
Z}}_{C^{0}})={\cal P}(\overline{{\cal Z}}_{C^{\prime\prime}})\sqcup{\cal
P}(\overline{{\cal Z}}_{C^{\prime}})$.

3) Assume, inductively, that we know ${\cal P}(\overline{{\cal Z}}_{C^{0}})$
when $|C^{\prime}|<m$, $2\leq m\leq 2^{n-1}$. In the case $|C^{\prime}|=m$, if
$C^{\prime}$ generate a nontrivial equitable partition $\pi_{1}$ in cycle
${\cal C}$, then $C^{\prime}$ is partitioned into
$C^{\prime}_{1},\ldots,C^{\prime}_{r}$, where
$C^{\prime}_{1},\ldots,C^{\prime}_{r}\in\pi_{1}$ and $r<m$. We construct
$\widetilde{\cal G}$ from ${\cal G}$ by shrinking cells in $\pi_{1}$. Then
${\cal P}(\overline{{\cal Z}}_{C^{0}})$ is equal to the equitable partition
generated by $C^{\prime\prime}\cup C^{\prime}_{1}\cup\cdots\cup
C^{\prime}_{r}$ in $\widetilde{\cal G}$.

If the equitable partition generated by $C^{\prime}$ in ${\cal C}$ is trivial,
then each vertex in $C^{\prime}=\\{v_{1},\ldots,v_{m}\\}$ is in a separate
cell of ${\cal P}(\overline{{\cal Z}}_{C^{0}})$. In the following, we only
need to consider the case whether $v_{i}$, $i=1,\ldots,m$, is contained in the
same cell with some vertices in $C^{\prime\prime}$. Thus ${\cal
P}(\overline{{\cal Z}}_{C^{0}})=\sqcup_{v_{i}\in C^{\prime}}{\cal
P}(\overline{{\cal Z}}_{C^{\prime\prime}\cup\\{v_{i}\\}})$.

$1$$2$$3$$4$ (a) ${\cal G}$ and $C^{0}=\\{v_{1},v_{3}\\}$. We have
$\operatorname{dist}(v_{3}\rightarrow v_{1})=2$.

$C_{1}$$\\{v_{1},v_{3}\\}$$C_{2}$$\\{v_{2},v_{4}\\}$ (b) ${\cal G}/{\cal
P}(\overline{{\cal Z}}_{C^{0}})$ and ${\cal P}(\overline{{\cal
Z}}_{C^{0}})=\\{\\{v_{1},v_{3}\\},\\{v_{2},v_{4}\\}\\}$.

Figure 7: STG ${\cal G}$ with 2-cycle ${\cal C}$ and its quotient graph (b).

In conclusion, the algorithms for finding ${\cal P}(\overline{{\cal
Z}}_{C^{0}})$ in STGs with cycles are as in Algorithm 3 and 4.

Algorithm 3  An algorithm for constructing the smallest invariant dual
subspace containing a given subspace when STG is connected and with a cycle.

Input: ${\cal G}$, $C^{0}$
Output: $\pi$

1:${\cal G}$ has a cycle ${\cal C}$

2:${\cal G}$ is connected

3:$C^{0}\subseteq V({\cal C})$

4:function Partition2(${\cal G}$, $C^{0}$)

5: $n\leftarrow|V({\cal G})|$

6: $l\leftarrow|V({\cal C})|$

7: if $l=n$ then $\triangleright$ ${\cal G}$ is a cycle.

8: if there exists $q|l$ and $S\subseteq[0:q-1]$ such that $C^{0}=\cup_{j\in
S}\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow v_{1})\equiv
j(\\!\\!\\!\\!\mod q)\\}$ then

9: $\pi_{1}\leftarrow\\{\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow
v_{1})\equiv j(\\!\\!\\!\\!\mod q)\\}|j\in[0;q-1]\\}$

10: $\pi\leftarrow\textsc{Partition2}({\cal G}/\pi_{1},C^{0})$

11: else

12: $\pi$ is trivial

13: end if

14: else if $|C^{0}|=1$ then

15: $v_{1}\leftarrow$the vertex in $C^{0}$, $e\leftarrow$ the out-edge of
$v_{1}$

16: ${\cal G}_{1}\leftarrow$ adding a loop to ${\cal G}\backslash e$ on
$v_{1}$

17: $\pi\leftarrow\textsc{Partition1}({\cal G}_{1},C^{0})$

18: else

19: $\pi_{1}\leftarrow\textsc{Partition2}({\cal C},C^{0})$

20: if $\pi_{1}$ is nontrivial then

21: ${\cal G}\leftarrow$ shrinking the cells of $\pi_{1}$ in ${\cal G}$

22: $\pi\leftarrow\textsc{Partition2}({\cal G},C^{0})$

23: else

24: $\pi\leftarrow\sqcup_{v_{i}\in C^{0}}\textsc{Partition2}({\cal
G},\\{v_{i}\\})$

25: end if

26: end if

27: return $\pi$

28:end function

Algorithm 4  An algorithm for constructing the smallest invariant dual
subspace containing a given subspace when STG is connected and with a cycle.

Input: ${\cal G}$, $C^{0}$
Output: $\pi$

1:${\cal G}$ has a cycle ${\cal C}$

2:${\cal G}$ is connected and ${\cal G}$ is not a cycle

3:function Partition3(${\cal G}$, $C^{0}$)

4: ${\cal C}\leftarrow$ the cycle in ${\cal G}$

5: $n\leftarrow|V({\cal G})|$, $l\leftarrow|V({\cal C})|$

6: $C^{\prime}\leftarrow V({\cal C})\cap C^{0}$, $C^{\prime\prime}\leftarrow
C^{0}\backslash C^{\prime}$

7: if $|C^{\prime}|=0$ then

8: $C_{1}\leftarrow N_{in}(C^{0},\infty)$

9: $\pi\leftarrow$ Partition1(${\cal G}/C_{1},C^{0}$)

10: else if $|C^{\prime}|=1$ then

11: $v_{1}\leftarrow$ the vertex in $C^{\prime}$

12: if $|C^{\prime\prime}|=1$ then

13: $u\leftarrow$ the vertex in $C^{\prime\prime}$

14: if $\operatorname{dist}(u\rightarrow v_{1})=l$ then

15: $\widetilde{C}\leftarrow$ the vertex set which $u$ can reach to

16:
$\pi_{1}\leftarrow\\{\\{v_{i}\in\widetilde{C}\cup\\{u\\}|\operatorname{dist}(v_{i}\rightarrow
v_{1})\equiv j(\\!\\!\\!\\!\mod l)\\}|j\in[0;l-1]\\}$

17: $\widetilde{\cal G}\leftarrow$ shrinking the cells of $\pi_{1}$ in ${\cal
G}$

18: $\pi\leftarrow$ Partition2($\widetilde{\cal G},C^{0}$)

19: else

20: $\pi\leftarrow$ Partition2(${\cal
G},\\{v_{1}\\}$)$\sqcup$Partition3(${\cal G},\\{u\\}$)

21: end if

22: else if there exists $u\in C^{\prime\prime}$ such that Partition3(${\cal
G},\\{u,v_{1}\\}$) is nontrivial then

23:
$\pi_{1}\leftarrow\\{\\{v_{i}\in\widetilde{C}\cup\\{u\\}|\operatorname{dist}(v_{i}\rightarrow
v_{1})\equiv j(\\!\\!\\!\\!\mod l)\\}|j\in[0;l-1]\\}$

24: $\widetilde{\cal G}\leftarrow$ shrinking the cells of $\pi_{1}$ in ${\cal
G}$

25: $\pi\leftarrow$ Partition2($\widetilde{\cal G},C^{0}/\\{u,v_{1}\\}$)

26: else

27: $\pi\leftarrow$ Partition2(${\cal G},C^{\prime}$)$\sqcup$Partition3(${\cal
G},C^{\prime\prime}$)

28: end if

29: else if Partition2(${\cal C},C^{\prime}$) is nontrivial then

30: $\pi_{1}\leftarrow$ Partition2(${\cal C},C^{\prime}$)

31: $C^{\prime}$ is partitioned into $C^{\prime}_{1},\ldots,C^{\prime}_{r}$

32: $\pi\leftarrow$Partition3(${\cal G},C^{\prime\prime}\cup
C^{\prime}_{1}\cup\ldots\cup C^{\prime}_{r}$)

33: else if Partition2(${\cal C},C^{\prime}$) is trivial then

34: $\pi\leftarrow\sqcup_{v_{i}\in C^{\prime}}$ Partition3(${\cal
G},C^{\prime\prime}\cup\\{v_{i}\\}$)

35: end if

36: return $\pi$

37:end function

##  4 Construction of observability outputs for a given BN

###  4.1 Unobservable subspaces and the smallest invariant dual subspaces

A Boolean network (BN) in an algebraic form is described as follows [10]

$\left\\{\begin{aligned} x(t+1)&=Mx(t),\\\ y(t)&=Ex(t).\end{aligned}\right.$
(27)

where $M\in{\cal L}_{2^{n}\times 2^{n}}$ and $E\in{\cal L}_{2^{q}\times
2^{n}}$ are the state-transition and output matrices, respectively. The
solution to BN (27) with initial state $x_{0}\in\Delta_{2^{n}}$ is denoted by
$x(t;x_{0})$. The output is denoted by $y(t;x_{0})$, that is,
$y(t;x_{0})=Ex(t;x_{0})$. For convenience, we define
$Y(t;x_{0}):=[y(0;x_{0})^{T}y(1;x_{0})^{T}\cdots y(t;x_{0})^{T}]^{T}$ and
denote by $\mathbf{y}(t;x_{0})$ the algebraic form of $Y(t;x_{0})$, i.e.,
$\mathbf{y}(t;x_{0}):=y(0;x_{0})\ltimes y(1;x_{0})\ltimes\cdots\ltimes
y(t;x_{0})$.

Two distinct initial states $x_{0}$ and $\overline{x}_{0}$ are said to be
distinguishable if there exists a positive integer $t$ such that
$\mathbf{y}(t;x_{0})\neq\mathbf{y}(t;\overline{x}_{0})$. BN (27) is said to be
observable if any two distinct initial states are distinguishable.

Denote $\mathcal{O}_{r}^{*}:=E*(EM)*\cdots*(EM^{r-1}).$ The observability
index of BN (27) is defined as $r_{0}=\min\left\\{r\mid
rank\left(\mathcal{O}_{r}^{*}\right)=rank\left(\mathcal{O}_{r+1}^{*}\right)\right\\}$.
The observability matrix is $\mathcal{O}_{r_{0}}^{*}$.

######  Theorem 4.1 ([13]).

In BN $(\ref{BN-out})$, two distinct states $x_{0}$ and $\overline{x}_{0}$ are
distinguishable if and only if $\mathcal{O}_{r_{0}}^{*}x_{0}$ and
$\mathcal{O}_{r_{0}}^{*}\overline{x}_{0}$ are different. Moreover, BN
$(\ref{BN-out})$ is observable if and only if no two columns of
$\mathcal{O}_{r_{0}}^{*}$ are identical.

According to Algorithm 1 and the definition of $r_{0}$,
$\mathcal{O}_{r_{0}}^{*}$ is exactly the structure matrix of the smallest
invariant dual subspace $\overline{{\cal Z}}$ containing ${\cal
F}_{\ell}\\{y(t)\\}$. It is easy to get the following lemma which is a special
case of [12, Theorem 6]. Theorem 6 of [12] was briefly restated in [9, Remark
4.1].

######  Lemma 4.2.

In BN $(\ref{BN-out})$, two states are distinguishable if and only if they are
in different cells of $\overline{{\cal Z}}$, where $\overline{{\cal Z}}$ is
the smallest invariant dual subspace containing ${\cal F}_{\ell}\\{y(t)\\}$.
Moreover BN (27) is observable if and only if ${\cal P}(\overline{{\cal Z}})$
is trivial.

###  4.2 Construction of observable output functions

In this subsection, we study the graphical properties preventing two vertices
from being distinguishable for a given BN. We can construct observable output
functions from following theorem.

######  Theorem 4.3.

Suppose that BN $(\ref{BN-out})$ has output function $y(t)$ and ${\cal
Z}={\cal F}_{\ell}\\{y(t)\\}$. If

  * $(i)$

the vertex with a loop (if it exists) and all of its in-neighbours are in
different cells of ${\cal P}({\cal Z})$ (i.e., these vertices produce distinct
outputs) or there is a vertex $v\in V({\cal C})$ (if there exists a cycle
${\cal C}$ in STG ${\cal G}$) such that all vertices of ${\cal C}$ are in
different cells of ${\cal P}(\overline{{\cal Z}})$;

  * $(ii)$

the in-neighbours of any vertex are in different cells of ${\cal P}({\cal
Z})$,

then $(\ref{BN-out})$ is observable.

###### Proof.

(1) If the STG ${\cal G}$ of (27) has a vertex $v_{1}$ with a loop and $v_{1}$
and all its in-neighbours are in different cells of ${\cal P}({\cal Z})$, then
$v_{1}$ forms a singleton cell of ${\cal P}(\overline{\cal Z})$ according to
Lemma 3.10. Thus ${\cal P}(\overline{\cal
Z}_{\\{v_{1}\\}})=\\{\\{v_{1}\\},N_{in}(v_{1},1),\ldots,N_{in}(v_{1},\operatorname{dist}_{in}(v_{1}))\\}\preceq{\cal
P}(\overline{\cal Z})$. Suppose $N_{in}(v_{1},1):=\\{v_{2},\ldots,v_{r}\\}$.
According to the assumption $(ii)$, $v_{2},\ldots,v_{r}$ are in distinct cells
of ${\cal P}({\cal Z})$. We get
$\\{\\!\\{v_{1}\\},\ldots,\\{v_{r}\\},\\!N_{in}(v_{1},2),\\!\ldots,\\!N_{in}(v_{1},\\!\operatorname{dist}_{in}(v_{1}))\\}\preceq{\cal
P}(\overline{\cal Z})$. Then ${\cal P}(\overline{\cal
Z}_{\\{v_{i}\\}})\preceq{\cal P}(\overline{\cal Z})$, $i\in[1;r]$ according to
Lemma 3.9. Thus

${\cal P}(\overline{\cal Z}_{\\{v_{1}\\}})\sqcup{\cal P}(\overline{\cal
Z}_{\\{v_{2}\\}})\sqcup\cdots\sqcup{\cal P}(\overline{\cal
Z}_{\\{v_{r}\\}})\preceq{\cal P}(\overline{\cal Z}).$

Repeating this procedure, finally we have ${\cal P}(\overline{\cal Z})$ is
trivial.

(2) If ${\cal G}$ has a $l$-cycle ${\cal C}$ and all vertices of ${\cal C}$
are in distinct cells of ${\cal P}({\cal Z})$, then all vertices in $V({\cal
C})$ are in different cells of ${\cal P}(\overline{\cal Z})$.

We only need consider whether $v_{1}$ is in the same cell as other vertices in
$N_{in}(v_{1},l)$. Assume that $u\in N_{in}(v_{1},l)$ and $v_{1}$ and $u$ are
in the same cell of ${\cal P}(\overline{\cal Z})$. Then in the induced
subgraph $\widetilde{{\cal G}}$ on vertex set $\\{u\\}\cup\widetilde{C}$,
where $\widetilde{C}$ is the vertex set reachable from $u$, there is a
nontrivial partition
$\pi_{1}:=\\{\\{v_{i}|\operatorname{dist}(v_{i}\rightarrow v_{1})\equiv
j(\\!\\!\\!\\!\mod l)\\}|j\in[0;l-1]\\}$ and each cell of $\pi_{1}$ is a
subset of some cell of ${\cal P}(\overline{\cal Z})$. There exists a cell
$\\{v_{i},v_{j}\\}\in\pi_{1}$ has the same out-neighbour, which contradicts to
the assumption $(ii)$. In conclusion, $v_{1}$ forms a singleton cell of ${\cal
P}(\overline{\cal Z})$.

As in the discussion above, the problem of finding the equitable partition
generated by $\\{v_{1}\\}$ when ${\cal G}$ contains a cycle can be reduced to
the problem in ${\cal G}^{\prime}$, which is constructed from ${\cal G}$ by
deleting the out-edge of $v_{1}$ and adding a loop to $v_{1}$. As our analysis
for STG with a loop, we get ${\cal P}(\overline{\cal Z})$ is trivial from
condition $(i)$ and $(ii)$, that is, (27) is observable. ∎

######  Example 4.4 ([14]).

A logical equation about the gene network of the $\lambda$ bacteriophage can
be expressed in the following form

${}\left\\{\begin{aligned} N(t+1)&=[\neg cI(t)]\wedge[\neg cro(t)],\\\
cI(t+1)&=[\neg cro(t)]\wedge[cI(t)\vee cII(t)],\\\ cII(t+1)&=[\neg
cI(t)]\wedge[N(t)\vee cIII(t)],\\\ cIII(t+1)&=[\neg cI(t)]\wedge N(t),\\\
cro(t+1)&=[\neg cI(t)]\wedge[\neg cII(t)].\end{aligned}\right.$ (28)

Suppose $x=N\ltimes cI\ltimes cII\ltimes cIII\ltimes cro4$. Equation
$(\ref{3.8})$ can be transformed into form $x(t+1)=Mx(t)$, where

$\begin{array}[]{l l
llllllllllllllll}M=\delta_{32}[&32&24&32&24&32&24&32&24\\\
&26&2&26&2&25&9&25&9\\\ &32&24&32&24&32&24&32&24\\\
&28&4&32&8&27&11&31&15].\end{array}$

${}\left\\{\begin{aligned} x(t+1)&=Mx(t),\\\ y(t)&=Ex(t).\end{aligned}\right.$
(29)

An observable output matrix is

$\begin{array}[]{llllllllllllllllll}E=\delta_{16}[&9&2&2&3&3&4&4&5\\\
&1&1&2&2&2&2&1&1\\\ &5&6&6&7&7&8&8&1\\\ &1&1&1&1&1&1&2&1].\end{array}$

The STG ${\cal G}$ is shown in Fig 8. For the purpose to ensure the condition
$(ii)$ of Theorem 4.3 holds, we need at least 9 cells to partition the in-
neighbours of $\delta_{32}$ in different cells. To study the observability of
BN $(\ref{3.8-1})$, we associate $y(t)$ with a partition
$\pi=\\{\\{x|Ex=\delta_{9}^{i}\\},i=1,2\ldots,9\\}$. We color the vertices in
the same cell with the same color. Let the color set be $C$, where $C$ is all
the possible output values of the BN, so
$C=\\{\delta_{9}^{1},\ldots,\delta_{9}^{9}\\}$. Given any output sequence of
$(\ref{3.8-1})$, we can determine the initial state.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$17$$18$$19$$20$$21$$22$$23$$24$$25$$26$$27$$28$$29$$30$$31$$32$
Figure 8: STG of BN (29).

##  5 Conclusion

In this paper an invariant dual subspace was proven to be an equitable
partition of the state-transition graph of a BN. Using this idea, we research
the dual dynamics of every invariant dual subspace from a graphical
perspective. Furthermore, we proved that the unobservable subspace of a BN is
equal to the smallest invariant dual subspace containing its output functions.
One rule to construct observable outputs was obtained.

When a BN/BCN is of large scale, the structure matrix of the overall BN/BCN
might be huge and practically uncomputable. However, the dual dynamics of a
huge BN with respect to a dual subspace is usually smaller than the original
BN but still can reflect partial properties of the BN. For example, the dual
dynamics of a BN with respect to a dual subspace can directly reflect the
observability of the BN with the dual subspace as its output function, because
the quotient graph generated by the corresponding unobservable subspace as a
dynamic system is exactly the dual dynamics of the BN with respect to the dual
subspace, see Theorem 3.6. Hence, this technique may provide a promising way
to overcoming high computational complexity in problem in large-scale BN/BCNs.

## References

  * [1] S.A. Kauffman, “Metabolic stability and epigenesis in randomly constructed genetic nets,” J. Theor. Biol., vol. 22, pp. 437-467, 1969.
  * [2] D. Cheng, H. Qi, Z. Li, Analysis and Control of BNs: A Semi-tensor Product Approach, Springer, London, 2011.
  * [3] D. Cheng, H. Qi, Y. Zhao, An Introduction to Semi-tensor Product of Matrices and Its Applications, World Scientific, Singapore, 2012.
  * [4] D. Cheng, L. Zhang, D. Bi, “Invariant subspace approach to Boolean (control) networks,” IEEE Trans. Automat. Contr., to be published.
  * [5] A. Bondy, U. S. R. Murty, Graph Theory, Springer, London, 2008.
  * [6] C. O. Aguilar, B. Gharesifard, “Almost equitable partitions and new necessary conditions for network controllability,” Automatica, vol. 80, pp. 25-31, 2017.
  * [7] D. M. Cardoso, C. Delorme, P. Rama, “Laplacian eigenvectors and eigenvalues and almost equitable partitions,” Eur. J. Comb., vol. 28, pp. 665-673, 2007.
  * [8] D. Cheng, H. Qi, “Controllability and observability of Boolean control networks,” Automatica, vol. 45, no. 7, pp. 1659-1667, 2009.
  * [9] K. Zhang, L. Zhang, L. Xie, Discrete-Time and Discrete-Space Dynamical Systems, Springer, Hong Kong, 2020.
  * [10] D. Cheng and Y. Zhao, “Identification of Boolean control networks,” Automatica, vol. 47, pp. 702–710, 2011.
  * [11] D. Cheng, H. Qi, “State-space analysis of Boolean networks,” IEEE Trans. Neur. Netw., vol. 21, no. 4, pp. 584-594, 2010.
  * [12] E. F. Moore, “Gedanken-experiments on sequential machines,” Annals of Mathematics Studies, vol. 34, pp. 129-153, 1956.
  * [13] Y. Guo, W. Gui, C. Yang, “Redefined observability matrix for Boolean networks and distinguishable partitions of state space,” Automatica, vol. 91, pp. 316-319, 2018.
  * [14] D. Laschov, M. Margaliot.“Minimum-time control of Boolean networks,” SIAM J. Control Optim., vol. 51, no. 4, pp. 2869-2892, 2013.