/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. !plus : [o * o] --> o 0 : [] --> o 1 : [] --> o 2 : [] --> o 3 : [] --> o 4 : [] --> o 5 : [] --> o 6 : [] --> o 7 : [] --> o 8 : [] --> o 9 : [] --> o c : [o * o] --> o !plus(0, 0) => 0 !plus(0, 1) => 1 !plus(0, 2) => 2 !plus(0, 3) => 3 !plus(0, 4) => 4 !plus(0, 5) => 5 !plus(0, 6) => 6 !plus(0, 7) => 7 !plus(0, 8) => 8 !plus(0, 9) => 9 !plus(1, 0) => 1 !plus(1, 1) => 2 !plus(1, 2) => 3 !plus(1, 3) => 4 !plus(1, 4) => 5 !plus(1, 5) => 6 !plus(1, 6) => 7 !plus(1, 7) => 8 !plus(1, 8) => 9 !plus(1, 9) => c(1, 0) !plus(2, 0) => 2 !plus(2, 1) => 3 !plus(2, 2) => 4 !plus(2, 3) => 5 !plus(2, 4) => 6 !plus(2, 5) => 7 !plus(2, 6) => 8 !plus(2, 7) => 9 !plus(2, 8) => c(1, 0) !plus(2, 9) => c(1, 1) !plus(3, 0) => 3 !plus(3, 1) => 4 !plus(3, 2) => 5 !plus(3, 3) => 6 !plus(3, 4) => 7 !plus(3, 5) => 8 !plus(3, 6) => 9 !plus(3, 7) => c(1, 0) !plus(3, 8) => c(1, 1) !plus(3, 9) => c(1, 2) !plus(4, 0) => 4 !plus(4, 1) => 5 !plus(4, 2) => 6 !plus(4, 3) => 7 !plus(4, 4) => 8 !plus(4, 5) => 9 !plus(4, 6) => c(1, 0) !plus(4, 7) => c(1, 1) !plus(4, 8) => c(1, 2) !plus(4, 9) => c(1, 3) !plus(5, 0) => 5 !plus(5, 1) => 6 !plus(5, 2) => 7 !plus(5, 3) => 8 !plus(5, 4) => 9 !plus(5, 5) => c(1, 0) !plus(5, 6) => c(1, 1) !plus(5, 7) => c(1, 2) !plus(5, 8) => c(1, 3) !plus(5, 9) => c(1, 4) !plus(6, 0) => 6 !plus(6, 1) => 7 !plus(6, 2) => 8 !plus(6, 3) => 9 !plus(6, 4) => c(1, 0) !plus(6, 5) => c(1, 1) !plus(6, 6) => c(1, 2) !plus(6, 7) => c(1, 3) !plus(6, 8) => c(1, 4) !plus(6, 9) => c(1, 5) !plus(7, 0) => 7 !plus(7, 1) => 8 !plus(7, 2) => 9 !plus(7, 3) => c(1, 0) !plus(7, 4) => c(1, 1) !plus(7, 5) => c(1, 2) !plus(7, 6) => c(1, 3) !plus(7, 7) => c(1, 4) !plus(7, 8) => c(1, 5) !plus(7, 9) => c(1, 6) !plus(8, 0) => 8 !plus(8, 1) => 9 !plus(8, 2) => c(1, 0) !plus(8, 3) => c(1, 1) !plus(8, 4) => c(1, 2) !plus(8, 5) => c(1, 3) !plus(8, 6) => c(1, 4) !plus(8, 7) => c(1, 5) !plus(8, 8) => c(1, 6) !plus(8, 9) => c(1, 7) !plus(9, 0) => 9 !plus(9, 1) => c(1, 0) !plus(9, 2) => c(1, 1) !plus(9, 3) => c(1, 2) !plus(9, 4) => c(1, 3) !plus(9, 5) => c(1, 4) !plus(9, 6) => c(1, 5) !plus(9, 7) => c(1, 6) !plus(9, 8) => c(1, 7) !plus(9, 9) => c(1, 8) !plus(X, c(Y, Z)) => c(Y, !plus(X, Z)) !plus(c(X, Y), Z) => c(X, !plus(Y, Z)) c(0, X) => X c(X, c(Y, Z)) => c(!plus(X, Y), Z) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !plus(0, 0) >? 0 !plus(0, 1) >? 1 !plus(0, 2) >? 2 !plus(0, 3) >? 3 !plus(0, 4) >? 4 !plus(0, 5) >? 5 !plus(0, 6) >? 6 !plus(0, 7) >? 7 !plus(0, 8) >? 8 !plus(0, 9) >? 9 !plus(1, 0) >? 1 !plus(1, 1) >? 2 !plus(1, 2) >? 3 !plus(1, 3) >? 4 !plus(1, 4) >? 5 !plus(1, 5) >? 6 !plus(1, 6) >? 7 !plus(1, 7) >? 8 !plus(1, 8) >? 9 !plus(1, 9) >? c(1, 0) !plus(2, 0) >? 2 !plus(2, 1) >? 3 !plus(2, 2) >? 4 !plus(2, 3) >? 5 !plus(2, 4) >? 6 !plus(2, 5) >? 7 !plus(2, 6) >? 8 !plus(2, 7) >? 9 !plus(2, 8) >? c(1, 0) !plus(2, 9) >? c(1, 1) !plus(3, 0) >? 3 !plus(3, 1) >? 4 !plus(3, 2) >? 5 !plus(3, 3) >? 6 !plus(3, 4) >? 7 !plus(3, 5) >? 8 !plus(3, 6) >? 9 !plus(3, 7) >? c(1, 0) !plus(3, 8) >? c(1, 1) !plus(3, 9) >? c(1, 2) !plus(4, 0) >? 4 !plus(4, 1) >? 5 !plus(4, 2) >? 6 !plus(4, 3) >? 7 !plus(4, 4) >? 8 !plus(4, 5) >? 9 !plus(4, 6) >? c(1, 0) !plus(4, 7) >? c(1, 1) !plus(4, 8) >? c(1, 2) !plus(4, 9) >? c(1, 3) !plus(5, 0) >? 5 !plus(5, 1) >? 6 !plus(5, 2) >? 7 !plus(5, 3) >? 8 !plus(5, 4) >? 9 !plus(5, 5) >? c(1, 0) !plus(5, 6) >? c(1, 1) !plus(5, 7) >? c(1, 2) !plus(5, 8) >? c(1, 3) !plus(5, 9) >? c(1, 4) !plus(6, 0) >? 6 !plus(6, 1) >? 7 !plus(6, 2) >? 8 !plus(6, 3) >? 9 !plus(6, 4) >? c(1, 0) !plus(6, 5) >? c(1, 1) !plus(6, 6) >? c(1, 2) !plus(6, 7) >? c(1, 3) !plus(6, 8) >? c(1, 4) !plus(6, 9) >? c(1, 5) !plus(7, 0) >? 7 !plus(7, 1) >? 8 !plus(7, 2) >? 9 !plus(7, 3) >? c(1, 0) !plus(7, 4) >? c(1, 1) !plus(7, 5) >? c(1, 2) !plus(7, 6) >? c(1, 3) !plus(7, 7) >? c(1, 4) !plus(7, 8) >? c(1, 5) !plus(7, 9) >? c(1, 6) !plus(8, 0) >? 8 !plus(8, 1) >? 9 !plus(8, 2) >? c(1, 0) !plus(8, 3) >? c(1, 1) !plus(8, 4) >? c(1, 2) !plus(8, 5) >? c(1, 3) !plus(8, 6) >? c(1, 4) !plus(8, 7) >? c(1, 5) !plus(8, 8) >? c(1, 6) !plus(8, 9) >? c(1, 7) !plus(9, 0) >? 9 !plus(9, 1) >? c(1, 0) !plus(9, 2) >? c(1, 1) !plus(9, 3) >? c(1, 2) !plus(9, 4) >? c(1, 3) !plus(9, 5) >? c(1, 4) !plus(9, 6) >? c(1, 5) !plus(9, 7) >? c(1, 6) !plus(9, 8) >? c(1, 7) !plus(9, 9) >? c(1, 8) !plus(X, c(Y, Z)) >? c(Y, !plus(X, Z)) !plus(c(X, Y), Z) >? c(X, !plus(Y, Z)) c(0, X) >? X c(X, c(Y, Z)) >? c(!plus(X, Y), Z) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.1 + y0 + y1 0 = 0 1 = 1 2 = 3 3 = 3 4 = 3 5 = 3 6 = 3 7 = 3 8 = 3 9 = 3 c = \y0y1.2 + y1 + 2y0 Using this interpretation, the requirements translate to: [[!plus(0, 0)]] = 1 > 0 = [[0]] [[!plus(0, 1)]] = 2 > 1 = [[1]] [[!plus(0, 2)]] = 4 > 3 = [[2]] [[!plus(0, 3)]] = 4 > 3 = [[3]] [[!plus(0, 4)]] = 4 > 3 = [[4]] [[!plus(0, 5)]] = 4 > 3 = [[5]] [[!plus(0, 6)]] = 4 > 3 = [[6]] [[!plus(0, 7)]] = 4 > 3 = [[7]] [[!plus(0, 8)]] = 4 > 3 = [[8]] [[!plus(0, 9)]] = 4 > 3 = [[9]] [[!plus(1, 0)]] = 2 > 1 = [[1]] [[!plus(1, 1)]] = 3 >= 3 = [[2]] [[!plus(1, 2)]] = 5 > 3 = [[3]] [[!plus(1, 3)]] = 5 > 3 = [[4]] [[!plus(1, 4)]] = 5 > 3 = [[5]] [[!plus(1, 5)]] = 5 > 3 = [[6]] [[!plus(1, 6)]] = 5 > 3 = [[7]] [[!plus(1, 7)]] = 5 > 3 = [[8]] [[!plus(1, 8)]] = 5 > 3 = [[9]] [[!plus(1, 9)]] = 5 > 4 = [[c(1, 0)]] [[!plus(2, 0)]] = 4 > 3 = [[2]] [[!plus(2, 1)]] = 5 > 3 = [[3]] [[!plus(2, 2)]] = 7 > 3 = [[4]] [[!plus(2, 3)]] = 7 > 3 = [[5]] [[!plus(2, 4)]] = 7 > 3 = [[6]] [[!plus(2, 5)]] = 7 > 3 = [[7]] [[!plus(2, 6)]] = 7 > 3 = [[8]] [[!plus(2, 7)]] = 7 > 3 = [[9]] [[!plus(2, 8)]] = 7 > 4 = [[c(1, 0)]] [[!plus(2, 9)]] = 7 > 5 = [[c(1, 1)]] [[!plus(3, 0)]] = 4 > 3 = [[3]] [[!plus(3, 1)]] = 5 > 3 = [[4]] [[!plus(3, 2)]] = 7 > 3 = [[5]] [[!plus(3, 3)]] = 7 > 3 = [[6]] [[!plus(3, 4)]] = 7 > 3 = [[7]] [[!plus(3, 5)]] = 7 > 3 = [[8]] [[!plus(3, 6)]] = 7 > 3 = [[9]] [[!plus(3, 7)]] = 7 > 4 = [[c(1, 0)]] [[!plus(3, 8)]] = 7 > 5 = [[c(1, 1)]] [[!plus(3, 9)]] = 7 >= 7 = [[c(1, 2)]] [[!plus(4, 0)]] = 4 > 3 = [[4]] [[!plus(4, 1)]] = 5 > 3 = [[5]] [[!plus(4, 2)]] = 7 > 3 = [[6]] [[!plus(4, 3)]] = 7 > 3 = [[7]] [[!plus(4, 4)]] = 7 > 3 = [[8]] [[!plus(4, 5)]] = 7 > 3 = [[9]] [[!plus(4, 6)]] = 7 > 4 = [[c(1, 0)]] [[!plus(4, 7)]] = 7 > 5 = [[c(1, 1)]] [[!plus(4, 8)]] = 7 >= 7 = [[c(1, 2)]] [[!plus(4, 9)]] = 7 >= 7 = [[c(1, 3)]] [[!plus(5, 0)]] = 4 > 3 = [[5]] [[!plus(5, 1)]] = 5 > 3 = [[6]] [[!plus(5, 2)]] = 7 > 3 = [[7]] [[!plus(5, 3)]] = 7 > 3 = [[8]] [[!plus(5, 4)]] = 7 > 3 = [[9]] [[!plus(5, 5)]] = 7 > 4 = [[c(1, 0)]] [[!plus(5, 6)]] = 7 > 5 = [[c(1, 1)]] [[!plus(5, 7)]] = 7 >= 7 = [[c(1, 2)]] [[!plus(5, 8)]] = 7 >= 7 = [[c(1, 3)]] [[!plus(5, 9)]] = 7 >= 7 = [[c(1, 4)]] [[!plus(6, 0)]] = 4 > 3 = [[6]] [[!plus(6, 1)]] = 5 > 3 = [[7]] [[!plus(6, 2)]] = 7 > 3 = [[8]] [[!plus(6, 3)]] = 7 > 3 = [[9]] [[!plus(6, 4)]] = 7 > 4 = [[c(1, 0)]] [[!plus(6, 5)]] = 7 > 5 = [[c(1, 1)]] [[!plus(6, 6)]] = 7 >= 7 = [[c(1, 2)]] [[!plus(6, 7)]] = 7 >= 7 = [[c(1, 3)]] [[!plus(6, 8)]] = 7 >= 7 = [[c(1, 4)]] [[!plus(6, 9)]] = 7 >= 7 = [[c(1, 5)]] [[!plus(7, 0)]] = 4 > 3 = [[7]] [[!plus(7, 1)]] = 5 > 3 = [[8]] [[!plus(7, 2)]] = 7 > 3 = [[9]] [[!plus(7, 3)]] = 7 > 4 = [[c(1, 0)]] [[!plus(7, 4)]] = 7 > 5 = [[c(1, 1)]] [[!plus(7, 5)]] = 7 >= 7 = [[c(1, 2)]] [[!plus(7, 6)]] = 7 >= 7 = [[c(1, 3)]] [[!plus(7, 7)]] = 7 >= 7 = [[c(1, 4)]] [[!plus(7, 8)]] = 7 >= 7 = [[c(1, 5)]] [[!plus(7, 9)]] = 7 >= 7 = [[c(1, 6)]] [[!plus(8, 0)]] = 4 > 3 = [[8]] [[!plus(8, 1)]] = 5 > 3 = [[9]] [[!plus(8, 2)]] = 7 > 4 = [[c(1, 0)]] [[!plus(8, 3)]] = 7 > 5 = [[c(1, 1)]] [[!plus(8, 4)]] = 7 >= 7 = [[c(1, 2)]] [[!plus(8, 5)]] = 7 >= 7 = [[c(1, 3)]] [[!plus(8, 6)]] = 7 >= 7 = [[c(1, 4)]] [[!plus(8, 7)]] = 7 >= 7 = [[c(1, 5)]] [[!plus(8, 8)]] = 7 >= 7 = [[c(1, 6)]] [[!plus(8, 9)]] = 7 >= 7 = [[c(1, 7)]] [[!plus(9, 0)]] = 4 > 3 = [[9]] [[!plus(9, 1)]] = 5 > 4 = [[c(1, 0)]] [[!plus(9, 2)]] = 7 > 5 = [[c(1, 1)]] [[!plus(9, 3)]] = 7 >= 7 = [[c(1, 2)]] [[!plus(9, 4)]] = 7 >= 7 = [[c(1, 3)]] [[!plus(9, 5)]] = 7 >= 7 = [[c(1, 4)]] [[!plus(9, 6)]] = 7 >= 7 = [[c(1, 5)]] [[!plus(9, 7)]] = 7 >= 7 = [[c(1, 6)]] [[!plus(9, 8)]] = 7 >= 7 = [[c(1, 7)]] [[!plus(9, 9)]] = 7 >= 7 = [[c(1, 8)]] [[!plus(_x0, c(_x1, _x2))]] = 3 + x0 + x2 + 2x1 >= 3 + x0 + x2 + 2x1 = [[c(_x1, !plus(_x0, _x2))]] [[!plus(c(_x0, _x1), _x2)]] = 3 + x1 + x2 + 2x0 >= 3 + x1 + x2 + 2x0 = [[c(_x0, !plus(_x1, _x2))]] [[c(0, _x0)]] = 2 + x0 > x0 = [[_x0]] [[c(_x0, c(_x1, _x2))]] = 4 + x2 + 2x0 + 2x1 >= 4 + x2 + 2x0 + 2x1 = [[c(!plus(_x0, _x1), _x2)]] We can thus remove the following rules: !plus(0, 0) => 0 !plus(0, 1) => 1 !plus(0, 2) => 2 !plus(0, 3) => 3 !plus(0, 4) => 4 !plus(0, 5) => 5 !plus(0, 6) => 6 !plus(0, 7) => 7 !plus(0, 8) => 8 !plus(0, 9) => 9 !plus(1, 0) => 1 !plus(1, 2) => 3 !plus(1, 3) => 4 !plus(1, 4) => 5 !plus(1, 5) => 6 !plus(1, 6) => 7 !plus(1, 7) => 8 !plus(1, 8) => 9 !plus(1, 9) => c(1, 0) !plus(2, 0) => 2 !plus(2, 1) => 3 !plus(2, 2) => 4 !plus(2, 3) => 5 !plus(2, 4) => 6 !plus(2, 5) => 7 !plus(2, 6) => 8 !plus(2, 7) => 9 !plus(2, 8) => c(1, 0) !plus(2, 9) => c(1, 1) !plus(3, 0) => 3 !plus(3, 1) => 4 !plus(3, 2) => 5 !plus(3, 3) => 6 !plus(3, 4) => 7 !plus(3, 5) => 8 !plus(3, 6) => 9 !plus(3, 7) => c(1, 0) !plus(3, 8) => c(1, 1) !plus(4, 0) => 4 !plus(4, 1) => 5 !plus(4, 2) => 6 !plus(4, 3) => 7 !plus(4, 4) => 8 !plus(4, 5) => 9 !plus(4, 6) => c(1, 0) !plus(4, 7) => c(1, 1) !plus(5, 0) => 5 !plus(5, 1) => 6 !plus(5, 2) => 7 !plus(5, 3) => 8 !plus(5, 4) => 9 !plus(5, 5) => c(1, 0) !plus(5, 6) => c(1, 1) !plus(6, 0) => 6 !plus(6, 1) => 7 !plus(6, 2) => 8 !plus(6, 3) => 9 !plus(6, 4) => c(1, 0) !plus(6, 5) => c(1, 1) !plus(7, 0) => 7 !plus(7, 1) => 8 !plus(7, 2) => 9 !plus(7, 3) => c(1, 0) !plus(7, 4) => c(1, 1) !plus(8, 0) => 8 !plus(8, 1) => 9 !plus(8, 2) => c(1, 0) !plus(8, 3) => c(1, 1) !plus(9, 0) => 9 !plus(9, 1) => c(1, 0) !plus(9, 2) => c(1, 1) c(0, X) => X We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !plus(1, 1) >? 2 !plus(3, 9) >? c(1, 2) !plus(4, 8) >? c(1, 2) !plus(4, 9) >? c(1, 3) !plus(5, 7) >? c(1, 2) !plus(5, 8) >? c(1, 3) !plus(5, 9) >? c(1, 4) !plus(6, 6) >? c(1, 2) !plus(6, 7) >? c(1, 3) !plus(6, 8) >? c(1, 4) !plus(6, 9) >? c(1, 5) !plus(7, 5) >? c(1, 2) !plus(7, 6) >? c(1, 3) !plus(7, 7) >? c(1, 4) !plus(7, 8) >? c(1, 5) !plus(7, 9) >? c(1, 6) !plus(8, 4) >? c(1, 2) !plus(8, 5) >? c(1, 3) !plus(8, 6) >? c(1, 4) !plus(8, 7) >? c(1, 5) !plus(8, 8) >? c(1, 6) !plus(8, 9) >? c(1, 7) !plus(9, 3) >? c(1, 2) !plus(9, 4) >? c(1, 3) !plus(9, 5) >? c(1, 4) !plus(9, 6) >? c(1, 5) !plus(9, 7) >? c(1, 6) !plus(9, 8) >? c(1, 7) !plus(9, 9) >? c(1, 8) !plus(X, c(Y, Z)) >? c(Y, !plus(X, Z)) !plus(c(X, Y), Z) >? c(X, !plus(Y, Z)) c(X, c(Y, Z)) >? c(!plus(X, Y), Z) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.y0 + y1 1 = 0 2 = 0 3 = 0 4 = 0 5 = 0 6 = 0 7 = 0 8 = 0 9 = 3 c = \y0y1.y1 + 2y0 Using this interpretation, the requirements translate to: [[!plus(1, 1)]] = 0 >= 0 = [[2]] [[!plus(3, 9)]] = 3 > 0 = [[c(1, 2)]] [[!plus(4, 8)]] = 0 >= 0 = [[c(1, 2)]] [[!plus(4, 9)]] = 3 > 0 = [[c(1, 3)]] [[!plus(5, 7)]] = 0 >= 0 = [[c(1, 2)]] [[!plus(5, 8)]] = 0 >= 0 = [[c(1, 3)]] [[!plus(5, 9)]] = 3 > 0 = [[c(1, 4)]] [[!plus(6, 6)]] = 0 >= 0 = [[c(1, 2)]] [[!plus(6, 7)]] = 0 >= 0 = [[c(1, 3)]] [[!plus(6, 8)]] = 0 >= 0 = [[c(1, 4)]] [[!plus(6, 9)]] = 3 > 0 = [[c(1, 5)]] [[!plus(7, 5)]] = 0 >= 0 = [[c(1, 2)]] [[!plus(7, 6)]] = 0 >= 0 = [[c(1, 3)]] [[!plus(7, 7)]] = 0 >= 0 = [[c(1, 4)]] [[!plus(7, 8)]] = 0 >= 0 = [[c(1, 5)]] [[!plus(7, 9)]] = 3 > 0 = [[c(1, 6)]] [[!plus(8, 4)]] = 0 >= 0 = [[c(1, 2)]] [[!plus(8, 5)]] = 0 >= 0 = [[c(1, 3)]] [[!plus(8, 6)]] = 0 >= 0 = [[c(1, 4)]] [[!plus(8, 7)]] = 0 >= 0 = [[c(1, 5)]] [[!plus(8, 8)]] = 0 >= 0 = [[c(1, 6)]] [[!plus(8, 9)]] = 3 > 0 = [[c(1, 7)]] [[!plus(9, 3)]] = 3 > 0 = [[c(1, 2)]] [[!plus(9, 4)]] = 3 > 0 = [[c(1, 3)]] [[!plus(9, 5)]] = 3 > 0 = [[c(1, 4)]] [[!plus(9, 6)]] = 3 > 0 = [[c(1, 5)]] [[!plus(9, 7)]] = 3 > 0 = [[c(1, 6)]] [[!plus(9, 8)]] = 3 > 0 = [[c(1, 7)]] [[!plus(9, 9)]] = 6 > 0 = [[c(1, 8)]] [[!plus(_x0, c(_x1, _x2))]] = x0 + x2 + 2x1 >= x0 + x2 + 2x1 = [[c(_x1, !plus(_x0, _x2))]] [[!plus(c(_x0, _x1), _x2)]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[c(_x0, !plus(_x1, _x2))]] [[c(_x0, c(_x1, _x2))]] = x2 + 2x0 + 2x1 >= x2 + 2x0 + 2x1 = [[c(!plus(_x0, _x1), _x2)]] We can thus remove the following rules: !plus(3, 9) => c(1, 2) !plus(4, 9) => c(1, 3) !plus(5, 9) => c(1, 4) !plus(6, 9) => c(1, 5) !plus(7, 9) => c(1, 6) !plus(8, 9) => c(1, 7) !plus(9, 3) => c(1, 2) !plus(9, 4) => c(1, 3) !plus(9, 5) => c(1, 4) !plus(9, 6) => c(1, 5) !plus(9, 7) => c(1, 6) !plus(9, 8) => c(1, 7) !plus(9, 9) => c(1, 8) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !plus(1, 1) >? 2 !plus(4, 8) >? c(1, 2) !plus(5, 7) >? c(1, 2) !plus(5, 8) >? c(1, 3) !plus(6, 6) >? c(1, 2) !plus(6, 7) >? c(1, 3) !plus(6, 8) >? c(1, 4) !plus(7, 5) >? c(1, 2) !plus(7, 6) >? c(1, 3) !plus(7, 7) >? c(1, 4) !plus(7, 8) >? c(1, 5) !plus(8, 4) >? c(1, 2) !plus(8, 5) >? c(1, 3) !plus(8, 6) >? c(1, 4) !plus(8, 7) >? c(1, 5) !plus(8, 8) >? c(1, 6) !plus(X, c(Y, Z)) >? c(Y, !plus(X, Z)) !plus(c(X, Y), Z) >? c(X, !plus(Y, Z)) c(X, c(Y, Z)) >? c(!plus(X, Y), Z) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.y0 + y1 1 = 0 2 = 0 3 = 0 4 = 0 5 = 1 6 = 0 7 = 3 8 = 3 c = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[!plus(1, 1)]] = 0 >= 0 = [[2]] [[!plus(4, 8)]] = 3 > 0 = [[c(1, 2)]] [[!plus(5, 7)]] = 4 > 0 = [[c(1, 2)]] [[!plus(5, 8)]] = 4 > 0 = [[c(1, 3)]] [[!plus(6, 6)]] = 0 >= 0 = [[c(1, 2)]] [[!plus(6, 7)]] = 3 > 0 = [[c(1, 3)]] [[!plus(6, 8)]] = 3 > 0 = [[c(1, 4)]] [[!plus(7, 5)]] = 4 > 0 = [[c(1, 2)]] [[!plus(7, 6)]] = 3 > 0 = [[c(1, 3)]] [[!plus(7, 7)]] = 6 > 0 = [[c(1, 4)]] [[!plus(7, 8)]] = 6 > 1 = [[c(1, 5)]] [[!plus(8, 4)]] = 3 > 0 = [[c(1, 2)]] [[!plus(8, 5)]] = 4 > 0 = [[c(1, 3)]] [[!plus(8, 6)]] = 3 > 0 = [[c(1, 4)]] [[!plus(8, 7)]] = 6 > 1 = [[c(1, 5)]] [[!plus(8, 8)]] = 6 > 0 = [[c(1, 6)]] [[!plus(_x0, c(_x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[c(_x1, !plus(_x0, _x2))]] [[!plus(c(_x0, _x1), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[c(_x0, !plus(_x1, _x2))]] [[c(_x0, c(_x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[c(!plus(_x0, _x1), _x2)]] We can thus remove the following rules: !plus(4, 8) => c(1, 2) !plus(5, 7) => c(1, 2) !plus(5, 8) => c(1, 3) !plus(6, 7) => c(1, 3) !plus(6, 8) => c(1, 4) !plus(7, 5) => c(1, 2) !plus(7, 6) => c(1, 3) !plus(7, 7) => c(1, 4) !plus(7, 8) => c(1, 5) !plus(8, 4) => c(1, 2) !plus(8, 5) => c(1, 3) !plus(8, 6) => c(1, 4) !plus(8, 7) => c(1, 5) !plus(8, 8) => c(1, 6) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !plus(1, 1) >? 2 !plus(6, 6) >? c(1, 2) !plus(X, c(Y, Z)) >? c(Y, !plus(X, Z)) !plus(c(X, Y), Z) >? c(X, !plus(Y, Z)) c(X, c(Y, Z)) >? c(!plus(X, Y), Z) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.y0 + y1 1 = 0 2 = 0 6 = 3 c = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[!plus(1, 1)]] = 0 >= 0 = [[2]] [[!plus(6, 6)]] = 6 > 0 = [[c(1, 2)]] [[!plus(_x0, c(_x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[c(_x1, !plus(_x0, _x2))]] [[!plus(c(_x0, _x1), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[c(_x0, !plus(_x1, _x2))]] [[c(_x0, c(_x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[c(!plus(_x0, _x1), _x2)]] We can thus remove the following rules: !plus(6, 6) => c(1, 2) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !plus(1, 1) >? 2 !plus(X, c(Y, Z)) >? c(Y, !plus(X, Z)) !plus(c(X, Y), Z) >? c(X, !plus(Y, Z)) c(X, c(Y, Z)) >? c(!plus(X, Y), Z) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.y0 + y1 1 = 3 2 = 0 c = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[!plus(1, 1)]] = 6 > 0 = [[2]] [[!plus(_x0, c(_x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[c(_x1, !plus(_x0, _x2))]] [[!plus(c(_x0, _x1), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[c(_x0, !plus(_x1, _x2))]] [[c(_x0, c(_x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[c(!plus(_x0, _x1), _x2)]] We can thus remove the following rules: !plus(1, 1) => 2 We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !plus(X, c(Y, Z)) >? c(Y, !plus(X, Z)) !plus(c(X, Y), Z) >? c(X, !plus(Y, Z)) c(X, c(Y, Z)) >? c(!plus(X, Y), Z) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.y0 + y1 c = \y0y1.1 + y1 + 2y0 Using this interpretation, the requirements translate to: [[!plus(_x0, c(_x1, _x2))]] = 1 + x0 + x2 + 2x1 >= 1 + x0 + x2 + 2x1 = [[c(_x1, !plus(_x0, _x2))]] [[!plus(c(_x0, _x1), _x2)]] = 1 + x1 + x2 + 2x0 >= 1 + x1 + x2 + 2x0 = [[c(_x0, !plus(_x1, _x2))]] [[c(_x0, c(_x1, _x2))]] = 2 + x2 + 2x0 + 2x1 > 1 + x2 + 2x0 + 2x1 = [[c(!plus(_x0, _x1), _x2)]] We can thus remove the following rules: c(X, c(Y, Z)) => c(!plus(X, Y), Z) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !plus(X, c(Y, Z)) >? c(Y, !plus(X, Z)) !plus(c(X, Y), Z) >? c(X, !plus(Y, Z)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.3y0 + 3y1 c = \y0y1.2 + y0 + y1 Using this interpretation, the requirements translate to: [[!plus(_x0, c(_x1, _x2))]] = 6 + 3x0 + 3x1 + 3x2 > 2 + x1 + 3x0 + 3x2 = [[c(_x1, !plus(_x0, _x2))]] [[!plus(c(_x0, _x1), _x2)]] = 6 + 3x0 + 3x1 + 3x2 > 2 + x0 + 3x1 + 3x2 = [[c(_x0, !plus(_x1, _x2))]] We can thus remove the following rules: !plus(X, c(Y, Z)) => c(Y, !plus(X, Z)) !plus(c(X, Y), Z) => c(X, !plus(Y, Z)) All rules were succesfully removed. Thus, termination of the original system has been reduced to termination of the beta-rule, which is well-known to hold. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012.