Page 275 - Artificial Intelligence for the Internet of Everything
P. 275
Compositional Models for Complex Systems 253
X
choice but to set h(0) ¼ c . Once we have h(0), condition (ii) tells us where
to send 1:
ðiiÞ X X X
hð1Þ¼ hðtð0jÞÞ ¼ t ðhð0ÞÞ ¼ t ðc Þ
Similarly, the value at 1 entails the value at 2, and so on, so that in general we
have no choice but to set
n times
zfflfflfflfflfflfflffl}|fflfflfflfflfflfflffl{
X X X
hðnÞ¼ t ð…t ðt ðc X Þ…Þ
We can tell a similar story about controlled DDS. These are structures in
which we have a set of commands A, and can issue a command to the system
at each timestep. This corresponds to a signature in which we have a con-
stant (initial state) c and several different transition functions t a , one for each
a 2 A. A mapping must preserve the initial state as well as each of the
controlled transitions.
The term algebra for controlled DDS is List(A), the set of lists with
entries from A. The “initial state” is just the empty list hi, and the transition
operations append elements of A to the front of the list. Just as above, a
homomorphism h: List(A) ! X is completely determined by the con-
trolled DDS constraints; for example,
ha 0 ,a 1 ,a 2 i7!t a 0 ðt a 1 ðt a 2 ðc X ÞÞÞ
Rather than treating each element of the signature individually, we can
wrap everything together into one component. First, we use the Cartesian
product to replace the individual mappings t a : X ! X with a single map t :
A X ! X. We can also use a disjoint union to package together the tran-
sition map with the constant, so that entire controlled DDS is represented by
a single map α:1+(A X)!X. Thus the construction FX ¼ 1+ (A X)
encodes the signature of the algebraic theory.
Similarly, the mapping condition for controlled DDS homomorphisms is
expressed by a single square:
1+(A×h)
1+(A × X) 1+(A × Y )
α β
X Y
h