    1. Algebra 2. Abstract Automata 3. Abstract Network 4. Partition Pairs and Pair Algebra 5. Construction of an Abstract Network 6. Structured Network 7. Additive Decomposition       7.1. Initial Automaton       7.2. Definition of States in Component Automata       7.3. Set of Input and Output Variables       7.4. Definition of Transition and Output Functions       7.5. Reduced Procedure of Decomposition       7.6. Result of Decomposition       7.7. Applet on Decomposition

7.1. Initial Automaton

Assume that we are given a Mealy type automaton and the partition . To illustrate each step of decomposition with an example, we will use some defined automaton A, and partition  B1 = {1, 2, 3};  B2 = {4, 5, 6}

Let put network N  with n component automata in accordance to pair . The number of component automata is equal to the number of blocks in the partition .
So, in our example there will be two component automata A1 and A2, since there are two blocks (B1 and B2) in the partition .

7.2.  Definition of States in Component Automata

First, define set of states in component automata as: where:
Bm- is the block of the partition,
cm - is the additional state that exist in each component automata.

Let define states of component automata in our example:
C1 = (s1, s2, s3, c1}
C2 = {s4, s5, s6, c2}

7.3. Set of Input and Output Variables

To define inputs and outputs of component automaton let put sets X(Bm), Y(Bm), Gm, Tm, Qm in accordance to each block of the partition :

• X (Bm) is the set of input variables at all transitions from the states of block Bm in the transition table of the automaton A: In our example:
X(B1) = {x1, x2, x6}
X(B2) = {x2, x3, x4, x5}

• Y(Bm) is the set of output variables at all transitions from the states of block Bm in the transition table of the automaton A: In our example:
Y(B1) = (y1, y2, y7, y8, y9}
Y(B2) = {y2, y3, y4, y5, y6, y8, y10}

• Gm is the set of states not included in Bm, from which there are transitions to the states of Bm: In our example:
G1 = {s5, s6}
G2 = {s2, s3}

• Tm is the of states not included in Bm, to which there are transitions from the states of Bm: In our example:
T1 = {s5, s6}
T2 = {s1}

• Qm is the subset of states of Bm, to which there transitions from states not included in Bm (from states of Gm): In our exmple:
Q1 = {s1}
Q2 = {s5, s6}
These sets can be illustrated by the figure: Now we can define the set of input vaiables Xm: Here is the set of additional input variables which connect other component automata with this automaton Am. To define let put the additional input variable wk in accordance to each state in set Qm.  So, the number of elements in is equal to the number of states in Qm: In our example: {w1} {w5, w6}

Similarly, we define the set of output variables Ym: Here is the set of additional output variables which connect the automaton Am with other component automata. To define let put the additional output variable wi in accordance to each state in set Tm. So, the number of elements in is equal to the number of states in Tm: In our example: {w5, w6} {w1}

In other words states Qm and Tm define the sets of additional input ( )  and output ( ):
if then and
if then 7.4. Definition of Transition and Output Functions

Let  be transition in the automaton A. Now we will define transition and output functions in the component automata.
There are two cases possible
a) If (si and sj are states of the same component automaton Am), then  is the transition in component automaton Am

b) If (si and sj are states of two different component automata Am and Ap ). Then, the component automaton Am transits from state si to the additional state cm with the output Yt and additional output wj :  The additional output  wj of the component automaton Am is the input of the component automaton Ap . This input wj produces the transition from the additional state cp to the state sj with the output Y0 in the automaton Ap :  How transitions in automaton A are defined in component automata showed on the figure below: 7.5. Reduced Procedure of Decomposition

The procedure of decomposition can be reduced to:

a) copiying row si, sj , X(si, sj), Y(si, sj) from the table of the automaton A to the table of component automaton Am , if si and sj are the states of Am.
b) the replacement of the row  si, sj,X(si, sj), Y(si, sj) in the table of automaton A by the row  si, cm X(si, sj) Y(si, sj)wi in the table of component automaton Am and the row cp , aj , wj in the table of component automaton Ap, si is the state of Am and sj is the state of Ap; m p.
c) adding row cm, cm to the transition table of component automaton Am.
7.6. Result of Decomposition

As result of decomposition of our sample automaton A we obtain the network N with two component automata A1 and A2 : Also we can build transition tables of each component automaton: Note: If there three or more signals in additional input (output) signals, then it is reasonable to code them by binary values. For example, to variables u1 and u2 are sufficient for coding four inputs wi, wj, wk and . Also zero-number state (s0) may be used to represent additional states (ci)  in each of component automata.

Last update: 3 August, 2004