Adapting Grammar Inference Techniques to Mine State Machines - Mining Software Specifications: Methodologies and Applications - page 69

Positive traces:
< load;edit;edit;save;close >
< load;edit;save;edit;edit >
< load;close;exit >
< load;edit;save;edit;save >
< load;edit;save;close;exit >
Negative traces:
< load;close;close >
FIGURE 3.4: Prefix Tree Acceptor with added negative trace.
close a file twice in a row). The rectangular state with the dashed transition
leading to it implies that it corresponds to an impossible execution.
Unlike findKPair in algorithm 1, the selectStatePair function does not
simply select the first pair of states that are deemed to be compatible. It
computes a \similarity score" for each pair, and then merges pairs in the order
of their scores (highest to lowest). Given that the initial set of traces contains
traces that are invalid, as well as valid traces, the merge is only accepted if
the resulting machine is compatible with both valid and invalid traces { this
is established by the compatible function.
The similarity score for a pair of states is computed by counting the extent
to which their outgoing paths overlap with each other. The greater the overlap,
the greater the score. Thanks to the availability of negative traces, it is also
possible to rule out state merges if they have a conflicting set of outgoing
paths (i.e., a sequence is deemed to be possible from one state but not from
another). If this is the case, the pair is assigned a score of -1 to prevent a
merge from occurring.
We select some examples to provide an idea of how they are scored. Pair
(b;f) produces the highest score, because their outgoing paths contain the
largest number of overlapping transitions. The scoring process is illustrated
in Figure 3.5; the outgoing paths from both states b and f that overlap are
displayed beside each other. A count of the number of overlapping transitions
gives us a score of 5. On the other hand, pair (b;c) produces a score of 1,