Mining Finite-State Automata with Annotations - Mining Software Specifications: Methodologies and Applications - page 50

these thresholds). If more than 10 symbols are used to rewrite a data clus-
ter, KLFA simply ignores the attributes and work by considering the events
without their attributes.

2.5.2 Generating Models
The rewritten traces are traces of event names where the attributes are
implicitly represented as part of the event labels. Thus, we can generate models
with classic engines to infer automata from traces.
The current KLFA prototype uses the KBehavior incremental inference
engine to infer automata [20]. At each step, KBehavior reads a trace and
updates the current FSA according to the content of the trace. The updated
FSA generates all the traces that have been analyzed.

next_A4_B0

hasNext

0 1 2

next_A0_B0

hasNext

3

4

getAvailableSeats_A1

add_A1_B1

FIGURE 2.11: An example FSA extended with a new trace.

Given a new trace, KBehavior extends the current FSA by identifying
sub-machines in the current FSA that generate sub-sequences in the input
trace, and suitably connecting them to accept the new trace. For example,
Figure 2.11 shows how kBehavior extends a FSA according to the new trace
shown in Table 2.5. State 0 is the initial state of the automaton, while State
4 is the final state. Events from 1 to 9 in the table are accepted by the given
automaton up to state 1, while event 10, nextA4B0 , is not accepted by
any submachine. Since events 11 to 13 are accepted from state 2, kBehavior
extends the automaton with a new branch from state 1 to state 2.
Figure 2.12 shows the automaton that KLFA derives from the traces
recorded during the execution of the running example. For brevity the model
includes only the attributes reported in the traces of Figure 2.2.
The automaton in Figure 2.12 suitably represents data-flow information.
For example, KLFA used the relative to instantiation strategy to rewrite the