Empirical Evaluation of "Automated Termination Analysis for Logic Programs by Term Rewriting"

In the paper Automated Termination Analysis for Logic Programs by Term Rewriting we present a novel non-termination preserving transformation from logic programs to term rewriting systems. In our experiments, we want to assess the power of our new transformational method compared to direct approaches and to the classical transformational method for well-moded logic programs.

Implementation in AProVE

We integrated our approach in the termination tool AProVE which implements the DP framework. It can be accessed via its web interface.

Tools

We compare our implementation of the new method with three other representative tools for termination analysis of logic programs. Thus, in our experiments we use the following four tools:

AProVE 2.0-prealpha1:
This is a pre-alpha version of AProVE 2.0 which is available through our web interface.
cTI 1.1pre1:
The cTI Termination Inference Engine implements a direct approach. Thanks to Roberto Bagnara we were able to use cTI 1.1pre1 in combination with the Parma Polyhedra library 0.8. We allowed 5 iterations before widening (-n 5).
TerminWeb 1.1:
The TerminWeb termination analyser also implements a direct approach. Thanks to Samir Genaim and Michael Codish we were able to run TerminWeb locally without interaction using a combination of the termsize (edges) and the list-length norm.
TALP:
The TALP system is a frontend to CiME implementing the classical transformational approach for well-moded logic programs. Enno Ohlebusch kindly provided us with the frontend. As a backend we used the most current version of CiME, CiME 2.02.

Examples

Our example collection consists of three parts. The first 151 examples (directory "TPDB05") are taken from the logic programming section of the Termination Problem Data Base (TPDB05). This is the collection of problems used in the annual termination competition.

The next 86 examples are taken from the experimental evaluation of the paper Termination Analysis of Logic Programs through Combination of Type-Based Norms by Maurice Bruynooghe, Michael Codish, John Gallagher, Samir Genaim and Wim Vanhoof (directory "toplas").

In order to evaluate the behavior of our new transformation as well as of our implementation we collected and adapted 59 further examples (directory "SGST06"). In particular, we also included examples to exhibit the limitations of our approach. Whenever it was possible, we mentioned the source of the example. Thus, in total there are 296 examples.

To eliminate the influence of the translation from Prolog to logic programs, we removed all examples from the collections that use non-trivial built-in predicates or that are not definite logic programs after ignoring the cut operator. This was necessary as all four tools handle unknown predicates differently. TALP just removes atoms containing unknown predicates, thereby assuming that they always terminate and succeed. cTI assumes finite failure for all unknown predicates. TerminWeb throws an error when encountering unknown predicates. AProVE handles some built-ins by translation, others by removal. Where possible, atoms containing trivial predicates like write and nl were simply removed from the bodies of the clauses.

Limitations

Our experiments also contain examples which demonstrate the limitations of our approach. Of course, our implementation in AProVE usually fails if there are features outside of pure logic programming (e.g., built-in predicates, negation as failure, etc.). But in the following, we tackle the question where the approach fails for pure logic programming. In principle, there could be three points where it fails:

The transformation of Thm. 14 could fail, i.e., there could be a logic program which is terminating for the set of queries, but not all corresponding terms are terminating in the transformed TRS. We do not know of any such example and it could be that this step is indeed complete.

The approach via dependency pairs (Thm. 18) can fail to prove termination of the transformed TRS, although the TRS is terminating. In particular, this can happen because of the variable condition required for Thm. 18. This is demonstrated by the following example (SGST06/incomplete.pl):

p(X) :- q(f(Y)), p(Y).
p(g(X)) :- p(X).
q(g(Y)).

The resulting TRS R is:

p_in(X) -> u1(q_in(f(Y)),X)
u1(q_out(f(Y)),X) -> u2(p_in(Y),X,Y)
u2(p_out(Y),X,Y) -> p_out(X)
p_in(g(X)) -> u3(p_in(X),X)
u3(p_out(X),X) -> p_out(g(X))
q_in(g(Y)) -> q_out(g(Y))

Let us regard all queries p(t) where t is ground. Looking at the logic program, it is obvious that they are all terminating. However, there is no argument filtering pi such that pi(R) satisfies the variable condition and such that f(t1,...,tn) is terminating for all terms where pi(f(t1,...,tn)) is finite and ground and where t1,...,tn are constructor terms.
To see this, note that in order to satisfy the variable condition in the TRS, due to the first rule we need to filter away the first argument of u1, q_in, or f.
If we filter away the first argument of u1 or the argument of f, then we also have to filter away the argument of p_in due to the second rule. Thus, we would have to prove termination of the TRS also for terms like p_in(g(g(...))) where p_in contains an infinite argument. But this term is not terminating.
Otherwise, let us filter away the argument of q_in. If we would also filter away the argument of q_out, we would result in the same contradiction as above. So in order to avoid filtering q_out, we have to filter away the argument of g (due to the last rule of the TRS). But then, we again would have to prove termination of the TRS also for terms like p_in(g(g(...))) which are not terminating.
Finally, it can happen that the resulting DP-problem of Thm. 18 is finite, but that our implementation fails to prove it. The reason can be that one should apply other DP processors or DP processors with other parameters. After all, finiteness of DP-problems is undecidable. This is shown by the following example (SGST06/incomplete2.pl):

f(X) :- g(s(s(s(X)))).
f(s(X)) :- f(X).
g(s(s(s(s(X))))) :- f(X).

Termination can (for example) be proved if one uses a polynomial order with coefficients from {0,1,2,3}. But the current automation does not use such polynomials and therefore it fails.

Experiments

For each example we used a time limit of 60 seconds. This corresponds to the way that tools were evaluated in the annual competitions for termination tools. The computer used was an AMD Athlon 64 at 2.2 GHz running Sun's J2SE 1.5.0 under GNU/Linux 2.6.14 which is similar in speed to the computer used in the 2005 competition.

In the first table, we give the number of examples where termination could be proved ("YES"), where the tools could not prove termination within the time limit of 60 seconds ("MAYBE"), and where the proof failed due to a time-out ("KILLED"). In square brackets, we give the average runtime (in seconds) needed where the tool could prove termination and where it failed in proving termination within the time limit. Clicking on the runtimes in the big table below leads to the detailed proof output by the corresponding tool. Clicking on the names of the examples leads to files containing them.

The comparison of AProVE and TALP shows that our approach improves significantly upon the previous transformational method that TALP is based on. In particular, TALP fails for all non-well-moded programs.

The comparison with cTI and TerminWeb demonstrates that our new transformational approach is comparable in power to direct approaches. But the second table below shows that there is a substantial set of programs where AProVE succeeds and direct tools fail and there is also a substantial set of examples where direct tools succeed and AProVE fails. Here, "AProVE \ cTI" is the number of examples where AProVE succeeds and cTI fails, "AProVE \ (cTI + TerminWeb)" is the number of examples where AProVE succeeds and neither cTI nor TerminWeb can prove termination, etc. But of course, cTI and TerminWeb (and other direct termination tools for logic programs) offer many additional features that are currently not supported by AProVE (e.g., termination inference, non-termination proving, and better handling of pre-defined predicates, of built-in integers, of cuts and negation, etc.).

Tool YES MAYBE TIMEOUT

AProVE 208 [3.9] 68 [15.1] 20

cTI 167 [0.1] 129 [0.0] 0

TerminWeb 178 [0.5] 117 [0.6] 1

TALP 163 [2.5] 112 [1.4] 21

Tool	YES	MAYBE	TIMEOUT
AProVE	208 [3.9]	68 [15.1]	20
cTI	167 [0.1]	129 [0.0]	0
TerminWeb	178 [0.5]	117 [0.6]	1
TALP	163 [2.5]	112 [1.4]	21

AProVE \ cTI AProVE \ TerminWeb AProVE \ (cTI + TerminWeb) cTI \ AProVE TerminWeb \ AProVE (cTI + TerminWeb) \ AProVE

57 46 36 16 16 18

AProVE \ cTI	AProVE \ TerminWeb	AProVE \ (cTI + TerminWeb)	cTI \ AProVE	TerminWeb \ AProVE	(cTI + TerminWeb) \ AProVE
57	46	36	16	16	18

Example	AProVE		cTI		TerminWeb		TALP
TPDB05/lpexamples/ackermann-ioi.pl	KILLED	60.00	MAYBE	0.02	MAYBE	0.34	MAYBE	0.33
TPDB05/lpexamples/ackermann.pl	YES	3.01	MAYBE	0.03	YES	0.30	YES	0.72
TPDB05/lpexamples/average-ioi.pl	YES	2.29	YES	0.01	YES	0.90	YES	0.33
TPDB05/lpexamples/average.pl	YES	2.73	YES	0.02	MAYBE	1.01	YES	1.03
TPDB05/lpexamples/log2a-oi.pl	MAYBE	13.14	MAYBE	0.03	MAYBE	0.11	MAYBE	0.73
TPDB05/lpexamples/log2a.pl	YES	4.19	YES	0.03	MAYBE	0.10	KILLED	60.00
TPDB05/lpexamples/log2b-oi.pl	MAYBE	14.04	MAYBE	0.05	MAYBE	1.17	MAYBE	0.31
TPDB05/lpexamples/log2b.pl	YES	3.08	YES	0.03	MAYBE	1.09	YES	0.37
TPDB05/lpexamples/mapcolor.pl	MAYBE	27.36	MAYBE	0.03	MAYBE	0.22	MAYBE	0.27
TPDB05/lpexamples/mergesort-oi.pl	KILLED	60.00	MAYBE	0.04	MAYBE	0.18	MAYBE	0.23
TPDB05/lpexamples/mergesort.pl	KILLED	60.00	MAYBE	0.04	MAYBE	0.18	KILLED	60.00
TPDB05/lpexamples/shapes.pl	YES	4.86	MAYBE	0.04	MAYBE	0.19	MAYBE	0.28
TPDB05/talp/apt/SS_map.pl	MAYBE	15.83	MAYBE	0.03	MAYBE	0.16	MAYBE	0.46
TPDB05/talp/apt/SS_map_out.pl	MAYBE	19.18	MAYBE	0.04	MAYBE	0.26	MAYBE	41.16
TPDB05/talp/apt/SS_map_t.pl	MAYBE	30.51	MAYBE	0.03	MAYBE	0.17	MAYBE	0.48
TPDB05/talp/apt/append.pl	YES	2.40	YES	0.02	YES	0.14	YES	0.46
TPDB05/talp/apt/fold.pl	YES	2.44	YES	0.01	YES	0.08	YES	0.34
TPDB05/talp/apt/list.pl	YES	1.92	YES	0.00	YES	0.07	YES	0.35
TPDB05/talp/apt/lte.pl	YES	2.54	YES	0.02	YES	0.08	YES	0.25
TPDB05/talp/apt/map.pl	YES	2.29	YES	0.01	YES	0.06	YES	0.29
TPDB05/talp/apt/map1.pl	YES	2.02	YES	0.00	YES	0.07	MAYBE	0.23
TPDB05/talp/apt/member.pl	YES	2.20	YES	0.00	YES	0.07	YES	0.27
TPDB05/talp/apt/mergesort.pl	KILLED	60.00	MAYBE	0.06	MAYBE	0.29	KILLED	60.00
TPDB05/talp/apt/mergesort_ap.pl	KILLED	60.00	MAYBE	0.07	MAYBE	0.54	MAYBE	0.23
TPDB05/talp/apt/naive_rev-oi.pl	MAYBE	13.50	MAYBE	0.02	MAYBE	0.13	MAYBE	0.31
TPDB05/talp/apt/naive_rev.pl	YES	2.64	YES	0.00	YES	0.11	YES	0.39
TPDB05/talp/apt/ordered.pl	YES	3.01	YES	0.01	YES	0.10	YES	0.35
TPDB05/talp/apt/overlap.pl	YES	3.12	YES	0.02	YES	0.10	YES	0.27
TPDB05/talp/apt/permutation.pl	YES	5.71	YES	0.03	YES	0.15	YES	0.34
TPDB05/talp/apt/quicksort-oi.pl	KILLED	60.00	MAYBE	0.06	MAYBE	1.05	MAYBE	0.26
TPDB05/talp/apt/quicksort.pl	YES	9.66	YES	0.07	YES	1.03	YES	33.76
TPDB05/talp/apt/select.pl	YES	2.50	YES	0.01	YES	0.10	YES	0.25
TPDB05/talp/apt/select1.pl	YES	1.94	YES	0.01	YES	0.09	YES	0.34
TPDB05/talp/apt/subset.pl	YES	2.87	YES	0.02	YES	0.13	YES	0.30
TPDB05/talp/apt/subset1.pl	MAYBE	13.03	MAYBE	0.02	MAYBE	0.11	MAYBE	3.50
TPDB05/talp/apt/sum.pl	YES	2.01	YES	0.01	YES	0.08	YES	0.27
TPDB05/talp/az/flat-oi.pl	MAYBE	13.61	MAYBE	0.02	MAYBE	0.10	MAYBE	0.21
TPDB05/talp/az/flat.pl	YES	3.05	MAYBE	0.01	MAYBE	0.10	YES	0.42
TPDB05/talp/az/p.pl	YES	3.05	YES	0.01	YES	0.07	YES	0.50
TPDB05/talp/az/perm.pl	YES	4.25	YES	0.02	YES	0.14	YES	0.31
TPDB05/talp/dds/append.pl	YES	2.35	YES	0.02	YES	0.10	YES	0.28
TPDB05/talp/dds/dis_con-bis.pl	YES	2.36	YES	0.02	YES	0.08	YES	0.46
TPDB05/talp/dds/dis_con.pl	YES	2.49	YES	0.02	YES	0.08	YES	0.24
TPDB05/talp/dds/duplicate.pl	YES	2.23	YES	0.01	YES	0.07	YES	0.28
TPDB05/talp/dds/merge.pl	YES	4.70	YES	0.03	YES	0.19	YES	0.40
TPDB05/talp/dds/permute.pl	YES	2.77	YES	0.02	YES	0.10	YES	0.27
TPDB05/talp/dds/reverse-iio.pl	YES	1.97	YES	0.01	YES	0.08	YES	0.25
TPDB05/talp/dds/reverse.pl	YES	2.38	YES	0.01	YES	0.09	YES	0.45
TPDB05/talp/dds/sum-ioi.pl	YES	3.04	YES	0.04	YES	0.13	YES	0.47
TPDB05/talp/dds/sum.pl	YES	3.04	YES	0.03	YES	0.15	YES	0.50
TPDB05/talp/maria/fib_t.pl	YES	3.29	YES	0.03	YES	0.48	YES	0.36
TPDB05/talp/maria/hanoiapp.suc.pl	YES	5.44	YES	0.05	YES	0.44	YES	11.42
TPDB05/talp/maria/zebra.pl	YES	6.45	YES	0.05	YES	0.21	MAYBE	0.32
TPDB05/talp/naomil/ack.pl	YES	2.25	MAYBE	0.01	YES	0.32	YES	0.47
TPDB05/talp/naomil/queens.pl	YES	4.79	YES	0.05	YES	0.33	YES	26.09
TPDB05/talp/naomil/reverse.pl	YES	2.04	YES	0.01	YES	0.09	YES	0.24
TPDB05/talp/naomil/sicstus1.pl	YES	2.59	YES	0.03	YES	0.14	YES	0.26
TPDB05/talp/plumer/mergesort_t.pl	KILLED	60.00	YES	0.08	MAYBE	0.34	KILLED	60.00
TPDB05/talp/plumer/pl1.1.pl	MAYBE	12.48	MAYBE	0.02	MAYBE	0.11	MAYBE	0.28
TPDB05/talp/plumer/pl1.2.pl	YES	3.91	YES	0.04	YES	0.17	YES	0.34
TPDB05/talp/plumer/pl1.2_t.pl	YES	6.16	YES	0.03	YES	0.17	YES	0.66
TPDB05/talp/plumer/pl2.3.1.pl	YES	2.18	MAYBE	0.01	MAYBE	0.05	YES	0.25
TPDB05/talp/plumer/pl3.1.1.pl	MAYBE	13.10	MAYBE	0.01	MAYBE	0.06	MAYBE	0.27
TPDB05/talp/plumer/pl3.5.6.pl	MAYBE	12.76	MAYBE	0.01	MAYBE	0.06	MAYBE	21.01
TPDB05/talp/plumer/pl3.5.6a.pl	MAYBE	12.97	MAYBE	0.01	YES	0.07	MAYBE	20.41
TPDB05/talp/plumer/pl4.0.1-oooi.pl	MAYBE	13.08	MAYBE	0.02	MAYBE	0.11	MAYBE	0.33
TPDB05/talp/plumer/pl4.0.1.pl	YES	2.65	YES	0.01	YES	0.09	YES	0.31
TPDB05/talp/plumer/pl4.4.3.pl	YES	3.44	YES	0.03	YES	0.22	YES	0.32
TPDB05/talp/plumer/pl4.4.6a.pl	YES	2.78	YES	0.01	YES	0.10	YES	0.33
TPDB05/talp/plumer/pl4.5.2.pl	MAYBE	14.05	MAYBE	0.03	MAYBE	0.17	KILLED	60.00
TPDB05/talp/plumer/pl4.5.3a.pl	MAYBE	12.62	MAYBE	0.01	MAYBE	0.07	MAYBE	0.29
TPDB05/talp/plumer/pl4.5.3b.pl	MAYBE	12.20	MAYBE	0.00	MAYBE	0.05	MAYBE	0.23
TPDB05/talp/plumer/pl4.5.3c.pl	MAYBE	13.07	MAYBE	0.00	MAYBE	0.05	MAYBE	0.19
TPDB05/talp/plumer/pl5.2.2.pl	KILLED	60.00	MAYBE	0.09	MAYBE	0.26	KILLED	60.00
TPDB05/talp/plumer/pl6.1.1.pl	YES	9.95	YES	0.05	MAYBE	1.33	YES	31.43
TPDB05/talp/plumer/pl7.2.9.pl	YES	2.71	YES	0.01	YES	0.11	YES	0.34
TPDB05/talp/plumer/pl7.6.2a.pl	MAYBE	13.18	MAYBE	0.02	MAYBE	0.12	MAYBE	22.71
TPDB05/talp/plumer/pl7.6.2b.pl	MAYBE	13.30	MAYBE	0.02	MAYBE	0.16	KILLED	60.00
TPDB05/talp/plumer/pl7.6.2c.pl	YES	5.38	YES	0.03	YES	0.20	YES	6.99
TPDB05/talp/plumer/pl8.2.1.pl	KILLED	60.00	MAYBE	0.06	MAYBE	0.36	KILLED	60.00
TPDB05/talp/plumer/pl8.2.1a.pl	YES	12.96	YES	0.05	MAYBE	0.30	KILLED	60.00
TPDB05/talp/plumer/pl8.3.1.pl	KILLED	60.00	MAYBE	0.05	MAYBE	0.31	KILLED	60.00
TPDB05/talp/plumer/pl8.3.1a.pl	YES	6.37	YES	0.04	YES	0.26	YES	32.42
TPDB05/talp/plumer/pl8.4.1.pl	YES	2.46	YES	0.00	YES	0.07	YES	0.24
TPDB05/talp/plumer/pl8.4.2.pl	YES	3.96	YES	0.04	YES	0.21	YES	0.32
TPDB05/talp/taboch/bad_sublist.pl	MAYBE	13.37	MAYBE	0.02	MAYBE	0.14	MAYBE	0.31
TPDB05/talp/taboch/mergesort.pl	KILLED	60.00	MAYBE	0.06	MAYBE	0.28	KILLED	60.00
TPDB05/talp/taboch/permute1.pl	YES	4.15	YES	0.04	YES	0.19	YES	0.33
TPDB05/talp/taboch/qicksort.pl	YES	14.15	YES	0.06	YES	1.09	YES	32.06
TPDB05/talp/taboch/rotate.pl	YES	3.38	YES	0.02	YES	0.15	YES	0.32
TPDB05/talp/taboch/sameleaves.pl	YES	4.49	YES	0.02	YES	0.13	YES	0.49
TPDB05/talp/taboch/sublist.pl	YES	3.28	YES	0.02	YES	0.12	YES	0.37
TPDB05/talp/taboch/sublist1.pl	YES	2.15	YES	0.02	YES	0.09	YES	0.25
TPDB05/talp/talp/append.pl	YES	2.71	YES	0.02	YES	0.17	YES	0.32
TPDB05/talp/talp/binary.pl	YES	6.26	YES	2.08	YES	8.02	YES	0.77
TPDB05/talp/talp/binary2.pl	YES	6.65	YES	2.08	YES	8.07	YES	0.60
TPDB05/talp/talp/binary3.pl	YES	7.20	YES	2.09	YES	8.14	YES	0.66
TPDB05/talp/talp/binary4.pl	MAYBE	18.63	MAYBE	2.15	MAYBE	7.90	MAYBE	0.29
TPDB05/talp/talp/div.pl	YES	3.74	YES	0.04	YES	0.13	YES	0.41
TPDB05/talp/talp/evaluate.pl	YES	4.62	YES	0.07	YES	0.22	YES	0.38
TPDB05/talp/talp/example1.pl	YES	2.02	MAYBE	0.00	MAYBE	0.06	MAYBE	0.25
TPDB05/talp/talp/example4-2.pl	MAYBE	12.27	MAYBE	0.00	MAYBE	0.06	MAYBE	0.27
TPDB05/talp/talp/example4.pl	YES	2.29	YES	0.01	YES	0.05	YES	0.25
TPDB05/talp/talp/flat.pl	YES	2.60	MAYBE	0.01	MAYBE	0.10	YES	0.26
TPDB05/talp/talp/gcd.pl	YES	34.28	YES	0.04	YES	1.69	KILLED	60.00
TPDB05/talp/talp/nat.pl	YES	4.38	YES	0.05	YES	0.19	YES	0.33
TPDB05/talp/talp/normal.pl	YES	2.94	MAYBE	0.01	MAYBE	0.08	YES	0.27
TPDB05/talp/talp/palindrome.pl	YES	2.98	YES	0.01	YES	0.09	YES	0.31
TPDB05/talp/talp/perm.pl	YES	4.49	YES	0.03	YES	0.12	YES	0.42
TPDB05/talp/talp/permute.pl	YES	3.49	YES	0.02	YES	0.10	YES	0.52
TPDB05/talp/talp/qsort.pl	YES	10.04	YES	0.06	MAYBE	1.04	YES	32.96
TPDB05/talp/talp/reminder-ioi.pl	MAYBE	13.61	YES	0.03	YES	0.13	MAYBE	0.24
TPDB05/talp/talp/reminder.pl	YES	14.63	YES	0.03	YES	0.13	KILLED	60.00
TPDB05/talp/talp/simple.pl	YES	2.08	MAYBE	0.00	MAYBE	0.07	MAYBE	0.34
TPDB05/talp/talp/slowsort-oi.pl	MAYBE	14.16	MAYBE	0.03	YES	0.13	MAYBE	0.21
TPDB05/talp/talp/slowsort.pl	YES	4.43	YES	0.02	YES	0.13	YES	1.20
TPDB05/talp/talp/transitive_closure.pl	YES	2.77	MAYBE	0.00	MAYBE	0.06	YES	0.27
TPDB05/talp/talp/vangelder.pl	YES	8.38	MAYBE	0.07	YES	1.79	KILLED	60.00
TPDB05/terminweb/Size-Change:NJ/NJ1.pl	YES	2.06	YES	0.01	YES	0.10	YES	0.29
TPDB05/terminweb/Size-Change:NJ/NJ2.pl	YES	2.39	YES	0.02	YES	0.54	YES	0.43
TPDB05/terminweb/Size-Change:NJ/NJ3.pl	YES	2.98	MAYBE	0.02	YES	0.34	YES	0.60
TPDB05/terminweb/Size-Change:NJ/NJ4.pl	YES	2.07	YES	0.02	YES	2.73	YES	0.30
TPDB05/terminweb/Size-Change:NJ/NJ5.pl	YES	2.52	MAYBE	0.02	YES	0.71	YES	0.37
TPDB05/terminweb/Size-Change:NJ/NJ6.pl	YES	2.07	YES	0.03	YES	0.14	YES	0.30
TPDB05/terminweb/backwards/append.pl	YES	2.12	YES	0.02	YES	0.09	YES	0.25
TPDB05/terminweb/basic/append-ooi.pl	YES	2.07	YES	0.00	YES	0.09	YES	0.36
TPDB05/terminweb/basic/append.pl	YES	2.40	YES	0.02	YES	0.10	YES	0.35
TPDB05/terminweb/basic/ways.pl	KILLED	60.00	YES	0.05	YES	0.41	KILLED	60.00
TPDB05/terminweb/combination/der.pl	YES	4.84	MAYBE	0.04	MAYBE	0.10	YES	0.48
TPDB05/terminweb/cti/som.pl	YES	2.23	YES	0.02	YES	0.10	MAYBE	0.41
TPDB05/terminweb/old-terminweb/ackerman.pl	YES	2.43	MAYBE	0.02	YES	0.29	YES	0.51
TPDB05/terminweb/old-terminweb/append3-bis.pl	YES	3.50	YES	0.02	YES	0.10	YES	0.31
TPDB05/terminweb/old-terminweb/append3.pl	YES	3.28	YES	0.02	YES	0.14	YES	0.30
TPDB05/terminweb/old-terminweb/balance_tree.pl	YES	3.42	YES	0.14	YES	34.01	MAYBE	0.35
TPDB05/terminweb/old-terminweb/balance_tree2.pl	KILLED	60.00	MAYBE	0.14	MAYBE	35.94	MAYBE	0.21
TPDB05/terminweb/old-terminweb/inorder.pl	YES	2.40	YES	0.02	YES	0.13	YES	0.39
TPDB05/terminweb/old-terminweb/interleave.pl	YES	2.38	YES	0.01	YES	0.10	YES	0.29
TPDB05/terminweb/old-terminweb/permutation1.pl	YES	4.50	YES	0.01	YES	0.15	YES	0.31
TPDB05/terminweb/old-terminweb/permutation2.pl	YES	3.73	YES	0.02	YES	0.11	YES	0.28
TPDB05/terminweb/old-terminweb/reach.pl	YES	3.40	YES	0.02	YES	0.17	YES	7.15
TPDB05/terminweb/old-terminweb/rotate.pl	YES	2.55	YES	0.02	YES	0.10	YES	0.27
TPDB05/terminweb/old-terminweb/sameleaves.pl	YES	4.20	YES	0.02	YES	0.15	YES	0.40
TPDB05/terminweb/old-terminweb/sublist.pl	YES	2.51	YES	0.01	YES	0.10	YES	0.27
TPDB05/terminweb/old-terminweb/sublist0.pl	YES	3.06	YES	0.01	YES	0.10	YES	0.27
TPDB05/terminweb/old-terminweb/sublist_bad.pl	MAYBE	13.02	MAYBE	0.01	MAYBE	0.10	MAYBE	0.22
TPDB05/terminweb/old-terminweb/subset-no.pl	MAYBE	13.27	MAYBE	0.01	MAYBE	0.09	MAYBE	2.95
TPDB05/terminweb/old-terminweb/subset.pl	YES	2.98	YES	0.01	YES	0.08	YES	0.26
TPDB05/terminweb/old-terminweb/untupled_bal_tree.pl	YES	4.24	YES	0.59	KILLED	60.00	MAYBE	0.29
TPDB05/terminweb/type-based/append.pl	YES	2.62	YES	0.01	YES	0.11	YES	0.27
TPDB05/terminweb/type-based/transpose.pl	MAYBE	18.99	YES	0.04	YES	0.29	MAYBE	0.25
TPDB05/terminweb/untupling/preorder_dl.pl	YES	3.35	YES	0.02	YES	0.10	MAYBE	0.22
toplas/ackerman.pl	YES	2.98	MAYBE	0.02	YES	0.35	YES	0.38
toplas/append-bff.pl	YES	2.54	YES	0.01	YES	0.09	MAYBE	0.21
toplas/append-ffb.pl	YES	2.88	YES	0.01	YES	0.08	YES	0.54
toplas/delete-bbf.pl	MAYBE	25.38	YES	0.04	YES	0.22	MAYBE	0.23
toplas/delete-bfb.pl	MAYBE	13.68	YES	0.03	YES	0.22	MAYBE	0.35
toplas/delete-bff.pl	MAYBE	24.59	MAYBE	0.03	MAYBE	0.22	MAYBE	0.23
toplas/delete-fbf.pl	MAYBE	13.98	YES	0.03	YES	0.27	MAYBE	0.27
toplas/delete-ffb.pl	MAYBE	13.74	YES	0.02	YES	0.24	MAYBE	0.26
toplas/delmin-bff.pl	YES	2.72	YES	0.03	YES	0.20	MAYBE	0.25
toplas/delmin-ffb.pl	YES	3.78	YES	0.03	YES	0.28	MAYBE	0.47
toplas/der-bf.pl	YES	3.65	MAYBE	0.03	MAYBE	0.15	YES	0.33
toplas/der-fb.pl	KILLED	60.00	MAYBE	0.03	MAYBE	0.12	MAYBE	0.20
toplas/factor.pl	YES	3.92	MAYBE	0.03	YES	0.12	YES	0.36
toplas/flat-bf.pl	YES	3.16	YES	0.01	YES	0.19	YES	0.36
toplas/flat-fb.pl	KILLED	60.00	MAYBE	0.00	MAYBE	0.13	MAYBE	0.29
toplas/flatlength-bbf.pl	YES	3.47	YES	0.02	YES	0.14	YES	0.26
toplas/flatlength-bfb.pl	YES	3.28	YES	0.02	YES	0.14	MAYBE	0.21
toplas/flatlength-bff.pl	YES	3.43	YES	0.03	YES	0.15	MAYBE	0.21
toplas/flatlength-fbf.pl	MAYBE	13.67	MAYBE	0.02	MAYBE	0.15	MAYBE	14.81
toplas/flatlength-ffb.pl	MAYBE	13.07	MAYBE	0.01	MAYBE	0.15	MAYBE	0.37
toplas/frontier-bf.pl	YES	2.81	YES	0.02	YES	0.12	YES	0.28
toplas/frontier-fb.pl	MAYBE	13.20	MAYBE	0.02	MAYBE	0.17	MAYBE	0.45
toplas/g.pl	MAYBE	14.17	MAYBE	0.02	MAYBE	0.14	MAYBE	0.23
toplas/in-bf.pl	MAYBE	13.07	MAYBE	0.01	MAYBE	0.16	MAYBE	0.25
toplas/in-fb.pl	MAYBE	13.98	YES	0.01	YES	0.13	MAYBE	0.31
toplas/inorder-bf.pl	YES	3.22	YES	0.02	YES	0.13	YES	0.35
toplas/inorder-fb.pl	MAYBE	13.58	MAYBE	0.02	MAYBE	0.12	MAYBE	0.41
toplas/insert-bbf.pl	YES	3.33	YES	0.01	YES	0.21	YES	1.07
toplas/insert-bfb.pl	YES	2.57	YES	0.02	YES	0.21	YES	0.80
toplas/insert-bff.pl	MAYBE	23.52	MAYBE	0.02	MAYBE	0.21	MAYBE	0.24
toplas/insert-fbf.pl	MAYBE	13.74	YES	0.02	YES	0.24	MAYBE	0.22
toplas/insert-ffb.pl	MAYBE	14.16	YES	0.02	YES	0.21	MAYBE	0.23
toplas/length.pl	YES	2.28	YES	0.00	YES	0.10	YES	0.24
toplas/length1.pl	YES	2.78	YES	0.01	YES	0.06	YES	0.25
toplas/less-bf.pl	MAYBE	12.71	YES	0.01	YES	0.08	MAYBE	0.20
toplas/less-fb.pl	YES	1.96	YES	0.01	YES	0.07	YES	0.25
toplas/list.pl	YES	2.03	YES	0.00	YES	0.06	YES	0.25
toplas/map_color.pl	YES	2.76	YES	0.02	YES	0.14	MAYBE	0.28
toplas/maximum-bff.pl	MAYBE	13.63	YES	0.01	YES	0.08	MAYBE	0.23
toplas/maximum-fbf.pl	MAYBE	13.44	YES	0.01	YES	0.08	MAYBE	0.22
toplas/maximum-ffb.pl	YES	2.63	YES	0.01	YES	0.08	YES	0.25
toplas/member-bf.pl	MAYBE	12.85	MAYBE	0.01	MAYBE	0.10	MAYBE	0.22
toplas/member-fb.pl	YES	2.58	YES	0.00	YES	0.07	YES	0.25
toplas/mergesort.pl	KILLED	60.00	MAYBE	0.06	MAYBE	0.28	MAYBE	0.53
toplas/minimum-bf.pl	YES	2.16	YES	0.00	YES	0.07	YES	0.24
toplas/minimum-fb.pl	MAYBE	12.67	MAYBE	0.00	MAYBE	0.11	MAYBE	0.22
toplas/mult.pl	YES	2.70	YES	0.01	YES	0.08	YES	0.25
toplas/naive_reverse-bf.pl	YES	3.73	YES	0.02	YES	0.11	YES	0.28
toplas/naive_reverse-fb.pl	MAYBE	13.34	MAYBE	0.02	MAYBE	0.15	MAYBE	0.21
toplas/numeral.pl	YES	2.29	YES	0.00	YES	0.06	YES	0.35
toplas/ordered.pl	YES	3.50	YES	0.01	YES	0.08	YES	0.27
toplas/p.pl	YES	4.18	MAYBE	0.01	YES	0.10	YES	6.41
toplas/p_nonlin.pl	YES	7.52	MAYBE	0.03	YES	0.17	YES	20.59
toplas/palindrome.pl	YES	2.43	YES	0.01	YES	0.10	YES	0.33
toplas/parse.pl	YES	16.78	MAYBE	0.04	YES	0.24	YES	0.44
toplas/permutation-bf.pl	YES	4.45	YES	0.01	YES	0.16	YES	0.27
toplas/permutation-fb.pl	MAYBE	13.35	MAYBE	0.02	MAYBE	0.13	MAYBE	0.21
toplas/permutation1-fb.pl	YES	3.57	YES	0.01	YES	0.10	YES	0.44
toplas/prefix-bf.pl	YES	2.66	YES	0.01	YES	0.10	MAYBE	0.21
toplas/prefix-fb.pl	YES	2.07	YES	0.01	YES	0.12	YES	0.30
toplas/quicksort-bf.pl	YES	6.46	YES	0.05	YES	0.66	YES	24.73
toplas/quicksort-fb.pl	KILLED	60.00	MAYBE	0.05	MAYBE	0.65	MAYBE	0.30
toplas/reverse-bf.pl	YES	2.25	YES	0.01	YES	0.08	YES	0.25
toplas/reverse-fb.pl	MAYBE	12.59	MAYBE	0.01	MAYBE	0.09	MAYBE	0.25
toplas/search_tree.pl	YES	4.26	YES	0.04	YES	0.20	YES	0.33
toplas/select-bff.pl	MAYBE	12.49	MAYBE	0.01	MAYBE	0.10	MAYBE	0.25
toplas/select-fbf.pl	YES	2.45	YES	0.01	YES	0.09	YES	0.27
toplas/select-ffb.pl	YES	2.15	YES	0.00	YES	0.09	MAYBE	0.25
toplas/slowsort-bb.pl	YES	4.17	YES	0.03	YES	0.19	YES	2.22
toplas/slowsort-bf.pl	YES	4.69	YES	0.05	YES	0.18	YES	0.66
toplas/slowsort-fb.pl	MAYBE	15.16	MAYBE	0.02	MAYBE	0.17	MAYBE	0.35
toplas/sublist-bf.pl	MAYBE	13.46	MAYBE	0.02	MAYBE	0.12	MAYBE	0.23
toplas/sublist-fb.pl	YES	3.69	YES	0.02	YES	0.13	YES	0.28
toplas/subset-bf.pl	MAYBE	13.17	MAYBE	0.01	MAYBE	0.10	MAYBE	0.21
toplas/subset-fb.pl	MAYBE	13.51	MAYBE	0.02	MAYBE	0.09	MAYBE	2.95
toplas/suffix-bf.pl	MAYBE	13.14	MAYBE	0.01	MAYBE	0.13	MAYBE	0.21
toplas/suffix-fb.pl	MAYBE	12.11	MAYBE	0.01	MAYBE	0.11	MAYBE	0.21
toplas/sum-fbf.pl	YES	2.09	YES	0.01	YES	0.08	MAYBE	0.23
toplas/sum-ffb.pl	YES	2.07	YES	0.01	YES	0.09	YES	0.28
toplas/t.pl	YES	3.98	MAYBE	0.01	YES	0.13	MAYBE	0.25
toplas/transpose-bb.pl	YES	2.87	YES	0.03	YES	0.27	YES	0.41
toplas/transpose-bf.pl	MAYBE	24.84	YES	0.04	YES	0.30	MAYBE	0.28
toplas/transpose-fb.pl	YES	4.37	MAYBE	0.03	YES	0.32	YES	10.18
toplas/tree.pl	YES	2.55	YES	0.00	YES	0.06	YES	0.24
toplas/tree_member-bf.pl	MAYBE	12.84	MAYBE	0.00	MAYBE	0.08	MAYBE	0.20
toplas/tree_member-fb.pl	YES	2.37	YES	0.01	YES	0.07	YES	0.28
SGST06/ackermann.pl	YES	2.49	MAYBE	0.03	YES	0.29	YES	0.42
SGST06/ag01.pl	YES	2.53	MAYBE	0.01	MAYBE	0.06	YES	0.27
SGST06/applast.pl	YES	3.47	MAYBE	0.03	YES	0.16	MAYBE	0.26
SGST06/at.pl	YES	2.15	MAYBE	0.01	MAYBE	0.07	YES	0.56
SGST06/avg-bfb.pl	YES	2.51	YES	0.02	YES	0.92	YES	0.24
SGST06/avg.pl	YES	2.67	YES	0.02	MAYBE	0.81	YES	0.25
SGST06/baby91.pl	KILLED	60.00	MAYBE	0.04	MAYBE	0.56	KILLED	60.00
SGST06/bappend.pl	YES	2.78	MAYBE	0.02	YES	0.15	MAYBE	0.22
SGST06/blist.pl	YES	2.67	MAYBE	0.01	YES	0.11	MAYBE	0.21
SGST06/btappend.pl	YES	3.92	MAYBE	0.02	MAYBE	0.10	MAYBE	0.25
SGST06/btapplast.pl	YES	4.61	MAYBE	0.03	MAYBE	0.14	MAYBE	0.26
SGST06/btree.pl	YES	3.47	MAYBE	0.02	MAYBE	0.08	MAYBE	0.23
SGST06/cconfdel.pl	YES	10.36	MAYBE	0.03	MAYBE	0.12	MAYBE	2.94
SGST06/cnfequiv.pl	MAYBE	13.88	MAYBE	0.04	MAYBE	0.13	MAYBE	0.24
SGST06/confdel.pl	YES	5.16	MAYBE	0.02	YES	0.12	MAYBE	0.27
SGST06/convert.pl	YES	2.70	YES	0.03	YES	0.22	YES	0.25
SGST06/countstack.pl	YES	3.28	MAYBE	0.00	MAYBE	0.22	YES	0.24
SGST06/csnake.pl	MAYBE	16.53	MAYBE	0.07	MAYBE	0.33	MAYBE	0.23
SGST06/d.pl	YES	5.05	MAYBE	0.04	MAYBE	0.34	YES	22.18
SGST06/doublehalfpred.pl	KILLED	60.00	MAYBE	0.03	MAYBE	0.10	KILLED	60.00
SGST06/evenodd.pl	YES	3.19	YES	0.01	MAYBE	0.08	YES	0.24
SGST06/factor.pl	YES	3.72	MAYBE	0.02	MAYBE	0.11	YES	0.37
SGST06/flatten.pl	YES	2.29	MAYBE	0.01	MAYBE	0.14	YES	0.32
SGST06/flatten_phd.pl	YES	4.82	MAYBE	0.02	MAYBE	0.31	YES	0.32
SGST06/giesl97.pl	YES	3.17	YES	0.00	YES	0.06	MAYBE	0.20
SGST06/gopher.pl	YES	2.23	MAYBE	0.01	MAYBE	0.06	YES	0.29
SGST06/hbal_tree.pl	KILLED	60.00	MAYBE	0.03	MAYBE	0.08	KILLED	60.00
SGST06/ifdiv.pl	MAYBE	13.50	MAYBE	0.04	MAYBE	0.21	KILLED	60.00
SGST06/ifminus.pl	YES	4.11	MAYBE	0.04	MAYBE	0.14	MAYBE	0.19
SGST06/incomplete.pl	MAYBE	13.91	MAYBE	0.00	MAYBE	0.07	MAYBE	0.46
SGST06/incomplete2.pl	MAYBE	13.03	YES	0.00	MAYBE	0.08	MAYBE	0.58
SGST06/incomplete_variant.pl	YES	1.78	MAYBE	0.00	MAYBE	0.05	MAYBE	0.19
SGST06/intlist.pl	YES	2.92	MAYBE	0.03	MAYBE	0.38	YES	0.27
SGST06/lessleaves.pl	YES	2.62	YES	0.01	YES	0.10	YES	0.31
SGST06/log.pl	YES	3.43	YES	0.02	MAYBE	0.08	YES	0.88
SGST06/mapcolor.pl	MAYBE	32.96	MAYBE	0.02	MAYBE	0.15	MAYBE	0.43
SGST06/p.pl	YES	4.86	MAYBE	0.01	MAYBE	0.07	YES	6.05
SGST06/p_nonlin.pl	YES	6.08	MAYBE	0.02	MAYBE	0.12	YES	20.54
SGST06/palindrome.pl	YES	5.08	YES	0.03	YES	0.15	YES	0.32
SGST06/paper1.pl	YES	2.65	MAYBE	0.01	MAYBE	0.11	MAYBE	0.94
SGST06/paper2.pl	YES	2.83	MAYBE	0.01	MAYBE	0.06	MAYBE	0.19
SGST06/parse.pl	YES	8.54	MAYBE	0.04	MAYBE	0.15	YES	0.94
SGST06/perm.pl	YES	4.06	YES	0.02	YES	0.14	YES	1.13
SGST06/plus.pl	YES	2.28	YES	0.01	YES	0.12	MAYBE	0.40
SGST06/pplus.pl	YES	3.04	YES	0.01	YES	0.07	MAYBE	0.20
SGST06/pplus2.pl	YES	3.37	YES	0.01	YES	0.07	MAYBE	0.22
SGST06/preorder.pl	YES	3.42	YES	0.01	YES	0.12	MAYBE	0.26
SGST06/prime.pl	YES	6.98	MAYBE	0.07	MAYBE	1.28	KILLED	60.00
SGST06/quot.pl	YES	2.48	MAYBE	0.03	MAYBE	1.26	YES	0.54
SGST06/rev.pl	YES	7.37	MAYBE	0.04	YES	0.25	YES	21.08
SGST06/samefringe.pl	YES	3.98	MAYBE	0.02	MAYBE	0.10	YES	2.04
SGST06/shuffle.pl	YES	4.71	MAYBE	0.02	MAYBE	0.12	MAYBE	0.20
SGST06/snake.pl	MAYBE	14.92	MAYBE	0.07	MAYBE	0.41	MAYBE	0.25
SGST06/times.pl	YES	3.04	MAYBE	0.02	YES	1.47	YES	0.26
SGST06/times2.pl	YES	14.64	YES	0.05	YES	0.19	KILLED	60.00
SGST06/toyama.pl	YES	2.02	MAYBE	0.01	MAYBE	0.06	MAYBE	0.24
SGST06/transpose-fb.pl	YES	3.79	MAYBE	0.04	MAYBE	0.21	YES	9.31
SGST06/transpose2.pl	MAYBE	12.96	MAYBE	0.01	MAYBE	0.11	MAYBE	0.40
SGST06/weight.pl	YES	3.66	MAYBE	0.03	YES	0.17	YES	0.32