Databases Reference
In-Depth Information
tics proposed in the kTail algorithm that iteratively merges likely equivalent
states [3].
The heuristics adopted by gkTail suggests to merge states that accept
equivalent sets of behaviors up to a maximum length k. The heuristic is based
on the observation that the initial version of the model may include multiple
representations of a same logical state, and merging states with the same
future can expand and generalize the set of behaviors accepted by the model,
likely increasing the model accuracy as well.
More formally, given an EFSA efsa with a set of states S and a state
s 2 S, we dene the k-future(s) as the set of sequences fseq
1
;:::seq
m
g
where seq
i
= f(x
i
1
;P
i
x
1
) ::: (x
i
l
;P
i
x
l
)g such that 9 a transition sequence
(s;x
i
1
;P
i
x
1
;s
1
)(s
1
;x
i
2
;P
i
x
2
;s
2
) ::: (s
l1
;x
i
l
;P
i
x
l
;s
l
) with l k. Figure 2.6 shows
the 2-future of the initial state of the EFSA shown in Figure 2.5.
bookFlight
persons > 0
from = 'MXP','BGY'
...
getCompaniesIterator
return = iterator
1
2
bookFlight
persons = 6
from = 'BDS'
...
getCompaniesIterator
return = iterator
0
41
42
bookFlight
persons = 10
from = 'BGY'
...
getCompaniesIterator
return = iterator
17
18
FIGURE 2.6: The 2-future of the initial state of the EFSA in Figure 2.5.
gkTail modifies the initial EFSA by iteratively merging the states with
an equivalent k-future. gkTail merges states according to three equivalence
criteria: equivalence, weak subsumption, and strong subsumption. Two states
are equivalent if the sequences of events in their k-futures are the same, and the
predicates associated with each pair of corresponding events are equivalent.
Figure 2.7 shows two states that are 2-equivalent in the running example.
Since behavioral models are generated from incomplete traces, merging
only equivalent state may lead to poor generalization, especially in presence of
partial samples, for example, when traces derive from shallow testing. gkTail
proposes also strong and weak subsumption to increase the effectiveness of
generalization even in presence of incomplete samples.
Search WWH ::
Custom Search