Connected Automata

As Bérard et al. (2001)[34]:Pp.14ff,Pp.62ff point out, there are many application scenarios where it is to complicated to model a problem as one big automaton. Instead one models several smaller automata and combines these afterwards to one unit. A typical strategy to connect automata is usually the socalled synchronized product, which has been introduced by Maurice Nivat 1979 (cf. Arnold and Nivat (1982) [20] and Arnold (1992) [18]).

This idea is straightforward but has the drawback, that the cartesian product of all sets can blow up the state space beyond practical limits. Another, more conservative approach could be, to restrict the interaction of the different automata strictly to their input output. A good example is the biological brain where billions of neurons are interconnected forming one big automaton.

Let us consider a simple example consisting of four neurons {A, B, C, D} from the McCulloch-Pitts type (cf. McCulloch and Pitts (1943) [195])(cf. figure 5.6).

Figure 5.6: Four connected automata representing McCulloch-Pitts neurons

These four neurons are interconnected. Let us look to every such neuron as a finite automaton of the type of a finite transducer (cf. figure 5.7).

Figure 5.7: Finite transducer (generalized mealy)

A finite transducer has an input tape and an output tape. Every neuron of the McCulloch-Pitts type can be considered as such a finite transducer. All the input neurons together are representing the actual input and the output represents the outgoing axon. A neuron can then be considered as an automaton representing some function $f$ wit $f(input) = output$, where the $input$ as well as the $output$ will be considered as words from the sets $\Sigma^{*}$ (words about the input alphabet $\Sigma$) and $\Xi^{*}$ (words about the output alphabet $\Xi$). We will make the assumption that the output is given at point in time t+1 when the input is given to the automaton at point in time t: output$_{t+1}$ = f(input)$_{t}$. Thus the output at point in time t+1 can be redirected as a new input at time t+1 (cf. figure 5.8).

Figure 5.8: Finite transducer with redirection of output

In the next step we consider the cooperation of two such automata. The output of automata A can be redirected -by the environment E- to the input of the automaton A itself but also to the input of the automaton B, and vice versa. One has only to assume that the input and the output tapes are arranged in sections; one section per transition and every section is subdivided into subsections thus that every participating automaton has one subsection of point in time t for input as well as for output (see figure 5.7). Because the input is assumed to be a string we can assume that the output of different automata can be inserted in one of these input strings constituting different parts $input_{A} = output_{A}\mid output_{B}\mid \cdots \mid output_{X}$.

To formalize this we take two automata $\cal A$ and $\cal B$ with the structure

$$\langle Q, I, F, \Sigma, \Xi, \Delta, \rangle$$

with $\Delta \subseteq Q \times \Sigma^{*} \times Q \times \Xi^{*}$. Thus the output of a finite transducer is a string $\xi \in \Xi^{*}$. Let $out_{A}$ design the output string of automaton $\cal A$ at a certain point of time. Similar let $in_{A}$ design the input of automaton $\cal A$ at a certain point of time. $OUT$ shall be the union of the outputs $out_{i}$ of all automata at a certain point in time t as well as $IN$ shall be the union of the inputs $in_{j}$ of all automata at a certain point in time t. Then we assume a connection (CON) between the participating automata as

$$CON \subseteq out_{i} \times 2^{IN}$$

for all outputs of all automata (cf. general structure by figure 5.7.

Figure 5.9: Two finite transducers with redirection of output

In the example with the four neurons A - D (cf. the example with the four McCulloch-Pitts neurons in figure 5.10) we have neuron A receiving an input from the environment named $S1$. Neuron B is receiving an input $S1$ from the environment as well as an input $S2$ as well as an input from another neuron D. neuron C is receiving inputs from the neurons A and B, and neuron D is receiving inputs from itself as well as from neuron B and some source $F1$.

Figure 5.10: Connected automata inputs illustrated by four neurons

Let us consider an automaton $\cal A$ for a moment as a function $f_{\cal A}(in)= out$. The execution of connected automata can then be formalized as a sequence $\sigma^{+}$ of configurations $\langle \sigma^{+}_{0},\sigma^{+}_{1}, \cdots, \sigma^{+}_{n}\rangle$ where every element $\sigma^{+}_{i}$ consists of two parts: a control part and a connection part.

The control part is the sequence of configuration elements like $\langle (f_{\cal A}, in_{\cal A}), (f_{\cal B}, in_{\cal B}), \cdots \rangle$. This means that at this point in time every participating automaton has some actual input $in$ as argument for the function $f_{\cal A}(in)$. By the definition of the function one can compute the output of the function. New is the connection part as $\langle (\xi_{\cal A},\langle in_{\cal A}, in_{\cal B}, \cdots \rangle), (\xi_{\cal B},\langle in_{\cal A}, in_{\cal B}, \cdots \rangle) \rangle$. Every output is here mapped onto the input of some destination. With $n$-many participating automata would this amount to $n^{2}$ many input fields. But in most practical cases is the mean number of output connections $m$ much much smaller than the number $n$ of participating automata. Let us look to the example of the four interconnected neurons $A, \cdots, D$.

The automata functions are defined as follows:

A(in) =	out
1	1
0	0

B(in) =			out
1	1	1	1
1	1	0	1
1	0	1	1
0	1	1	1
1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	0

C(in) =		out
1	1	1
1	0	1
0	1	1
0	0	0

D(in) =			out
1	1	1	1
1	1	0	1
1	0	1	1
0	1	1	1
1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	0

With these functions one can construct a possible execution as follows:

1. Control: $\langle A(0), B(0,0,0), C(0,0), D(0,0,1) \rangle$
2. Connection: $\langle (out_{A}, \{ in_{B}, in_{C}\}), (out_{B}, \{ in_{C}, in_{D}\}), (out_{D}, \{ in_{D}, in_{B}\}),\rangle$
3. Control: $\langle A(1), B(1,0,0), C(1,0), D(0,0,1) \rangle$
4. Connection: $\cdots$
5. Control: $\langle A(0), B(0,1,0), C(0,0), D(0,0,1) \rangle$
6. Connection: $\cdots$
7. Control: $\langle A(1), B(1,1,0), C(1,1), D(0,1,1) \rangle$
8. Connection: $\cdots$
9. Control: $\langle A(0), B(0,0,1), C(0,0), D(1,1,0) \rangle$
10. Connection: $\cdots$
11. Control: $\langle A(0), B(0,1,1), C(0,1), D(1,1,1) \rangle$
12. Connection: $\cdots$
13. $\cdots$

This execution shows some interesting dynamics in the behavior of these four neurons. There is a change in the observable behavior of this small network which happens after the occurence of S1 and S2 synchronously being '1':

S1	S2	$f_{A} \oplus f_{B} \oplus f_{C} \oplus f_{D}$
1	1	1
1	0	1
0	1	0
0	0	0
1	1	1
1	0	1
0	1	1
0	0	0

This ability that a function can change its behavior during the course of time triggered by some observable event is in psychology and biology usually called learning. In the example we can observe the simplest known case of learning called classical conditioning. From this example follows that the execution protocol of connected automata can be used to document processes which show the property of learning behavior. With appropriate extensions of CTL-specifications and model checking one can then try to explore observable behavior of automata with regard to learning properties.

So far we are using in the execution protocol the abstraction that we take automata as whole units like $f_{\cal A}(in)$ and compute the output $out$ of the whole automata function. Someone could raise the question whether this can bring up a conflict between different automata if these have different numbers of states $\mid Q \mid$ and therefore they have possibly different execution times because the execution time for all participating automata is limited to one cycle $(t, t+1)$.

In the general case one can replace the automata function like $f_{\cal A}(in)$ by a finite list of states where every state is represented by a finite set of lines where every line is written as

$$\langle q, in_{i}, q', out_{j} \rangle$$

where $q$ is the actual state, $in_{i}$ is the actual input, $q'$ is the successor state and $out_{j}$ is the actual output. It is assumed that for every state that there can only exist a finite set of different input strings $in_{i}$ from $\Sigma^{*}$. Thus for every participating automaton we have at a certain point in time t to assume that there is exactly one actual state $q$ with exactly one actual input string $in$ out of a finite set of possible input strings, and from this has the succesor state $q'$ and the output string $out$ to be computed. From this we have to conclude that in the general case there can be no conflict with regard to the duration of the execution of the participating automata.

But assuming k-many participating automata working in parallel one has to consider that the following can happen: (i) one automaton $a_{i}$ reaches a final state before all the other automata reach a final state, or (ii) at least one automaton $a_{j}$ will never reach a final state; it will run infinitely, or (iii) no automaton $a_{i}$ will reach a final state and will run infinitely.

In case (i) where an automaton $a_{i}$ reaches a final state this will be documented in an execution protocol such that from that point in time, where the automaton $a_{i}$ reaches a final state the changes will stop. All values will stay to be fixed. We call this case monotonic finite.

In case (ii) where an automaton $a_{i}$ will never reache a final state this will be documented in an execution protocol such that the execution will not stop and there will no final state show up. We call this case nonmonotonic finite.

In case (iii) where all automata $a_{0}, \cdots, a_{k}$ will never reache a final state this will be documented in an execution protocol such that the execution will not stop in no trace and there will no final state show up. We call this case monotonic infinite.

If one wants to keep the information about all participating automata separated and not unified into one 'big' automaton one can define the following structure:

Def.: A Network of Connected Automata (NCA) is given as a structure of the following kind:

$$\langle A_{1}, \cdots, A_{k}, {\cal C}\rangle$$

with $A_{i}$ as a participating automaton and $\cal C$ as connection relation.

Def.: An Execution of a Network of Connected Automata ( $\sigma^{+}$) is given as a sequence a sequence of configurations $\langle \sigma^{+}_{0},\sigma^{+}_{1}, \cdots, \sigma^{+}_{n}\rangle$ where every element $\sigma^{+}_{i}$ consists of two parts: a control part and a connection part (see above).