Databases Reference
In-Depth Information
Input: (Pos;Neg)
PLTS generateAPTA(Pos;Neg);
1
while (q;q
0
) selectStatePair(PLTS) do
2
PLTS
0
merge(PLTS; (q;q
0
));
3
if compatible(PLTS
0
;Neg) then
4
while query generateQueries(PLTS;PLTS
0
) do
5
counter askOracle(query);
6
if counter 6= then
7
if counter 2 PreL(PLTS
0
) then
8
Neg Neg[counter;
9
else
10
Pos Pos[counter;
11
return QSM(Pos;Neg);
12
else if query 2 PreL(PLTS
0
) then
13
Pos Pos[query;
14
else
15
Neg Neg[query;
16
end
17
end
18
PLTS PLTS
0
;
19
end
20
end
21
return PLTS
22
Algorithm 3: QSM algorithm
state machine (unless the initial set of traces fulfills a particular constraint,
which is discussed below). Nonetheless, it does not rely on exhaustively query-
ing an oracle, and can handle incomplete sets of traces. Consequently, it will
at least provide an approximate model, given an incomplete set of traces and
an oracle that is capable of answering some queries about it.
The QSM algorithm is shown in algorithm 3. When compared to the EDSM
algorithm in algorithm 2, the dierence is the while-loop in lines 5 { 19. Once
a merge has been found to be compatible with Pos and Neg (i.e., all positive
traces are accepted and negative traces are not), a set of membership queries
are generated with the generateQuery function, and are posed to the oracle
by the askOracle function.
The purpose of the queries is to verify that the decision to merge a pair of
states is indeed correct. The generateQuery function achieves this by gener-
ating sequences from the merged machine that do not already belong either
to Pos or Neg. Depending on the answers to the queries, these are added to
one of the two sets. If the answer conflicts with the language of the current
hypothesis PLTS
0
, the inference process is restarted so that it can take into
account the augmented sets Pos and Neg.
Search WWH ::
Custom Search