Remark 55. In the case m = 0, we have F mq = F0 q = {() } (the set containing the empty tuple) and thus F nq × F mq = F nq × F0 q = F nq × {() } = F nq. In other words, g is a monomial dynamical system over F q. From now on we will refer to a time invariant monomial control system over F q as monomial
control system over F q.
Definition 56. Let X be a nonempty finite set and n, l ∈ N natural numbers. The set of all functions
f : Xl → Xn is denoted with Fn( X).
l
Definition 57. Let F q be a finite field and l, m, n ∈ N natural numbers. Furthermore, let Eq be the exponents semiring of F q and M( n × l; Eq) the set of n × l matrices with entries in Eq. Consider the
map
Γ : Flm(F q) × M( n × l; Eq) → Fnm(F q)
( f , A) → Γ A( f )
where Γ A( f ) is defined for every x ∈ F m
q and i ∈ { 1, ..., n} by
Γ A( f )( x) i := f 1( x) Ai 1... fl( x) Ail
We denote the mapping Γ A( f ) ∈ Fnm(F q) simply A f .
Remark 58. Let l = m, id ∈ Fm
m (F q) be the identity map (i.e. idi ( x) = xi ∀ i ∈ { 1, ..., m}) and
A ∈ M( n × m; Eq) Then the following relationship between the mapping Aid ∈ Fnm(F q) and any
f ∈ Fm
m (F q) holds
Aid( f ( x)) = A f ( x) ∀ x ∈ F m
q
Remark 59. Consider the case l = m = n. For every monomial dynamical system f ∈ MFnn(F q) ⊂
Fn
n (F q) with corresponding matrix F := Ψ − 1( f ) ∈ M( n × n; Eq) it holds Fid = f . On the other hand, given a matrix F ∈ M( n × n; Eq) we have Ψ − 1( Fid) = F. Moreover, the map Γ : Fnn(F q) ×
M( n × n; Eq) → Fnn(F q) is an action of the multiplicative monoid M( n × n; Eq) on the set Fnn(F q). It holds namely, that 12 I f = f ∀ f ∈ Fnn(F q) (which is trivial) and ( A · B) f = A( B f ) ∀ f ∈ Fnn(F q), A, B ∈ M( n × n; Eq). To see this, consider
n
(( A · B) f ) i( x) = f 1( x)( A·B) i 1... fn( x)( A·B) in = ∏ fj( x)( Ai 1 •B 1 j⊕... ⊕Ain•Bnj) j=1
= ( Aid ◦ Bid) i( f ( x)) = ( Aid) i( Bid( f ( x)))
= ( Aid) i( f B( x)) = ( A( B f )) i( x)
where id ∈ Fnn(F q) is the identity map (i.e. idi( x) = xi ∀ i ∈ { 1, ..., n}). (cf. with the proof of Theorem 29). As a consequence, MFn
n (F q) is the orbit in Fn
n (F q) of id under the monoid M( n × n; Eq). In
particular (see Theorem 29), we have
( F · G) id = F( Gid) = f ◦ g
12 I ∈ M( n × n; Eq) denotes the identity matrix.
Discrete Time Systems with Event-Based Dynamics:
Recent Developments in Analysis and Synthesis Methods
471
where g ∈ MFnn(F q) is another monomial dynamical system with corresponding matrix G :=
Ψ − 1( g) ∈ M( n × n; Eq).
Lemma 60. Let F q be a finite field, n ∈ N a natural number and m ∈ N0 a nonnegative integer.
(
Furthermore, let id ∈ F n+ m)
( n+ m) (F q) be the identity map (i.e. idi( x) = xi ∀ i ∈ { 1, ..., n + m}) and
g : F nq × F mq → F nq a monomial control system over Fq. Then there are matrices A ∈ M( n × n; Eq) and B ∈ M( n × m; Eq) such that
(( A|B) id)( x, u) = g( x, u) ∀ ( x, u) ∈ F nq × F mq where ( A|B) ∈ M( n × ( n + m); Eq) is the matrix that results by writing A and B side by side. In this sense we denote g as the monomial control system ( A, B) with n state variables and m control inputs.
Proof. This follows immediately from the previous definitions.
Remark 61. If the matrix B ∈ M( n × m; Eq) is equal to the zero matrix, then g is called a control
system with no controls. In contrast to linear control systems (see the previous sections and also
Sontag (1998)), when the input vector u ∈ F m
q satisfies
u = 1 := (1, ..., 1) t ∈ F m
q
then no control input is being applied on the system, i.e. the monomial dynamical system over F q
σ : F nq → F nq
x → g( x, 1)
satisfies
σ( x) = (( A| 0) id)( x, u) ∀ ( x, u) ∈ F nq × F mq where 0 ∈ M( n × m; Eq) stands for the zero matrix.
Definition 62. Let F q be a finite field and n, m ∈ N natural numbers. A monomial feedback
controller is a mapping
f : F nq → F mq
such that for every i ∈ { 1, ..., m} there is a tuple ( Fi 1, ..., Fin) ∈ Enq such that
fi( x) = xFi 1...
1
xFin
n
∀ x ∈ F nq
Remark 63. We exclude in the definition of monomial feedback controller the possibility that one of the
functions fi is equal to the zero function. The reason for this will become apparent in the next remark
(see below).
Now we are able to formulate the first control theoretic problem to be addressed in this section:
Problem 64. Let F q be a finite field and n, m ∈ N natural numbers. Given a monomial control system g : F nq × F mq → F nq with completely observable state, design a monomial state feedback controller f : F nq → F mq such that the closed-loop system
h : F nq → F nq
x → g( x, f ( x))
472
Discrete Time Systems
has a desired period number and cycle structure of its phase space. What properties has g to fulfill for
this task to be accomplished?
Remark 65. Note that every component
hi : F nq → F q, i = 1, ..., n
x → gi( x, f ( x))
is a nonzero monic monomial function, i.e. the mapping h : F nq → F nq is a monomial dynamical system
over F q. Remember that we excluded in the definition of monomial feedback controller the possibility
that one of the functions fi is equal to the zero function. Indeed, the only effect of a component fi ≡ 0
in the closed-loop system h would be to possibly generate a component hj ≡ 0. As explained in Remark
28 of Section 3.1, this component would not play a crucial role determining the long term dynamics of
h.
Due to the monomial structure of h, the results presented in Section 3.1 of this chapter can be used to
analyze the dynamical properties of h. Moreover, the following identity holds
h = ( A + B · F) id
where F ∈ M( m × n; Eq) is the corresponding matrix of f (see Remark 30), ( A, B) are the matrices in Lemma 60 and id ∈ Fnn(F q) . To see this, consider the mapping
μ : F mq → F nq
u → g(1, u)
where 1 ∈ F nq. From the definition of g it follows that μ ∈ MFnm(F q) . Now, since f ∈ MFm n (F q), by
Remark 30 we have for the composition μ ◦ f : F nq → F nq
μ ◦ f = ( B · F) id
Now its easy to see
h = ( A + B · F) id
The most significant results proved in Colón-Reyes et al. (2004), Delgado-Eckert (2008)
concern Boolean monomial dynamical systems with a strongly connected dependency graph.
Therefore, in the next section we will focus on the solution of Problem 64 for Boolean
monomial control systems g : F n × F m → F n
2
2
2 with the property that the mapping
σ : F n → F n
2
2
x → g( x, 1)
has a strongly connected dependency graph. Such systems are called strongly dependent
monomial control systems. If we drop this requirement, we would not be able to use Theorems
45 and 46 to analyze h regarding its cycle structure. However, if we are only interested in
forcing the period number of h to be equal to 1, we can still use Theorem 47 (see Remark 48).
This feature will be exploited in Section 3.3, when we study the stabilization problem.
Although the above representation
h = ( A + B · F) id
Discrete Time Systems with Event-Based Dynamics:
Recent Developments in Analysis and Synthesis Methods
473
of the closed loop system displays a striking structural similarity with linear control
systems and linear feedback laws, our approach will completely differ from the well known
"Pole-Assignment" method.
3.3 State feedback controller design for Boolean monomial control systems
Our goal in this section is to illustrate how the loop number, a parameter that, as we
saw, characterizes the dynamic properties of Boolean monomial dynamical systems, can be
exploited for the synthesis of suitable feedback controllers. To this end, we will demonstrate
the basic ideas using a very simple subclass of systems that allow for a graphical elucidation
of the rationale behind our approach. The structural similarity demonstrated in Remark 53
then enables the extension of the results to more general cases. A rigorous implementation of
the ideas developed here can be found in Delgado-Eckert (2009b).
As explained in Remark 53, a Boolean monomial dynamical system with a strongly connected
non-trivial dependency graph can be visualized as a simple cycle of loop-equivalence classes
(see Fig. 1). In the simplest case, each loop-equivalence class only contains one node and
the dependency graph is a closed path. A first step towards solving Problem 64 for strongly
dependent Boolean monomial control systems g : F n × F m → F n
2
2
2 would be to consider the
simpler subclass of problems in which the mapping
σ : F n → F n
2
2
x → g( x, 1)
simply has a closed path of length n as its dependency graph (see Fig. 2 a for an example
in the case n = 6). By the definition of dependency graph and after choosing any monomial
feedback controller f : F n → F m
2
2 , it becomes apparent that the dependency graph of the
closed-loop system
h f : F n → F n
2
2
x → g( x, f ( x))
arises from adding new edges to the dependency graph of σ. Since we assumed that the
dependency graph of σ is just a closed path, adding new edges to it can only generate new
closed paths of length in the range 1, . . . , n − 1. By Corollary 41, we immediately see that the
loop number of the modified dependency graph (i.e., the dependency graph of h f ) must be a
divisor of the original loop number. This result is telling us that no matter how complicated
we choose a monomial feedback controller f : F n → F m
2
2 , the closed loop system h f will
have a dependency graph with a loop number L which divides the loop number L of the
dependency graph of σ. This is all we can achieve in terms of loop number assignment. When a
system allows for assignment to all values out of the set D( L), we call it completely loop number
controllable. We just proved this limitation for systems in which σ has a simple closed path
as its dependency graph. However, due to the structural similarity between such systems
and strongly dependent systems (see Remark 53), this result remains valid in the general case
where σ has a strongly connected dependency graph.
Let us simplify the scenario a bit more and assume that the system g has only one control
variable u (i.e., g : F n × F
2
2 → F n
2 ) and that this variable appears in only one component
function, say gk. As before, assume σ has a simple closed path as its dependency graph. Under
these circumstances, we choose the following monomial feedback controllers: fi : F n → F
2
2,
474
Discrete Time Systems
fi( x) := xi, i = 1, ..., n. When we look at the closed-loop systems
h f : F n → F n
i
2
2
x → g( x, fi( x))
and their dependency graphs, we realize that the dependency graph of h f corresponds to the
i
one of σ with one single additional edge. Depending on the value of i under consideration,
this additional edge adds a closed path of length l in the range l = 1, .., n − 1 to the dependency
graph of σ. In Figures 2 b-e, we see all the possibilities in the case of n = L = 6, except for
l = 1 (self-loop around the kth node).
a
b
c
L = 6
L = 2
L = 3
d
e
f
L = 1
L = 1
L = 1
Fig. 2. Loop number assignment through the choice of different feeback controllers.
We realize that with only one control variable appearing in only one of the components of
the system g, we can set the loop number of the closed-loop system h f to be equal to any
i
of the possible values (out of the set D( L)) by choosing among the feedback controllers fi,
i = 1, ..., n, defined above. This proves that the type of systems we are considering here are
indeed completely loop number controllable. Moreover, as illustrated in Figure 2 f, if the
control variable u would appear in another component function of g, we may loose the loop
number controllability. Again, due to the structural similarity (see Remark 53), this complete
loop number controllability statement is valid for strongly dependent systems.
In the light of Theorem 47 (see Remark 48), for the stabilization13 problem we can consider