458
J. An et al.
Table 1: Experimental results on random examples for the smart teacher situation.
Case ID |Δ|mean
#Membership
#Equivalence
nmean tmean
Nmin Nmean Nmax Nmin Nmean Nmax
4 4 20
16.3
118 245.0 650
20 30.1 42
4.5 24.7
7 2 10
16.9
568 920.8 1393
23 31.3 37
9.1 14.6
7 4 10
25.7
348 921.7 1296
34 50.9 64
9.3 38.0
7 6 10
26.0
351 634.5 1050
35 44.7 70
7.8 49.6
7 4 20
34.3
411 1183.4 1890
52 70.5 93
9.5 101.7
10 4 20
39.1
920 1580.9 2160
61 73.1 88
11.7 186.7
12 4 20
47.6 1090 2731.6 5733
66 97.4 125
16.0 521.8
14 4 20
58.4 1390 2238.6 4430
79 107.7 135
16.0 515.5
Case ID: n m κ, consisting of the number of locations, the size of the alphabet and the maximum
constant appearing in the clock constraints, respectively, of the corresponding group of A’s.
|Δ|mean: the average number of transitions in the corresponding group.
#Membership & #Equivalence: the number of conducted membership and equivalence queries,
respectively. N min : the minimal, Nmean: the mean, Nmax: the maximum.
nmean: the average number of locations of the learned automata in the corresponding group.
tmean: the average wall-clock time in seconds, including that taken by the learner and the teacher.
correct DOTA H is learned in 155 seconds after 2600 membership queries and 28 equivalence queries. Specifically, H has 15 locations excluding a sink location connected by
28 transitions. The introduction of 4 new locations comes from splitting of guards along
transitions, which however can be trivially merged back with other locations. The figures depicting A and H can be found in Appendix D of [7].
Random examples for a smart teacher. We randomly generated 80 DOTAs in eight
groups, with each group having different numbers of locations, size of alphabet, and
maximum constant appearing in clock constraints. As shown in Table 1, the proposed
learning method succeeds in all cases in identifying a DOTA that recognizes the same
timed language. In particular, the number of membership queries and that of equivalence queries appear to grow polynomially with the size of the problem
4 , and are
much smaller than the worst-case bounds estimated in Sect. 3.5. Moreover, the learned
DOTAs do not have prominent increases in the number of locations (by comparing
n mean with the first component of Case IDs). The average wall-clock time including
both time taken by the learner and by the teacher is recorded in the last column t mean , of
which, however, often over 90% is spent by the teacher for checking equivalences w.r.t.
small T’s while around 50% by the learner for checking the preparedness condition
w.r.t. large T’s.
It is worth noting that all of the results reported above are carried out on an implementation equipped with the accelerating trick discussed in Sect. 3.6. We remark that
when dropping this trick, the average number of membership queries blow up with a
factor of 0.83 (min) to 15.02 (max) with 2.16 in average for all the 8 groups, and 0.84
(min) to 1.71 (max) with 1.04 for the average number of equivalence queries, leading
to dramatic increases also in the computation time (including that in operating tables).
4 An exception w.r.t. the group 7 6 10 is due to relatively simple DOTAs generated occasionally.
J. An et al.
Table 1: Experimental results on random examples for the smart teacher situation.
Case ID |Δ|mean
#Membership
#Equivalence
nmean tmean
Nmin Nmean Nmax Nmin Nmean Nmax
4 4 20
16.3
118 245.0 650
20 30.1 42
4.5 24.7
7 2 10
16.9
568 920.8 1393
23 31.3 37
9.1 14.6
7 4 10
25.7
348 921.7 1296
34 50.9 64
9.3 38.0
7 6 10
26.0
351 634.5 1050
35 44.7 70
7.8 49.6
7 4 20
34.3
411 1183.4 1890
52 70.5 93
9.5 101.7
10 4 20
39.1
920 1580.9 2160
61 73.1 88
11.7 186.7
12 4 20
47.6 1090 2731.6 5733
66 97.4 125
16.0 521.8
14 4 20
58.4 1390 2238.6 4430
79 107.7 135
16.0 515.5
Case ID: n m κ, consisting of the number of locations, the size of the alphabet and the maximum
constant appearing in the clock constraints, respectively, of the corresponding group of A’s.
|Δ|mean: the average number of transitions in the corresponding group.
#Membership & #Equivalence: the number of conducted membership and equivalence queries,
respectively. N min : the minimal, Nmean: the mean, Nmax: the maximum.
nmean: the average number of locations of the learned automata in the corresponding group.
tmean: the average wall-clock time in seconds, including that taken by the learner and the teacher.
correct DOTA H is learned in 155 seconds after 2600 membership queries and 28 equivalence queries. Specifically, H has 15 locations excluding a sink location connected by
28 transitions. The introduction of 4 new locations comes from splitting of guards along
transitions, which however can be trivially merged back with other locations. The figures depicting A and H can be found in Appendix D of [7].
Random examples for a smart teacher. We randomly generated 80 DOTAs in eight
groups, with each group having different numbers of locations, size of alphabet, and
maximum constant appearing in clock constraints. As shown in Table 1, the proposed
learning method succeeds in all cases in identifying a DOTA that recognizes the same
timed language. In particular, the number of membership queries and that of equivalence queries appear to grow polynomially with the size of the problem
4 , and are
much smaller than the worst-case bounds estimated in Sect. 3.5. Moreover, the learned
DOTAs do not have prominent increases in the number of locations (by comparing
n mean with the first component of Case IDs). The average wall-clock time including
both time taken by the learner and by the teacher is recorded in the last column t mean , of
which, however, often over 90% is spent by the teacher for checking equivalences w.r.t.
small T’s while around 50% by the learner for checking the preparedness condition
w.r.t. large T’s.
It is worth noting that all of the results reported above are carried out on an implementation equipped with the accelerating trick discussed in Sect. 3.6. We remark that
when dropping this trick, the average number of membership queries blow up with a
factor of 0.83 (min) to 15.02 (max) with 2.16 in average for all the 8 groups, and 0.84
(min) to 1.71 (max) with 1.04 for the average number of equivalence queries, leading
to dramatic increases also in the computation time (including that in operating tables).
4 An exception w.r.t. the group 7 6 10 is due to relatively simple DOTAs generated occasionally.