Goal directed and relative dependency pairs for the termination of narrowing

Jose Iborra, Naoki Nishida and German Vidal

Empirical evaluation

In the paper Goal-Directed and Relative Dependency Pairs for the Termination of Narrowing, we discuss a new approach to the automated proof of termination for narrowing from an initial goal. Instead of computing a global argument filtering which eliminates all the occurrences of logic variables, the proposed approach uses a framework of goal-directed dependency pairs with a specialized notion of usable rules, together with a novel result for relative termination proofs using dependency pairs. As a result it is no longer required to employ heuristics and search due to the implicit incompleteness of a global argument filtering, as it was the case in previous approaches.

Tools

In these experiments we compare our implementation of the new approach with a variant of the global filtering approach.

LOPSTR'09
The implementation of the approach described in the paper, using a reduction pair processor based on SAT solving complemented with a set of graph refinement processors: instantiation, forward instantiation and narrowing.
FLOPS'08 innermost
A variant of the global filtering approach described in Termination of Narrowing in Left-Linear Constructor Systems . Although this approach does not consider extra variables, our implementation replaces them with generators, in the spirit of the related work such as this paper or Automated Termination Analysis for Logic Programs by Term Rewriting. In order to compute safe argument filterins we use a simple innermost heuristic which selects always the innermost position. We also tried a search heuristic, based on generation of all the possible candidates and ranking based on the size of the right hand sides of pairs in the filtered problem, but this proved to work badly in practice. In order to ensure we compare apples to apples, the generated rewriting problems are solved using the same processors used in the LOPSTR09 implementation, together with a subterm criterion processor. We include the subterm criterion processor as a testament of the shortcomings created by the loss of minimality in the new approach, where such a processor cannot be used.
SGST'07 type
A variant of the global filtering approach described in Automated Termination Analysis for Logic Programs by Term Rewriting targeted at infinitary rewriting termination. As heuristic for selecting the optimal argument filterings, we use the advanced type heuristic described here . As above, the generated rewriting problems are solved using the same processors used in the LOPSTR09 implementation, together with a subterm criterion processor. We include the subterm criterion processor to exemplify the shortcomings created by the loss of minimality in the new approach, where such a processor cannot be used.

Examples

We generated a set of initial goal narrowing problems by applying the transformation of Automated Termination Analysis for Logic Programs by Term Rewriting to the LP category of the Termination Problem database, excluding those examples which are not amenable to the transformation due to the use of cut, impure primitives or arithmetic.

Web interface

You can experiment with an online interface of the Narradar version used for these experiments.

Experiments

All the examples were ran in fully automated mode on a Intel Core 2 Quad Q9300 CPU at 2.50Ghz. We used a timeout of 60 seconds as it is done in the annual termination competition.

Summary:

Strategy Successes Failures Total time Average success time
LOPSTR09 183 122 1104.46 1.33
FLOPS08 innermost 167 138 1377.53 0.23
SGST07 type 178 127 840.97 0.24
Overall, these experiments show that the new technique is promising, beating the global argument filtering approach by an acceptable margin already at this early stage. Moreover, it does so without making use of type information or other static analysis of the program. Integrating such a static analysis step in the approach can potentially greatly improve the results, and is the subject of ongoing work.

Results::

Test LOPSTR09 FLOPS08 innermost SGST07 type
BCGGV05/ackerman.pl 0.64 ( out , err ) 0.12 ( out , err ) 0.17 ( out , err )
BCGGV05/append-bff.pl 0.13 ( out , err ) 0.05 ( out , err ) 0.05 ( out , err )
BCGGV05/append-ffb.pl 0.14 ( out , err ) 0.05 ( out , err ) 0.07 ( out , err )
BCGGV05/delete-bbf.pl 1.94 ( out , err ) 0.09 ( out , err ) 0.22 ( out , err )
BCGGV05/delete-bfb.pl 2.26 ( out , err ) 0.11 ( out , err ) 0.21 ( out , err )
BCGGV05/delete-bff.pl 1.31 ( out , err ) 0.10 ( out , err ) 0.09 ( out , err )
BCGGV05/delete-fbf.pl 2.89 ( out , err ) 0.09 ( out , err ) 0.16 ( out , err )
BCGGV05/delete-ffb.pl 2.81 ( out , err ) 0.08 ( out , err ) 0.11 ( out , err )
BCGGV05/delmin-bff.pl 0.86 ( out , err ) 0.09 ( out , err ) 0.22 ( out , err )
BCGGV05/delmin-ffb.pl 0.94 ( out , err ) 0.09 ( out , err ) 0.20 ( out , err )
BCGGV05/der-bf.pl 4.69 ( out , err ) 0.60 ( out , err ) 0.69 ( out , err )
BCGGV05/der-fb.pl 3.14 ( out , err ) 60.01 ( out , err ) 7.78 ( out , err )
BCGGV05/factor.pl 1.09 ( out , err ) 0.27 ( out , err ) 0.32 ( out , err )
BCGGV05/flat-bf.pl 0.20 ( out , err ) 0.08 ( out , err ) 0.11 ( out , err )
BCGGV05/flat-fb.pl 0.91 ( out , err ) 0.04 ( out , err ) 0.07 ( out , err )
BCGGV05/flatlength-bbf.pl 0.57 ( out , err ) 0.10 ( out , err ) 0.10 ( out , err )
BCGGV05/flatlength-bfb.pl 0.51 ( out , err ) 0.08 ( out , err ) 0.10 ( out , err )
BCGGV05/flatlength-bff.pl 0.54 ( out , err ) 0.08 ( out , err ) 0.11 ( out , err )
BCGGV05/flatlength-fbf.pl 1.02 ( out , err ) 0.17 ( out , err ) 0.20 ( out , err )
BCGGV05/flatlength-ffb.pl 0.44 ( out , err ) 0.05 ( out , err ) 0.08 ( out , err )
BCGGV05/frontier-bf.pl 0.76 ( out , err ) 0.15 ( out , err ) 0.11 ( out , err )
BCGGV05/frontier-fb.pl 0.62 ( out , err ) 5.25 ( out , err ) 0.73 ( out , err )
BCGGV05/g.pl 2.98 ( out , err ) 0.13 ( out , err ) 0.12 ( out , err )
BCGGV05/in-bf.pl 0.51 ( out , err ) 0.06 ( out , err ) 0.08 ( out , err )
BCGGV05/in-fb.pl 0.48 ( out , err ) 0.08 ( out , err ) 0.06 ( out , err )
BCGGV05/inorder-bf.pl 0.69 ( out , err ) 0.10 ( out , err ) 0.11 ( out , err )
BCGGV05/inorder-fb.pl 0.71 ( out , err ) 3.07 ( out , err ) 0.84 ( out , err )
BCGGV05/insert-bbf.pl 0.85 ( out , err ) 0.12 ( out , err ) 0.14 ( out , err )
BCGGV05/insert-bfb.pl 0.89 ( out , err ) 0.11 ( out , err ) 0.14 ( out , err )
BCGGV05/insert-bff.pl 0.82 ( out , err ) 0.08 ( out , err ) 0.08 ( out , err )
BCGGV05/insert-fbf.pl 0.89 ( out , err ) 0.09 ( out , err ) 0.06 ( out , err )
BCGGV05/insert-ffb.pl 0.77 ( out , err ) 0.08 ( out , err ) 0.06 ( out , err )
BCGGV05/length.pl 0.12 ( out , err ) 0.04 ( out , err ) 0.05 ( out , err )
BCGGV05/length1.pl 0.16 ( out , err ) 0.05 ( out , err ) 0.05 ( out , err )
BCGGV05/less-bf.pl 0.11 ( out , err ) 0.03 ( out , err ) 0.06 ( out , err )
BCGGV05/less-fb.pl 0.11 ( out , err ) 0.04 ( out , err ) 0.04 ( out , err )
BCGGV05/list.pl 0.08 ( out , err ) 0.06 ( out , err ) 0.11 ( out , err )
BCGGV05/map_color.pl 0.27 ( out , err ) 0.29 ( out , err ) 0.30 ( out , err )
BCGGV05/maximum-bff.pl 0.24 ( out , err ) 0.05 ( out , err ) 0.06 ( out , err )
BCGGV05/maximum-fbf.pl 0.24 ( out , err ) 0.05 ( out , err ) 0.03 ( out , err )
BCGGV05/maximum-ffb.pl 0.21 ( out , err ) 0.06 ( out , err ) 0.10 ( out , err )
BCGGV05/member-bf.pl 0.13 ( out , err ) 0.03 ( out , err ) 0.05 ( out , err )
BCGGV05/member-fb.pl 0.09 ( out , err ) 0.04 ( out , err ) 0.08 ( out , err )
BCGGV05/mergesort.pl 1.77 ( out , err ) 0.12 ( out , err ) 0.14 ( out , err )
BCGGV05/minimum-bf.pl 0.14 ( out , err ) 0.05 ( out , err ) 0.07 ( out , err )
BCGGV05/minimum-fb.pl 0.17 ( out , err ) 0.03 ( out , err ) 0.04 ( out , err )
BCGGV05/mult.pl 0.35 ( out , err ) 0.09 ( out , err ) 0.08 ( out , err )
BCGGV05/naive_reverse-bf.pl 0.40 ( out , err ) 0.07 ( out , err ) 0.09 ( out , err )
BCGGV05/naive_reverse-fb.pl 0.51 ( out , err ) 0.05 ( out , err ) 0.04 ( out , err )
BCGGV05/numeral.pl 0.07 ( out , err ) 0.04 ( out , err ) 0.04 ( out , err )
BCGGV05/ordered.pl 0.47 ( out , err ) 0.15 ( out , err ) 0.15 ( out , err )
BCGGV05/p.pl 0.53 ( out , err ) 0.10 ( out , err ) 0.12 ( out , err )
BCGGV05/p_nonlin.pl 1.78 ( out , err ) 1.30 ( out , err ) 1.28 ( out , err )
BCGGV05/palindrome.pl 0.18 ( out , err ) 0.07 ( out , err ) 0.11 ( out , err )
BCGGV05/parse.pl 2.21 ( out , err ) 0.18 ( out , err ) 0.24 ( out , err )
BCGGV05/permutation-bf.pl 0.50 ( out , err ) 0.05 ( out , err ) 0.05 ( out , err )
BCGGV05/permutation-fb.pl 0.57 ( out , err ) 0.07 ( out , err ) 0.07 ( out , err )
BCGGV05/permutation1-fb.pl 0.41 ( out , err ) 0.13 ( out , err ) 0.13 ( out , err )
BCGGV05/prefix-bf.pl 0.23 ( out , err ) 0.06 ( out , err ) 0.06 ( out , err )
BCGGV05/prefix-fb.pl 0.18 ( out , err ) 0.06 ( out , err ) 0.06 ( out , err )
BCGGV05/quicksort-bf.pl 1.88 ( out , err ) 35.37 ( out , err ) 21.50 ( out , err )
BCGGV05/quicksort-fb.pl 1.42 ( out , err ) 0.14 ( out , err ) 0.13 ( out , err )
BCGGV05/reverse-bf.pl 0.17 ( out , err ) 0.07 ( out , err ) 0.06 ( out , err )
BCGGV05/reverse-fb.pl 1.50 ( out , err ) 0.24 ( out , err ) 0.15 ( out , err )
BCGGV05/search_tree.pl 1.70 ( out , err ) 0.18 ( out , err ) 0.24 ( out , err )
BCGGV05/select-bff.pl 0.20 ( out , err ) 0.04 ( out , err ) 0.04 ( out , err )
BCGGV05/select-fbf.pl 0.15 ( out , err ) 0.05 ( out , err ) 0.05 ( out , err )
BCGGV05/select-ffb.pl 0.14 ( out , err ) 0.05 ( out , err ) 0.04 ( out , err )
BCGGV05/slowsort-bb.pl 1.01 ( out , err ) 0.09 ( out , err ) 0.15 ( out , err )
BCGGV05/slowsort-bf.pl 1.03 ( out , err ) 0.11 ( out , err ) 0.15 ( out , err )
BCGGV05/slowsort-fb.pl 0.97 ( out , err ) 0.10 ( out , err ) 0.10 ( out , err )
BCGGV05/sublist-bf.pl 0.28 ( out , err ) 0.05 ( out , err ) 0.04 ( out , err )
BCGGV05/sublist-fb.pl 0.22 ( out , err ) 0.06 ( out , err ) 0.06 ( out , err )
BCGGV05/subset-bf.pl 0.26 ( out , err ) 0.06 ( out , err ) 0.03 ( out , err )
BCGGV05/subset-fb.pl 0.54 ( out , err ) 0.14 ( out , err ) 0.14 ( out , err )
BCGGV05/suffix-bf.pl 0.24 ( out , err ) 0.04 ( out , err ) 0.04 ( out , err )
BCGGV05/sum-fbf.pl 0.11 ( out , err ) 0.04 ( out , err ) 0.06 ( out , err )
BCGGV05/sum-ffb.pl 0.12 ( out , err ) 0.05 ( out , err ) 0.08 ( out , err )
BCGGV05/t.pl 0.54 ( out , err ) 0.08 ( out , err ) 0.07 ( out , err )
BCGGV05/transpose-bb.pl 0.96 ( out , err ) 0.11 ( out , err ) 0.15 ( out , err )
BCGGV05/transpose-bf.pl 1.12 ( out , err ) 0.09 ( out , err ) 0.05 ( out , err )
BCGGV05/transpose-fb.pl 2.29 ( out , err ) 1.82 ( out , err ) 2.12 ( out , err )
BCGGV05/tree.pl 0.14 ( out , err ) 0.05 ( out , err ) 0.06 ( out , err )
BCGGV05/tree_member-bf.pl 0.27 ( out , err ) 0.04 ( out , err ) 0.04 ( out , err )
BCGGV05/tree_member-fb.pl 0.19 ( out , err ) 0.06 ( out , err ) 0.12 ( out , err )
SGST06/ackermann.pl 0.68 ( out , err ) 0.10 ( out , err ) 0.10 ( out , err )
SGST06/ag01.pl 0.31 ( out , err ) 0.12 ( out , err ) 0.12 ( out , err )
SGST06/applast.pl 1.40 ( out , err ) 0.13 ( out , err ) 0.15 ( out , err )
SGST06/at.pl 0.06 ( out , err ) 0.05 ( out , err ) 0.03 ( out , err )
SGST06/avg-bfb.pl 0.39 ( out , err ) 0.05 ( out , err ) 0.07 ( out , err )
SGST06/avg.pl 0.41 ( out , err ) 49.79 ( out , err ) 0.96 ( out , err )
SGST06/baby91.pl 2.59 ( out , err ) 0.17 ( out , err ) 0.13 ( out , err )
SGST06/bappend.pl 0.39 ( out , err ) 0.08 ( out , err ) 0.12 ( out , err )
SGST06/blist.pl 0.28 ( out , err ) 0.07 ( out , err ) 0.08 ( out , err )
SGST06/btappend.pl 1.26 ( out , err ) 0.12 ( out , err ) 0.18 ( out , err )
SGST06/btapplast.pl 2.98 ( out , err ) 0.24 ( out , err ) 0.34 ( out , err )
SGST06/btree.pl 0.68 ( out , err ) 0.10 ( out , err ) 0.15 ( out , err )
SGST06/cconfdel.pl 0.61 ( out , err ) 0.12 ( out , err ) 0.07 ( out , err )
SGST06/cnfequiv.pl 2.53 ( out , err ) 0.92 ( out , err ) 0.90 ( out , err )
SGST06/confdel.pl 0.71 ( out , err ) 0.09 ( out , err ) 0.08 ( out , err )
SGST06/convert.pl 1.38 ( out , err ) 0.19 ( out , err ) 0.18 ( out , err )
SGST06/countstack.pl 0.22 ( out , err ) 0.11 ( out , err ) 0.10 ( out , err )
SGST06/csnake.pl 15.85 ( out , err ) 0.75 ( out , err ) 0.25 ( out , err )
SGST06/d.pl 1.56 ( out , err ) 0.57 ( out , err ) 0.62 ( out , err )
SGST06/doublehalfpred.pl 0.84 ( out , err ) 0.81 ( out , err ) 0.81 ( out , err )
SGST06/evenodd.pl 0.13 ( out , err ) 0.08 ( out , err ) 0.07 ( out , err )
SGST06/factor.pl 1.03 ( out , err ) 0.24 ( out , err ) 0.27 ( out , err )
SGST06/flatten.pl 0.24 ( out , err ) 0.08 ( out , err ) 0.12 ( out , err )
SGST06/flatten_phd.pl 1.01 ( out , err ) 0.28 ( out , err ) 0.40 ( out , err )
SGST06/giesl97.pl 0.16 ( out , err ) 0.09 ( out , err ) 0.12 ( out , err )
SGST06/gopher.pl 0.15 ( out , err ) 0.07 ( out , err ) 0.08 ( out , err )
SGST06/hbal_tree.pl 0.43 ( out , err ) 0.22 ( out , err ) 0.22 ( out , err )
SGST06/ifdiv.pl 7.55 ( out , err ) 19.22 ( out , err ) 16.10 ( out , err )
SGST06/ifminus.pl 2.24 ( out , err ) 1.79 ( out , err ) 1.81 ( out , err )
SGST06/incomplete.pl 0.12 ( out , err ) 0.03 ( out , err ) 0.06 ( out , err )
SGST06/incomplete2.pl 0.18 ( out , err ) 2.53 ( out , err ) 0.40 ( out , err )
SGST06/incomplete_variant.pl 0.06 ( out , err ) 0.07 ( out , err ) 0.04 ( out , err )
SGST06/intlist.pl 0.57 ( out , err ) 0.09 ( out , err ) 0.11 ( out , err )
SGST06/lessleaves.pl 1.22 ( out , err ) 0.70 ( out , err ) 0.74 ( out , err )
SGST06/log.pl 0.63 ( out , err ) 0.54 ( out , err ) 0.64 ( out , err )
SGST06/mapcolor.pl 2.95 ( out , err ) 0.22 ( out , err ) 0.26 ( out , err )
SGST06/p.pl 0.56 ( out , err ) 0.32 ( out , err ) 0.37 ( out , err )
SGST06/p_nonlin.pl 2.10 ( out , err ) 0.56 ( out , err ) 0.56 ( out , err )
SGST06/palindrome.pl 1.77 ( out , err ) 0.26 ( out , err ) 0.30 ( out , err )
SGST06/paper1.pl 0.16 ( out , err ) 0.07 ( out , err ) 0.11 ( out , err )
SGST06/paper2.pl 0.16 ( out , err ) 0.07 ( out , err ) 0.10 ( out , err )
SGST06/parse.pl 2.25 ( out , err ) 0.16 ( out , err ) 0.16 ( out , err )
SGST06/perm.pl 0.77 ( out , err ) 0.12 ( out , err ) 0.13 ( out , err )
SGST06/plus.pl 0.11 ( out , err ) 0.04 ( out , err ) 0.04 ( out , err )
SGST06/pplus.pl 0.19 ( out , err ) 0.08 ( out , err ) 0.08 ( out , err )
SGST06/pplus2.pl 0.44 ( out , err ) 0.12 ( out , err ) 0.13 ( out , err )
SGST06/preorder.pl 0.44 ( out , err ) 0.06 ( out , err ) 0.09 ( out , err )
SGST06/prime.pl 1.62 ( out , err ) 0.78 ( out , err ) 0.81 ( out , err )
SGST06/quot.pl 0.31 ( out , err ) 0.06 ( out , err ) 0.07 ( out , err )
SGST06/rev.pl 1.17 ( out , err ) 0.83 ( out , err ) 0.82 ( out , err )
SGST06/samefringe.pl 1.14 ( out , err ) 0.05 ( out , err ) 0.32 ( out , err )
SGST06/shuffle.pl 2.30 ( out , err ) 1.42 ( out , err ) 1.49 ( out , err )
SGST06/snake.pl 17.00 ( out , err ) 0.80 ( out , err ) 0.54 ( out , err )
SGST06/times.pl 0.23 ( out , err ) 0.09 ( out , err ) 0.09 ( out , err )
SGST06/times2.pl 5.33 ( out , err ) 60.03 ( out , err ) 60.01 ( out , err )
SGST06/toyama.pl 0.11 ( out , err ) 0.04 ( out , err ) 0.04 ( out , err )
SGST06/transpose-fb.pl 2.42 ( out , err ) 1.96 ( out , err ) 1.77 ( out , err )
SGST06/transpose2.pl 4.54 ( out , err ) 0.08 ( out , err ) 0.04 ( out , err )
SGST06/weight.pl 0.10 ( out , err ) 0.13 ( out , err ) 0.14 ( out , err )
lpexamples/ackermann-ioi.pl 1.12 ( out , err ) 6.29 ( out , err ) 0.05 ( out , err )
lpexamples/ackermann.pl 0.63 ( out , err ) 0.12 ( out , err ) 0.10 ( out , err )
lpexamples/average-ioi.pl 0.36 ( out , err ) 0.04 ( out , err ) 0.09 ( out , err )
lpexamples/average.pl 0.43 ( out , err ) 60.01 ( out , err ) 0.96 ( out , err )
lpexamples/kay4.pl 60.03 ( out , err ) 60.02 ( out , err ) 60.01 ( out , err )
lpexamples/log2a-oi.pl 0.41 ( out , err ) 0.06 ( out , err ) 0.04 ( out , err )
lpexamples/log2a.pl 4.43 ( out , err ) 13.00 ( out , err ) 4.19 ( out , err )
lpexamples/log2b-oi.pl 60.02 ( out , err ) 60.01 ( out , err ) 3.96 ( out , err )
lpexamples/log2b.pl 60.02 ( out , err ) 60.01 ( out , err ) 11.31 ( out , err )
lpexamples/mapcolor.pl 2.82 ( out , err ) 0.22 ( out , err ) 0.22 ( out , err )
lpexamples/mergesort-oi.pl 1.70 ( out , err ) 0.13 ( out , err ) 0.10 ( out , err )
lpexamples/mergesort.pl 2.03 ( out , err ) 46.27 ( out , err ) 23.18 ( out , err )
lpexamples/shapes.pl 14.93 ( out , err ) 6.24 ( out , err ) 6.12 ( out , err )
lpexamples/tautology.pl 60.03 ( out , err ) 60.02 ( out , err ) 60.01 ( out , err )
talp/apt/SS_map.pl 60.11 ( out , err ) 0.44 ( out , err ) 0.52 ( out , err )
talp/apt/SS_map_out.pl 60.12 ( out , err ) 0.52 ( out , err ) 0.67 ( out , err )
talp/apt/SS_map_t.pl 60.05 ( out , err ) 0.36 ( out , err ) 0.34 ( out , err )
talp/apt/append.pl 0.22 ( out , err ) 0.08 ( out , err ) 0.07 ( out , err )
talp/apt/dc_schema.pl 1.22 ( out , err ) 13.81 ( out , err ) 2.35 ( out , err )
talp/apt/fold.pl 0.22 ( out , err ) 0.05 ( out , err ) 0.06 ( out , err )
talp/apt/gtsolve.pl 0.09 ( out , err ) 0.08 ( out , err ) 0.06 ( out , err )
talp/apt/list.pl 0.08 ( out , err ) 0.06 ( out , err ) 0.05 ( out , err )
talp/apt/lte.pl 0.07 ( out , err ) 0.09 ( out , err ) 0.08 ( out , err )
talp/apt/map.pl 0.18 ( out , err ) 0.06 ( out , err ) 0.06 ( out , err )
talp/apt/map1.pl 0.18 ( out , err ) 0.06 ( out , err ) 0.06 ( out , err )
talp/apt/member.pl 0.10 ( out , err ) 0.05 ( out , err ) 0.05 ( out , err )
talp/apt/mergesort.pl 2.53 ( out , err ) 60.02 ( out , err ) 40.67 ( out , err )
talp/apt/mergesort_ap.pl 3.98 ( out , err ) 0.16 ( out , err ) 0.24 ( out , err )
talp/apt/mergesort_ap_variant.pl 9.42 ( out , err ) 1.50 ( out , err ) 1.92 ( out , err )
talp/apt/naive_rev-oi.pl 0.41 ( out , err ) 0.05 ( out , err ) 0.04 ( out , err )
talp/apt/naive_rev.pl 0.40 ( out , err ) 0.08 ( out , err ) 0.08 ( out , err )
talp/apt/ordered.pl 0.36 ( out , err ) 0.15 ( out , err ) 0.17 ( out , err )
talp/apt/overlap.pl 0.45 ( out , err ) 0.10 ( out , err ) 0.11 ( out , err )
talp/apt/permutation.pl 3.31 ( out , err ) 0.07 ( out , err ) 0.08 ( out , err )
talp/apt/quicksort-oi.pl 2.04 ( out , err ) 0.17 ( out , err ) 0.15 ( out , err )
talp/apt/quicksort.pl 2.25 ( out , err ) 40.22 ( out , err ) 25.49 ( out , err )
talp/apt/select.pl 0.17 ( out , err ) 0.05 ( out , err ) 0.07 ( out , err )
talp/apt/select1.pl 0.14 ( out , err ) 0.05 ( out , err ) 0.05 ( out , err )
talp/apt/subset.pl 0.69 ( out , err ) 0.16 ( out , err ) 0.15 ( out , err )
talp/apt/subset1.pl 1.10 ( out , err ) 0.22 ( out , err ) 0.21 ( out , err )
talp/apt/sum.pl 0.12 ( out , err ) 0.05 ( out , err ) 0.06 ( out , err )
talp/az/flat-oi.pl 1.97 ( out , err ) 0.06 ( out , err ) 0.06 ( out , err )
talp/az/flat.pl 0.50 ( out , err ) 0.15 ( out , err ) 0.18 ( out , err )
talp/az/p.pl 0.25 ( out , err ) 0.14 ( out , err ) 0.10 ( out , err )
talp/az/perm.pl 3.23 ( out , err ) 0.09 ( out , err ) 0.79 ( out , err )
talp/dds/append.pl 0.19 ( out , err ) 0.05 ( out , err ) 0.05 ( out , err )
talp/dds/dis_con-bis.pl 0.30 ( out , err ) 0.11 ( out , err ) 0.09 ( out , err )
talp/dds/dis_con.pl 0.27 ( out , err ) 0.12 ( out , err ) 0.09 ( out , err )
talp/dds/duplicate.pl 0.14 ( out , err ) 0.06 ( out , err ) 0.05 ( out , err )
talp/dds/merge.pl 2.31 ( out , err ) 0.46 ( out , err ) 0.44 ( out , err )
talp/dds/permute.pl 0.55 ( out , err ) 0.14 ( out , err ) 0.14 ( out , err )
talp/dds/reverse-iio.pl 0.16 ( out , err ) 0.04 ( out , err ) 0.04 ( out , err )
talp/dds/reverse.pl 0.14 ( out , err ) 0.04 ( out , err ) 0.05 ( out , err )
talp/dds/sum-ioi.pl 0.61 ( out , err ) 0.08 ( out , err ) 0.09 ( out , err )
talp/dds/sum.pl 0.63 ( out , err ) 0.09 ( out , err ) 0.09 ( out , err )
talp/maria/fib_t.pl 0.94 ( out , err ) 0.13 ( out , err ) 0.15 ( out , err )
talp/maria/grammar.pl 0.26 ( out , err ) 0.14 ( out , err ) 0.17 ( out , err )
talp/maria/grammar2.pl 0.28 ( out , err ) 0.13 ( out , err ) 0.17 ( out , err )
talp/maria/hanoiapp.suc.pl 1.99 ( out , err ) 0.73 ( out , err ) 0.77 ( out , err )
talp/maria/tak.pl 23.78 ( out , err ) 25.65 ( out , err ) 29.77 ( out , err )
talp/maria/zebra.pl 60.14 ( out , err ) 1.07 ( out , err ) 1.40 ( out , err )
talp/naomil/ack.pl 0.60 ( out , err ) 0.08 ( out , err ) 0.08 ( out , err )
talp/naomil/queens.pl 14.95 ( out , err ) 0.74 ( out , err ) 0.84 ( out , err )
talp/naomil/reverse.pl 0.16 ( out , err ) 0.05 ( out , err ) 0.06 ( out , err )
talp/naomil/sicstus1.pl 0.38 ( out , err ) 0.11 ( out , err ) 0.12 ( out , err )
talp/plumer/mergesort_t.pl 2.94 ( out , err ) 60.02 ( out , err ) 60.02 ( out , err )
talp/plumer/pl1.1.pl 0.33 ( out , err ) 0.04 ( out , err ) 0.04 ( out , err )
talp/plumer/pl1.2.pl 3.02 ( out , err ) 0.06 ( out , err ) 0.06 ( out , err )
talp/plumer/pl2.3.1.pl 0.13 ( out , err ) 0.06 ( out , err ) 0.07 ( out , err )
talp/plumer/pl3.1.1.pl 0.08 ( out , err ) 0.04 ( out , err ) 0.03 ( out , err )
talp/plumer/pl3.5.6.pl 0.23 ( out , err ) 0.10 ( out , err ) 0.09 ( out , err )
talp/plumer/pl3.5.6a.pl 0.17 ( out , err ) 0.06 ( out , err ) 0.06 ( out , err )
talp/plumer/pl4.0.1-oooi.pl 0.40 ( out , err ) 0.07 ( out , err ) 0.04 ( out , err )
talp/plumer/pl4.0.1.pl 0.23 ( out , err ) 0.06 ( out , err ) 0.07 ( out , err )
talp/plumer/pl4.4.3.pl 2.19 ( out , err ) 0.47 ( out , err ) 0.43 ( out , err )
talp/plumer/pl4.4.6a.pl 0.39 ( out , err ) 0.10 ( out , err ) 0.08 ( out , err )
talp/plumer/pl4.5.2.pl 1.12 ( out , err ) 8.38 ( out , err ) 10.80 ( out , err )
talp/plumer/pl4.5.3a.pl 0.17 ( out , err ) 0.03 ( out , err ) 0.03 ( out , err )
talp/plumer/pl4.5.3b.pl 0.08 ( out , err ) 0.04 ( out , err ) 0.03 ( out , err )
talp/plumer/pl4.5.3c.pl 0.12 ( out , err ) 0.04 ( out , err ) 0.03 ( out , err )
talp/plumer/pl5.2.2.pl 29.50 ( out , err ) 60.01 ( out , err ) 59.11 ( out , err )
talp/plumer/pl6.1.1.pl 2.21 ( out , err ) 30.70 ( out , err ) 22.21 ( out , err )
talp/plumer/pl7.2.9.pl 0.36 ( out , err ) 0.07 ( out , err ) 0.08 ( out , err )
talp/plumer/pl7.6.2a.pl 1.73 ( out , err ) 0.30 ( out , err ) 0.30 ( out , err )
talp/plumer/pl7.6.2b.pl 4.38 ( out , err ) 14.90 ( out , err ) 7.27 ( out , err )
talp/plumer/pl7.6.2c.pl 3.09 ( out , err ) 0.41 ( out , err ) 0.44 ( out , err )
talp/plumer/pl8.2.1.pl 2.29 ( out , err ) 60.02 ( out , err ) 39.18 ( out , err )
talp/plumer/pl8.2.1a.pl 2.57 ( out , err ) 60.01 ( out , err ) 37.32 ( out , err )
talp/plumer/pl8.3.1.pl 15.66 ( out , err ) 2.55 ( out , err ) 2.93 ( out , err )
talp/plumer/pl8.3.1a.pl 6.38 ( out , err ) 0.84 ( out , err ) 0.89 ( out , err )
talp/plumer/pl8.4.1.pl 0.10 ( out , err ) 0.04 ( out , err ) 0.05 ( out , err )
talp/plumer/pl8.4.2.pl 0.48 ( out , err ) 60.01 ( out , err ) 2.87 ( out , err )
talp/taboch/bad_sublist.pl 0.47 ( out , err ) 0.07 ( out , err ) 0.12 ( out , err )
talp/taboch/mergesort.pl 2.30 ( out , err ) 60.02 ( out , err ) 39.63 ( out , err )
talp/taboch/permute1.pl 3.10 ( out , err ) 0.06 ( out , err ) 0.07 ( out , err )
talp/taboch/permute2.pl 0.51 ( out , err ) 0.15 ( out , err ) 0.14 ( out , err )
talp/taboch/qicksort.pl 1.95 ( out , err ) 33.02 ( out , err ) 24.07 ( out , err )
talp/taboch/rotate.pl 0.48 ( out , err ) 0.09 ( out , err ) 0.09 ( out , err )
talp/taboch/sameleaves.pl 0.83 ( out , err ) 0.28 ( out , err ) 0.29 ( out , err )
talp/taboch/sublist.pl 0.51 ( out , err ) 0.09 ( out , err ) 0.09 ( out , err )
talp/taboch/sublist1.pl 0.22 ( out , err ) 0.06 ( out , err ) 0.07 ( out , err )
talp/talp/append.pl 0.30 ( out , err ) 0.10 ( out , err ) 0.10 ( out , err )
talp/talp/binary.pl 20.55 ( out , err ) 1.54 ( out , err ) 1.89 ( out , err )
talp/talp/binary2.pl 17.83 ( out , err ) 1.05 ( out , err ) 1.29 ( out , err )
talp/talp/binary3.pl 34.93 ( out , err ) 1.51 ( out , err ) 1.90 ( out , err )
talp/talp/binary4.pl 3.93 ( out , err ) 1.03 ( out , err ) 1.36 ( out , err )
talp/talp/div.pl 1.04 ( out , err ) 0.17 ( out , err ) 0.20 ( out , err )
talp/talp/evaluate.pl 8.62 ( out , err ) 0.79 ( out , err ) 0.93 ( out , err )
talp/talp/example1.pl 0.05 ( out , err ) 0.03 ( out , err ) 0.06 ( out , err )
talp/talp/example4-2.pl 0.08 ( out , err ) 0.03 ( out , err ) 0.03 ( out , err )
talp/talp/example4.pl 0.09 ( out , err ) 0.06 ( out , err ) 0.05 ( out , err )
talp/talp/flat.pl 0.27 ( out , err ) 0.10 ( out , err ) 0.10 ( out , err )
talp/talp/gcd.pl 12.53 ( out , err ) 60.00 ( out , err ) 60.01 ( out , err )
talp/talp/nat.pl 2.30 ( out , err ) 0.44 ( out , err ) 0.49 ( out , err )
talp/talp/normal.pl 0.62 ( out , err ) 0.34 ( out , err ) 0.37 ( out , err )
talp/talp/palindrome.pl 0.18 ( out , err ) 0.06 ( out , err ) 0.07 ( out , err )
talp/talp/perm.pl 2.86 ( out , err ) 0.07 ( out , err ) 0.76 ( out , err )
talp/talp/permute.pl 0.54 ( out , err ) 0.14 ( out , err ) 0.17 ( out , err )
talp/talp/qsort.pl 1.83 ( out , err ) 30.32 ( out , err ) 23.52 ( out , err )
talp/talp/reminder-ioi.pl 2.00 ( out , err ) 0.08 ( out , err ) 0.78 ( out , err )
talp/talp/reminder.pl 2.29 ( out , err ) 1.06 ( out , err ) 1.11 ( out , err )
talp/talp/simple.pl 0.05 ( out , err ) 0.04 ( out , err ) 0.04 ( out , err )
talp/talp/slowsort-oi.pl 0.77 ( out , err ) 0.09 ( out , err ) 0.08 ( out , err )
talp/talp/slowsort.pl 2.14 ( out , err ) 0.39 ( out , err ) 0.40 ( out , err )
talp/talp/transitive_closure.pl 0.11 ( out , err ) 0.08 ( out , err ) 0.08 ( out , err )
talp/talp/vangelder.pl 2.29 ( out , err ) 0.88 ( out , err ) 1.04 ( out , err )
terminweb/Size-Change:NJ/NJ1.pl 0.17 ( out , err ) 0.06 ( out , err ) 0.06 ( out , err )
terminweb/Size-Change:NJ/NJ2.pl 0.21 ( out , err ) 0.06 ( out , err ) 0.06 ( out , err )
terminweb/Size-Change:NJ/NJ3.pl 0.62 ( out , err ) 0.09 ( out , err ) 0.09 ( out , err )
terminweb/Size-Change:NJ/NJ4.pl 0.35 ( out , err ) 0.11 ( out , err ) 0.10 ( out , err )
terminweb/Size-Change:NJ/NJ5.pl 0.25 ( out , err ) 5.74 ( out , err ) 0.67 ( out , err )
terminweb/Size-Change:NJ/NJ6.pl 0.49 ( out , err ) 0.08 ( out , err ) 0.09 ( out , err )
terminweb/backwards/append.pl 0.14 ( out , err ) 0.05 ( out , err ) 0.05 ( out , err )
terminweb/basic/append-ooi.pl 0.14 ( out , err ) 0.05 ( out , err ) 0.05 ( out , err )
terminweb/basic/append.pl 0.14 ( out , err ) 0.05 ( out , err ) 0.06 ( out , err )
terminweb/basic/ways.pl 1.46 ( out , err ) 0.16 ( out , err ) 0.13 ( out , err )
terminweb/combination/der.pl 3.47 ( out , err ) 0.54 ( out , err ) 0.57 ( out , err )
terminweb/cti/som.pl 0.43 ( out , err ) 0.08 ( out , err ) 0.06 ( out , err )
terminweb/old-terminweb/ackerman.pl 0.62 ( out , err ) 0.08 ( out , err ) 0.09 ( out , err )
terminweb/old-terminweb/append3-bis.pl 0.36 ( out , err ) 0.08 ( out , err ) 0.09 ( out , err )
terminweb/old-terminweb/append3.pl 0.34 ( out , err ) 0.08 ( out , err ) 0.11 ( out , err )
terminweb/old-terminweb/balance_tree.pl 5.73 ( out , err ) 0.10 ( out , err ) 0.14 ( out , err )
terminweb/old-terminweb/balance_tree2.pl 30.93 ( out , err ) 26.81 ( out , err ) 8.66 ( out , err )
terminweb/old-terminweb/inorder.pl 0.57 ( out , err ) 0.09 ( out , err ) 0.10 ( out , err )
terminweb/old-terminweb/interleave.pl 0.28 ( out , err ) 0.08 ( out , err ) 0.08 ( out , err )
terminweb/old-terminweb/mergesort.pl 7.54 ( out , err ) 1.45 ( out , err ) 1.89 ( out , err )
terminweb/old-terminweb/permutation1.pl 0.52 ( out , err ) 0.05 ( out , err ) 0.04 ( out , err )
terminweb/old-terminweb/permutation2.pl 0.45 ( out , err ) 0.14 ( out , err ) 0.15 ( out , err )
terminweb/old-terminweb/quicksort.pl 60.08 ( out , err ) 1.31 ( out , err ) 1.80 ( out , err )
terminweb/old-terminweb/reach.pl 1.58 ( out , err ) 0.25 ( out , err ) 0.26 ( out , err )
terminweb/old-terminweb/rotate.pl 0.31 ( out , err ) 0.05 ( out , err ) 0.06 ( out , err )
terminweb/old-terminweb/sameleaves.pl 0.69 ( out , err ) 0.28 ( out , err ) 0.26 ( out , err )
terminweb/old-terminweb/sublist.pl 0.22 ( out , err ) 0.06 ( out , err ) 0.07 ( out , err )
terminweb/old-terminweb/sublist0.pl 0.21 ( out , err ) 0.06 ( out , err ) 0.07 ( out , err )
terminweb/old-terminweb/sublist_bad.pl 0.32 ( out , err ) 0.05 ( out , err ) 0.03 ( out , err )
terminweb/old-terminweb/subset-no.pl 0.48 ( out , err ) 0.15 ( out , err ) 0.13 ( out , err )
terminweb/old-terminweb/subset.pl 0.30 ( out , err ) 0.08 ( out , err ) 0.07 ( out , err )
terminweb/old-terminweb/untupled_bal_tree.pl 13.80 ( out , err ) 0.26 ( out , err ) 0.37 ( out , err )
terminweb/type-based/append.pl 0.14 ( out , err ) 0.05 ( out , err ) 0.05 ( out , err )
terminweb/type-based/transpose.pl 1.13 ( out , err ) 0.11 ( out , err ) 0.09 ( out , err )
terminweb/untupling/preorder_dl.pl 0.41 ( out , err ) 0.07 ( out , err ) 0.07 ( out , err )