/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/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 !times : [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 c(0, X) => X c(X, c(Y, Z)) => c(!plus(X, Y), Z) !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)) !times(0, 0) => 0 !times(0, 1) => 0 !times(0, 2) => 0 !times(0, 3) => 0 !times(0, 4) => 0 !times(0, 5) => 0 !times(0, 6) => 0 !times(0, 7) => 0 !times(0, 8) => 0 !times(0, 9) => 0 !times(1, 0) => 0 !times(1, 1) => 1 !times(1, 2) => 2 !times(1, 3) => 3 !times(1, 4) => 4 !times(1, 5) => 5 !times(1, 6) => 6 !times(1, 7) => 7 !times(1, 8) => 8 !times(1, 9) => 9 !times(2, 0) => 0 !times(2, 1) => 2 !times(2, 2) => 4 !times(2, 3) => 6 !times(2, 4) => 8 !times(2, 5) => c(1, 0) !times(2, 6) => c(1, 2) !times(2, 7) => c(1, 4) !times(2, 8) => c(1, 6) !times(2, 9) => c(1, 8) !times(3, 0) => 0 !times(3, 1) => 3 !times(3, 2) => 6 !times(3, 3) => 9 !times(3, 4) => c(1, 2) !times(3, 5) => c(1, 5) !times(3, 6) => c(1, 8) !times(3, 7) => c(2, 1) !times(3, 8) => c(2, 4) !times(3, 9) => c(2, 7) !times(4, 0) => 0 !times(4, 1) => 4 !times(4, 2) => 8 !times(4, 3) => c(1, 2) !times(4, 4) => c(1, 6) !times(4, 5) => c(2, 0) !times(4, 6) => c(2, 4) !times(4, 7) => c(2, 8) !times(4, 8) => c(3, 2) !times(4, 9) => c(3, 6) !times(5, 0) => 0 !times(5, 1) => 5 !times(5, 2) => c(1, 0) !times(5, 3) => c(1, 5) !times(5, 4) => c(2, 0) !times(5, 5) => c(2, 5) !times(5, 6) => c(3, 0) !times(5, 7) => c(3, 5) !times(5, 8) => c(4, 0) !times(5, 9) => c(4, 5) !times(6, 0) => 0 !times(6, 1) => 6 !times(6, 2) => c(1, 2) !times(6, 3) => c(1, 8) !times(6, 4) => c(2, 4) !times(6, 5) => c(3, 0) !times(6, 6) => c(3, 6) !times(6, 7) => c(4, 2) !times(6, 8) => c(4, 8) !times(6, 9) => c(5, 4) !times(7, 0) => 0 !times(7, 1) => 7 !times(7, 2) => c(1, 4) !times(7, 3) => c(2, 1) !times(7, 4) => c(2, 8) !times(7, 5) => c(3, 5) !times(7, 6) => c(4, 2) !times(7, 7) => c(4, 9) !times(7, 8) => c(5, 6) !times(7, 9) => c(6, 3) !times(8, 0) => 0 !times(8, 1) => 8 !times(8, 2) => c(1, 8) !times(8, 3) => c(2, 4) !times(8, 4) => c(3, 2) !times(8, 5) => c(4, 0) !times(8, 6) => c(4, 8) !times(8, 7) => c(5, 6) !times(8, 8) => c(6, 4) !times(8, 9) => c(7, 2) !times(9, 0) => 0 !times(9, 1) => 9 !times(9, 2) => c(1, 8) !times(9, 3) => c(2, 7) !times(9, 4) => c(3, 6) !times(9, 5) => c(4, 5) !times(9, 6) => c(5, 4) !times(9, 7) => c(6, 3) !times(9, 8) => c(7, 2) !times(9, 9) => c(8, 1) !times(X, c(Y, Z)) => c(!times(X, Y), !times(X, Z)) !times(c(X, Y), Z) => c(!times(X, Z), !times(Y, Z)) We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] c#(X, c(Y, Z)) =#> c#(!plus(X, Y), Z) 1] c#(X, c(Y, Z)) =#> !plus#(X, Y) 2] !plus#(1, 9) =#> c#(1, 0) 3] !plus#(2, 8) =#> c#(1, 0) 4] !plus#(2, 9) =#> c#(1, 1) 5] !plus#(3, 7) =#> c#(1, 0) 6] !plus#(3, 8) =#> c#(1, 1) 7] !plus#(3, 9) =#> c#(1, 2) 8] !plus#(4, 6) =#> c#(1, 0) 9] !plus#(4, 7) =#> c#(1, 1) 10] !plus#(4, 8) =#> c#(1, 2) 11] !plus#(4, 9) =#> c#(1, 3) 12] !plus#(5, 5) =#> c#(1, 0) 13] !plus#(5, 6) =#> c#(1, 1) 14] !plus#(5, 7) =#> c#(1, 2) 15] !plus#(5, 8) =#> c#(1, 3) 16] !plus#(5, 9) =#> c#(1, 4) 17] !plus#(6, 4) =#> c#(1, 0) 18] !plus#(6, 5) =#> c#(1, 1) 19] !plus#(6, 6) =#> c#(1, 2) 20] !plus#(6, 7) =#> c#(1, 3) 21] !plus#(6, 8) =#> c#(1, 4) 22] !plus#(6, 9) =#> c#(1, 5) 23] !plus#(7, 3) =#> c#(1, 0) 24] !plus#(7, 4) =#> c#(1, 1) 25] !plus#(7, 5) =#> c#(1, 2) 26] !plus#(7, 6) =#> c#(1, 3) 27] !plus#(7, 7) =#> c#(1, 4) 28] !plus#(7, 8) =#> c#(1, 5) 29] !plus#(7, 9) =#> c#(1, 6) 30] !plus#(8, 2) =#> c#(1, 0) 31] !plus#(8, 3) =#> c#(1, 1) 32] !plus#(8, 4) =#> c#(1, 2) 33] !plus#(8, 5) =#> c#(1, 3) 34] !plus#(8, 6) =#> c#(1, 4) 35] !plus#(8, 7) =#> c#(1, 5) 36] !plus#(8, 8) =#> c#(1, 6) 37] !plus#(8, 9) =#> c#(1, 7) 38] !plus#(9, 1) =#> c#(1, 0) 39] !plus#(9, 2) =#> c#(1, 1) 40] !plus#(9, 3) =#> c#(1, 2) 41] !plus#(9, 4) =#> c#(1, 3) 42] !plus#(9, 5) =#> c#(1, 4) 43] !plus#(9, 6) =#> c#(1, 5) 44] !plus#(9, 7) =#> c#(1, 6) 45] !plus#(9, 8) =#> c#(1, 7) 46] !plus#(9, 9) =#> c#(1, 8) 47] !plus#(X, c(Y, Z)) =#> c#(Y, !plus(X, Z)) 48] !plus#(X, c(Y, Z)) =#> !plus#(X, Z) 49] !plus#(c(X, Y), Z) =#> c#(X, !plus(Y, Z)) 50] !plus#(c(X, Y), Z) =#> !plus#(Y, Z) 51] !times#(2, 5) =#> c#(1, 0) 52] !times#(2, 6) =#> c#(1, 2) 53] !times#(2, 7) =#> c#(1, 4) 54] !times#(2, 8) =#> c#(1, 6) 55] !times#(2, 9) =#> c#(1, 8) 56] !times#(3, 4) =#> c#(1, 2) 57] !times#(3, 5) =#> c#(1, 5) 58] !times#(3, 6) =#> c#(1, 8) 59] !times#(3, 7) =#> c#(2, 1) 60] !times#(3, 8) =#> c#(2, 4) 61] !times#(3, 9) =#> c#(2, 7) 62] !times#(4, 3) =#> c#(1, 2) 63] !times#(4, 4) =#> c#(1, 6) 64] !times#(4, 5) =#> c#(2, 0) 65] !times#(4, 6) =#> c#(2, 4) 66] !times#(4, 7) =#> c#(2, 8) 67] !times#(4, 8) =#> c#(3, 2) 68] !times#(4, 9) =#> c#(3, 6) 69] !times#(5, 2) =#> c#(1, 0) 70] !times#(5, 3) =#> c#(1, 5) 71] !times#(5, 4) =#> c#(2, 0) 72] !times#(5, 5) =#> c#(2, 5) 73] !times#(5, 6) =#> c#(3, 0) 74] !times#(5, 7) =#> c#(3, 5) 75] !times#(5, 8) =#> c#(4, 0) 76] !times#(5, 9) =#> c#(4, 5) 77] !times#(6, 2) =#> c#(1, 2) 78] !times#(6, 3) =#> c#(1, 8) 79] !times#(6, 4) =#> c#(2, 4) 80] !times#(6, 5) =#> c#(3, 0) 81] !times#(6, 6) =#> c#(3, 6) 82] !times#(6, 7) =#> c#(4, 2) 83] !times#(6, 8) =#> c#(4, 8) 84] !times#(6, 9) =#> c#(5, 4) 85] !times#(7, 2) =#> c#(1, 4) 86] !times#(7, 3) =#> c#(2, 1) 87] !times#(7, 4) =#> c#(2, 8) 88] !times#(7, 5) =#> c#(3, 5) 89] !times#(7, 6) =#> c#(4, 2) 90] !times#(7, 7) =#> c#(4, 9) 91] !times#(7, 8) =#> c#(5, 6) 92] !times#(7, 9) =#> c#(6, 3) 93] !times#(8, 2) =#> c#(1, 8) 94] !times#(8, 3) =#> c#(2, 4) 95] !times#(8, 4) =#> c#(3, 2) 96] !times#(8, 5) =#> c#(4, 0) 97] !times#(8, 6) =#> c#(4, 8) 98] !times#(8, 7) =#> c#(5, 6) 99] !times#(8, 8) =#> c#(6, 4) 100] !times#(8, 9) =#> c#(7, 2) 101] !times#(9, 2) =#> c#(1, 8) 102] !times#(9, 3) =#> c#(2, 7) 103] !times#(9, 4) =#> c#(3, 6) 104] !times#(9, 5) =#> c#(4, 5) 105] !times#(9, 6) =#> c#(5, 4) 106] !times#(9, 7) =#> c#(6, 3) 107] !times#(9, 8) =#> c#(7, 2) 108] !times#(9, 9) =#> c#(8, 1) 109] !times#(X, c(Y, Z)) =#> c#(!times(X, Y), !times(X, Z)) 110] !times#(X, c(Y, Z)) =#> !times#(X, Y) 111] !times#(X, c(Y, Z)) =#> !times#(X, Z) 112] !times#(c(X, Y), Z) =#> c#(!times(X, Z), !times(Y, Z)) 113] !times#(c(X, Y), Z) =#> !times#(X, Z) 114] !times#(c(X, Y), Z) =#> !times#(Y, Z) Rules R_0: c(0, X) => X c(X, c(Y, Z)) => c(!plus(X, Y), Z) !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)) !times(0, 0) => 0 !times(0, 1) => 0 !times(0, 2) => 0 !times(0, 3) => 0 !times(0, 4) => 0 !times(0, 5) => 0 !times(0, 6) => 0 !times(0, 7) => 0 !times(0, 8) => 0 !times(0, 9) => 0 !times(1, 0) => 0 !times(1, 1) => 1 !times(1, 2) => 2 !times(1, 3) => 3 !times(1, 4) => 4 !times(1, 5) => 5 !times(1, 6) => 6 !times(1, 7) => 7 !times(1, 8) => 8 !times(1, 9) => 9 !times(2, 0) => 0 !times(2, 1) => 2 !times(2, 2) => 4 !times(2, 3) => 6 !times(2, 4) => 8 !times(2, 5) => c(1, 0) !times(2, 6) => c(1, 2) !times(2, 7) => c(1, 4) !times(2, 8) => c(1, 6) !times(2, 9) => c(1, 8) !times(3, 0) => 0 !times(3, 1) => 3 !times(3, 2) => 6 !times(3, 3) => 9 !times(3, 4) => c(1, 2) !times(3, 5) => c(1, 5) !times(3, 6) => c(1, 8) !times(3, 7) => c(2, 1) !times(3, 8) => c(2, 4) !times(3, 9) => c(2, 7) !times(4, 0) => 0 !times(4, 1) => 4 !times(4, 2) => 8 !times(4, 3) => c(1, 2) !times(4, 4) => c(1, 6) !times(4, 5) => c(2, 0) !times(4, 6) => c(2, 4) !times(4, 7) => c(2, 8) !times(4, 8) => c(3, 2) !times(4, 9) => c(3, 6) !times(5, 0) => 0 !times(5, 1) => 5 !times(5, 2) => c(1, 0) !times(5, 3) => c(1, 5) !times(5, 4) => c(2, 0) !times(5, 5) => c(2, 5) !times(5, 6) => c(3, 0) !times(5, 7) => c(3, 5) !times(5, 8) => c(4, 0) !times(5, 9) => c(4, 5) !times(6, 0) => 0 !times(6, 1) => 6 !times(6, 2) => c(1, 2) !times(6, 3) => c(1, 8) !times(6, 4) => c(2, 4) !times(6, 5) => c(3, 0) !times(6, 6) => c(3, 6) !times(6, 7) => c(4, 2) !times(6, 8) => c(4, 8) !times(6, 9) => c(5, 4) !times(7, 0) => 0 !times(7, 1) => 7 !times(7, 2) => c(1, 4) !times(7, 3) => c(2, 1) !times(7, 4) => c(2, 8) !times(7, 5) => c(3, 5) !times(7, 6) => c(4, 2) !times(7, 7) => c(4, 9) !times(7, 8) => c(5, 6) !times(7, 9) => c(6, 3) !times(8, 0) => 0 !times(8, 1) => 8 !times(8, 2) => c(1, 8) !times(8, 3) => c(2, 4) !times(8, 4) => c(3, 2) !times(8, 5) => c(4, 0) !times(8, 6) => c(4, 8) !times(8, 7) => c(5, 6) !times(8, 8) => c(6, 4) !times(8, 9) => c(7, 2) !times(9, 0) => 0 !times(9, 1) => 9 !times(9, 2) => c(1, 8) !times(9, 3) => c(2, 7) !times(9, 4) => c(3, 6) !times(9, 5) => c(4, 5) !times(9, 6) => c(5, 4) !times(9, 7) => c(6, 3) !times(9, 8) => c(7, 2) !times(9, 9) => c(8, 1) !times(X, c(Y, Z)) => c(!times(X, Y), !times(X, Z)) !times(c(X, Y), Z) => c(!times(X, Z), !times(Y, Z)) Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 0, 1 * 1 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 2 : * 3 : * 4 : * 5 : * 6 : * 7 : * 8 : * 9 : * 10 : * 11 : * 12 : * 13 : * 14 : * 15 : * 16 : * 17 : * 18 : * 19 : * 20 : * 21 : * 22 : * 23 : * 24 : * 25 : * 26 : * 27 : * 28 : * 29 : * 30 : * 31 : * 32 : * 33 : * 34 : * 35 : * 36 : * 37 : * 38 : * 39 : * 40 : * 41 : * 42 : * 43 : * 44 : * 45 : * 46 : * 47 : 0, 1 * 48 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 49 : 0, 1 * 50 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 51 : * 52 : * 53 : * 54 : * 55 : * 56 : * 57 : * 58 : * 59 : * 60 : * 61 : * 62 : * 63 : * 64 : * 65 : * 66 : * 67 : * 68 : * 69 : * 70 : * 71 : * 72 : * 73 : * 74 : * 75 : * 76 : * 77 : * 78 : * 79 : * 80 : * 81 : * 82 : * 83 : * 84 : * 85 : * 86 : * 87 : * 88 : * 89 : * 90 : * 91 : * 92 : * 93 : * 94 : * 95 : * 96 : * 97 : * 98 : * 99 : * 100 : * 101 : * 102 : * 103 : * 104 : * 105 : * 106 : * 107 : * 108 : * 109 : 0, 1 * 110 : 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114 * 111 : 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114 * 112 : 0, 1 * 113 : 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114 * 114 : 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114 This graph has the following strongly connected components: P_1: c#(X, c(Y, Z)) =#> c#(!plus(X, Y), Z) c#(X, c(Y, Z)) =#> !plus#(X, Y) !plus#(X, c(Y, Z)) =#> c#(Y, !plus(X, Z)) !plus#(X, c(Y, Z)) =#> !plus#(X, Z) !plus#(c(X, Y), Z) =#> c#(X, !plus(Y, Z)) !plus#(c(X, Y), Z) =#> !plus#(Y, Z) P_2: !times#(X, c(Y, Z)) =#> !times#(X, Y) !times#(X, c(Y, Z)) =#> !times#(X, Z) !times#(c(X, Y), Z) =#> !times#(X, Z) !times#(c(X, Y), Z) =#> !times#(Y, Z) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f) and (P_2, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(!times#) = 2 Thus, we can orient the dependency pairs as follows: nu(!times#(X, c(Y, Z))) = c(Y, Z) |> Y = nu(!times#(X, Y)) nu(!times#(X, c(Y, Z))) = c(Y, Z) |> Z = nu(!times#(X, Z)) nu(!times#(c(X, Y), Z)) = Z = Z = nu(!times#(X, Z)) nu(!times#(c(X, Y), Z)) = Z = Z = nu(!times#(Y, Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_2, R_0, minimal, f) by (P_3, R_0, minimal, f), where P_3 contains: !times#(c(X, Y), Z) =#> !times#(X, Z) !times#(c(X, Y), Z) =#> !times#(Y, Z) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_3, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_3, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(!times#) = 1 Thus, we can orient the dependency pairs as follows: nu(!times#(c(X, Y), Z)) = c(X, Y) |> X = nu(!times#(X, Z)) nu(!times#(c(X, Y), Z)) = c(X, Y) |> Y = nu(!times#(Y, Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_3, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_0, minimal, formative). We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_1, R_0) are: c(0, X) => X c(X, c(Y, Z)) => c(!plus(X, Y), Z) !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)) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: c#(X, c(Y, Z)) >? c#(!plus(X, Y), Z) c#(X, c(Y, Z)) >? !plus#(X, Y) !plus#(X, c(Y, Z)) >? c#(Y, !plus(X, Z)) !plus#(X, c(Y, Z)) >? !plus#(X, Z) !plus#(c(X, Y), Z) >? c#(X, !plus(Y, Z)) !plus#(c(X, Y), Z) >? !plus#(Y, Z) c(0, X) >= X c(X, c(Y, Z)) >= c(!plus(X, Y), Z) !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)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.1 + y0 + y1 !plus# = \y0y1.3 + y0 + 2y1 0 = 0 1 = 0 2 = 0 3 = 0 4 = 1 5 = 1 6 = 1 7 = 1 8 = 2 9 = 2 c = \y0y1.2 + y1 + 2y0 c# = \y0y1.1 + y1 + 2y0 Using this interpretation, the requirements translate to: [[c#(_x0, c(_x1, _x2))]] = 3 + x2 + 2x0 + 2x1 >= 3 + x2 + 2x0 + 2x1 = [[c#(!plus(_x0, _x1), _x2)]] [[c#(_x0, c(_x1, _x2))]] = 3 + x2 + 2x0 + 2x1 >= 3 + x0 + 2x1 = [[!plus#(_x0, _x1)]] [[!plus#(_x0, c(_x1, _x2))]] = 7 + x0 + 2x2 + 4x1 > 2 + x0 + x2 + 2x1 = [[c#(_x1, !plus(_x0, _x2))]] [[!plus#(_x0, c(_x1, _x2))]] = 7 + x0 + 2x2 + 4x1 > 3 + x0 + 2x2 = [[!plus#(_x0, _x2)]] [[!plus#(c(_x0, _x1), _x2)]] = 5 + x1 + 2x0 + 2x2 > 2 + x1 + x2 + 2x0 = [[c#(_x0, !plus(_x1, _x2))]] [[!plus#(c(_x0, _x1), _x2)]] = 5 + x1 + 2x0 + 2x2 > 3 + x1 + 2x2 = [[!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)]] [[!plus(0, 0)]] = 1 >= 0 = [[0]] [[!plus(0, 1)]] = 1 >= 0 = [[1]] [[!plus(0, 2)]] = 1 >= 0 = [[2]] [[!plus(0, 3)]] = 1 >= 0 = [[3]] [[!plus(0, 4)]] = 2 >= 1 = [[4]] [[!plus(0, 5)]] = 2 >= 1 = [[5]] [[!plus(0, 6)]] = 2 >= 1 = [[6]] [[!plus(0, 7)]] = 2 >= 1 = [[7]] [[!plus(0, 8)]] = 3 >= 2 = [[8]] [[!plus(0, 9)]] = 3 >= 2 = [[9]] [[!plus(1, 0)]] = 1 >= 0 = [[1]] [[!plus(1, 1)]] = 1 >= 0 = [[2]] [[!plus(1, 2)]] = 1 >= 0 = [[3]] [[!plus(1, 3)]] = 1 >= 1 = [[4]] [[!plus(1, 4)]] = 2 >= 1 = [[5]] [[!plus(1, 5)]] = 2 >= 1 = [[6]] [[!plus(1, 6)]] = 2 >= 1 = [[7]] [[!plus(1, 7)]] = 2 >= 2 = [[8]] [[!plus(1, 8)]] = 3 >= 2 = [[9]] [[!plus(1, 9)]] = 3 >= 2 = [[c(1, 0)]] [[!plus(2, 0)]] = 1 >= 0 = [[2]] [[!plus(2, 1)]] = 1 >= 0 = [[3]] [[!plus(2, 2)]] = 1 >= 1 = [[4]] [[!plus(2, 3)]] = 1 >= 1 = [[5]] [[!plus(2, 4)]] = 2 >= 1 = [[6]] [[!plus(2, 5)]] = 2 >= 1 = [[7]] [[!plus(2, 6)]] = 2 >= 2 = [[8]] [[!plus(2, 7)]] = 2 >= 2 = [[9]] [[!plus(2, 8)]] = 3 >= 2 = [[c(1, 0)]] [[!plus(2, 9)]] = 3 >= 2 = [[c(1, 1)]] [[!plus(3, 0)]] = 1 >= 0 = [[3]] [[!plus(3, 1)]] = 1 >= 1 = [[4]] [[!plus(3, 2)]] = 1 >= 1 = [[5]] [[!plus(3, 3)]] = 1 >= 1 = [[6]] [[!plus(3, 4)]] = 2 >= 1 = [[7]] [[!plus(3, 5)]] = 2 >= 2 = [[8]] [[!plus(3, 6)]] = 2 >= 2 = [[9]] [[!plus(3, 7)]] = 2 >= 2 = [[c(1, 0)]] [[!plus(3, 8)]] = 3 >= 2 = [[c(1, 1)]] [[!plus(3, 9)]] = 3 >= 2 = [[c(1, 2)]] [[!plus(4, 0)]] = 2 >= 1 = [[4]] [[!plus(4, 1)]] = 2 >= 1 = [[5]] [[!plus(4, 2)]] = 2 >= 1 = [[6]] [[!plus(4, 3)]] = 2 >= 1 = [[7]] [[!plus(4, 4)]] = 3 >= 2 = [[8]] [[!plus(4, 5)]] = 3 >= 2 = [[9]] [[!plus(4, 6)]] = 3 >= 2 = [[c(1, 0)]] [[!plus(4, 7)]] = 3 >= 2 = [[c(1, 1)]] [[!plus(4, 8)]] = 4 >= 2 = [[c(1, 2)]] [[!plus(4, 9)]] = 4 >= 2 = [[c(1, 3)]] [[!plus(5, 0)]] = 2 >= 1 = [[5]] [[!plus(5, 1)]] = 2 >= 1 = [[6]] [[!plus(5, 2)]] = 2 >= 1 = [[7]] [[!plus(5, 3)]] = 2 >= 2 = [[8]] [[!plus(5, 4)]] = 3 >= 2 = [[9]] [[!plus(5, 5)]] = 3 >= 2 = [[c(1, 0)]] [[!plus(5, 6)]] = 3 >= 2 = [[c(1, 1)]] [[!plus(5, 7)]] = 3 >= 2 = [[c(1, 2)]] [[!plus(5, 8)]] = 4 >= 2 = [[c(1, 3)]] [[!plus(5, 9)]] = 4 >= 3 = [[c(1, 4)]] [[!plus(6, 0)]] = 2 >= 1 = [[6]] [[!plus(6, 1)]] = 2 >= 1 = [[7]] [[!plus(6, 2)]] = 2 >= 2 = [[8]] [[!plus(6, 3)]] = 2 >= 2 = [[9]] [[!plus(6, 4)]] = 3 >= 2 = [[c(1, 0)]] [[!plus(6, 5)]] = 3 >= 2 = [[c(1, 1)]] [[!plus(6, 6)]] = 3 >= 2 = [[c(1, 2)]] [[!plus(6, 7)]] = 3 >= 2 = [[c(1, 3)]] [[!plus(6, 8)]] = 4 >= 3 = [[c(1, 4)]] [[!plus(6, 9)]] = 4 >= 3 = [[c(1, 5)]] [[!plus(7, 0)]] = 2 >= 1 = [[7]] [[!plus(7, 1)]] = 2 >= 2 = [[8]] [[!plus(7, 2)]] = 2 >= 2 = [[9]] [[!plus(7, 3)]] = 2 >= 2 = [[c(1, 0)]] [[!plus(7, 4)]] = 3 >= 2 = [[c(1, 1)]] [[!plus(7, 5)]] = 3 >= 2 = [[c(1, 2)]] [[!plus(7, 6)]] = 3 >= 2 = [[c(1, 3)]] [[!plus(7, 7)]] = 3 >= 3 = [[c(1, 4)]] [[!plus(7, 8)]] = 4 >= 3 = [[c(1, 5)]] [[!plus(7, 9)]] = 4 >= 3 = [[c(1, 6)]] [[!plus(8, 0)]] = 3 >= 2 = [[8]] [[!plus(8, 1)]] = 3 >= 2 = [[9]] [[!plus(8, 2)]] = 3 >= 2 = [[c(1, 0)]] [[!plus(8, 3)]] = 3 >= 2 = [[c(1, 1)]] [[!plus(8, 4)]] = 4 >= 2 = [[c(1, 2)]] [[!plus(8, 5)]] = 4 >= 2 = [[c(1, 3)]] [[!plus(8, 6)]] = 4 >= 3 = [[c(1, 4)]] [[!plus(8, 7)]] = 4 >= 3 = [[c(1, 5)]] [[!plus(8, 8)]] = 5 >= 3 = [[c(1, 6)]] [[!plus(8, 9)]] = 5 >= 3 = [[c(1, 7)]] [[!plus(9, 0)]] = 3 >= 2 = [[9]] [[!plus(9, 1)]] = 3 >= 2 = [[c(1, 0)]] [[!plus(9, 2)]] = 3 >= 2 = [[c(1, 1)]] [[!plus(9, 3)]] = 3 >= 2 = [[c(1, 2)]] [[!plus(9, 4)]] = 4 >= 2 = [[c(1, 3)]] [[!plus(9, 5)]] = 4 >= 3 = [[c(1, 4)]] [[!plus(9, 6)]] = 4 >= 3 = [[c(1, 5)]] [[!plus(9, 7)]] = 4 >= 3 = [[c(1, 6)]] [[!plus(9, 8)]] = 5 >= 3 = [[c(1, 7)]] [[!plus(9, 9)]] = 5 >= 4 = [[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))]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_4, R_0, minimal, formative), where P_4 consists of: c#(X, c(Y, Z)) =#> c#(!plus(X, Y), Z) c#(X, c(Y, Z)) =#> !plus#(X, Y) Thus, the original system is terminating if (P_4, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 0, 1 * 1 : This graph has the following strongly connected components: P_5: c#(X, c(Y, Z)) =#> c#(!plus(X, Y), Z) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_4, R_0, m, f) by (P_5, R_0, m, f). Thus, the original system is terminating if (P_5, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_5, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(c#) = 2 Thus, we can orient the dependency pairs as follows: nu(c#(X, c(Y, Z))) = c(Y, Z) |> Z = nu(c#(!plus(X, Y), Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_5, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. [KusIsoSakBla09] K. Kusakari, Y. Isogai, M. Sakai, and F. Blanqui. Static Dependency Pair Method Based On Strong Computability for Higher-Order Rewrite Systems. In volume 92(10) of IEICE Transactions on Information and Systems. 2007--2015, 2009.