Tyrolean Complexity Tool
Polynomial Path Orders
This page collects experimental results conducted with 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 polynomial path orders to its predecessors. 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 polynomial path orders to its predecessors 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.