Automated Implicit Computational Complexity Analysis
This page provides a detailed summary of the experiments performed with the icct complexity tool, which is based on the termination prover TTT2. icct is available for download as bytecode executable. Further, a native version for linux can be found here. It can be invoked using the command $ icct -s "<STRATEGY>" [-p] <FILE> . Here <FILE> should be a file according to the Termination Competition Data Base Format. If the option option -p is additionally supplied then a detailed proof script is printed to the console. The option -s <STRATEGY> decides the method that should be applied. Currently the following strategies are supported:- popstar [-qp] Tries to orient the input system using an instance of the Polynomial Path Order using a strict precedence per default. When additionally the switch -qp is set then a quasi-precedence suffices.
- popstarSL Same as the previous option, but additionally Semantic Labelling using Boolean models is applied.
- lmpo Tries to orient the system using an instance of the Light Multiset Path Order.
- ppo Orientation of the system using Recursive Path Order with Product status.
- smc [-b <bound>] [-i] Tries to find a simple-mixed, constructor-restricted interpretation. The switch -b <bound> sets the upper bound for the used coefficients to <bound> (the default value is 3). The switch -i activates the incremental search strategy: the given bound is not immediately used fully. The program first tries to find a suitable interpretation with a lower bound. The search is started with bound 1. If this is not successful, the bound is incremented to 3,7,15,... until the final bound is reached.
- qi [-b <bound>] [-i] Additive polynomial quasi-interpretation. The switches -b <bound> and -i work in the same way as for smc.
Experimental Data
All test were performed on a standard PC with a 2.4 GHz Intel Pentium IV processor and 512 MB of RAM. A green cell indicates that the method was successful, when the cell is yellow the test failed. A red cell indicates that either a timeout of 60 seconds was reached or the calculation was aborted due to a stack overflow. We have tested all methods described above. Additionally, we compare them to Quasi-MPO (MPO+QP), which is theoretically more powerful than LMPO and POP*, but does not induce polytime computability anymore.
We consider two testbeds:
- Testbed C collects all constructor-based systems from the current version of the Termination Problems Data Base Version 4.0 that was used in the Termination Competition of 2007. Notice that this data set is used in the competition for both proving and disproving termination.
- We have selected a subset of the Testbed C that reassembles functional programs in Testbed FP. These are all orthogonal and constructor-based and are taken from AG01, D33 and SK90.
TCT on testbed C
Popstar | POP* + QP | POP* + SL | LMPO | SMC | PPO AND QI | MPO + QP | ||||||||
count | average time | count | average time | count | average time | count | average time | count | average time | count | average time | count | average time | |
Yes | 41 | 0.053 | 43 | 0.047 | 74 | 0.192 | 54 | 0.044 | 69 | 0.507 | 51 | 0.279 | 69 | 0.052 |
Maybe | 551 | 0.091 | 549 | 0.102 | 511 | 1.024 | 538 | 0.080 | 394 | 4.740 | 540 | 0.216 | 523 | 0.120 |
No | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 |
TIMEOUT (60.0 sec.) | 0 | 0.000 | 0 | 0.000 | 7 | 56.145 | 0 | 0.000 | 129 | 57.771 | 1 | 60.089 | 0 | 0.000 |
TCT on testbed FP
Popstar | POP* + QP | POP* + SL | LMPO | SMC | PPO AND QI | MPO + QP | ||||||||
count | average time | count | average time | count | average time | count | average time | count | average time | count | average time | count | average time | |
Yes | 7 | 0.044 | 8 | 0.042 | 14 | 0.163 | 13 | 0.039 | 15 | 0.815 | 13 | 0.241 | 17 | 0.047 |
Maybe | 64 | 0.046 | 63 | 0.051 | 57 | 0.574 | 58 | 0.043 | 49 | 3.415 | 58 | 0.113 | 54 | 0.052 |
No | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 |
TIMEOUT (60.0 sec.) | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 | 0 | 0.000 | 7 | 60.250 | 0 | 0.000 | 0 | 0.000 |