Tyrolean Complexity Tool
Small Polynomial Path Orders
This page collects experimental results conducted with small polynomial path orders as implemented in our complexity analyser TcT, version 1.9. All Experiments were conducted on a laptop with 4Gb of RAM and Intel® Core™ i7-2620M CPU (2.7GHz).

Testbed TC

In Table TC we compare small polynomial path orders to various similar techniques. The employed testbed collects a subset of 597 examples from the termination problem database, version 8.0. This subset was obtained by restricting the runtime complexity problem set to constructor TRSs that are known to be terminating.

Testbed TCO

In Table TCO we compare small polynomial path orders to various similar techniques as in Table TC, but the testbed has been restricted additionally to orthogonal systems. Conclusively this testbed allows us to conclude polytime computability from polynomially bounded runtime complexity.

Testbed RaML

Finally, in Table RaML we show the effect of integrating small polynomial path orders in our complexity analyser TcT. As testbed we use straight forward translations of Resource aware ML programs to TRSs.