Tyrolean Complexity Tool
Polynomial Path Orders
On this page we compare polynomial path orders to its predecessors. The employed testbed collects a subset of 290 examples from the termination problem database, version 8.0. This subset was obtained by restricting the runtime complexity problem set to orthogonal constructor TRSs that are known to be terminating .

Techniques

Interpretations
Polynomial (degree 2 and 3) and Matrix Interpretations (dimension 1 and 3) run in parallel. The implementation uses the usable arguments criterion to weaken monotonicity constraints.
LMPO
Lightweight multiset path orders
MPO
Multiset Path Orders
POP*
Polynomial Path Orders
POP* (PS)
Polynomial Path Orders with Parameter Substitution

Overview

Interpretations
LMPO
MPO
POP*
POP* (PS)
O(n^1)
46----
O(n^2)
11----
O(n^3)
18----
POLY
---2429
ELEMENTARY
-29---
PRIMREC
--40--
Total YES
7529402429
Total MAYBE
133261250266261
Total TIMEOUT
82----
Strict Wins
7529--

Average Execution Time (in seconds)

Interpretations
LMPO
MPO
POP*
POP* (PS)
O(n^1)
0.392
-
-
-
-
O(n^2)
1.895
-
-
-
-
O(n^3)
9.529
-
-
-
-
POLY
-
-
-
0.143
0.153
ELEMENTARY
-
0.155
-
-
-
PRIMREC
-
-
0.300
-
-
Total YES
2.805
0.155
0.300
0.143
0.153
Total MAYBE
6.124
0.218
0.281
0.219
0.224

Details

Problem (all selected)
Interpretations
LMPO
MPO
POP*
POP* (PS)
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^2)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
PRIMREC
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^2)
ELEMENTARY
PRIMREC
MAYBE
MAYBE
O(n^2)
ELEMENTARY
PRIMREC
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
PRIMREC
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^2)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^2)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
POLY
O(n^2)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
PRIMREC
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^2)
ELEMENTARY
PRIMREC
POLY
POLY
MAYBE
ELEMENTARY
PRIMREC
MAYBE
MAYBE
MAYBE
ELEMENTARY
PRIMREC
MAYBE
MAYBE
MAYBE
MAYBE
PRIMREC
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
PRIMREC
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
POLY
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
POLY
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^2)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
PRIMREC
MAYBE
MAYBE
MAYBE
MAYBE
PRIMREC
MAYBE
MAYBE
TIMEOUT
MAYBE
PRIMREC
MAYBE
MAYBE
O(n^1)
MAYBE
MAYBE
MAYBE
POLY
O(n^1)
MAYBE
MAYBE
MAYBE
POLY
O(n^2)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
PRIMREC
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
MAYBE
MAYBE
PRIMREC
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
O(n^2)
ELEMENTARY
PRIMREC
POLY
POLY
O(n^2)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^1)
ELEMENTARY
PRIMREC
POLY
POLY
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
O(n^3)
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
PRIMREC
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
TIMEOUT
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE
MAYBE