/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. 0 : [] --> o U11 : [o * o] --> o U12 : [o] --> o U21 : [o] --> o U31 : [o * o] --> o U41 : [o * o * o] --> o U42 : [o * o * o] --> o active : [o] --> o isNat : [o] --> o mark : [o] --> o plus : [o * o] --> o s : [o] --> o tt : [] --> o active(U11(tt, X)) => mark(U12(isNat(X))) active(U12(tt)) => mark(tt) active(U21(tt)) => mark(tt) active(U31(tt, X)) => mark(X) active(U41(tt, X, Y)) => mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) => mark(s(plus(Y, X))) active(isNat(0)) => mark(tt) active(isNat(plus(X, Y))) => mark(U11(isNat(X), Y)) active(isNat(s(X))) => mark(U21(isNat(X))) active(plus(X, 0)) => mark(U31(isNat(X), X)) active(plus(X, s(Y))) => mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) => active(U11(mark(X), Y)) mark(tt) => active(tt) mark(U12(X)) => active(U12(mark(X))) mark(isNat(X)) => active(isNat(X)) mark(U21(X)) => active(U21(mark(X))) mark(U31(X, Y)) => active(U31(mark(X), Y)) mark(U41(X, Y, Z)) => active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) => active(U42(mark(X), Y, Z)) mark(s(X)) => active(s(mark(X))) mark(plus(X, Y)) => active(plus(mark(X), mark(Y))) mark(0) => active(0) U11(mark(X), Y) => U11(X, Y) U11(X, mark(Y)) => U11(X, Y) U11(active(X), Y) => U11(X, Y) U11(X, active(Y)) => U11(X, Y) U12(mark(X)) => U12(X) U12(active(X)) => U12(X) isNat(mark(X)) => isNat(X) isNat(active(X)) => isNat(X) U21(mark(X)) => U21(X) U21(active(X)) => U21(X) U31(mark(X), Y) => U31(X, Y) U31(X, mark(Y)) => U31(X, Y) U31(active(X), Y) => U31(X, Y) U31(X, active(Y)) => U31(X, Y) U41(mark(X), Y, Z) => U41(X, Y, Z) U41(X, mark(Y), Z) => U41(X, Y, Z) U41(X, Y, mark(Z)) => U41(X, Y, Z) U41(active(X), Y, Z) => U41(X, Y, Z) U41(X, active(Y), Z) => U41(X, Y, Z) U41(X, Y, active(Z)) => U41(X, Y, Z) U42(mark(X), Y, Z) => U42(X, Y, Z) U42(X, mark(Y), Z) => U42(X, Y, Z) U42(X, Y, mark(Z)) => U42(X, Y, Z) U42(active(X), Y, Z) => U42(X, Y, Z) U42(X, active(Y), Z) => U42(X, Y, Z) U42(X, Y, active(Z)) => U42(X, Y, Z) s(mark(X)) => s(X) s(active(X)) => s(X) plus(mark(X), Y) => plus(X, Y) plus(X, mark(Y)) => plus(X, Y) plus(active(X), Y) => plus(X, Y) plus(X, active(Y)) => plus(X, Y) 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] active#(U11(tt, X)) =#> mark#(U12(isNat(X))) 1] active#(U11(tt, X)) =#> U12#(isNat(X)) 2] active#(U11(tt, X)) =#> isNat#(X) 3] active#(U12(tt)) =#> mark#(tt) 4] active#(U21(tt)) =#> mark#(tt) 5] active#(U31(tt, X)) =#> mark#(X) 6] active#(U41(tt, X, Y)) =#> mark#(U42(isNat(Y), X, Y)) 7] active#(U41(tt, X, Y)) =#> U42#(isNat(Y), X, Y) 8] active#(U41(tt, X, Y)) =#> isNat#(Y) 9] active#(U42(tt, X, Y)) =#> mark#(s(plus(Y, X))) 10] active#(U42(tt, X, Y)) =#> s#(plus(Y, X)) 11] active#(U42(tt, X, Y)) =#> plus#(Y, X) 12] active#(isNat(0)) =#> mark#(tt) 13] active#(isNat(plus(X, Y))) =#> mark#(U11(isNat(X), Y)) 14] active#(isNat(plus(X, Y))) =#> U11#(isNat(X), Y) 15] active#(isNat(plus(X, Y))) =#> isNat#(X) 16] active#(isNat(s(X))) =#> mark#(U21(isNat(X))) 17] active#(isNat(s(X))) =#> U21#(isNat(X)) 18] active#(isNat(s(X))) =#> isNat#(X) 19] active#(plus(X, 0)) =#> mark#(U31(isNat(X), X)) 20] active#(plus(X, 0)) =#> U31#(isNat(X), X) 21] active#(plus(X, 0)) =#> isNat#(X) 22] active#(plus(X, s(Y))) =#> mark#(U41(isNat(Y), Y, X)) 23] active#(plus(X, s(Y))) =#> U41#(isNat(Y), Y, X) 24] active#(plus(X, s(Y))) =#> isNat#(Y) 25] mark#(U11(X, Y)) =#> active#(U11(mark(X), Y)) 26] mark#(U11(X, Y)) =#> U11#(mark(X), Y) 27] mark#(U11(X, Y)) =#> mark#(X) 28] mark#(tt) =#> active#(tt) 29] mark#(U12(X)) =#> active#(U12(mark(X))) 30] mark#(U12(X)) =#> U12#(mark(X)) 31] mark#(U12(X)) =#> mark#(X) 32] mark#(isNat(X)) =#> active#(isNat(X)) 33] mark#(isNat(X)) =#> isNat#(X) 34] mark#(U21(X)) =#> active#(U21(mark(X))) 35] mark#(U21(X)) =#> U21#(mark(X)) 36] mark#(U21(X)) =#> mark#(X) 37] mark#(U31(X, Y)) =#> active#(U31(mark(X), Y)) 38] mark#(U31(X, Y)) =#> U31#(mark(X), Y) 39] mark#(U31(X, Y)) =#> mark#(X) 40] mark#(U41(X, Y, Z)) =#> active#(U41(mark(X), Y, Z)) 41] mark#(U41(X, Y, Z)) =#> U41#(mark(X), Y, Z) 42] mark#(U41(X, Y, Z)) =#> mark#(X) 43] mark#(U42(X, Y, Z)) =#> active#(U42(mark(X), Y, Z)) 44] mark#(U42(X, Y, Z)) =#> U42#(mark(X), Y, Z) 45] mark#(U42(X, Y, Z)) =#> mark#(X) 46] mark#(s(X)) =#> active#(s(mark(X))) 47] mark#(s(X)) =#> s#(mark(X)) 48] mark#(s(X)) =#> mark#(X) 49] mark#(plus(X, Y)) =#> active#(plus(mark(X), mark(Y))) 50] mark#(plus(X, Y)) =#> plus#(mark(X), mark(Y)) 51] mark#(plus(X, Y)) =#> mark#(X) 52] mark#(plus(X, Y)) =#> mark#(Y) 53] mark#(0) =#> active#(0) 54] U11#(mark(X), Y) =#> U11#(X, Y) 55] U11#(X, mark(Y)) =#> U11#(X, Y) 56] U11#(active(X), Y) =#> U11#(X, Y) 57] U11#(X, active(Y)) =#> U11#(X, Y) 58] U12#(mark(X)) =#> U12#(X) 59] U12#(active(X)) =#> U12#(X) 60] isNat#(mark(X)) =#> isNat#(X) 61] isNat#(active(X)) =#> isNat#(X) 62] U21#(mark(X)) =#> U21#(X) 63] U21#(active(X)) =#> U21#(X) 64] U31#(mark(X), Y) =#> U31#(X, Y) 65] U31#(X, mark(Y)) =#> U31#(X, Y) 66] U31#(active(X), Y) =#> U31#(X, Y) 67] U31#(X, active(Y)) =#> U31#(X, Y) 68] U41#(mark(X), Y, Z) =#> U41#(X, Y, Z) 69] U41#(X, mark(Y), Z) =#> U41#(X, Y, Z) 70] U41#(X, Y, mark(Z)) =#> U41#(X, Y, Z) 71] U41#(active(X), Y, Z) =#> U41#(X, Y, Z) 72] U41#(X, active(Y), Z) =#> U41#(X, Y, Z) 73] U41#(X, Y, active(Z)) =#> U41#(X, Y, Z) 74] U42#(mark(X), Y, Z) =#> U42#(X, Y, Z) 75] U42#(X, mark(Y), Z) =#> U42#(X, Y, Z) 76] U42#(X, Y, mark(Z)) =#> U42#(X, Y, Z) 77] U42#(active(X), Y, Z) =#> U42#(X, Y, Z) 78] U42#(X, active(Y), Z) =#> U42#(X, Y, Z) 79] U42#(X, Y, active(Z)) =#> U42#(X, Y, Z) 80] s#(mark(X)) =#> s#(X) 81] s#(active(X)) =#> s#(X) 82] plus#(mark(X), Y) =#> plus#(X, Y) 83] plus#(X, mark(Y)) =#> plus#(X, Y) 84] plus#(active(X), Y) =#> plus#(X, Y) 85] plus#(X, active(Y)) =#> plus#(X, Y) Rules R_0: active(U11(tt, X)) => mark(U12(isNat(X))) active(U12(tt)) => mark(tt) active(U21(tt)) => mark(tt) active(U31(tt, X)) => mark(X) active(U41(tt, X, Y)) => mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) => mark(s(plus(Y, X))) active(isNat(0)) => mark(tt) active(isNat(plus(X, Y))) => mark(U11(isNat(X), Y)) active(isNat(s(X))) => mark(U21(isNat(X))) active(plus(X, 0)) => mark(U31(isNat(X), X)) active(plus(X, s(Y))) => mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) => active(U11(mark(X), Y)) mark(tt) => active(tt) mark(U12(X)) => active(U12(mark(X))) mark(isNat(X)) => active(isNat(X)) mark(U21(X)) => active(U21(mark(X))) mark(U31(X, Y)) => active(U31(mark(X), Y)) mark(U41(X, Y, Z)) => active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) => active(U42(mark(X), Y, Z)) mark(s(X)) => active(s(mark(X))) mark(plus(X, Y)) => active(plus(mark(X), mark(Y))) mark(0) => active(0) U11(mark(X), Y) => U11(X, Y) U11(X, mark(Y)) => U11(X, Y) U11(active(X), Y) => U11(X, Y) U11(X, active(Y)) => U11(X, Y) U12(mark(X)) => U12(X) U12(active(X)) => U12(X) isNat(mark(X)) => isNat(X) isNat(active(X)) => isNat(X) U21(mark(X)) => U21(X) U21(active(X)) => U21(X) U31(mark(X), Y) => U31(X, Y) U31(X, mark(Y)) => U31(X, Y) U31(active(X), Y) => U31(X, Y) U31(X, active(Y)) => U31(X, Y) U41(mark(X), Y, Z) => U41(X, Y, Z) U41(X, mark(Y), Z) => U41(X, Y, Z) U41(X, Y, mark(Z)) => U41(X, Y, Z) U41(active(X), Y, Z) => U41(X, Y, Z) U41(X, active(Y), Z) => U41(X, Y, Z) U41(X, Y, active(Z)) => U41(X, Y, Z) U42(mark(X), Y, Z) => U42(X, Y, Z) U42(X, mark(Y), Z) => U42(X, Y, Z) U42(X, Y, mark(Z)) => U42(X, Y, Z) U42(active(X), Y, Z) => U42(X, Y, Z) U42(X, active(Y), Z) => U42(X, Y, Z) U42(X, Y, active(Z)) => U42(X, Y, Z) s(mark(X)) => s(X) s(active(X)) => s(X) plus(mark(X), Y) => plus(X, Y) plus(X, mark(Y)) => plus(X, Y) plus(active(X), Y) => plus(X, Y) plus(X, active(Y)) => plus(X, Y) 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 : 29, 30, 31 * 1 : * 2 : 60, 61 * 3 : 28 * 4 : 28 * 5 : 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 * 6 : 43, 44, 45 * 7 : 75, 76, 78, 79 * 8 : 60, 61 * 9 : 46, 47, 48 * 10 : * 11 : 82, 83, 84, 85 * 12 : 28 * 13 : 25, 26, 27 * 14 : 55, 57 * 15 : 60, 61 * 16 : 34, 35, 36 * 17 : * 18 : 60, 61 * 19 : 37, 38, 39 * 20 : 65, 67 * 21 : 60, 61 * 22 : 40, 41, 42 * 23 : 69, 70, 72, 73 * 24 : 60, 61 * 25 : 0, 1, 2 * 26 : 54, 55, 56, 57 * 27 : 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 * 28 : * 29 : 3 * 30 : 58, 59 * 31 : 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 * 32 : 12, 13, 14, 15, 16, 17, 18 * 33 : 60, 61 * 34 : 4 * 35 : 62, 63 * 36 : 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 * 37 : 5 * 38 : 64, 65, 66, 67 * 39 : 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 * 40 : 6, 7, 8 * 41 : 68, 69, 70, 71, 72, 73 * 42 : 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 * 43 : 9, 10, 11 * 44 : 74, 75, 76, 77, 78, 79 * 45 : 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 * 46 : * 47 : 80, 81 * 48 : 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 * 49 : 19, 20, 21, 22, 23, 24 * 50 : 82, 83, 84, 85 * 51 : 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 * 52 : 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 * 53 : * 54 : 54, 55, 56, 57 * 55 : 54, 55, 56, 57 * 56 : 54, 55, 56, 57 * 57 : 54, 55, 56, 57 * 58 : 58, 59 * 59 : 58, 59 * 60 : 60, 61 * 61 : 60, 61 * 62 : 62, 63 * 63 : 62, 63 * 64 : 64, 65, 66, 67 * 65 : 64, 65, 66, 67 * 66 : 64, 65, 66, 67 * 67 : 64, 65, 66, 67 * 68 : 68, 69, 70, 71, 72, 73 * 69 : 68, 69, 70, 71, 72, 73 * 70 : 68, 69, 70, 71, 72, 73 * 71 : 68, 69, 70, 71, 72, 73 * 72 : 68, 69, 70, 71, 72, 73 * 73 : 68, 69, 70, 71, 72, 73 * 74 : 74, 75, 76, 77, 78, 79 * 75 : 74, 75, 76, 77, 78, 79 * 76 : 74, 75, 76, 77, 78, 79 * 77 : 74, 75, 76, 77, 78, 79 * 78 : 74, 75, 76, 77, 78, 79 * 79 : 74, 75, 76, 77, 78, 79 * 80 : 80, 81 * 81 : 80, 81 * 82 : 82, 83, 84, 85 * 83 : 82, 83, 84, 85 * 84 : 82, 83, 84, 85 * 85 : 82, 83, 84, 85 This graph has the following strongly connected components: P_1: active#(U11(tt, X)) =#> mark#(U12(isNat(X))) active#(U31(tt, X)) =#> mark#(X) active#(U41(tt, X, Y)) =#> mark#(U42(isNat(Y), X, Y)) active#(U42(tt, X, Y)) =#> mark#(s(plus(Y, X))) active#(isNat(plus(X, Y))) =#> mark#(U11(isNat(X), Y)) active#(isNat(s(X))) =#> mark#(U21(isNat(X))) active#(plus(X, 0)) =#> mark#(U31(isNat(X), X)) active#(plus(X, s(Y))) =#> mark#(U41(isNat(Y), Y, X)) mark#(U11(X, Y)) =#> active#(U11(mark(X), Y)) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNat(X)) =#> active#(isNat(X)) mark#(U21(X)) =#> mark#(X) mark#(U31(X, Y)) =#> active#(U31(mark(X), Y)) mark#(U31(X, Y)) =#> mark#(X) mark#(U41(X, Y, Z)) =#> active#(U41(mark(X), Y, Z)) mark#(U41(X, Y, Z)) =#> mark#(X) mark#(U42(X, Y, Z)) =#> active#(U42(mark(X), Y, Z)) mark#(U42(X, Y, Z)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(plus(X, Y)) =#> active#(plus(mark(X), mark(Y))) mark#(plus(X, Y)) =#> mark#(X) mark#(plus(X, Y)) =#> mark#(Y) P_2: U11#(mark(X), Y) =#> U11#(X, Y) U11#(X, mark(Y)) =#> U11#(X, Y) U11#(active(X), Y) =#> U11#(X, Y) U11#(X, active(Y)) =#> U11#(X, Y) P_3: U12#(mark(X)) =#> U12#(X) U12#(active(X)) =#> U12#(X) P_4: isNat#(mark(X)) =#> isNat#(X) isNat#(active(X)) =#> isNat#(X) P_5: U21#(mark(X)) =#> U21#(X) U21#(active(X)) =#> U21#(X) P_6: U31#(mark(X), Y) =#> U31#(X, Y) U31#(X, mark(Y)) =#> U31#(X, Y) U31#(active(X), Y) =#> U31#(X, Y) U31#(X, active(Y)) =#> U31#(X, Y) P_7: U41#(mark(X), Y, Z) =#> U41#(X, Y, Z) U41#(X, mark(Y), Z) =#> U41#(X, Y, Z) U41#(X, Y, mark(Z)) =#> U41#(X, Y, Z) U41#(active(X), Y, Z) =#> U41#(X, Y, Z) U41#(X, active(Y), Z) =#> U41#(X, Y, Z) U41#(X, Y, active(Z)) =#> U41#(X, Y, Z) P_8: U42#(mark(X), Y, Z) =#> U42#(X, Y, Z) U42#(X, mark(Y), Z) =#> U42#(X, Y, Z) U42#(X, Y, mark(Z)) =#> U42#(X, Y, Z) U42#(active(X), Y, Z) =#> U42#(X, Y, Z) U42#(X, active(Y), Z) =#> U42#(X, Y, Z) U42#(X, Y, active(Z)) =#> U42#(X, Y, Z) P_9: s#(mark(X)) =#> s#(X) s#(active(X)) =#> s#(X) P_10: plus#(mark(X), Y) =#> plus#(X, Y) plus#(X, mark(Y)) =#> plus#(X, Y) plus#(active(X), Y) =#> plus#(X, Y) plus#(X, active(Y)) =#> plus#(X, Y) 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), (P_2, R_0, m, f), (P_3, R_0, m, f), (P_4, R_0, m, f), (P_5, R_0, m, f), (P_6, R_0, m, f), (P_7, R_0, m, f), (P_8, R_0, m, f), (P_9, R_0, m, f) and (P_10, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative), (P_9, R_0, minimal, formative) and (P_10, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_10, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(plus#) = 1 Thus, we can orient the dependency pairs as follows: nu(plus#(mark(X), Y)) = mark(X) |> X = nu(plus#(X, Y)) nu(plus#(X, mark(Y))) = X = X = nu(plus#(X, Y)) nu(plus#(active(X), Y)) = active(X) |> X = nu(plus#(X, Y)) nu(plus#(X, active(Y))) = X = X = nu(plus#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_10, R_0, minimal, f) by (P_11, R_0, minimal, f), where P_11 contains: plus#(X, mark(Y)) =#> plus#(X, Y) plus#(X, active(Y)) =#> plus#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative), (P_9, R_0, minimal, formative) and (P_11, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_11, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(plus#) = 2 Thus, we can orient the dependency pairs as follows: nu(plus#(X, mark(Y))) = mark(Y) |> Y = nu(plus#(X, Y)) nu(plus#(X, active(Y))) = active(Y) |> Y = nu(plus#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_11, 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 each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative) and (P_9, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_9, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(s#) = 1 Thus, we can orient the dependency pairs as follows: nu(s#(mark(X))) = mark(X) |> X = nu(s#(X)) nu(s#(active(X))) = active(X) |> X = nu(s#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_9, 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 each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative) and (P_8, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_8, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(U42#) = 1 Thus, we can orient the dependency pairs as follows: nu(U42#(mark(X), Y, Z)) = mark(X) |> X = nu(U42#(X, Y, Z)) nu(U42#(X, mark(Y), Z)) = X = X = nu(U42#(X, Y, Z)) nu(U42#(X, Y, mark(Z))) = X = X = nu(U42#(X, Y, Z)) nu(U42#(active(X), Y, Z)) = active(X) |> X = nu(U42#(X, Y, Z)) nu(U42#(X, active(Y), Z)) = X = X = nu(U42#(X, Y, Z)) nu(U42#(X, Y, active(Z))) = X = X = nu(U42#(X, Y, Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_8, R_0, minimal, f) by (P_12, R_0, minimal, f), where P_12 contains: U42#(X, mark(Y), Z) =#> U42#(X, Y, Z) U42#(X, Y, mark(Z)) =#> U42#(X, Y, Z) U42#(X, active(Y), Z) =#> U42#(X, Y, Z) U42#(X, Y, active(Z)) =#> U42#(X, Y, Z) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative) and (P_12, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_12, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(U42#) = 2 Thus, we can orient the dependency pairs as follows: nu(U42#(X, mark(Y), Z)) = mark(Y) |> Y = nu(U42#(X, Y, Z)) nu(U42#(X, Y, mark(Z))) = Y = Y = nu(U42#(X, Y, Z)) nu(U42#(X, active(Y), Z)) = active(Y) |> Y = nu(U42#(X, Y, Z)) nu(U42#(X, Y, active(Z))) = Y = Y = nu(U42#(X, Y, Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_12, R_0, minimal, f) by (P_13, R_0, minimal, f), where P_13 contains: U42#(X, Y, mark(Z)) =#> U42#(X, Y, Z) U42#(X, Y, active(Z)) =#> U42#(X, Y, Z) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative) and (P_13, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_13, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(U42#) = 3 Thus, we can orient the dependency pairs as follows: nu(U42#(X, Y, mark(Z))) = mark(Z) |> Z = nu(U42#(X, Y, Z)) nu(U42#(X, Y, active(Z))) = active(Z) |> Z = nu(U42#(X, Y, Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_13, 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 each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative) and (P_7, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_7, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(U41#) = 1 Thus, we can orient the dependency pairs as follows: nu(U41#(mark(X), Y, Z)) = mark(X) |> X = nu(U41#(X, Y, Z)) nu(U41#(X, mark(Y), Z)) = X = X = nu(U41#(X, Y, Z)) nu(U41#(X, Y, mark(Z))) = X = X = nu(U41#(X, Y, Z)) nu(U41#(active(X), Y, Z)) = active(X) |> X = nu(U41#(X, Y, Z)) nu(U41#(X, active(Y), Z)) = X = X = nu(U41#(X, Y, Z)) nu(U41#(X, Y, active(Z))) = X = X = nu(U41#(X, Y, Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_7, R_0, minimal, f) by (P_14, R_0, minimal, f), where P_14 contains: U41#(X, mark(Y), Z) =#> U41#(X, Y, Z) U41#(X, Y, mark(Z)) =#> U41#(X, Y, Z) U41#(X, active(Y), Z) =#> U41#(X, Y, Z) U41#(X, Y, active(Z)) =#> U41#(X, Y, Z) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative) and (P_14, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_14, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(U41#) = 2 Thus, we can orient the dependency pairs as follows: nu(U41#(X, mark(Y), Z)) = mark(Y) |> Y = nu(U41#(X, Y, Z)) nu(U41#(X, Y, mark(Z))) = Y = Y = nu(U41#(X, Y, Z)) nu(U41#(X, active(Y), Z)) = active(Y) |> Y = nu(U41#(X, Y, Z)) nu(U41#(X, Y, active(Z))) = Y = Y = nu(U41#(X, Y, Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_14, R_0, minimal, f) by (P_15, R_0, minimal, f), where P_15 contains: U41#(X, Y, mark(Z)) =#> U41#(X, Y, Z) U41#(X, Y, active(Z)) =#> U41#(X, Y, Z) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative) and (P_15, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_15, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(U41#) = 3 Thus, we can orient the dependency pairs as follows: nu(U41#(X, Y, mark(Z))) = mark(Z) |> Z = nu(U41#(X, Y, Z)) nu(U41#(X, Y, active(Z))) = active(Z) |> Z = nu(U41#(X, Y, Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_15, 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 each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative) and (P_6, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_6, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(U31#) = 1 Thus, we can orient the dependency pairs as follows: nu(U31#(mark(X), Y)) = mark(X) |> X = nu(U31#(X, Y)) nu(U31#(X, mark(Y))) = X = X = nu(U31#(X, Y)) nu(U31#(active(X), Y)) = active(X) |> X = nu(U31#(X, Y)) nu(U31#(X, active(Y))) = X = X = nu(U31#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_6, R_0, minimal, f) by (P_16, R_0, minimal, f), where P_16 contains: U31#(X, mark(Y)) =#> U31#(X, Y) U31#(X, active(Y)) =#> U31#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative) and (P_16, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_16, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(U31#) = 2 Thus, we can orient the dependency pairs as follows: nu(U31#(X, mark(Y))) = mark(Y) |> Y = nu(U31#(X, Y)) nu(U31#(X, active(Y))) = active(Y) |> Y = nu(U31#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_16, 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 each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative) and (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(U21#) = 1 Thus, we can orient the dependency pairs as follows: nu(U21#(mark(X))) = mark(X) |> X = nu(U21#(X)) nu(U21#(active(X))) = active(X) |> X = nu(U21#(X)) 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. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative) and (P_4, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(isNat#) = 1 Thus, we can orient the dependency pairs as follows: nu(isNat#(mark(X))) = mark(X) |> X = nu(isNat#(X)) nu(isNat#(active(X))) = active(X) |> X = nu(isNat#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_4, 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 each of (P_1, R_0, minimal, formative), (P_2, 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(U12#) = 1 Thus, we can orient the dependency pairs as follows: nu(U12#(mark(X))) = mark(X) |> X = nu(U12#(X)) nu(U12#(active(X))) = active(X) |> X = nu(U12#(X)) 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 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(U11#) = 1 Thus, we can orient the dependency pairs as follows: nu(U11#(mark(X), Y)) = mark(X) |> X = nu(U11#(X, Y)) nu(U11#(X, mark(Y))) = X = X = nu(U11#(X, Y)) nu(U11#(active(X), Y)) = active(X) |> X = nu(U11#(X, Y)) nu(U11#(X, active(Y))) = X = X = nu(U11#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_2, R_0, minimal, f) by (P_17, R_0, minimal, f), where P_17 contains: U11#(X, mark(Y)) =#> U11#(X, Y) U11#(X, active(Y)) =#> U11#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_17, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_17, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(U11#) = 2 Thus, we can orient the dependency pairs as follows: nu(U11#(X, mark(Y))) = mark(Y) |> Y = nu(U11#(X, Y)) nu(U11#(X, active(Y))) = active(Y) |> Y = nu(U11#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_17, 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 [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(U11(tt, X)) >? mark#(U12(isNat(X))) active#(U31(tt, X)) >? mark#(X) active#(U41(tt, X, Y)) >? mark#(U42(isNat(Y), X, Y)) active#(U42(tt, X, Y)) >? mark#(s(plus(Y, X))) active#(isNat(plus(X, Y))) >? mark#(U11(isNat(X), Y)) active#(isNat(s(X))) >? mark#(U21(isNat(X))) active#(plus(X, 0)) >? mark#(U31(isNat(X), X)) active#(plus(X, s(Y))) >? mark#(U41(isNat(Y), Y, X)) mark#(U11(X, Y)) >? active#(U11(mark(X), Y)) mark#(U11(X, Y)) >? mark#(X) mark#(U12(X)) >? mark#(X) mark#(isNat(X)) >? active#(isNat(X)) mark#(U21(X)) >? mark#(X) mark#(U31(X, Y)) >? active#(U31(mark(X), Y)) mark#(U31(X, Y)) >? mark#(X) mark#(U41(X, Y, Z)) >? active#(U41(mark(X), Y, Z)) mark#(U41(X, Y, Z)) >? mark#(X) mark#(U42(X, Y, Z)) >? active#(U42(mark(X), Y, Z)) mark#(U42(X, Y, Z)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(plus(X, Y)) >? active#(plus(mark(X), mark(Y))) mark#(plus(X, Y)) >? mark#(X) mark#(plus(X, Y)) >? mark#(Y) active(U11(tt, X)) >= mark(U12(isNat(X))) active(U12(tt)) >= mark(tt) active(U21(tt)) >= mark(tt) active(U31(tt, X)) >= mark(X) active(U41(tt, X, Y)) >= mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) >= mark(s(plus(Y, X))) active(isNat(0)) >= mark(tt) active(isNat(plus(X, Y))) >= mark(U11(isNat(X), Y)) active(isNat(s(X))) >= mark(U21(isNat(X))) active(plus(X, 0)) >= mark(U31(isNat(X), X)) active(plus(X, s(Y))) >= mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) >= active(U11(mark(X), Y)) mark(tt) >= active(tt) mark(U12(X)) >= active(U12(mark(X))) mark(isNat(X)) >= active(isNat(X)) mark(U21(X)) >= active(U21(mark(X))) mark(U31(X, Y)) >= active(U31(mark(X), Y)) mark(U41(X, Y, Z)) >= active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) >= active(U42(mark(X), Y, Z)) mark(s(X)) >= active(s(mark(X))) mark(plus(X, Y)) >= active(plus(mark(X), mark(Y))) mark(0) >= active(0) U11(mark(X), Y) >= U11(X, Y) U11(X, mark(Y)) >= U11(X, Y) U11(active(X), Y) >= U11(X, Y) U11(X, active(Y)) >= U11(X, Y) U12(mark(X)) >= U12(X) U12(active(X)) >= U12(X) isNat(mark(X)) >= isNat(X) isNat(active(X)) >= isNat(X) U21(mark(X)) >= U21(X) U21(active(X)) >= U21(X) U31(mark(X), Y) >= U31(X, Y) U31(X, mark(Y)) >= U31(X, Y) U31(active(X), Y) >= U31(X, Y) U31(X, active(Y)) >= U31(X, Y) U41(mark(X), Y, Z) >= U41(X, Y, Z) U41(X, mark(Y), Z) >= U41(X, Y, Z) U41(X, Y, mark(Z)) >= U41(X, Y, Z) U41(active(X), Y, Z) >= U41(X, Y, Z) U41(X, active(Y), Z) >= U41(X, Y, Z) U41(X, Y, active(Z)) >= U41(X, Y, Z) U42(mark(X), Y, Z) >= U42(X, Y, Z) U42(X, mark(Y), Z) >= U42(X, Y, Z) U42(X, Y, mark(Z)) >= U42(X, Y, Z) U42(active(X), Y, Z) >= U42(X, Y, Z) U42(X, active(Y), Z) >= U42(X, Y, Z) U42(X, Y, active(Z)) >= U42(X, Y, Z) s(mark(X)) >= s(X) s(active(X)) >= s(X) plus(mark(X), Y) >= plus(X, Y) plus(X, mark(Y)) >= plus(X, Y) plus(active(X), Y) >= plus(X, Y) plus(X, active(Y)) >= plus(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 2 U11 = \y0y1.2y0 U12 = \y0.y0 U21 = \y0.y0 U31 = \y0y1.1 + y1 + 2y0 U41 = \y0y1y2.y1 + 2y0 + 2y2 U42 = \y0y1y2.y1 + 2y0 + 2y2 active = \y0.y0 active# = \y0.2y0 isNat = \y0.0 mark = \y0.y0 mark# = \y0.2y0 plus = \y0y1.y1 + 2y0 s = \y0.y0 tt = 0 Using this interpretation, the requirements translate to: [[active#(U11(tt, _x0))]] = 0 >= 0 = [[mark#(U12(isNat(_x0)))]] [[active#(U31(tt, _x0))]] = 2 + 2x0 > 2x0 = [[mark#(_x0)]] [[active#(U41(tt, _x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[mark#(U42(isNat(_x1), _x0, _x1))]] [[active#(U42(tt, _x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[mark#(s(plus(_x1, _x0)))]] [[active#(isNat(plus(_x0, _x1)))]] = 0 >= 0 = [[mark#(U11(isNat(_x0), _x1))]] [[active#(isNat(s(_x0)))]] = 0 >= 0 = [[mark#(U21(isNat(_x0)))]] [[active#(plus(_x0, 0))]] = 4 + 4x0 > 2 + 2x0 = [[mark#(U31(isNat(_x0), _x0))]] [[active#(plus(_x0, s(_x1)))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[mark#(U41(isNat(_x1), _x1, _x0))]] [[mark#(U11(_x0, _x1))]] = 4x0 >= 4x0 = [[active#(U11(mark(_x0), _x1))]] [[mark#(U11(_x0, _x1))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U12(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(isNat(_x0))]] = 0 >= 0 = [[active#(isNat(_x0))]] [[mark#(U21(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U31(_x0, _x1))]] = 2 + 2x1 + 4x0 >= 2 + 2x1 + 4x0 = [[active#(U31(mark(_x0), _x1))]] [[mark#(U31(_x0, _x1))]] = 2 + 2x1 + 4x0 > 2x0 = [[mark#(_x0)]] [[mark#(U41(_x0, _x1, _x2))]] = 2x1 + 4x0 + 4x2 >= 2x1 + 4x0 + 4x2 = [[active#(U41(mark(_x0), _x1, _x2))]] [[mark#(U41(_x0, _x1, _x2))]] = 2x1 + 4x0 + 4x2 >= 2x0 = [[mark#(_x0)]] [[mark#(U42(_x0, _x1, _x2))]] = 2x1 + 4x0 + 4x2 >= 2x1 + 4x0 + 4x2 = [[active#(U42(mark(_x0), _x1, _x2))]] [[mark#(U42(_x0, _x1, _x2))]] = 2x1 + 4x0 + 4x2 >= 2x0 = [[mark#(_x0)]] [[mark#(s(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(plus(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[active#(plus(mark(_x0), mark(_x1)))]] [[mark#(plus(_x0, _x1))]] = 2x1 + 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(plus(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 = [[mark#(_x1)]] [[active(U11(tt, _x0))]] = 0 >= 0 = [[mark(U12(isNat(_x0)))]] [[active(U12(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U21(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U31(tt, _x0))]] = 1 + x0 >= x0 = [[mark(_x0)]] [[active(U41(tt, _x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[mark(U42(isNat(_x1), _x0, _x1))]] [[active(U42(tt, _x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[mark(s(plus(_x1, _x0)))]] [[active(isNat(0))]] = 0 >= 0 = [[mark(tt)]] [[active(isNat(plus(_x0, _x1)))]] = 0 >= 0 = [[mark(U11(isNat(_x0), _x1))]] [[active(isNat(s(_x0)))]] = 0 >= 0 = [[mark(U21(isNat(_x0)))]] [[active(plus(_x0, 0))]] = 2 + 2x0 >= 1 + x0 = [[mark(U31(isNat(_x0), _x0))]] [[active(plus(_x0, s(_x1)))]] = x1 + 2x0 >= x1 + 2x0 = [[mark(U41(isNat(_x1), _x1, _x0))]] [[mark(U11(_x0, _x1))]] = 2x0 >= 2x0 = [[active(U11(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U12(_x0))]] = x0 >= x0 = [[active(U12(mark(_x0)))]] [[mark(isNat(_x0))]] = 0 >= 0 = [[active(isNat(_x0))]] [[mark(U21(_x0))]] = x0 >= x0 = [[active(U21(mark(_x0)))]] [[mark(U31(_x0, _x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[active(U31(mark(_x0), _x1))]] [[mark(U41(_x0, _x1, _x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[active(U41(mark(_x0), _x1, _x2))]] [[mark(U42(_x0, _x1, _x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[active(U42(mark(_x0), _x1, _x2))]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(plus(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(plus(mark(_x0), mark(_x1)))]] [[mark(0)]] = 2 >= 2 = [[active(0)]] [[U11(mark(_x0), _x1)]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U11(_x0, mark(_x1))]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U11(active(_x0), _x1)]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U11(_x0, active(_x1))]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U12(mark(_x0))]] = x0 >= x0 = [[U12(_x0)]] [[U12(active(_x0))]] = x0 >= x0 = [[U12(_x0)]] [[isNat(mark(_x0))]] = 0 >= 0 = [[isNat(_x0)]] [[isNat(active(_x0))]] = 0 >= 0 = [[isNat(_x0)]] [[U21(mark(_x0))]] = x0 >= x0 = [[U21(_x0)]] [[U21(active(_x0))]] = x0 >= x0 = [[U21(_x0)]] [[U31(mark(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[U31(_x0, _x1)]] [[U31(_x0, mark(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[U31(_x0, _x1)]] [[U31(active(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[U31(_x0, _x1)]] [[U31(_x0, active(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[U31(_x0, _x1)]] [[U41(mark(_x0), _x1, _x2)]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U41(_x0, mark(_x1), _x2)]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U41(_x0, _x1, mark(_x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U41(active(_x0), _x1, _x2)]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U41(_x0, active(_x1), _x2)]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U41(_x0, _x1, active(_x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U42(mark(_x0), _x1, _x2)]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U42(_x0, _x1, _x2)]] [[U42(_x0, mark(_x1), _x2)]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U42(_x0, _x1, _x2)]] [[U42(_x0, _x1, mark(_x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U42(_x0, _x1, _x2)]] [[U42(active(_x0), _x1, _x2)]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U42(_x0, _x1, _x2)]] [[U42(_x0, active(_x1), _x2)]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U42(_x0, _x1, _x2)]] [[U42(_x0, _x1, active(_x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U42(_x0, _x1, _x2)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[plus(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] 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_18, R_0, minimal, formative), where P_18 consists of: active#(U11(tt, X)) =#> mark#(U12(isNat(X))) active#(U41(tt, X, Y)) =#> mark#(U42(isNat(Y), X, Y)) active#(U42(tt, X, Y)) =#> mark#(s(plus(Y, X))) active#(isNat(plus(X, Y))) =#> mark#(U11(isNat(X), Y)) active#(isNat(s(X))) =#> mark#(U21(isNat(X))) active#(plus(X, s(Y))) =#> mark#(U41(isNat(Y), Y, X)) mark#(U11(X, Y)) =#> active#(U11(mark(X), Y)) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNat(X)) =#> active#(isNat(X)) mark#(U21(X)) =#> mark#(X) mark#(U31(X, Y)) =#> active#(U31(mark(X), Y)) mark#(U41(X, Y, Z)) =#> active#(U41(mark(X), Y, Z)) mark#(U41(X, Y, Z)) =#> mark#(X) mark#(U42(X, Y, Z)) =#> active#(U42(mark(X), Y, Z)) mark#(U42(X, Y, Z)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(plus(X, Y)) =#> active#(plus(mark(X), mark(Y))) mark#(plus(X, Y)) =#> mark#(X) mark#(plus(X, Y)) =#> mark#(Y) Thus, the original system is terminating if (P_18, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_18, 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 : 8 * 1 : 14, 15 * 2 : 16 * 3 : 6, 7 * 4 : 10 * 5 : 12, 13 * 6 : 0 * 7 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 8 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 9 : 3, 4 * 10 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 11 : * 12 : 1 * 13 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 14 : 2 * 15 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 16 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 17 : 5 * 18 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 19 : 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 This graph has the following strongly connected components: P_19: active#(U11(tt, X)) =#> mark#(U12(isNat(X))) active#(U41(tt, X, Y)) =#> mark#(U42(isNat(Y), X, Y)) active#(U42(tt, X, Y)) =#> mark#(s(plus(Y, X))) active#(isNat(plus(X, Y))) =#> mark#(U11(isNat(X), Y)) active#(isNat(s(X))) =#> mark#(U21(isNat(X))) active#(plus(X, s(Y))) =#> mark#(U41(isNat(Y), Y, X)) mark#(U11(X, Y)) =#> active#(U11(mark(X), Y)) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNat(X)) =#> active#(isNat(X)) mark#(U21(X)) =#> mark#(X) mark#(U41(X, Y, Z)) =#> active#(U41(mark(X), Y, Z)) mark#(U41(X, Y, Z)) =#> mark#(X) mark#(U42(X, Y, Z)) =#> active#(U42(mark(X), Y, Z)) mark#(U42(X, Y, Z)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(plus(X, Y)) =#> active#(plus(mark(X), mark(Y))) mark#(plus(X, Y)) =#> mark#(X) mark#(plus(X, Y)) =#> mark#(Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_18, R_0, m, f) by (P_19, R_0, m, f). Thus, the original system is terminating if (P_19, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_19, R_0, minimal, formative). The formative rules of (P_19, R_0) are R_1 ::= active(U11(tt, X)) => mark(U12(isNat(X))) active(U12(tt)) => mark(tt) active(U21(tt)) => mark(tt) active(U31(tt, X)) => mark(X) active(U41(tt, X, Y)) => mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) => mark(s(plus(Y, X))) active(isNat(0)) => mark(tt) active(isNat(plus(X, Y))) => mark(U11(isNat(X), Y)) active(isNat(s(X))) => mark(U21(isNat(X))) active(plus(X, 0)) => mark(U31(isNat(X), X)) active(plus(X, s(Y))) => mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) => active(U11(mark(X), Y)) mark(tt) => active(tt) mark(U12(X)) => active(U12(mark(X))) mark(isNat(X)) => active(isNat(X)) mark(U21(X)) => active(U21(mark(X))) mark(U31(X, Y)) => active(U31(mark(X), Y)) mark(U41(X, Y, Z)) => active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) => active(U42(mark(X), Y, Z)) mark(s(X)) => active(s(mark(X))) mark(plus(X, Y)) => active(plus(mark(X), mark(Y))) mark(0) => active(0) U11(mark(X), Y) => U11(X, Y) U11(X, mark(Y)) => U11(X, Y) U11(active(X), Y) => U11(X, Y) U11(X, active(Y)) => U11(X, Y) U12(mark(X)) => U12(X) U12(active(X)) => U12(X) isNat(mark(X)) => isNat(X) isNat(active(X)) => isNat(X) U21(mark(X)) => U21(X) U21(active(X)) => U21(X) U41(mark(X), Y, Z) => U41(X, Y, Z) U41(X, mark(Y), Z) => U41(X, Y, Z) U41(X, Y, mark(Z)) => U41(X, Y, Z) U41(active(X), Y, Z) => U41(X, Y, Z) U41(X, active(Y), Z) => U41(X, Y, Z) U41(X, Y, active(Z)) => U41(X, Y, Z) U42(mark(X), Y, Z) => U42(X, Y, Z) U42(X, mark(Y), Z) => U42(X, Y, Z) U42(X, Y, mark(Z)) => U42(X, Y, Z) U42(active(X), Y, Z) => U42(X, Y, Z) U42(X, active(Y), Z) => U42(X, Y, Z) U42(X, Y, active(Z)) => U42(X, Y, Z) s(mark(X)) => s(X) s(active(X)) => s(X) plus(mark(X), Y) => plus(X, Y) plus(X, mark(Y)) => plus(X, Y) plus(active(X), Y) => plus(X, Y) plus(X, active(Y)) => plus(X, Y) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_19, R_0, minimal, formative) by (P_19, R_1, minimal, formative). Thus, the original system is terminating if (P_19, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_19, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(U11(tt, X)) >? mark#(U12(isNat(X))) active#(U41(tt, X, Y)) >? mark#(U42(isNat(Y), X, Y)) active#(U42(tt, X, Y)) >? mark#(s(plus(Y, X))) active#(isNat(plus(X, Y))) >? mark#(U11(isNat(X), Y)) active#(isNat(s(X))) >? mark#(U21(isNat(X))) active#(plus(X, s(Y))) >? mark#(U41(isNat(Y), Y, X)) mark#(U11(X, Y)) >? active#(U11(mark(X), Y)) mark#(U11(X, Y)) >? mark#(X) mark#(U12(X)) >? mark#(X) mark#(isNat(X)) >? active#(isNat(X)) mark#(U21(X)) >? mark#(X) mark#(U41(X, Y, Z)) >? active#(U41(mark(X), Y, Z)) mark#(U41(X, Y, Z)) >? mark#(X) mark#(U42(X, Y, Z)) >? active#(U42(mark(X), Y, Z)) mark#(U42(X, Y, Z)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(plus(X, Y)) >? active#(plus(mark(X), mark(Y))) mark#(plus(X, Y)) >? mark#(X) mark#(plus(X, Y)) >? mark#(Y) active(U11(tt, X)) >= mark(U12(isNat(X))) active(U12(tt)) >= mark(tt) active(U21(tt)) >= mark(tt) active(U31(tt, X)) >= mark(X) active(U41(tt, X, Y)) >= mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) >= mark(s(plus(Y, X))) active(isNat(0)) >= mark(tt) active(isNat(plus(X, Y))) >= mark(U11(isNat(X), Y)) active(isNat(s(X))) >= mark(U21(isNat(X))) active(plus(X, 0)) >= mark(U31(isNat(X), X)) active(plus(X, s(Y))) >= mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) >= active(U11(mark(X), Y)) mark(tt) >= active(tt) mark(U12(X)) >= active(U12(mark(X))) mark(isNat(X)) >= active(isNat(X)) mark(U21(X)) >= active(U21(mark(X))) mark(U31(X, Y)) >= active(U31(mark(X), Y)) mark(U41(X, Y, Z)) >= active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) >= active(U42(mark(X), Y, Z)) mark(s(X)) >= active(s(mark(X))) mark(plus(X, Y)) >= active(plus(mark(X), mark(Y))) mark(0) >= active(0) U11(mark(X), Y) >= U11(X, Y) U11(X, mark(Y)) >= U11(X, Y) U11(active(X), Y) >= U11(X, Y) U11(X, active(Y)) >= U11(X, Y) U12(mark(X)) >= U12(X) U12(active(X)) >= U12(X) isNat(mark(X)) >= isNat(X) isNat(active(X)) >= isNat(X) U21(mark(X)) >= U21(X) U21(active(X)) >= U21(X) U41(mark(X), Y, Z) >= U41(X, Y, Z) U41(X, mark(Y), Z) >= U41(X, Y, Z) U41(X, Y, mark(Z)) >= U41(X, Y, Z) U41(active(X), Y, Z) >= U41(X, Y, Z) U41(X, active(Y), Z) >= U41(X, Y, Z) U41(X, Y, active(Z)) >= U41(X, Y, Z) U42(mark(X), Y, Z) >= U42(X, Y, Z) U42(X, mark(Y), Z) >= U42(X, Y, Z) U42(X, Y, mark(Z)) >= U42(X, Y, Z) U42(active(X), Y, Z) >= U42(X, Y, Z) U42(X, active(Y), Z) >= U42(X, Y, Z) U42(X, Y, active(Z)) >= U42(X, Y, Z) s(mark(X)) >= s(X) s(active(X)) >= s(X) plus(mark(X), Y) >= plus(X, Y) plus(X, mark(Y)) >= plus(X, Y) plus(active(X), Y) >= plus(X, Y) plus(X, active(Y)) >= plus(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.2y0 U12 = \y0.y0 U21 = \y0.y0 U31 = \y0y1.y1 U41 = \y0y1y2.2 + y0 + 2y1 + 2y2 U42 = \y0y1y2.2 + 2y0 + 2y1 + 2y2 active = \y0.y0 active# = \y0.y0 isNat = \y0.0 mark = \y0.y0 mark# = \y0.y0 plus = \y0y1.2y0 + 2y1 s = \y0.1 + y0 tt = 0 Using this interpretation, the requirements translate to: [[active#(U11(tt, _x0))]] = 0 >= 0 = [[mark#(U12(isNat(_x0)))]] [[active#(U41(tt, _x0, _x1))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[mark#(U42(isNat(_x1), _x0, _x1))]] [[active#(U42(tt, _x0, _x1))]] = 2 + 2x0 + 2x1 > 1 + 2x0 + 2x1 = [[mark#(s(plus(_x1, _x0)))]] [[active#(isNat(plus(_x0, _x1)))]] = 0 >= 0 = [[mark#(U11(isNat(_x0), _x1))]] [[active#(isNat(s(_x0)))]] = 0 >= 0 = [[mark#(U21(isNat(_x0)))]] [[active#(plus(_x0, s(_x1)))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[mark#(U41(isNat(_x1), _x1, _x0))]] [[mark#(U11(_x0, _x1))]] = 2x0 >= 2x0 = [[active#(U11(mark(_x0), _x1))]] [[mark#(U11(_x0, _x1))]] = 2x0 >= x0 = [[mark#(_x0)]] [[mark#(U12(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(isNat(_x0))]] = 0 >= 0 = [[active#(isNat(_x0))]] [[mark#(U21(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(U41(_x0, _x1, _x2))]] = 2 + x0 + 2x1 + 2x2 >= 2 + x0 + 2x1 + 2x2 = [[active#(U41(mark(_x0), _x1, _x2))]] [[mark#(U41(_x0, _x1, _x2))]] = 2 + x0 + 2x1 + 2x2 > x0 = [[mark#(_x0)]] [[mark#(U42(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[active#(U42(mark(_x0), _x1, _x2))]] [[mark#(U42(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 + 2x2 > x0 = [[mark#(_x0)]] [[mark#(s(_x0))]] = 1 + x0 > x0 = [[mark#(_x0)]] [[mark#(plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active#(plus(mark(_x0), mark(_x1)))]] [[mark#(plus(_x0, _x1))]] = 2x0 + 2x1 >= x0 = [[mark#(_x0)]] [[mark#(plus(_x0, _x1))]] = 2x0 + 2x1 >= x1 = [[mark#(_x1)]] [[active(U11(tt, _x0))]] = 0 >= 0 = [[mark(U12(isNat(_x0)))]] [[active(U12(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U21(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U31(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(U41(tt, _x0, _x1))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[mark(U42(isNat(_x1), _x0, _x1))]] [[active(U42(tt, _x0, _x1))]] = 2 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[mark(s(plus(_x1, _x0)))]] [[active(isNat(0))]] = 0 >= 0 = [[mark(tt)]] [[active(isNat(plus(_x0, _x1)))]] = 0 >= 0 = [[mark(U11(isNat(_x0), _x1))]] [[active(isNat(s(_x0)))]] = 0 >= 0 = [[mark(U21(isNat(_x0)))]] [[active(plus(_x0, 0))]] = 2x0 >= x0 = [[mark(U31(isNat(_x0), _x0))]] [[active(plus(_x0, s(_x1)))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[mark(U41(isNat(_x1), _x1, _x0))]] [[mark(U11(_x0, _x1))]] = 2x0 >= 2x0 = [[active(U11(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U12(_x0))]] = x0 >= x0 = [[active(U12(mark(_x0)))]] [[mark(isNat(_x0))]] = 0 >= 0 = [[active(isNat(_x0))]] [[mark(U21(_x0))]] = x0 >= x0 = [[active(U21(mark(_x0)))]] [[mark(U31(_x0, _x1))]] = x1 >= x1 = [[active(U31(mark(_x0), _x1))]] [[mark(U41(_x0, _x1, _x2))]] = 2 + x0 + 2x1 + 2x2 >= 2 + x0 + 2x1 + 2x2 = [[active(U41(mark(_x0), _x1, _x2))]] [[mark(U42(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[active(U42(mark(_x0), _x1, _x2))]] [[mark(s(_x0))]] = 1 + x0 >= 1 + x0 = [[active(s(mark(_x0)))]] [[mark(plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(plus(mark(_x0), mark(_x1)))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[U11(mark(_x0), _x1)]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U11(_x0, mark(_x1))]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U11(active(_x0), _x1)]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U11(_x0, active(_x1))]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U12(mark(_x0))]] = x0 >= x0 = [[U12(_x0)]] [[U12(active(_x0))]] = x0 >= x0 = [[U12(_x0)]] [[isNat(mark(_x0))]] = 0 >= 0 = [[isNat(_x0)]] [[isNat(active(_x0))]] = 0 >= 0 = [[isNat(_x0)]] [[U21(mark(_x0))]] = x0 >= x0 = [[U21(_x0)]] [[U21(active(_x0))]] = x0 >= x0 = [[U21(_x0)]] [[U41(mark(_x0), _x1, _x2)]] = 2 + x0 + 2x1 + 2x2 >= 2 + x0 + 2x1 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U41(_x0, mark(_x1), _x2)]] = 2 + x0 + 2x1 + 2x2 >= 2 + x0 + 2x1 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U41(_x0, _x1, mark(_x2))]] = 2 + x0 + 2x1 + 2x2 >= 2 + x0 + 2x1 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U41(active(_x0), _x1, _x2)]] = 2 + x0 + 2x1 + 2x2 >= 2 + x0 + 2x1 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U41(_x0, active(_x1), _x2)]] = 2 + x0 + 2x1 + 2x2 >= 2 + x0 + 2x1 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U41(_x0, _x1, active(_x2))]] = 2 + x0 + 2x1 + 2x2 >= 2 + x0 + 2x1 + 2x2 = [[U41(_x0, _x1, _x2)]] [[U42(mark(_x0), _x1, _x2)]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[U42(_x0, _x1, _x2)]] [[U42(_x0, mark(_x1), _x2)]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[U42(_x0, _x1, _x2)]] [[U42(_x0, _x1, mark(_x2))]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[U42(_x0, _x1, _x2)]] [[U42(active(_x0), _x1, _x2)]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[U42(_x0, _x1, _x2)]] [[U42(_x0, active(_x1), _x2)]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[U42(_x0, _x1, _x2)]] [[U42(_x0, _x1, active(_x2))]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[U42(_x0, _x1, _x2)]] [[s(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[s(_x0)]] [[s(active(_x0))]] = 1 + x0 >= 1 + x0 = [[s(_x0)]] [[plus(mark(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_19, R_1, minimal, formative) by (P_20, R_1, minimal, formative), where P_20 consists of: active#(U11(tt, X)) =#> mark#(U12(isNat(X))) active#(U41(tt, X, Y)) =#> mark#(U42(isNat(Y), X, Y)) active#(isNat(plus(X, Y))) =#> mark#(U11(isNat(X), Y)) active#(isNat(s(X))) =#> mark#(U21(isNat(X))) active#(plus(X, s(Y))) =#> mark#(U41(isNat(Y), Y, X)) mark#(U11(X, Y)) =#> active#(U11(mark(X), Y)) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNat(X)) =#> active#(isNat(X)) mark#(U21(X)) =#> mark#(X) mark#(U41(X, Y, Z)) =#> active#(U41(mark(X), Y, Z)) mark#(U42(X, Y, Z)) =#> active#(U42(mark(X), Y, Z)) mark#(plus(X, Y)) =#> active#(plus(mark(X), mark(Y))) mark#(plus(X, Y)) =#> mark#(X) mark#(plus(X, Y)) =#> mark#(Y) Thus, the original system is terminating if (P_20, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_20, R_1, 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 : 7 * 1 : 11 * 2 : 5, 6 * 3 : 9 * 4 : 10 * 5 : 0 * 6 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 7 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 8 : 2, 3 * 9 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 10 : 1 * 11 : * 12 : 4 * 13 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 14 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 This graph has the following strongly connected components: P_21: active#(U11(tt, X)) =#> mark#(U12(isNat(X))) active#(isNat(plus(X, Y))) =#> mark#(U11(isNat(X), Y)) active#(isNat(s(X))) =#> mark#(U21(isNat(X))) mark#(U11(X, Y)) =#> active#(U11(mark(X), Y)) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNat(X)) =#> active#(isNat(X)) mark#(U21(X)) =#> mark#(X) mark#(plus(X, Y)) =#> mark#(X) mark#(plus(X, Y)) =#> mark#(Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_20, R_1, m, f) by (P_21, R_1, m, f). Thus, the original system is terminating if (P_21, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_21, R_1, minimal, formative). The formative rules of (P_21, R_1) are R_2 ::= active(U11(tt, X)) => mark(U12(isNat(X))) active(U12(tt)) => mark(tt) active(U21(tt)) => mark(tt) active(U31(tt, X)) => mark(X) active(U41(tt, X, Y)) => mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) => mark(s(plus(Y, X))) active(isNat(0)) => mark(tt) active(isNat(plus(X, Y))) => mark(U11(isNat(X), Y)) active(isNat(s(X))) => mark(U21(isNat(X))) active(plus(X, 0)) => mark(U31(isNat(X), X)) active(plus(X, s(Y))) => mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) => active(U11(mark(X), Y)) mark(tt) => active(tt) mark(U12(X)) => active(U12(mark(X))) mark(isNat(X)) => active(isNat(X)) mark(U21(X)) => active(U21(mark(X))) mark(U31(X, Y)) => active(U31(mark(X), Y)) mark(U41(X, Y, Z)) => active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) => active(U42(mark(X), Y, Z)) mark(s(X)) => active(s(mark(X))) mark(plus(X, Y)) => active(plus(mark(X), mark(Y))) mark(0) => active(0) U11(mark(X), Y) => U11(X, Y) U11(X, mark(Y)) => U11(X, Y) U11(active(X), Y) => U11(X, Y) U11(X, active(Y)) => U11(X, Y) U12(mark(X)) => U12(X) U12(active(X)) => U12(X) isNat(mark(X)) => isNat(X) isNat(active(X)) => isNat(X) U21(mark(X)) => U21(X) U21(active(X)) => U21(X) s(mark(X)) => s(X) s(active(X)) => s(X) plus(mark(X), Y) => plus(X, Y) plus(X, mark(Y)) => plus(X, Y) plus(active(X), Y) => plus(X, Y) plus(X, active(Y)) => plus(X, Y) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_21, R_1, minimal, formative) by (P_21, R_2, minimal, formative). Thus, the original system is terminating if (P_21, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_21, R_2, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(U11(tt, X)) >? mark#(U12(isNat(X))) active#(isNat(plus(X, Y))) >? mark#(U11(isNat(X), Y)) active#(isNat(s(X))) >? mark#(U21(isNat(X))) mark#(U11(X, Y)) >? active#(U11(mark(X), Y)) mark#(U11(X, Y)) >? mark#(X) mark#(U12(X)) >? mark#(X) mark#(isNat(X)) >? active#(isNat(X)) mark#(U21(X)) >? mark#(X) mark#(plus(X, Y)) >? mark#(X) mark#(plus(X, Y)) >? mark#(Y) active(U11(tt, X)) >= mark(U12(isNat(X))) active(U12(tt)) >= mark(tt) active(U21(tt)) >= mark(tt) active(U31(tt, X)) >= mark(X) active(U41(tt, X, Y)) >= mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) >= mark(s(plus(Y, X))) active(isNat(0)) >= mark(tt) active(isNat(plus(X, Y))) >= mark(U11(isNat(X), Y)) active(isNat(s(X))) >= mark(U21(isNat(X))) active(plus(X, 0)) >= mark(U31(isNat(X), X)) active(plus(X, s(Y))) >= mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) >= active(U11(mark(X), Y)) mark(tt) >= active(tt) mark(U12(X)) >= active(U12(mark(X))) mark(isNat(X)) >= active(isNat(X)) mark(U21(X)) >= active(U21(mark(X))) mark(U31(X, Y)) >= active(U31(mark(X), Y)) mark(U41(X, Y, Z)) >= active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) >= active(U42(mark(X), Y, Z)) mark(s(X)) >= active(s(mark(X))) mark(plus(X, Y)) >= active(plus(mark(X), mark(Y))) mark(0) >= active(0) U11(mark(X), Y) >= U11(X, Y) U11(X, mark(Y)) >= U11(X, Y) U11(active(X), Y) >= U11(X, Y) U11(X, active(Y)) >= U11(X, Y) U12(mark(X)) >= U12(X) U12(active(X)) >= U12(X) isNat(mark(X)) >= isNat(X) isNat(active(X)) >= isNat(X) U21(mark(X)) >= U21(X) U21(active(X)) >= U21(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) plus(mark(X), Y) >= plus(X, Y) plus(X, mark(Y)) >= plus(X, Y) plus(active(X), Y) >= plus(X, Y) plus(X, active(Y)) >= plus(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.y0 + 2y1 U12 = \y0.y0 U21 = \y0.y0 U31 = \y0y1.y1 U41 = \y0y1y2.1 + y1 + 2y2 U42 = \y0y1y2.1 + y1 + 2y2 active = \y0.y0 active# = \y0.y0 isNat = \y0.2y0 mark = \y0.y0 mark# = \y0.y0 plus = \y0y1.y1 + 2y0 s = \y0.1 + y0 tt = 0 Using this interpretation, the requirements translate to: [[active#(U11(tt, _x0))]] = 2x0 >= 2x0 = [[mark#(U12(isNat(_x0)))]] [[active#(isNat(plus(_x0, _x1)))]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[mark#(U11(isNat(_x0), _x1))]] [[active#(isNat(s(_x0)))]] = 2 + 2x0 > 2x0 = [[mark#(U21(isNat(_x0)))]] [[mark#(U11(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active#(U11(mark(_x0), _x1))]] [[mark#(U11(_x0, _x1))]] = x0 + 2x1 >= x0 = [[mark#(_x0)]] [[mark#(U12(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(isNat(_x0))]] = 2x0 >= 2x0 = [[active#(isNat(_x0))]] [[mark#(U21(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(plus(_x0, _x1))]] = x1 + 2x0 >= x0 = [[mark#(_x0)]] [[mark#(plus(_x0, _x1))]] = x1 + 2x0 >= x1 = [[mark#(_x1)]] [[active(U11(tt, _x0))]] = 2x0 >= 2x0 = [[mark(U12(isNat(_x0)))]] [[active(U12(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U21(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U31(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(U41(tt, _x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[mark(U42(isNat(_x1), _x0, _x1))]] [[active(U42(tt, _x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[mark(s(plus(_x1, _x0)))]] [[active(isNat(0))]] = 0 >= 0 = [[mark(tt)]] [[active(isNat(plus(_x0, _x1)))]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[mark(U11(isNat(_x0), _x1))]] [[active(isNat(s(_x0)))]] = 2 + 2x0 >= 2x0 = [[mark(U21(isNat(_x0)))]] [[active(plus(_x0, 0))]] = 2x0 >= x0 = [[mark(U31(isNat(_x0), _x0))]] [[active(plus(_x0, s(_x1)))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[mark(U41(isNat(_x1), _x1, _x0))]] [[mark(U11(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(U11(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U12(_x0))]] = x0 >= x0 = [[active(U12(mark(_x0)))]] [[mark(isNat(_x0))]] = 2x0 >= 2x0 = [[active(isNat(_x0))]] [[mark(U21(_x0))]] = x0 >= x0 = [[active(U21(mark(_x0)))]] [[mark(U31(_x0, _x1))]] = x1 >= x1 = [[active(U31(mark(_x0), _x1))]] [[mark(U41(_x0, _x1, _x2))]] = 1 + x1 + 2x2 >= 1 + x1 + 2x2 = [[active(U41(mark(_x0), _x1, _x2))]] [[mark(U42(_x0, _x1, _x2))]] = 1 + x1 + 2x2 >= 1 + x1 + 2x2 = [[active(U42(mark(_x0), _x1, _x2))]] [[mark(s(_x0))]] = 1 + x0 >= 1 + x0 = [[active(s(mark(_x0)))]] [[mark(plus(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(plus(mark(_x0), mark(_x1)))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[U11(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U11(_x0, _x1)]] [[U11(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U11(_x0, _x1)]] [[U11(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U11(_x0, _x1)]] [[U11(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U11(_x0, _x1)]] [[U12(mark(_x0))]] = x0 >= x0 = [[U12(_x0)]] [[U12(active(_x0))]] = x0 >= x0 = [[U12(_x0)]] [[isNat(mark(_x0))]] = 2x0 >= 2x0 = [[isNat(_x0)]] [[isNat(active(_x0))]] = 2x0 >= 2x0 = [[isNat(_x0)]] [[U21(mark(_x0))]] = x0 >= x0 = [[U21(_x0)]] [[U21(active(_x0))]] = x0 >= x0 = [[U21(_x0)]] [[s(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[s(_x0)]] [[s(active(_x0))]] = 1 + x0 >= 1 + x0 = [[s(_x0)]] [[plus(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_21, R_2, minimal, formative) by (P_22, R_2, minimal, formative), where P_22 consists of: active#(U11(tt, X)) =#> mark#(U12(isNat(X))) active#(isNat(plus(X, Y))) =#> mark#(U11(isNat(X), Y)) mark#(U11(X, Y)) =#> active#(U11(mark(X), Y)) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNat(X)) =#> active#(isNat(X)) mark#(U21(X)) =#> mark#(X) mark#(plus(X, Y)) =#> mark#(X) mark#(plus(X, Y)) =#> mark#(Y) Thus, the original system is terminating if (P_22, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_22, R_2, minimal, formative). The formative rules of (P_22, R_2) are R_3 ::= active(U11(tt, X)) => mark(U12(isNat(X))) active(U12(tt)) => mark(tt) active(U21(tt)) => mark(tt) active(U31(tt, X)) => mark(X) active(U41(tt, X, Y)) => mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) => mark(s(plus(Y, X))) active(isNat(0)) => mark(tt) active(isNat(plus(X, Y))) => mark(U11(isNat(X), Y)) active(isNat(s(X))) => mark(U21(isNat(X))) active(plus(X, 0)) => mark(U31(isNat(X), X)) active(plus(X, s(Y))) => mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) => active(U11(mark(X), Y)) mark(tt) => active(tt) mark(U12(X)) => active(U12(mark(X))) mark(isNat(X)) => active(isNat(X)) mark(U21(X)) => active(U21(mark(X))) mark(U31(X, Y)) => active(U31(mark(X), Y)) mark(U41(X, Y, Z)) => active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) => active(U42(mark(X), Y, Z)) mark(s(X)) => active(s(mark(X))) mark(plus(X, Y)) => active(plus(mark(X), mark(Y))) mark(0) => active(0) U11(mark(X), Y) => U11(X, Y) U11(X, mark(Y)) => U11(X, Y) U11(active(X), Y) => U11(X, Y) U11(X, active(Y)) => U11(X, Y) U12(mark(X)) => U12(X) U12(active(X)) => U12(X) isNat(mark(X)) => isNat(X) isNat(active(X)) => isNat(X) U21(mark(X)) => U21(X) U21(active(X)) => U21(X) plus(mark(X), Y) => plus(X, Y) plus(X, mark(Y)) => plus(X, Y) plus(active(X), Y) => plus(X, Y) plus(X, active(Y)) => plus(X, Y) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_22, R_2, minimal, formative) by (P_22, R_3, minimal, formative). Thus, the original system is terminating if (P_22, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_22, R_3, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(U11(tt, X)) >? mark#(U12(isNat(X))) active#(isNat(plus(X, Y))) >? mark#(U11(isNat(X), Y)) mark#(U11(X, Y)) >? active#(U11(mark(X), Y)) mark#(U11(X, Y)) >? mark#(X) mark#(U12(X)) >? mark#(X) mark#(isNat(X)) >? active#(isNat(X)) mark#(U21(X)) >? mark#(X) mark#(plus(X, Y)) >? mark#(X) mark#(plus(X, Y)) >? mark#(Y) active(U11(tt, X)) >= mark(U12(isNat(X))) active(U12(tt)) >= mark(tt) active(U21(tt)) >= mark(tt) active(U31(tt, X)) >= mark(X) active(U41(tt, X, Y)) >= mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) >= mark(s(plus(Y, X))) active(isNat(0)) >= mark(tt) active(isNat(plus(X, Y))) >= mark(U11(isNat(X), Y)) active(isNat(s(X))) >= mark(U21(isNat(X))) active(plus(X, 0)) >= mark(U31(isNat(X), X)) active(plus(X, s(Y))) >= mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) >= active(U11(mark(X), Y)) mark(tt) >= active(tt) mark(U12(X)) >= active(U12(mark(X))) mark(isNat(X)) >= active(isNat(X)) mark(U21(X)) >= active(U21(mark(X))) mark(U31(X, Y)) >= active(U31(mark(X), Y)) mark(U41(X, Y, Z)) >= active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) >= active(U42(mark(X), Y, Z)) mark(s(X)) >= active(s(mark(X))) mark(plus(X, Y)) >= active(plus(mark(X), mark(Y))) mark(0) >= active(0) U11(mark(X), Y) >= U11(X, Y) U11(X, mark(Y)) >= U11(X, Y) U11(active(X), Y) >= U11(X, Y) U11(X, active(Y)) >= U11(X, Y) U12(mark(X)) >= U12(X) U12(active(X)) >= U12(X) isNat(mark(X)) >= isNat(X) isNat(active(X)) >= isNat(X) U21(mark(X)) >= U21(X) U21(active(X)) >= U21(X) plus(mark(X), Y) >= plus(X, Y) plus(X, mark(Y)) >= plus(X, Y) plus(active(X), Y) >= plus(X, Y) plus(X, active(Y)) >= plus(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: active#(x_1) = active#() This leaves the following ordering requirements: active#(U11(tt, X)) >= mark#(U12(isNat(X))) active#(isNat(plus(X, Y))) >= mark#(U11(isNat(X), Y)) mark#(U11(X, Y)) >= active#(U11(mark(X), Y)) mark#(U11(X, Y)) >= mark#(X) mark#(U12(X)) >= mark#(X) mark#(isNat(X)) >= active#(isNat(X)) mark#(U21(X)) >= mark#(X) mark#(plus(X, Y)) >= mark#(X) mark#(plus(X, Y)) > mark#(Y) U11(mark(X), Y) >= U11(X, Y) U11(X, mark(Y)) >= U11(X, Y) U11(active(X), Y) >= U11(X, Y) U11(X, active(Y)) >= U11(X, Y) U12(mark(X)) >= U12(X) U12(active(X)) >= U12(X) isNat(mark(X)) >= isNat(X) isNat(active(X)) >= isNat(X) The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.2y0 U12 = \y0.2y0 U21 = \y0.2y0 U31 = \y0y1.0 U41 = \y0y1y2.0 U42 = \y0y1y2.0 active = \y0.y0 active# = \y0.0 isNat = \y0.0 mark = \y0.2y0 mark# = \y0.2y0 plus = \y0y1.2 + y1 + 2y0 s = \y0.0 tt = 0 Using this interpretation, the requirements translate to: [[active#(U11(tt, _x0))]] = 0 >= 0 = [[mark#(U12(isNat(_x0)))]] [[active#(isNat(plus(_x0, _x1)))]] = 0 >= 0 = [[mark#(U11(isNat(_x0), _x1))]] [[mark#(U11(_x0, _x1))]] = 4x0 >= 0 = [[active#(U11(mark(_x0), _x1))]] [[mark#(U11(_x0, _x1))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(U12(_x0))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(isNat(_x0))]] = 0 >= 0 = [[active#(isNat(_x0))]] [[mark#(U21(_x0))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(plus(_x0, _x1))]] = 4 + 2x1 + 4x0 > 2x0 = [[mark#(_x0)]] [[mark#(plus(_x0, _x1))]] = 4 + 2x1 + 4x0 > 2x1 = [[mark#(_x1)]] [[U11(mark(_x0), _x1)]] = 4x0 >= 2x0 = [[U11(_x0, _x1)]] [[U11(_x0, mark(_x1))]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U11(active(_x0), _x1)]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U11(_x0, active(_x1))]] = 2x0 >= 2x0 = [[U11(_x0, _x1)]] [[U12(mark(_x0))]] = 4x0 >= 2x0 = [[U12(_x0)]] [[U12(active(_x0))]] = 2x0 >= 2x0 = [[U12(_x0)]] [[isNat(mark(_x0))]] = 0 >= 0 = [[isNat(_x0)]] [[isNat(active(_x0))]] = 0 >= 0 = [[isNat(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_22, R_3, minimal, formative) by (P_23, R_3, minimal, formative), where P_23 consists of: active#(U11(tt, X)) =#> mark#(U12(isNat(X))) active#(isNat(plus(X, Y))) =#> mark#(U11(isNat(X), Y)) mark#(U11(X, Y)) =#> active#(U11(mark(X), Y)) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNat(X)) =#> active#(isNat(X)) mark#(U21(X)) =#> mark#(X) Thus, the original system is terminating if (P_23, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_23, R_3, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(U11(tt, X)) >? mark#(U12(isNat(X))) active#(isNat(plus(X, Y))) >? mark#(U11(isNat(X), Y)) mark#(U11(X, Y)) >? active#(U11(mark(X), Y)) mark#(U11(X, Y)) >? mark#(X) mark#(U12(X)) >? mark#(X) mark#(isNat(X)) >? active#(isNat(X)) mark#(U21(X)) >? mark#(X) active(U11(tt, X)) >= mark(U12(isNat(X))) active(U12(tt)) >= mark(tt) active(U21(tt)) >= mark(tt) active(U31(tt, X)) >= mark(X) active(U41(tt, X, Y)) >= mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) >= mark(s(plus(Y, X))) active(isNat(0)) >= mark(tt) active(isNat(plus(X, Y))) >= mark(U11(isNat(X), Y)) active(isNat(s(X))) >= mark(U21(isNat(X))) active(plus(X, 0)) >= mark(U31(isNat(X), X)) active(plus(X, s(Y))) >= mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) >= active(U11(mark(X), Y)) mark(tt) >= active(tt) mark(U12(X)) >= active(U12(mark(X))) mark(isNat(X)) >= active(isNat(X)) mark(U21(X)) >= active(U21(mark(X))) mark(U31(X, Y)) >= active(U31(mark(X), Y)) mark(U41(X, Y, Z)) >= active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) >= active(U42(mark(X), Y, Z)) mark(s(X)) >= active(s(mark(X))) mark(plus(X, Y)) >= active(plus(mark(X), mark(Y))) mark(0) >= active(0) U11(mark(X), Y) >= U11(X, Y) U11(X, mark(Y)) >= U11(X, Y) U11(active(X), Y) >= U11(X, Y) U11(X, active(Y)) >= U11(X, Y) U12(mark(X)) >= U12(X) U12(active(X)) >= U12(X) isNat(mark(X)) >= isNat(X) isNat(active(X)) >= isNat(X) U21(mark(X)) >= U21(X) U21(active(X)) >= U21(X) plus(mark(X), Y) >= plus(X, Y) plus(X, mark(Y)) >= plus(X, Y) plus(active(X), Y) >= plus(X, Y) plus(X, active(Y)) >= plus(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.2y0 + 2y1 U12 = \y0.2y0 U21 = \y0.y0 U31 = \y0y1.y1 U41 = \y0y1y2.1 + 2y1 + 2y2 U42 = \y0y1y2.1 + 2y1 + 2y2 active = \y0.y0 active# = \y0.y0 isNat = \y0.y0 mark = \y0.y0 mark# = \y0.y0 plus = \y0y1.1 + 2y0 + 2y1 s = \y0.y0 tt = 0 Using this interpretation, the requirements translate to: [[active#(U11(tt, _x0))]] = 2x0 >= 2x0 = [[mark#(U12(isNat(_x0)))]] [[active#(isNat(plus(_x0, _x1)))]] = 1 + 2x0 + 2x1 > 2x0 + 2x1 = [[mark#(U11(isNat(_x0), _x1))]] [[mark#(U11(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active#(U11(mark(_x0), _x1))]] [[mark#(U11(_x0, _x1))]] = 2x0 + 2x1 >= x0 = [[mark#(_x0)]] [[mark#(U12(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] [[mark#(isNat(_x0))]] = x0 >= x0 = [[active#(isNat(_x0))]] [[mark#(U21(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[active(U11(tt, _x0))]] = 2x0 >= 2x0 = [[mark(U12(isNat(_x0)))]] [[active(U12(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U21(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U31(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(U41(tt, _x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[mark(U42(isNat(_x1), _x0, _x1))]] [[active(U42(tt, _x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[mark(s(plus(_x1, _x0)))]] [[active(isNat(0))]] = 0 >= 0 = [[mark(tt)]] [[active(isNat(plus(_x0, _x1)))]] = 1 + 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(U11(isNat(_x0), _x1))]] [[active(isNat(s(_x0)))]] = x0 >= x0 = [[mark(U21(isNat(_x0)))]] [[active(plus(_x0, 0))]] = 1 + 2x0 >= x0 = [[mark(U31(isNat(_x0), _x0))]] [[active(plus(_x0, s(_x1)))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[mark(U41(isNat(_x1), _x1, _x0))]] [[mark(U11(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(U11(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U12(_x0))]] = 2x0 >= 2x0 = [[active(U12(mark(_x0)))]] [[mark(isNat(_x0))]] = x0 >= x0 = [[active(isNat(_x0))]] [[mark(U21(_x0))]] = x0 >= x0 = [[active(U21(mark(_x0)))]] [[mark(U31(_x0, _x1))]] = x1 >= x1 = [[active(U31(mark(_x0), _x1))]] [[mark(U41(_x0, _x1, _x2))]] = 1 + 2x1 + 2x2 >= 1 + 2x1 + 2x2 = [[active(U41(mark(_x0), _x1, _x2))]] [[mark(U42(_x0, _x1, _x2))]] = 1 + 2x1 + 2x2 >= 1 + 2x1 + 2x2 = [[active(U42(mark(_x0), _x1, _x2))]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(plus(_x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[active(plus(mark(_x0), mark(_x1)))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[U11(mark(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U11(_x0, _x1)]] [[U11(_x0, mark(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U11(_x0, _x1)]] [[U11(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U11(_x0, _x1)]] [[U11(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U11(_x0, _x1)]] [[U12(mark(_x0))]] = 2x0 >= 2x0 = [[U12(_x0)]] [[U12(active(_x0))]] = 2x0 >= 2x0 = [[U12(_x0)]] [[isNat(mark(_x0))]] = x0 >= x0 = [[isNat(_x0)]] [[isNat(active(_x0))]] = x0 >= x0 = [[isNat(_x0)]] [[U21(mark(_x0))]] = x0 >= x0 = [[U21(_x0)]] [[U21(active(_x0))]] = x0 >= x0 = [[U21(_x0)]] [[plus(mark(_x0), _x1)]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[plus(_x0, _x1)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_23, R_3, minimal, formative) by (P_24, R_3, minimal, formative), where P_24 consists of: active#(U11(tt, X)) =#> mark#(U12(isNat(X))) mark#(U11(X, Y)) =#> active#(U11(mark(X), Y)) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(isNat(X)) =#> active#(isNat(X)) mark#(U21(X)) =#> mark#(X) Thus, the original system is terminating if (P_24, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_24, R_3, 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 : 3 * 1 : 0 * 2 : 1, 2, 3, 4, 5 * 3 : 1, 2, 3, 4, 5 * 4 : * 5 : 1, 2, 3, 4, 5 This graph has the following strongly connected components: P_25: active#(U11(tt, X)) =#> mark#(U12(isNat(X))) mark#(U11(X, Y)) =#> active#(U11(mark(X), Y)) mark#(U11(X, Y)) =#> mark#(X) mark#(U12(X)) =#> mark#(X) mark#(U21(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_24, R_3, m, f) by (P_25, R_3, m, f). Thus, the original system is terminating if (P_25, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_25, R_3, minimal, formative). The formative rules of (P_25, R_3) are R_4 ::= active(U11(tt, X)) => mark(U12(isNat(X))) active(U12(tt)) => mark(tt) active(U21(tt)) => mark(tt) active(U31(tt, X)) => mark(X) active(U41(tt, X, Y)) => mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) => mark(s(plus(Y, X))) active(isNat(0)) => mark(tt) active(isNat(plus(X, Y))) => mark(U11(isNat(X), Y)) active(isNat(s(X))) => mark(U21(isNat(X))) active(plus(X, 0)) => mark(U31(isNat(X), X)) active(plus(X, s(Y))) => mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) => active(U11(mark(X), Y)) mark(tt) => active(tt) mark(U12(X)) => active(U12(mark(X))) mark(isNat(X)) => active(isNat(X)) mark(U21(X)) => active(U21(mark(X))) mark(U31(X, Y)) => active(U31(mark(X), Y)) mark(U41(X, Y, Z)) => active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) => active(U42(mark(X), Y, Z)) mark(s(X)) => active(s(mark(X))) mark(plus(X, Y)) => active(plus(mark(X), mark(Y))) mark(0) => active(0) U11(mark(X), Y) => U11(X, Y) U11(X, mark(Y)) => U11(X, Y) U11(active(X), Y) => U11(X, Y) U11(X, active(Y)) => U11(X, Y) U12(mark(X)) => U12(X) U12(active(X)) => U12(X) U21(mark(X)) => U21(X) U21(active(X)) => U21(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_25, R_3, minimal, formative) by (P_25, R_4, minimal, formative). Thus, the original system is terminating if (P_25, R_4, minimal, formative) is finite. We consider the dependency pair problem (P_25, R_4, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(U11(tt, X)) >? mark#(U12(isNat(X))) mark#(U11(X, Y)) >? active#(U11(mark(X), Y)) mark#(U11(X, Y)) >? mark#(X) mark#(U12(X)) >? mark#(X) mark#(U21(X)) >? mark#(X) active(U11(tt, X)) >= mark(U12(isNat(X))) active(U12(tt)) >= mark(tt) active(U21(tt)) >= mark(tt) active(U31(tt, X)) >= mark(X) active(U41(tt, X, Y)) >= mark(U42(isNat(Y), X, Y)) active(U42(tt, X, Y)) >= mark(s(plus(Y, X))) active(isNat(0)) >= mark(tt) active(isNat(plus(X, Y))) >= mark(U11(isNat(X), Y)) active(isNat(s(X))) >= mark(U21(isNat(X))) active(plus(X, 0)) >= mark(U31(isNat(X), X)) active(plus(X, s(Y))) >= mark(U41(isNat(Y), Y, X)) mark(U11(X, Y)) >= active(U11(mark(X), Y)) mark(tt) >= active(tt) mark(U12(X)) >= active(U12(mark(X))) mark(isNat(X)) >= active(isNat(X)) mark(U21(X)) >= active(U21(mark(X))) mark(U31(X, Y)) >= active(U31(mark(X), Y)) mark(U41(X, Y, Z)) >= active(U41(mark(X), Y, Z)) mark(U42(X, Y, Z)) >= active(U42(mark(X), Y, Z)) mark(s(X)) >= active(s(mark(X))) mark(plus(X, Y)) >= active(plus(mark(X), mark(Y))) mark(0) >= active(0) U11(mark(X), Y) >= U11(X, Y) U11(X, mark(Y)) >= U11(X, Y) U11(active(X), Y) >= U11(X, Y) U11(X, active(Y)) >= U11(X, Y) U12(mark(X)) >= U12(X) U12(active(X)) >= U12(X) U21(mark(X)) >= U21(X) U21(active(X)) >= U21(X) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: active#(x_1) = active#() This leaves the following ordering requirements: active#(U11(tt, X)) > mark#(U12(isNat(X))) mark#(U11(X, Y)) >= active#(U11(mark(X), Y)) mark#(U11(X, Y)) >= mark#(X) mark#(U12(X)) >= mark#(X) mark#(U21(X)) >= mark#(X) The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.3 + 3y0 + 3y1 U12 = \y0.2y0 U21 = \y0.2y0 U31 = \y0y1.0 U41 = \y0y1y2.0 U42 = \y0y1y2.0 active = \y0.0 active# = \y0.2 isNat = \y0.0 mark = \y0.0 mark# = \y0.3y0 plus = \y0y1.0 s = \y0.0 tt = 0 Using this interpretation, the requirements translate to: [[active#(U11(tt, _x0))]] = 2 > 0 = [[mark#(U12(isNat(_x0)))]] [[mark#(U11(_x0, _x1))]] = 9 + 9x0 + 9x1 > 2 = [[active#(U11(mark(_x0), _x1))]] [[mark#(U11(_x0, _x1))]] = 9 + 9x0 + 9x1 > 3x0 = [[mark#(_x0)]] [[mark#(U12(_x0))]] = 6x0 >= 3x0 = [[mark#(_x0)]] [[mark#(U21(_x0))]] = 6x0 >= 3x0 = [[mark#(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_25, R_4, minimal, formative) by (P_26, R_4, minimal, formative), where P_26 consists of: mark#(U12(X)) =#> mark#(X) mark#(U21(X)) =#> mark#(X) Thus, the original system is terminating if (P_26, R_4, minimal, formative) is finite. We consider the dependency pair problem (P_26, R_4, minimal, formative). We apply the subterm criterion with the following projection function: nu(mark#) = 1 Thus, we can orient the dependency pairs as follows: nu(mark#(U12(X))) = U12(X) |> X = nu(mark#(X)) nu(mark#(U21(X))) = U21(X) |> X = nu(mark#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_26, R_4, minimal, f) by ({}, R_4, 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.