Exploitation of Flexibility in Sequential Networks - The Unknown Component Problem: Theory and Applications - page 221

We can use this property to make many states immediately equivalent to each
other. 1 A sufficient condition for two different states to be made equivalent is that
their sets of care transitions (i.e. those that go to some accepting state other than
DC1 ), do not intersect. Thus if p 1 and p 2 are the sets of care transitions from states
s 1 and s 2 , respectively, where p 1 ^ p 2 D; ,thens 1 and s 2 can be made equivalent
using the don't cares to extend the care transitions of each of the states, s 1 and s 2 ,
to the set of care transitions described by p 1 C p 2 . For example, if p 2 goes from
s 2 to s, then we can add a transition from s 1 to s because p 2 is a don't-care for s 1 .
Continuing in this manner, we can make two or more states immediately equivalent
because on every input they go to the same next state.
The BALM command dcmin uses this property to build an incompatibility
graph among the states. In this graph, there is an edge s 1 ! s 2 if and only if
p 1 ^ p 2 ¤; . The decision what states to merge is made by applying a minimal
coloring algorithm to the incompatibility graph.
We note that this is just one way of using the flexibility provided by the don't
cares in the solution X and certainly may not be the best way. On the positive
side, command dcmin is fast (because equivalent states are found structurally by
immediate equivalence) and in practice it is quite effective on some examples.
In comparison, other good methods of state minimization may be much more
computationally intensive. We will provide an illustration of the use of dcmin in
the next section.
We illustrate the use of dcmin by continuing the example of Sect. 13.3. We saw
that by exposing internal variables v11 and v12 in S, a relation between states can
be forced. Thus inputs u to the solution automaton planetxs.aut must agree
with the product state in the u variables of F , v11 and v12 . For example, if the
S state had 01 in these positions, then any input u with v11 = 1 or v12 = 0
would be a u input to X that would never occur, and its corresponding transition
would be directed to the accepting don't care state. This is purely due to the fact that
u was exposed as an output of S. Hence, this can be used by dcmin in minimizing
the result, as follows:
dcmin planetxs.aut planetxs-dcmin.aut.
Looking at the relative sizes before and after dcmin , we see it is very effective.
Executing print stats aut planetxs.aut ,before dcmin we would see:
"csf": incomplete (48 st), deterministic,
non-progressive (48 st), and non-Moore (48 st).
13 inputs (13 FSM inputs) 49 states (49 accepting)120
trans
Inputs = {v0,v1,v2,v3,v4,v5,v6,v11,v12,v7,v8,v9,v10}
1 Two states are immediately equivalent if for any input, they produce the same output and go to
the same next state.