/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o U11 : [o * o] --> o U12 : [o] --> o U21 : [o] --> o U31 : [o * o] --> o U32 : [o] --> o U41 : [o * o] --> o U51 : [o * o * o] --> o U52 : [o * o * o] --> o U61 : [o] --> o U71 : [o * o * o] --> o U72 : [o * o * o] --> o activate : [o] --> o isNat : [o] --> o n!6220!62200 : [] --> o n!6220!6220plus : [o * o] --> o n!6220!6220s : [o] --> o n!6220!6220x : [o * o] --> o plus : [o * o] --> o s : [o] --> o tt : [] --> o x : [o * o] --> o U11(tt, X) => U12(isNat(activate(X))) U12(tt) => tt U21(tt) => tt U31(tt, X) => U32(isNat(activate(X))) U32(tt) => tt U41(tt, X) => activate(X) U51(tt, X, Y) => U52(isNat(activate(Y)), activate(X), activate(Y)) U52(tt, X, Y) => s(plus(activate(Y), activate(X))) U61(tt) => 0 U71(tt, X, Y) => U72(isNat(activate(Y)), activate(X), activate(Y)) U72(tt, X, Y) => plus(x(activate(Y), activate(X)), activate(Y)) isNat(n!6220!62200) => tt isNat(n!6220!6220plus(X, Y)) => U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) => U21(isNat(activate(X))) isNat(n!6220!6220x(X, Y)) => U31(isNat(activate(X)), activate(Y)) plus(X, 0) => U41(isNat(X), X) plus(X, s(Y)) => U51(isNat(Y), Y, X) x(X, 0) => U61(isNat(X)) x(X, s(Y)) => U71(isNat(Y), Y, X) 0 => n!6220!62200 plus(X, Y) => n!6220!6220plus(X, Y) s(X) => n!6220!6220s(X) x(X, Y) => n!6220!6220x(X, Y) activate(n!6220!62200) => 0 activate(n!6220!6220plus(X, Y)) => plus(activate(X), activate(Y)) activate(n!6220!6220s(X)) => s(activate(X)) activate(n!6220!6220x(X, Y)) => x(activate(X), activate(Y)) activate(X) => X 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] U11#(tt, X) =#> U12#(isNat(activate(X))) 1] U11#(tt, X) =#> isNat#(activate(X)) 2] U11#(tt, X) =#> activate#(X) 3] U31#(tt, X) =#> U32#(isNat(activate(X))) 4] U31#(tt, X) =#> isNat#(activate(X)) 5] U31#(tt, X) =#> activate#(X) 6] U41#(tt, X) =#> activate#(X) 7] U51#(tt, X, Y) =#> U52#(isNat(activate(Y)), activate(X), activate(Y)) 8] U51#(tt, X, Y) =#> isNat#(activate(Y)) 9] U51#(tt, X, Y) =#> activate#(Y) 10] U51#(tt, X, Y) =#> activate#(X) 11] U51#(tt, X, Y) =#> activate#(Y) 12] U52#(tt, X, Y) =#> s#(plus(activate(Y), activate(X))) 13] U52#(tt, X, Y) =#> plus#(activate(Y), activate(X)) 14] U52#(tt, X, Y) =#> activate#(Y) 15] U52#(tt, X, Y) =#> activate#(X) 16] U61#(tt) =#> 0# 17] U71#(tt, X, Y) =#> U72#(isNat(activate(Y)), activate(X), activate(Y)) 18] U71#(tt, X, Y) =#> isNat#(activate(Y)) 19] U71#(tt, X, Y) =#> activate#(Y) 20] U71#(tt, X, Y) =#> activate#(X) 21] U71#(tt, X, Y) =#> activate#(Y) 22] U72#(tt, X, Y) =#> plus#(x(activate(Y), activate(X)), activate(Y)) 23] U72#(tt, X, Y) =#> x#(activate(Y), activate(X)) 24] U72#(tt, X, Y) =#> activate#(Y) 25] U72#(tt, X, Y) =#> activate#(X) 26] U72#(tt, X, Y) =#> activate#(Y) 27] isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) 28] isNat#(n!6220!6220plus(X, Y)) =#> isNat#(activate(X)) 29] isNat#(n!6220!6220plus(X, Y)) =#> activate#(X) 30] isNat#(n!6220!6220plus(X, Y)) =#> activate#(Y) 31] isNat#(n!6220!6220s(X)) =#> U21#(isNat(activate(X))) 32] isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) 33] isNat#(n!6220!6220s(X)) =#> activate#(X) 34] isNat#(n!6220!6220x(X, Y)) =#> U31#(isNat(activate(X)), activate(Y)) 35] isNat#(n!6220!6220x(X, Y)) =#> isNat#(activate(X)) 36] isNat#(n!6220!6220x(X, Y)) =#> activate#(X) 37] isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) 38] plus#(X, 0) =#> U41#(isNat(X), X) 39] plus#(X, 0) =#> isNat#(X) 40] plus#(X, s(Y)) =#> U51#(isNat(Y), Y, X) 41] plus#(X, s(Y)) =#> isNat#(Y) 42] x#(X, 0) =#> U61#(isNat(X)) 43] x#(X, 0) =#> isNat#(X) 44] x#(X, s(Y)) =#> U71#(isNat(Y), Y, X) 45] x#(X, s(Y)) =#> isNat#(Y) 46] activate#(n!6220!62200) =#> 0# 47] activate#(n!6220!6220plus(X, Y)) =#> plus#(activate(X), activate(Y)) 48] activate#(n!6220!6220plus(X, Y)) =#> activate#(X) 49] activate#(n!6220!6220plus(X, Y)) =#> activate#(Y) 50] activate#(n!6220!6220s(X)) =#> s#(activate(X)) 51] activate#(n!6220!6220s(X)) =#> activate#(X) 52] activate#(n!6220!6220x(X, Y)) =#> x#(activate(X), activate(Y)) 53] activate#(n!6220!6220x(X, Y)) =#> activate#(X) 54] activate#(n!6220!6220x(X, Y)) =#> activate#(Y) Rules R_0: U11(tt, X) => U12(isNat(activate(X))) U12(tt) => tt U21(tt) => tt U31(tt, X) => U32(isNat(activate(X))) U32(tt) => tt U41(tt, X) => activate(X) U51(tt, X, Y) => U52(isNat(activate(Y)), activate(X), activate(Y)) U52(tt, X, Y) => s(plus(activate(Y), activate(X))) U61(tt) => 0 U71(tt, X, Y) => U72(isNat(activate(Y)), activate(X), activate(Y)) U72(tt, X, Y) => plus(x(activate(Y), activate(X)), activate(Y)) isNat(n!6220!62200) => tt isNat(n!6220!6220plus(X, Y)) => U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) => U21(isNat(activate(X))) isNat(n!6220!6220x(X, Y)) => U31(isNat(activate(X)), activate(Y)) plus(X, 0) => U41(isNat(X), X) plus(X, s(Y)) => U51(isNat(Y), Y, X) x(X, 0) => U61(isNat(X)) x(X, s(Y)) => U71(isNat(Y), Y, X) 0 => n!6220!62200 plus(X, Y) => n!6220!6220plus(X, Y) s(X) => n!6220!6220s(X) x(X, Y) => n!6220!6220x(X, Y) activate(n!6220!62200) => 0 activate(n!6220!6220plus(X, Y)) => plus(activate(X), activate(Y)) activate(n!6220!6220s(X)) => s(activate(X)) activate(n!6220!6220x(X, Y)) => x(activate(X), activate(Y)) activate(X) => X 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 : * 1 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 2 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 3 : * 4 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 5 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 6 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 7 : 12, 13, 14, 15 * 8 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 9 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 10 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 11 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 12 : * 13 : 38, 39, 40, 41 * 14 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 15 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 16 : * 17 : 22, 23, 24, 25, 26 * 18 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 19 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 20 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 21 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 22 : 38, 39, 40, 41 * 23 : 42, 43, 44, 45 * 24 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 25 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 26 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 27 : 0, 1, 2 * 28 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 29 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 30 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 31 : * 32 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 33 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 34 : 3, 4, 5 * 35 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 36 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 37 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 38 : 6 * 39 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 40 : 7, 8, 9, 10, 11 * 41 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 42 : 16 * 43 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 44 : 17, 18, 19, 20, 21 * 45 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 46 : * 47 : 38, 39, 40, 41 * 48 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 49 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 50 : * 51 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 52 : 42, 43, 44, 45 * 53 : 46, 47, 48, 49, 50, 51, 52, 53, 54 * 54 : 46, 47, 48, 49, 50, 51, 52, 53, 54 This graph has the following strongly connected components: P_1: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U31#(tt, X) =#> isNat#(activate(X)) U31#(tt, X) =#> activate#(X) U41#(tt, X) =#> activate#(X) U51#(tt, X, Y) =#> U52#(isNat(activate(Y)), activate(X), activate(Y)) U51#(tt, X, Y) =#> isNat#(activate(Y)) U51#(tt, X, Y) =#> activate#(Y) U51#(tt, X, Y) =#> activate#(X) U51#(tt, X, Y) =#> activate#(Y) U52#(tt, X, Y) =#> plus#(activate(Y), activate(X)) U52#(tt, X, Y) =#> activate#(Y) U52#(tt, X, Y) =#> activate#(X) U71#(tt, X, Y) =#> U72#(isNat(activate(Y)), activate(X), activate(Y)) U71#(tt, X, Y) =#> isNat#(activate(Y)) U71#(tt, X, Y) =#> activate#(Y) U71#(tt, X, Y) =#> activate#(X) U71#(tt, X, Y) =#> activate#(Y) U72#(tt, X, Y) =#> plus#(x(activate(Y), activate(X)), activate(Y)) U72#(tt, X, Y) =#> x#(activate(Y), activate(X)) U72#(tt, X, Y) =#> activate#(Y) U72#(tt, X, Y) =#> activate#(X) U72#(tt, X, Y) =#> activate#(Y) isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220plus(X, Y)) =#> activate#(X) isNat#(n!6220!6220plus(X, Y)) =#> activate#(Y) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> U31#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220x(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) plus#(X, 0) =#> U41#(isNat(X), X) plus#(X, 0) =#> isNat#(X) plus#(X, s(Y)) =#> U51#(isNat(Y), Y, X) plus#(X, s(Y)) =#> isNat#(Y) x#(X, 0) =#> isNat#(X) x#(X, s(Y)) =#> U71#(isNat(Y), Y, X) x#(X, s(Y)) =#> isNat#(Y) activate#(n!6220!6220plus(X, Y)) =#> plus#(activate(X), activate(Y)) activate#(n!6220!6220plus(X, Y)) =#> activate#(X) activate#(n!6220!6220plus(X, Y)) =#> activate#(Y) activate#(n!6220!6220s(X)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> x#(activate(X), activate(Y)) activate#(n!6220!6220x(X, Y)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> activate#(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). 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: U11#(tt, X) >? isNat#(activate(X)) U11#(tt, X) >? activate#(X) U31#(tt, X) >? isNat#(activate(X)) U31#(tt, X) >? activate#(X) U41#(tt, X) >? activate#(X) U51#(tt, X, Y) >? U52#(isNat(activate(Y)), activate(X), activate(Y)) U51#(tt, X, Y) >? isNat#(activate(Y)) U51#(tt, X, Y) >? activate#(Y) U51#(tt, X, Y) >? activate#(X) U51#(tt, X, Y) >? activate#(Y) U52#(tt, X, Y) >? plus#(activate(Y), activate(X)) U52#(tt, X, Y) >? activate#(Y) U52#(tt, X, Y) >? activate#(X) U71#(tt, X, Y) >? U72#(isNat(activate(Y)), activate(X), activate(Y)) U71#(tt, X, Y) >? isNat#(activate(Y)) U71#(tt, X, Y) >? activate#(Y) U71#(tt, X, Y) >? activate#(X) U71#(tt, X, Y) >? activate#(Y) U72#(tt, X, Y) >? plus#(x(activate(Y), activate(X)), activate(Y)) U72#(tt, X, Y) >? x#(activate(Y), activate(X)) U72#(tt, X, Y) >? activate#(Y) U72#(tt, X, Y) >? activate#(X) U72#(tt, X, Y) >? activate#(Y) isNat#(n!6220!6220plus(X, Y)) >? U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) >? isNat#(activate(X)) isNat#(n!6220!6220plus(X, Y)) >? activate#(X) isNat#(n!6220!6220plus(X, Y)) >? activate#(Y) isNat#(n!6220!6220s(X)) >? isNat#(activate(X)) isNat#(n!6220!6220s(X)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? U31#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220x(X, Y)) >? isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? activate#(Y) plus#(X, 0) >? U41#(isNat(X), X) plus#(X, 0) >? isNat#(X) plus#(X, s(Y)) >? U51#(isNat(Y), Y, X) plus#(X, s(Y)) >? isNat#(Y) x#(X, 0) >? isNat#(X) x#(X, s(Y)) >? U71#(isNat(Y), Y, X) x#(X, s(Y)) >? isNat#(Y) activate#(n!6220!6220plus(X, Y)) >? plus#(activate(X), activate(Y)) activate#(n!6220!6220plus(X, Y)) >? activate#(X) activate#(n!6220!6220plus(X, Y)) >? activate#(Y) activate#(n!6220!6220s(X)) >? activate#(X) activate#(n!6220!6220x(X, Y)) >? x#(activate(X), activate(Y)) activate#(n!6220!6220x(X, Y)) >? activate#(X) activate#(n!6220!6220x(X, Y)) >? activate#(Y) U11(tt, X) >= U12(isNat(activate(X))) U12(tt) >= tt U21(tt) >= tt U31(tt, X) >= U32(isNat(activate(X))) U32(tt) >= tt U41(tt, X) >= activate(X) U51(tt, X, Y) >= U52(isNat(activate(Y)), activate(X), activate(Y)) U52(tt, X, Y) >= s(plus(activate(Y), activate(X))) U61(tt) >= 0 U71(tt, X, Y) >= U72(isNat(activate(Y)), activate(X), activate(Y)) U72(tt, X, Y) >= plus(x(activate(Y), activate(X)), activate(Y)) isNat(n!6220!62200) >= tt isNat(n!6220!6220plus(X, Y)) >= U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) >= U21(isNat(activate(X))) isNat(n!6220!6220x(X, Y)) >= U31(isNat(activate(X)), activate(Y)) plus(X, 0) >= U41(isNat(X), X) plus(X, s(Y)) >= U51(isNat(Y), Y, X) x(X, 0) >= U61(isNat(X)) x(X, s(Y)) >= U71(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(activate(X), activate(Y)) activate(n!6220!6220s(X)) >= s(activate(X)) activate(n!6220!6220x(X, Y)) >= x(activate(X), activate(Y)) activate(X) >= X Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.) We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U11(x_1, x_2)]] = x_1 [[U12(x_1)]] = _|_ [[U21(x_1)]] = x_1 [[U31(x_1, x_2)]] = x_1 [[U31#(x_1, x_2)]] = U31#(x_2) [[U32(x_1)]] = x_1 [[U41(x_1, x_2)]] = x_2 [[U51#(x_1, x_2, x_3)]] = U51#(x_2, x_3) [[U52#(x_1, x_2, x_3)]] = U52#(x_2, x_3) [[U61(x_1)]] = x_1 [[activate(x_1)]] = x_1 [[isNat(x_1)]] = _|_ [[n!6220!62200]] = _|_ [[tt]] = _|_ We choose Lex = {} and Mul = {U11#, U31#, U41#, U51, U51#, U52, U52#, U71, U71#, U72, U72#, activate#, isNat#, n!6220!6220plus, n!6220!6220s, n!6220!6220x, plus, plus#, s, x, x#}, and the following precedence: U71 = U71# = U72 = U72# = n!6220!6220x = x = x# > U11# = U51 = U52 = n!6220!6220plus = plus > U31# = U41# = U51# = U52# = isNat# = plus# > activate# > n!6220!6220s = s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11#(_|_, X) >= isNat#(X) U11#(_|_, X) >= activate#(X) U31#(X) >= isNat#(X) U31#(X) >= activate#(X) U41#(_|_, X) >= activate#(X) U51#(X, Y) >= U52#(X, Y) U51#(X, Y) >= isNat#(Y) U51#(X, Y) >= activate#(Y) U51#(X, Y) >= activate#(X) U51#(X, Y) >= activate#(Y) U52#(X, Y) >= plus#(Y, X) U52#(X, Y) >= activate#(Y) U52#(X, Y) > activate#(X) U71#(_|_, X, Y) >= U72#(_|_, X, Y) U71#(_|_, X, Y) >= isNat#(Y) U71#(_|_, X, Y) >= activate#(Y) U71#(_|_, X, Y) >= activate#(X) U71#(_|_, X, Y) >= activate#(Y) U72#(_|_, X, Y) >= plus#(x(Y, X), Y) U72#(_|_, X, Y) >= x#(Y, X) U72#(_|_, X, Y) >= activate#(Y) U72#(_|_, X, Y) >= activate#(X) U72#(_|_, X, Y) >= activate#(Y) isNat#(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) isNat#(n!6220!6220plus(X, Y)) >= isNat#(X) isNat#(n!6220!6220plus(X, Y)) >= activate#(X) isNat#(n!6220!6220plus(X, Y)) > activate#(Y) isNat#(n!6220!6220s(X)) >= isNat#(X) isNat#(n!6220!6220s(X)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) >= U31#(Y) isNat#(n!6220!6220x(X, Y)) >= isNat#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(Y) plus#(X, _|_) >= U41#(_|_, X) plus#(X, _|_) >= isNat#(X) plus#(X, s(Y)) >= U51#(Y, X) plus#(X, s(Y)) >= isNat#(Y) x#(X, _|_) >= isNat#(X) x#(X, s(Y)) >= U71#(_|_, Y, X) x#(X, s(Y)) >= isNat#(Y) activate#(n!6220!6220plus(X, Y)) >= plus#(X, Y) activate#(n!6220!6220plus(X, Y)) >= activate#(X) activate#(n!6220!6220plus(X, Y)) >= activate#(Y) activate#(n!6220!6220s(X)) >= activate#(X) activate#(n!6220!6220x(X, Y)) >= x#(X, Y) activate#(n!6220!6220x(X, Y)) >= activate#(X) activate#(n!6220!6220x(X, Y)) >= activate#(Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ X >= X U51(_|_, X, Y) >= U52(_|_, X, Y) U52(_|_, X, Y) >= s(plus(Y, X)) _|_ >= _|_ U71(_|_, X, Y) >= U72(_|_, X, Y) U72(_|_, X, Y) >= plus(x(Y, X), Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ plus(X, _|_) >= X plus(X, s(Y)) >= U51(_|_, Y, X) x(X, _|_) >= _|_ x(X, s(Y)) >= U71(_|_, Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220s(X) >= s(X) n!6220!6220x(X, Y) >= x(X, Y) X >= X With these choices, we have: 1] U11#(_|_, X) >= isNat#(X) because [2], by (Star) 2] U11#*(_|_, X) >= isNat#(X) because U11# > isNat# and [3], by (Copy) 3] U11#*(_|_, X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] U11#(_|_, X) >= activate#(X) because [6], by (Star) 6] U11#*(_|_, X) >= activate#(X) because U11# > activate# and [3], by (Copy) 7] U31#(X) >= isNat#(X) because U31# = isNat#, U31# in Mul and [8], by (Fun) 8] X >= X by (Meta) 9] U31#(X) >= activate#(X) because [10], by (Star) 10] U31#*(X) >= activate#(X) because U31# > activate# and [11], by (Copy) 11] U31#*(X) >= X because [8], by (Select) 12] U41#(_|_, X) >= activate#(X) because [13], by (Star) 13] U41#*(_|_, X) >= activate#(X) because U41# > activate# and [14], by (Copy) 14] U41#*(_|_, X) >= X because [15], by (Select) 15] X >= X by (Meta) 16] U51#(X, Y) >= U52#(X, Y) because U51# = U52#, U51# in Mul, [17] and [18], by (Fun) 17] X >= X by (Meta) 18] Y >= Y by (Meta) 19] U51#(X, Y) >= isNat#(Y) because [20], by (Star) 20] U51#*(X, Y) >= isNat#(Y) because U51# = isNat#, U51# in Mul and [18], by (Stat) 21] U51#(X, Y) >= activate#(Y) because [22], by (Star) 22] U51#*(X, Y) >= activate#(Y) because U51# > activate# and [23], by (Copy) 23] U51#*(X, Y) >= Y because [18], by (Select) 24] U51#(X, Y) >= activate#(X) because [25], by (Star) 25] U51#*(X, Y) >= activate#(X) because U51# > activate# and [26], by (Copy) 26] U51#*(X, Y) >= X because [17], by (Select) 27] U51#(X, Y) >= activate#(Y) because [22], by (Star) 28] U52#(X, Y) >= plus#(Y, X) because U52# = plus#, U52# in Mul, [17] and [18], by (Fun) 29] U52#(X, Y) >= activate#(Y) because [30], by (Star) 30] U52#*(X, Y) >= activate#(Y) because U52# > activate# and [31], by (Copy) 31] U52#*(X, Y) >= Y because [18], by (Select) 32] U52#(X, Y) > activate#(X) because [33], by definition 33] U52#*(X, Y) >= activate#(X) because U52# > activate# and [34], by (Copy) 34] U52#*(X, Y) >= X because [17], by (Select) 35] U71#(_|_, X, Y) >= U72#(_|_, X, Y) because U71# = U72#, U71# in Mul, [36], [17] and [18], by (Fun) 36] _|_ >= _|_ by (Bot) 37] U71#(_|_, X, Y) >= isNat#(Y) because [38], by (Star) 38] U71#*(_|_, X, Y) >= isNat#(Y) because U71# > isNat# and [39], by (Copy) 39] U71#*(_|_, X, Y) >= Y because [18], by (Select) 40] U71#(_|_, X, Y) >= activate#(Y) because [41], by (Star) 41] U71#*(_|_, X, Y) >= activate#(Y) because U71# > activate# and [39], by (Copy) 42] U71#(_|_, X, Y) >= activate#(X) because [43], by (Star) 43] U71#*(_|_, X, Y) >= activate#(X) because U71# > activate# and [44], by (Copy) 44] U71#*(_|_, X, Y) >= X because [17], by (Select) 45] U71#(_|_, X, Y) >= activate#(Y) because [41], by (Star) 46] U72#(_|_, X, Y) >= plus#(x(Y, X), Y) because [47], by (Star) 47] U72#*(_|_, X, Y) >= plus#(x(Y, X), Y) because U72# > plus#, [48] and [49], by (Copy) 48] U72#*(_|_, X, Y) >= x(Y, X) because U72# = x, U72# in Mul, [17] and [18], by (Stat) 49] U72#*(_|_, X, Y) >= Y because [18], by (Select) 50] U72#(_|_, X, Y) >= x#(Y, X) because [51], by (Star) 51] U72#*(_|_, X, Y) >= x#(Y, X) because U72# = x#, U72# in Mul, [17] and [18], by (Stat) 52] U72#(_|_, X, Y) >= activate#(Y) because [53], by (Star) 53] U72#*(_|_, X, Y) >= activate#(Y) because U72# > activate# and [49], by (Copy) 54] U72#(_|_, X, Y) >= activate#(X) because [55], by (Star) 55] U72#*(_|_, X, Y) >= activate#(X) because U72# > activate# and [56], by (Copy) 56] U72#*(_|_, X, Y) >= X because [17], by (Select) 57] U72#(_|_, X, Y) >= activate#(Y) because [53], by (Star) 58] isNat#(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because [59], by (Star) 59] isNat#*(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because [60], by (Select) 60] n!6220!6220plus(X, Y) >= U11#(_|_, Y) because n!6220!6220plus = U11#, n!6220!6220plus in Mul, [61] and [8], by (Fun) 61] X >= _|_ by (Bot) 62] isNat#(n!6220!6220plus(X, Y)) >= isNat#(X) because isNat# in Mul and [63], by (Fun) 63] n!6220!6220plus(X, Y) >= X because [64], by (Star) 64] n!6220!6220plus*(X, Y) >= X because [65], by (Select) 65] X >= X by (Meta) 66] isNat#(n!6220!6220plus(X, Y)) >= activate#(X) because [67], by (Star) 67] isNat#*(n!6220!6220plus(X, Y)) >= activate#(X) because isNat# > activate# and [68], by (Copy) 68] isNat#*(n!6220!6220plus(X, Y)) >= X because [63], by (Select) 69] isNat#(n!6220!6220plus(X, Y)) > activate#(Y) because [70], by definition 70] isNat#*(n!6220!6220plus(X, Y)) >= activate#(Y) because isNat# > activate# and [71], by (Copy) 71] isNat#*(n!6220!6220plus(X, Y)) >= Y because [72], by (Select) 72] n!6220!6220plus(X, Y) >= Y because [73], by (Star) 73] n!6220!6220plus*(X, Y) >= Y because [8], by (Select) 74] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [75], by (Fun) 75] n!6220!6220s(X) >= X because [76], by (Star) 76] n!6220!6220s*(X) >= X because [65], by (Select) 77] isNat#(n!6220!6220s(X)) >= activate#(X) because [78], by (Star) 78] isNat#*(n!6220!6220s(X)) >= activate#(X) because isNat# > activate# and [79], by (Copy) 79] isNat#*(n!6220!6220s(X)) >= X because [75], by (Select) 80] isNat#(n!6220!6220x(X, Y)) >= U31#(Y) because isNat# = U31#, isNat# in Mul and [81], by (Fun) 81] n!6220!6220x(X, Y) >= Y because [82], by (Star) 82] n!6220!6220x*(X, Y) >= Y because [8], by (Select) 83] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because isNat# in Mul and [84], by (Fun) 84] n!6220!6220x(X, Y) >= X because [85], by (Star) 85] n!6220!6220x*(X, Y) >= X because [65], by (Select) 86] isNat#(n!6220!6220x(X, Y)) >= activate#(X) because [87], by (Star) 87] isNat#*(n!6220!6220x(X, Y)) >= activate#(X) because isNat# > activate# and [88], by (Copy) 88] isNat#*(n!6220!6220x(X, Y)) >= X because [84], by (Select) 89] isNat#(n!6220!6220x(X, Y)) >= activate#(Y) because [90], by (Star) 90] isNat#*(n!6220!6220x(X, Y)) >= activate#(Y) because [91], by (Select) 91] n!6220!6220x(X, Y) >= activate#(Y) because [92], by (Star) 92] n!6220!6220x*(X, Y) >= activate#(Y) because n!6220!6220x > activate# and [93], by (Copy) 93] n!6220!6220x*(X, Y) >= Y because [8], by (Select) 94] plus#(X, _|_) >= U41#(_|_, X) because plus# = U41#, plus# in Mul, [18] and [95], by (Fun) 95] _|_ >= _|_ by (Bot) 96] plus#(X, _|_) >= isNat#(X) because [97], by (Star) 97] plus#*(X, _|_) >= isNat#(X) because plus# = isNat#, plus# in Mul and [18], by (Stat) 98] plus#(X, s(Y)) >= U51#(Y, X) because [99], by (Star) 99] plus#*(X, s(Y)) >= U51#(Y, X) because plus# = U51#, plus# in Mul, [18] and [100], by (Stat) 100] s(Y) > Y because [101], by definition 101] s*(Y) >= Y because [17], by (Select) 102] plus#(X, s(Y)) >= isNat#(Y) because [103], by (Star) 103] plus#*(X, s(Y)) >= isNat#(Y) because plus# = isNat#, plus# in Mul and [100], by (Stat) 104] x#(X, _|_) >= isNat#(X) because [105], by (Star) 105] x#*(X, _|_) >= isNat#(X) because x# > isNat# and [106], by (Copy) 106] x#*(X, _|_) >= X because [18], by (Select) 107] x#(X, s(Y)) >= U71#(_|_, Y, X) because [108], by (Star) 108] x#*(X, s(Y)) >= U71#(_|_, Y, X) because x# = U71#, x# in Mul, [18], [109] and [100], by (Stat) 109] s(Y) > _|_ because [110], by definition 110] s*(Y) >= _|_ by (Bot) 111] x#(X, s(Y)) >= isNat#(Y) because [112], by (Star) 112] x#*(X, s(Y)) >= isNat#(Y) because x# > isNat# and [113], by (Copy) 113] x#*(X, s(Y)) >= Y because [114], by (Select) 114] s(Y) >= Y because [101], by (Star) 115] activate#(n!6220!6220plus(X, Y)) >= plus#(X, Y) because [116], by (Star) 116] activate#*(n!6220!6220plus(X, Y)) >= plus#(X, Y) because [117], by (Select) 117] n!6220!6220plus(X, Y) >= plus#(X, Y) because [118], by (Star) 118] n!6220!6220plus*(X, Y) >= plus#(X, Y) because n!6220!6220plus > plus#, [119] and [121], by (Copy) 119] n!6220!6220plus*(X, Y) >= X because [120], by (Select) 120] X >= X by (Meta) 121] n!6220!6220plus*(X, Y) >= Y because [122], by (Select) 122] Y >= Y by (Meta) 123] activate#(n!6220!6220plus(X, Y)) >= activate#(X) because [124], by (Star) 124] activate#*(n!6220!6220plus(X, Y)) >= activate#(X) because activate# in Mul and [125], by (Stat) 125] n!6220!6220plus(X, Y) > X because [119], by definition 126] activate#(n!6220!6220plus(X, Y)) >= activate#(Y) because [127], by (Star) 127] activate#*(n!6220!6220plus(X, Y)) >= activate#(Y) because activate# in Mul and [128], by (Stat) 128] n!6220!6220plus(X, Y) > Y because [121], by definition 129] activate#(n!6220!6220s(X)) >= activate#(X) because activate# in Mul and [130], by (Fun) 130] n!6220!6220s(X) >= X because [131], by (Star) 131] n!6220!6220s*(X) >= X because [132], by (Select) 132] X >= X by (Meta) 133] activate#(n!6220!6220x(X, Y)) >= x#(X, Y) because [134], by (Star) 134] activate#*(n!6220!6220x(X, Y)) >= x#(X, Y) because [135], by (Select) 135] n!6220!6220x(X, Y) >= x#(X, Y) because n!6220!6220x = x#, n!6220!6220x in Mul, [136] and [137], by (Fun) 136] X >= X by (Meta) 137] Y >= Y by (Meta) 138] activate#(n!6220!6220x(X, Y)) >= activate#(X) because activate# in Mul and [139], by (Fun) 139] n!6220!6220x(X, Y) >= X because [140], by (Star) 140] n!6220!6220x*(X, Y) >= X because [136], by (Select) 141] activate#(n!6220!6220x(X, Y)) >= activate#(Y) because [142], by (Star) 142] activate#*(n!6220!6220x(X, Y)) >= activate#(Y) because activate# in Mul and [143], by (Stat) 143] n!6220!6220x(X, Y) > Y because [144], by definition 144] n!6220!6220x*(X, Y) >= Y because [137], by (Select) 145] _|_ >= _|_ by (Bot) 146] _|_ >= _|_ by (Bot) 147] _|_ >= _|_ by (Bot) 148] _|_ >= _|_ by (Bot) 149] _|_ >= _|_ by (Bot) 150] X >= X by (Meta) 151] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [36], [17] and [18], by (Fun) 152] U52(_|_, X, Y) >= s(plus(Y, X)) because [153], by (Star) 153] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [154], by (Copy) 154] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [17] and [18], by (Stat) 155] _|_ >= _|_ by (Bot) 156] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [36], [17] and [18], by (Fun) 157] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [158], by (Star) 158] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [159] and [160], by (Copy) 159] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [17] and [18], by (Stat) 160] U72*(_|_, X, Y) >= Y because [150], by (Select) 161] _|_ >= _|_ by (Bot) 162] _|_ >= _|_ by (Bot) 163] _|_ >= _|_ by (Bot) 164] _|_ >= _|_ by (Bot) 165] plus(X, _|_) >= X because [166], by (Star) 166] plus*(X, _|_) >= X because [150], by (Select) 167] plus(X, s(Y)) >= U51(_|_, Y, X) because [168], by (Star) 168] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [18], [109] and [100], by (Stat) 169] x(X, _|_) >= _|_ by (Bot) 170] x(X, s(Y)) >= U71(_|_, Y, X) because [171], by (Star) 171] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [18], [109] and [100], by (Stat) 172] _|_ >= _|_ by (Bot) 173] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [136] and [137], by (Fun) 174] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [175], by (Fun) 175] X >= X by (Meta) 176] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [136] and [137], by (Fun) 177] _|_ >= _|_ by (Bot) 178] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [136] and [137], by (Fun) 179] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [180], by (Fun) 180] X >= X by (Meta) 181] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [136] and [137], by (Fun) 182] X >= X by (Meta) 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_2, R_0, minimal, formative), where P_2 consists of: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U31#(tt, X) =#> isNat#(activate(X)) U31#(tt, X) =#> activate#(X) U41#(tt, X) =#> activate#(X) U51#(tt, X, Y) =#> U52#(isNat(activate(Y)), activate(X), activate(Y)) U51#(tt, X, Y) =#> isNat#(activate(Y)) U51#(tt, X, Y) =#> activate#(Y) U51#(tt, X, Y) =#> activate#(X) U51#(tt, X, Y) =#> activate#(Y) U52#(tt, X, Y) =#> plus#(activate(Y), activate(X)) U52#(tt, X, Y) =#> activate#(Y) U71#(tt, X, Y) =#> U72#(isNat(activate(Y)), activate(X), activate(Y)) U71#(tt, X, Y) =#> isNat#(activate(Y)) U71#(tt, X, Y) =#> activate#(Y) U71#(tt, X, Y) =#> activate#(X) U71#(tt, X, Y) =#> activate#(Y) U72#(tt, X, Y) =#> plus#(x(activate(Y), activate(X)), activate(Y)) U72#(tt, X, Y) =#> x#(activate(Y), activate(X)) U72#(tt, X, Y) =#> activate#(Y) U72#(tt, X, Y) =#> activate#(X) U72#(tt, X, Y) =#> activate#(Y) isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220plus(X, Y)) =#> activate#(X) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> U31#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220x(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) plus#(X, 0) =#> U41#(isNat(X), X) plus#(X, 0) =#> isNat#(X) plus#(X, s(Y)) =#> U51#(isNat(Y), Y, X) plus#(X, s(Y)) =#> isNat#(Y) x#(X, 0) =#> isNat#(X) x#(X, s(Y)) =#> U71#(isNat(Y), Y, X) x#(X, s(Y)) =#> isNat#(Y) activate#(n!6220!6220plus(X, Y)) =#> plus#(activate(X), activate(Y)) activate#(n!6220!6220plus(X, Y)) =#> activate#(X) activate#(n!6220!6220plus(X, Y)) =#> activate#(Y) activate#(n!6220!6220s(X)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> x#(activate(X), activate(Y)) activate#(n!6220!6220x(X, Y)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> activate#(Y) Thus, the original system is terminating if (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, 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: U11#(tt, X) >? isNat#(activate(X)) U11#(tt, X) >? activate#(X) U31#(tt, X) >? isNat#(activate(X)) U31#(tt, X) >? activate#(X) U41#(tt, X) >? activate#(X) U51#(tt, X, Y) >? U52#(isNat(activate(Y)), activate(X), activate(Y)) U51#(tt, X, Y) >? isNat#(activate(Y)) U51#(tt, X, Y) >? activate#(Y) U51#(tt, X, Y) >? activate#(X) U51#(tt, X, Y) >? activate#(Y) U52#(tt, X, Y) >? plus#(activate(Y), activate(X)) U52#(tt, X, Y) >? activate#(Y) U71#(tt, X, Y) >? U72#(isNat(activate(Y)), activate(X), activate(Y)) U71#(tt, X, Y) >? isNat#(activate(Y)) U71#(tt, X, Y) >? activate#(Y) U71#(tt, X, Y) >? activate#(X) U71#(tt, X, Y) >? activate#(Y) U72#(tt, X, Y) >? plus#(x(activate(Y), activate(X)), activate(Y)) U72#(tt, X, Y) >? x#(activate(Y), activate(X)) U72#(tt, X, Y) >? activate#(Y) U72#(tt, X, Y) >? activate#(X) U72#(tt, X, Y) >? activate#(Y) isNat#(n!6220!6220plus(X, Y)) >? U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) >? isNat#(activate(X)) isNat#(n!6220!6220plus(X, Y)) >? activate#(X) isNat#(n!6220!6220s(X)) >? isNat#(activate(X)) isNat#(n!6220!6220s(X)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? U31#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220x(X, Y)) >? isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? activate#(Y) plus#(X, 0) >? U41#(isNat(X), X) plus#(X, 0) >? isNat#(X) plus#(X, s(Y)) >? U51#(isNat(Y), Y, X) plus#(X, s(Y)) >? isNat#(Y) x#(X, 0) >? isNat#(X) x#(X, s(Y)) >? U71#(isNat(Y), Y, X) x#(X, s(Y)) >? isNat#(Y) activate#(n!6220!6220plus(X, Y)) >? plus#(activate(X), activate(Y)) activate#(n!6220!6220plus(X, Y)) >? activate#(X) activate#(n!6220!6220plus(X, Y)) >? activate#(Y) activate#(n!6220!6220s(X)) >? activate#(X) activate#(n!6220!6220x(X, Y)) >? x#(activate(X), activate(Y)) activate#(n!6220!6220x(X, Y)) >? activate#(X) activate#(n!6220!6220x(X, Y)) >? activate#(Y) U11(tt, X) >= U12(isNat(activate(X))) U12(tt) >= tt U21(tt) >= tt U31(tt, X) >= U32(isNat(activate(X))) U32(tt) >= tt U41(tt, X) >= activate(X) U51(tt, X, Y) >= U52(isNat(activate(Y)), activate(X), activate(Y)) U52(tt, X, Y) >= s(plus(activate(Y), activate(X))) U61(tt) >= 0 U71(tt, X, Y) >= U72(isNat(activate(Y)), activate(X), activate(Y)) U72(tt, X, Y) >= plus(x(activate(Y), activate(X)), activate(Y)) isNat(n!6220!62200) >= tt isNat(n!6220!6220plus(X, Y)) >= U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) >= U21(isNat(activate(X))) isNat(n!6220!6220x(X, Y)) >= U31(isNat(activate(X)), activate(Y)) plus(X, 0) >= U41(isNat(X), X) plus(X, s(Y)) >= U51(isNat(Y), Y, X) x(X, 0) >= U61(isNat(X)) x(X, s(Y)) >= U71(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(activate(X), activate(Y)) activate(n!6220!6220s(X)) >= s(activate(X)) activate(n!6220!6220x(X, Y)) >= x(activate(X), activate(Y)) activate(X) >= X Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.) We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U11(x_1, x_2)]] = x_1 [[U12(x_1)]] = x_1 [[U21(x_1)]] = x_1 [[U31(x_1, x_2)]] = x_1 [[U32(x_1)]] = x_1 [[U41(x_1, x_2)]] = U41(x_2) [[U52#(x_1, x_2, x_3)]] = U52#(x_2, x_3) [[activate(x_1)]] = x_1 [[isNat(x_1)]] = isNat [[n!6220!62200]] = _|_ We choose Lex = {} and Mul = {U11#, U31#, U41, U41#, U51, U51#, U52, U52#, U61, U71, U71#, U72, U72#, activate#, isNat, isNat#, n!6220!6220plus, n!6220!6220s, n!6220!6220x, plus, plus#, s, tt, x, x#}, and the following precedence: U71 = U71# = U72 = U72# = n!6220!6220x = x = x# > U31# > U61 > U41 = U51 = U51# = U52 = U52# = n!6220!6220plus = plus = plus# > U11# = U41# > n!6220!6220s = s > isNat = tt > activate# > isNat# Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11#(tt, X) >= isNat#(X) U11#(tt, X) >= activate#(X) U31#(tt, X) >= isNat#(X) U31#(tt, X) >= activate#(X) U41#(tt, X) >= activate#(X) U51#(tt, X, Y) > U52#(X, Y) U51#(tt, X, Y) >= isNat#(Y) U51#(tt, X, Y) >= activate#(Y) U51#(tt, X, Y) >= activate#(X) U51#(tt, X, Y) >= activate#(Y) U52#(X, Y) >= plus#(Y, X) U52#(X, Y) >= activate#(Y) U71#(tt, X, Y) >= U72#(isNat, X, Y) U71#(tt, X, Y) > isNat#(Y) U71#(tt, X, Y) >= activate#(Y) U71#(tt, X, Y) >= activate#(X) U71#(tt, X, Y) >= activate#(Y) U72#(tt, X, Y) >= plus#(x(Y, X), Y) U72#(tt, X, Y) >= x#(Y, X) U72#(tt, X, Y) >= activate#(Y) U72#(tt, X, Y) >= activate#(X) U72#(tt, X, Y) >= activate#(Y) isNat#(n!6220!6220plus(X, Y)) >= U11#(isNat, Y) isNat#(n!6220!6220plus(X, Y)) > isNat#(X) isNat#(n!6220!6220plus(X, Y)) >= activate#(X) isNat#(n!6220!6220s(X)) >= isNat#(X) isNat#(n!6220!6220s(X)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) > U31#(isNat, Y) isNat#(n!6220!6220x(X, Y)) >= isNat#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(Y) plus#(X, _|_) >= U41#(isNat, X) plus#(X, _|_) >= isNat#(X) plus#(X, s(Y)) >= U51#(isNat, Y, X) plus#(X, s(Y)) >= isNat#(Y) x#(X, _|_) >= isNat#(X) x#(X, s(Y)) > U71#(isNat, Y, X) x#(X, s(Y)) >= isNat#(Y) activate#(n!6220!6220plus(X, Y)) >= plus#(X, Y) activate#(n!6220!6220plus(X, Y)) >= activate#(X) activate#(n!6220!6220plus(X, Y)) >= activate#(Y) activate#(n!6220!6220s(X)) >= activate#(X) activate#(n!6220!6220x(X, Y)) >= x#(X, Y) activate#(n!6220!6220x(X, Y)) >= activate#(X) activate#(n!6220!6220x(X, Y)) >= activate#(Y) tt >= isNat tt >= tt tt >= tt tt >= isNat tt >= tt U41(X) >= X U51(tt, X, Y) >= U52(isNat, X, Y) U52(tt, X, Y) >= s(plus(Y, X)) U61(tt) >= _|_ U71(tt, X, Y) >= U72(isNat, X, Y) U72(tt, X, Y) >= plus(x(Y, X), Y) isNat >= tt isNat >= isNat isNat >= isNat isNat >= isNat plus(X, _|_) >= U41(X) plus(X, s(Y)) >= U51(isNat, Y, X) x(X, _|_) >= U61(isNat) x(X, s(Y)) >= U71(isNat, Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220s(X) >= s(X) n!6220!6220x(X, Y) >= x(X, Y) X >= X With these choices, we have: 1] U11#(tt, X) >= isNat#(X) because [2], by (Star) 2] U11#*(tt, X) >= isNat#(X) because U11# > isNat# and [3], by (Copy) 3] U11#*(tt, X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] U11#(tt, X) >= activate#(X) because [6], by (Star) 6] U11#*(tt, X) >= activate#(X) because U11# > activate# and [3], by (Copy) 7] U31#(tt, X) >= isNat#(X) because [8], by (Star) 8] U31#*(tt, X) >= isNat#(X) because U31# > isNat# and [9], by (Copy) 9] U31#*(tt, X) >= X because [4], by (Select) 10] U31#(tt, X) >= activate#(X) because [11], by (Star) 11] U31#*(tt, X) >= activate#(X) because U31# > activate# and [9], by (Copy) 12] U41#(tt, X) >= activate#(X) because [13], by (Star) 13] U41#*(tt, X) >= activate#(X) because U41# > activate# and [14], by (Copy) 14] U41#*(tt, X) >= X because [15], by (Select) 15] X >= X by (Meta) 16] U51#(tt, X, Y) > U52#(X, Y) because [17], by definition 17] U51#*(tt, X, Y) >= U52#(X, Y) because U51# = U52#, U51# in Mul, [18] and [19], by (Stat) 18] X >= X by (Meta) 19] Y >= Y by (Meta) 20] U51#(tt, X, Y) >= isNat#(Y) because [21], by (Star) 21] U51#*(tt, X, Y) >= isNat#(Y) because U51# > isNat# and [22], by (Copy) 22] U51#*(tt, X, Y) >= Y because [19], by (Select) 23] U51#(tt, X, Y) >= activate#(Y) because [24], by (Star) 24] U51#*(tt, X, Y) >= activate#(Y) because U51# > activate# and [22], by (Copy) 25] U51#(tt, X, Y) >= activate#(X) because [26], by (Star) 26] U51#*(tt, X, Y) >= activate#(X) because U51# > activate# and [27], by (Copy) 27] U51#*(tt, X, Y) >= X because [18], by (Select) 28] U51#(tt, X, Y) >= activate#(Y) because [24], by (Star) 29] U52#(X, Y) >= plus#(Y, X) because U52# = plus#, U52# in Mul, [18] and [19], by (Fun) 30] U52#(X, Y) >= activate#(Y) because [31], by (Star) 31] U52#*(X, Y) >= activate#(Y) because U52# > activate# and [32], by (Copy) 32] U52#*(X, Y) >= Y because [19], by (Select) 33] U71#(tt, X, Y) >= U72#(isNat, X, Y) because U71# = U72#, U71# in Mul, [34], [18] and [19], by (Fun) 34] tt >= isNat because tt = isNat, by (Fun) 35] U71#(tt, X, Y) > isNat#(Y) because [36], by definition 36] U71#*(tt, X, Y) >= isNat#(Y) because U71# > isNat# and [37], by (Copy) 37] U71#*(tt, X, Y) >= Y because [19], by (Select) 38] U71#(tt, X, Y) >= activate#(Y) because [39], by (Star) 39] U71#*(tt, X, Y) >= activate#(Y) because U71# > activate# and [37], by (Copy) 40] U71#(tt, X, Y) >= activate#(X) because [41], by (Star) 41] U71#*(tt, X, Y) >= activate#(X) because U71# > activate# and [42], by (Copy) 42] U71#*(tt, X, Y) >= X because [18], by (Select) 43] U71#(tt, X, Y) >= activate#(Y) because [39], by (Star) 44] U72#(tt, X, Y) >= plus#(x(Y, X), Y) because [45], by (Star) 45] U72#*(tt, X, Y) >= plus#(x(Y, X), Y) because U72# > plus#, [46] and [47], by (Copy) 46] U72#*(tt, X, Y) >= x(Y, X) because U72# = x, U72# in Mul, [18] and [19], by (Stat) 47] U72#*(tt, X, Y) >= Y because [19], by (Select) 48] U72#(tt, X, Y) >= x#(Y, X) because [49], by (Star) 49] U72#*(tt, X, Y) >= x#(Y, X) because U72# = x#, U72# in Mul, [18] and [19], by (Stat) 50] U72#(tt, X, Y) >= activate#(Y) because [51], by (Star) 51] U72#*(tt, X, Y) >= activate#(Y) because U72# > activate# and [47], by (Copy) 52] U72#(tt, X, Y) >= activate#(X) because [53], by (Star) 53] U72#*(tt, X, Y) >= activate#(X) because U72# > activate# and [54], by (Copy) 54] U72#*(tt, X, Y) >= X because [18], by (Select) 55] U72#(tt, X, Y) >= activate#(Y) because [51], by (Star) 56] isNat#(n!6220!6220plus(X, Y)) >= U11#(isNat, Y) because [57], by (Star) 57] isNat#*(n!6220!6220plus(X, Y)) >= U11#(isNat, Y) because [58], by (Select) 58] n!6220!6220plus(X, Y) >= U11#(isNat, Y) because [59], by (Star) 59] n!6220!6220plus*(X, Y) >= U11#(isNat, Y) because n!6220!6220plus > U11#, [60] and [61], by (Copy) 60] n!6220!6220plus*(X, Y) >= isNat because n!6220!6220plus > isNat, by (Copy) 61] n!6220!6220plus*(X, Y) >= Y because [4], by (Select) 62] isNat#(n!6220!6220plus(X, Y)) > isNat#(X) because [63], by definition 63] isNat#*(n!6220!6220plus(X, Y)) >= isNat#(X) because [64], by (Select) 64] n!6220!6220plus(X, Y) >= isNat#(X) because [65], by (Star) 65] n!6220!6220plus*(X, Y) >= isNat#(X) because n!6220!6220plus > isNat# and [66], by (Copy) 66] n!6220!6220plus*(X, Y) >= X because [67], by (Select) 67] X >= X by (Meta) 68] isNat#(n!6220!6220plus(X, Y)) >= activate#(X) because [69], by (Star) 69] isNat#*(n!6220!6220plus(X, Y)) >= activate#(X) because [70], by (Select) 70] n!6220!6220plus(X, Y) >= activate#(X) because [71], by (Star) 71] n!6220!6220plus*(X, Y) >= activate#(X) because n!6220!6220plus > activate# and [66], by (Copy) 72] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [73], by (Fun) 73] n!6220!6220s(X) >= X because [74], by (Star) 74] n!6220!6220s*(X) >= X because [67], by (Select) 75] isNat#(n!6220!6220s(X)) >= activate#(X) because [76], by (Star) 76] isNat#*(n!6220!6220s(X)) >= activate#(X) because [77], by (Select) 77] n!6220!6220s(X) >= activate#(X) because [78], by (Star) 78] n!6220!6220s*(X) >= activate#(X) because n!6220!6220s > activate# and [79], by (Copy) 79] n!6220!6220s*(X) >= X because [67], by (Select) 80] isNat#(n!6220!6220x(X, Y)) > U31#(isNat, Y) because [81], by definition 81] isNat#*(n!6220!6220x(X, Y)) >= U31#(isNat, Y) because [82], by (Select) 82] n!6220!6220x(X, Y) >= U31#(isNat, Y) because [83], by (Star) 83] n!6220!6220x*(X, Y) >= U31#(isNat, Y) because n!6220!6220x > U31#, [84] and [85], by (Copy) 84] n!6220!6220x*(X, Y) >= isNat because n!6220!6220x > isNat, by (Copy) 85] n!6220!6220x*(X, Y) >= Y because [4], by (Select) 86] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because isNat# in Mul and [87], by (Fun) 87] n!6220!6220x(X, Y) >= X because [88], by (Star) 88] n!6220!6220x*(X, Y) >= X because [67], by (Select) 89] isNat#(n!6220!6220x(X, Y)) >= activate#(X) because [90], by (Star) 90] isNat#*(n!6220!6220x(X, Y)) >= activate#(X) because [91], by (Select) 91] n!6220!6220x(X, Y) >= activate#(X) because [92], by (Star) 92] n!6220!6220x*(X, Y) >= activate#(X) because n!6220!6220x > activate# and [93], by (Copy) 93] n!6220!6220x*(X, Y) >= X because [67], by (Select) 94] isNat#(n!6220!6220x(X, Y)) >= activate#(Y) because [95], by (Star) 95] isNat#*(n!6220!6220x(X, Y)) >= activate#(Y) because [96], by (Select) 96] n!6220!6220x(X, Y) >= activate#(Y) because [97], by (Star) 97] n!6220!6220x*(X, Y) >= activate#(Y) because n!6220!6220x > activate# and [85], by (Copy) 98] plus#(X, _|_) >= U41#(isNat, X) because [99], by (Star) 99] plus#*(X, _|_) >= U41#(isNat, X) because plus# > U41#, [100] and [101], by (Copy) 100] plus#*(X, _|_) >= isNat because plus# > isNat, by (Copy) 101] plus#*(X, _|_) >= X because [19], by (Select) 102] plus#(X, _|_) >= isNat#(X) because [103], by (Star) 103] plus#*(X, _|_) >= isNat#(X) because plus# > isNat# and [101], by (Copy) 104] plus#(X, s(Y)) >= U51#(isNat, Y, X) because [105], by (Star) 105] plus#*(X, s(Y)) >= U51#(isNat, Y, X) because plus# = U51#, plus# in Mul, [19], [106] and [108], by (Stat) 106] s(Y) > isNat because [107], by definition 107] s*(Y) >= isNat because s > isNat, by (Copy) 108] s(Y) > Y because [109], by definition 109] s*(Y) >= Y because [18], by (Select) 110] plus#(X, s(Y)) >= isNat#(Y) because [111], by (Star) 111] plus#*(X, s(Y)) >= isNat#(Y) because plus# > isNat# and [112], by (Copy) 112] plus#*(X, s(Y)) >= Y because [113], by (Select) 113] s(Y) >= Y because [109], by (Star) 114] x#(X, _|_) >= isNat#(X) because [115], by (Star) 115] x#*(X, _|_) >= isNat#(X) because x# > isNat# and [116], by (Copy) 116] x#*(X, _|_) >= X because [19], by (Select) 117] x#(X, s(Y)) > U71#(isNat, Y, X) because [118], by definition 118] x#*(X, s(Y)) >= U71#(isNat, Y, X) because x# = U71#, x# in Mul, [19], [106] and [108], by (Stat) 119] x#(X, s(Y)) >= isNat#(Y) because [120], by (Star) 120] x#*(X, s(Y)) >= isNat#(Y) because x# > isNat# and [121], by (Copy) 121] x#*(X, s(Y)) >= Y because [113], by (Select) 122] activate#(n!6220!6220plus(X, Y)) >= plus#(X, Y) because [123], by (Star) 123] activate#*(n!6220!6220plus(X, Y)) >= plus#(X, Y) because [124], by (Select) 124] n!6220!6220plus(X, Y) >= plus#(X, Y) because n!6220!6220plus = plus#, n!6220!6220plus in Mul, [125] and [126], by (Fun) 125] X >= X by (Meta) 126] Y >= Y by (Meta) 127] activate#(n!6220!6220plus(X, Y)) >= activate#(X) because activate# in Mul and [128], by (Fun) 128] n!6220!6220plus(X, Y) >= X because [129], by (Star) 129] n!6220!6220plus*(X, Y) >= X because [125], by (Select) 130] activate#(n!6220!6220plus(X, Y)) >= activate#(Y) because activate# in Mul and [131], by (Fun) 131] n!6220!6220plus(X, Y) >= Y because [132], by (Star) 132] n!6220!6220plus*(X, Y) >= Y because [126], by (Select) 133] activate#(n!6220!6220s(X)) >= activate#(X) because activate# in Mul and [134], by (Fun) 134] n!6220!6220s(X) >= X because [135], by (Star) 135] n!6220!6220s*(X) >= X because [136], by (Select) 136] X >= X by (Meta) 137] activate#(n!6220!6220x(X, Y)) >= x#(X, Y) because [138], by (Star) 138] activate#*(n!6220!6220x(X, Y)) >= x#(X, Y) because [139], by (Select) 139] n!6220!6220x(X, Y) >= x#(X, Y) because n!6220!6220x = x#, n!6220!6220x in Mul, [125] and [126], by (Fun) 140] activate#(n!6220!6220x(X, Y)) >= activate#(X) because activate# in Mul and [141], by (Fun) 141] n!6220!6220x(X, Y) >= X because [142], by (Star) 142] n!6220!6220x*(X, Y) >= X because [125], by (Select) 143] activate#(n!6220!6220x(X, Y)) >= activate#(Y) because [144], by (Star) 144] activate#*(n!6220!6220x(X, Y)) >= activate#(Y) because activate# in Mul and [145], by (Stat) 145] n!6220!6220x(X, Y) > Y because [146], by definition 146] n!6220!6220x*(X, Y) >= Y because [126], by (Select) 147] tt >= isNat because tt = isNat, by (Fun) 148] tt >= tt by (Fun) 149] tt >= tt by (Fun) 150] tt >= isNat because tt = isNat, by (Fun) 151] tt >= tt by (Fun) 152] U41(X) >= X because [153], by (Star) 153] U41*(X) >= X because [19], by (Select) 154] U51(tt, X, Y) >= U52(isNat, X, Y) because U51 = U52, U51 in Mul, [34], [18] and [19], by (Fun) 155] U52(tt, X, Y) >= s(plus(Y, X)) because [156], by (Star) 156] U52*(tt, X, Y) >= s(plus(Y, X)) because U52 > s and [157], by (Copy) 157] U52*(tt, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [18] and [19], by (Stat) 158] U61(tt) >= _|_ by (Bot) 159] U71(tt, X, Y) >= U72(isNat, X, Y) because U71 = U72, U71 in Mul, [34], [18] and [19], by (Fun) 160] U72(tt, X, Y) >= plus(x(Y, X), Y) because [161], by (Star) 161] U72*(tt, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [162] and [163], by (Copy) 162] U72*(tt, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [18] and [19], by (Stat) 163] U72*(tt, X, Y) >= Y because [19], by (Select) 164] isNat >= tt because isNat = tt, by (Fun) 165] isNat >= isNat because isNat in Mul, by (Fun) 166] isNat >= isNat because isNat in Mul, by (Fun) 167] isNat >= isNat because isNat in Mul, by (Fun) 168] plus(X, _|_) >= U41(X) because [169], by (Star) 169] plus*(X, _|_) >= U41(X) because plus = U41, plus in Mul and [19], by (Stat) 170] plus(X, s(Y)) >= U51(isNat, Y, X) because [171], by (Star) 171] plus*(X, s(Y)) >= U51(isNat, Y, X) because plus = U51, plus in Mul, [19], [106] and [108], by (Stat) 172] x(X, _|_) >= U61(isNat) because [173], by (Star) 173] x*(X, _|_) >= U61(isNat) because x > U61 and [174], by (Copy) 174] x*(X, _|_) >= isNat because x > isNat, by (Copy) 175] x(X, s(Y)) >= U71(isNat, Y, X) because [176], by (Star) 176] x*(X, s(Y)) >= U71(isNat, Y, X) because x = U71, x in Mul, [19], [106] and [108], by (Stat) 177] _|_ >= _|_ by (Bot) 178] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [125] and [126], by (Fun) 179] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [180], by (Fun) 180] X >= X by (Meta) 181] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [125] and [126], by (Fun) 182] _|_ >= _|_ by (Bot) 183] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [125] and [126], by (Fun) 184] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [185], by (Fun) 185] X >= X by (Meta) 186] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [125] and [126], by (Fun) 187] X >= X by (Meta) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_2, R_0, minimal, formative) by (P_3, R_0, minimal, formative), where P_3 consists of: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U31#(tt, X) =#> isNat#(activate(X)) U31#(tt, X) =#> activate#(X) U41#(tt, X) =#> activate#(X) U51#(tt, X, Y) =#> isNat#(activate(Y)) U51#(tt, X, Y) =#> activate#(Y) U51#(tt, X, Y) =#> activate#(X) U51#(tt, X, Y) =#> activate#(Y) U52#(tt, X, Y) =#> plus#(activate(Y), activate(X)) U52#(tt, X, Y) =#> activate#(Y) U71#(tt, X, Y) =#> U72#(isNat(activate(Y)), activate(X), activate(Y)) U71#(tt, X, Y) =#> activate#(Y) U71#(tt, X, Y) =#> activate#(X) U71#(tt, X, Y) =#> activate#(Y) U72#(tt, X, Y) =#> plus#(x(activate(Y), activate(X)), activate(Y)) U72#(tt, X, Y) =#> x#(activate(Y), activate(X)) U72#(tt, X, Y) =#> activate#(Y) U72#(tt, X, Y) =#> activate#(X) U72#(tt, X, Y) =#> activate#(Y) isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) =#> activate#(X) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) plus#(X, 0) =#> U41#(isNat(X), X) plus#(X, 0) =#> isNat#(X) plus#(X, s(Y)) =#> U51#(isNat(Y), Y, X) plus#(X, s(Y)) =#> isNat#(Y) x#(X, 0) =#> isNat#(X) x#(X, s(Y)) =#> isNat#(Y) activate#(n!6220!6220plus(X, Y)) =#> plus#(activate(X), activate(Y)) activate#(n!6220!6220plus(X, Y)) =#> activate#(X) activate#(n!6220!6220plus(X, Y)) =#> activate#(Y) activate#(n!6220!6220s(X)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> x#(activate(X), activate(Y)) activate#(n!6220!6220x(X, Y)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> activate#(Y) Thus, the original system is terminating if (P_3, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_3, 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 : 20, 21, 22, 23, 24, 25, 26 * 1 : 33, 34, 35, 36, 37, 38, 39 * 2 : 20, 21, 22, 23, 24, 25, 26 * 3 : 33, 34, 35, 36, 37, 38, 39 * 4 : 33, 34, 35, 36, 37, 38, 39 * 5 : 20, 21, 22, 23, 24, 25, 26 * 6 : 33, 34, 35, 36, 37, 38, 39 * 7 : 33, 34, 35, 36, 37, 38, 39 * 8 : 33, 34, 35, 36, 37, 38, 39 * 9 : 27, 28, 29, 30 * 10 : 33, 34, 35, 36, 37, 38, 39 * 11 : 15, 16, 17, 18, 19 * 12 : 33, 34, 35, 36, 37, 38, 39 * 13 : 33, 34, 35, 36, 37, 38, 39 * 14 : 33, 34, 35, 36, 37, 38, 39 * 15 : 27, 28, 29, 30 * 16 : 31, 32 * 17 : 33, 34, 35, 36, 37, 38, 39 * 18 : 33, 34, 35, 36, 37, 38, 39 * 19 : 33, 34, 35, 36, 37, 38, 39 * 20 : 0, 1 * 21 : 33, 34, 35, 36, 37, 38, 39 * 22 : 20, 21, 22, 23, 24, 25, 26 * 23 : 33, 34, 35, 36, 37, 38, 39 * 24 : 20, 21, 22, 23, 24, 25, 26 * 25 : 33, 34, 35, 36, 37, 38, 39 * 26 : 33, 34, 35, 36, 37, 38, 39 * 27 : 4 * 28 : 20, 21, 22, 23, 24, 25, 26 * 29 : 5, 6, 7, 8 * 30 : 20, 21, 22, 23, 24, 25, 26 * 31 : 20, 21, 22, 23, 24, 25, 26 * 32 : 20, 21, 22, 23, 24, 25, 26 * 33 : 27, 28, 29, 30 * 34 : 33, 34, 35, 36, 37, 38, 39 * 35 : 33, 34, 35, 36, 37, 38, 39 * 36 : 33, 34, 35, 36, 37, 38, 39 * 37 : 31, 32 * 38 : 33, 34, 35, 36, 37, 38, 39 * 39 : 33, 34, 35, 36, 37, 38, 39 This graph has the following strongly connected components: P_4: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U41#(tt, X) =#> activate#(X) U51#(tt, X, Y) =#> isNat#(activate(Y)) U51#(tt, X, Y) =#> activate#(Y) U51#(tt, X, Y) =#> activate#(X) U51#(tt, X, Y) =#> activate#(Y) isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) =#> activate#(X) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) plus#(X, 0) =#> U41#(isNat(X), X) plus#(X, 0) =#> isNat#(X) plus#(X, s(Y)) =#> U51#(isNat(Y), Y, X) plus#(X, s(Y)) =#> isNat#(Y) x#(X, 0) =#> isNat#(X) x#(X, s(Y)) =#> isNat#(Y) activate#(n!6220!6220plus(X, Y)) =#> plus#(activate(X), activate(Y)) activate#(n!6220!6220plus(X, Y)) =#> activate#(X) activate#(n!6220!6220plus(X, Y)) =#> activate#(Y) activate#(n!6220!6220s(X)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> x#(activate(X), activate(Y)) activate#(n!6220!6220x(X, Y)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> activate#(Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_3, R_0, m, f) by (P_4, R_0, m, f). 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 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: U11#(tt, X) >? isNat#(activate(X)) U11#(tt, X) >? activate#(X) U41#(tt, X) >? activate#(X) U51#(tt, X, Y) >? isNat#(activate(Y)) U51#(tt, X, Y) >? activate#(Y) U51#(tt, X, Y) >? activate#(X) U51#(tt, X, Y) >? activate#(Y) isNat#(n!6220!6220plus(X, Y)) >? U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) >? activate#(X) isNat#(n!6220!6220s(X)) >? isNat#(activate(X)) isNat#(n!6220!6220s(X)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? activate#(Y) plus#(X, 0) >? U41#(isNat(X), X) plus#(X, 0) >? isNat#(X) plus#(X, s(Y)) >? U51#(isNat(Y), Y, X) plus#(X, s(Y)) >? isNat#(Y) x#(X, 0) >? isNat#(X) x#(X, s(Y)) >? isNat#(Y) activate#(n!6220!6220plus(X, Y)) >? plus#(activate(X), activate(Y)) activate#(n!6220!6220plus(X, Y)) >? activate#(X) activate#(n!6220!6220plus(X, Y)) >? activate#(Y) activate#(n!6220!6220s(X)) >? activate#(X) activate#(n!6220!6220x(X, Y)) >? x#(activate(X), activate(Y)) activate#(n!6220!6220x(X, Y)) >? activate#(X) activate#(n!6220!6220x(X, Y)) >? activate#(Y) U11(tt, X) >= U12(isNat(activate(X))) U12(tt) >= tt U21(tt) >= tt U31(tt, X) >= U32(isNat(activate(X))) U32(tt) >= tt U41(tt, X) >= activate(X) U51(tt, X, Y) >= U52(isNat(activate(Y)), activate(X), activate(Y)) U52(tt, X, Y) >= s(plus(activate(Y), activate(X))) U61(tt) >= 0 U71(tt, X, Y) >= U72(isNat(activate(Y)), activate(X), activate(Y)) U72(tt, X, Y) >= plus(x(activate(Y), activate(X)), activate(Y)) isNat(n!6220!62200) >= tt isNat(n!6220!6220plus(X, Y)) >= U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) >= U21(isNat(activate(X))) isNat(n!6220!6220x(X, Y)) >= U31(isNat(activate(X)), activate(Y)) plus(X, 0) >= U41(isNat(X), X) plus(X, s(Y)) >= U51(isNat(Y), Y, X) x(X, 0) >= U61(isNat(X)) x(X, s(Y)) >= U71(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(activate(X), activate(Y)) activate(n!6220!6220s(X)) >= s(activate(X)) activate(n!6220!6220x(X, Y)) >= x(activate(X), activate(Y)) activate(X) >= X Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.) We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[U11(x_1, x_2)]] = _|_ [[U12(x_1)]] = x_1 [[U21(x_1)]] = _|_ [[U31(x_1, x_2)]] = x_1 [[U32(x_1)]] = _|_ [[U61(x_1)]] = U61 [[activate(x_1)]] = x_1 [[isNat(x_1)]] = _|_ [[tt]] = _|_ We choose Lex = {} and Mul = {0, U11#, U41, U41#, U51, U51#, U52, U61, U71, U72, activate#, isNat#, n!6220!62200, n!6220!6220plus, n!6220!6220s, n!6220!6220x, plus, plus#, s, x, x#}, and the following precedence: U71 = U72 = n!6220!6220x = x = x# > U41 = U51 = U52 = n!6220!6220plus = plus > n!6220!6220s = s > U11# = U41# = U51# = activate# = isNat# = plus# > 0 = U61 = n!6220!62200 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11#(_|_, X) >= isNat#(X) U11#(_|_, X) >= activate#(X) U41#(_|_, X) > activate#(X) U51#(_|_, X, Y) >= isNat#(Y) U51#(_|_, X, Y) >= activate#(Y) U51#(_|_, X, Y) >= activate#(X) U51#(_|_, X, Y) >= activate#(Y) isNat#(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) isNat#(n!6220!6220plus(X, Y)) >= activate#(X) isNat#(n!6220!6220s(X)) >= isNat#(X) isNat#(n!6220!6220s(X)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) >= isNat#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(Y) plus#(X, 0) >= U41#(_|_, X) plus#(X, 0) >= isNat#(X) plus#(X, s(Y)) >= U51#(_|_, Y, X) plus#(X, s(Y)) >= isNat#(Y) x#(X, 0) >= isNat#(X) x#(X, s(Y)) >= isNat#(Y) activate#(n!6220!6220plus(X, Y)) >= plus#(X, Y) activate#(n!6220!6220plus(X, Y)) >= activate#(X) activate#(n!6220!6220plus(X, Y)) >= activate#(Y) activate#(n!6220!6220s(X)) >= activate#(X) activate#(n!6220!6220x(X, Y)) >= x#(X, Y) activate#(n!6220!6220x(X, Y)) >= activate#(X) activate#(n!6220!6220x(X, Y)) >= activate#(Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ U41(_|_, X) >= X U51(_|_, X, Y) >= U52(_|_, X, Y) U52(_|_, X, Y) >= s(plus(Y, X)) U61 >= 0 U71(_|_, X, Y) >= U72(_|_, X, Y) U72(_|_, X, Y) >= plus(x(Y, X), Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ plus(X, 0) >= U41(_|_, X) plus(X, s(Y)) >= U51(_|_, Y, X) x(X, 0) >= U61 x(X, s(Y)) >= U71(_|_, Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) n!6220!62200 >= 0 n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220s(X) >= s(X) n!6220!6220x(X, Y) >= x(X, Y) X >= X With these choices, we have: 1] U11#(_|_, X) >= isNat#(X) because [2], by (Star) 2] U11#*(_|_, X) >= isNat#(X) because U11# = isNat#, U11# in Mul and [3], by (Stat) 3] X >= X by (Meta) 4] U11#(_|_, X) >= activate#(X) because [5], by (Star) 5] U11#*(_|_, X) >= activate#(X) because U11# = activate#, U11# in Mul and [3], by (Stat) 6] U41#(_|_, X) > activate#(X) because [7], by definition 7] U41#*(_|_, X) >= activate#(X) because U41# = activate#, U41# in Mul and [8], by (Stat) 8] X >= X by (Meta) 9] U51#(_|_, X, Y) >= isNat#(Y) because [10], by (Star) 10] U51#*(_|_, X, Y) >= isNat#(Y) because U51# = isNat#, U51# in Mul and [11], by (Stat) 11] Y >= Y by (Meta) 12] U51#(_|_, X, Y) >= activate#(Y) because [13], by (Star) 13] U51#*(_|_, X, Y) >= activate#(Y) because U51# = activate#, U51# in Mul and [11], by (Stat) 14] U51#(_|_, X, Y) >= activate#(X) because [15], by (Star) 15] U51#*(_|_, X, Y) >= activate#(X) because U51# = activate#, U51# in Mul and [16], by (Stat) 16] X >= X by (Meta) 17] U51#(_|_, X, Y) >= activate#(Y) because [13], by (Star) 18] isNat#(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because [19], by (Star) 19] isNat#*(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because isNat# = U11#, isNat# in Mul, [20] and [22], by (Stat) 20] n!6220!6220plus(X, Y) > _|_ because [21], by definition 21] n!6220!6220plus*(X, Y) >= _|_ by (Bot) 22] n!6220!6220plus(X, Y) > Y because [23], by definition 23] n!6220!6220plus*(X, Y) >= Y because [3], by (Select) 24] isNat#(n!6220!6220plus(X, Y)) >= activate#(X) because isNat# = activate#, isNat# in Mul and [25], by (Fun) 25] n!6220!6220plus(X, Y) >= X because [26], by (Star) 26] n!6220!6220plus*(X, Y) >= X because [27], by (Select) 27] X >= X by (Meta) 28] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [29], by (Fun) 29] n!6220!6220s(X) >= X because [30], by (Star) 30] n!6220!6220s*(X) >= X because [27], by (Select) 31] isNat#(n!6220!6220s(X)) >= activate#(X) because isNat# = activate#, isNat# in Mul and [29], by (Fun) 32] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because isNat# in Mul and [33], by (Fun) 33] n!6220!6220x(X, Y) >= X because [34], by (Star) 34] n!6220!6220x*(X, Y) >= X because [27], by (Select) 35] isNat#(n!6220!6220x(X, Y)) >= activate#(X) because isNat# = activate#, isNat# in Mul and [33], by (Fun) 36] isNat#(n!6220!6220x(X, Y)) >= activate#(Y) because isNat# = activate#, isNat# in Mul and [37], by (Fun) 37] n!6220!6220x(X, Y) >= Y because [38], by (Star) 38] n!6220!6220x*(X, Y) >= Y because [3], by (Select) 39] plus#(X, 0) >= U41#(_|_, X) because [40], by (Star) 40] plus#*(X, 0) >= U41#(_|_, X) because plus# = U41#, plus# in Mul, [11] and [41], by (Stat) 41] 0 > _|_ because [42], by definition 42] 0* >= _|_ by (Bot) 43] plus#(X, 0) >= isNat#(X) because [44], by (Star) 44] plus#*(X, 0) >= isNat#(X) because plus# = isNat#, plus# in Mul and [11], by (Stat) 45] plus#(X, s(Y)) >= U51#(_|_, Y, X) because [46], by (Star) 46] plus#*(X, s(Y)) >= U51#(_|_, Y, X) because plus# = U51#, plus# in Mul, [11], [47] and [49], by (Stat) 47] s(Y) > _|_ because [48], by definition 48] s*(Y) >= _|_ by (Bot) 49] s(Y) > Y because [50], by definition 50] s*(Y) >= Y because [16], by (Select) 51] plus#(X, s(Y)) >= isNat#(Y) because [52], by (Star) 52] plus#*(X, s(Y)) >= isNat#(Y) because plus# = isNat#, plus# in Mul and [49], by (Stat) 53] x#(X, 0) >= isNat#(X) because [54], by (Star) 54] x#*(X, 0) >= isNat#(X) because x# > isNat# and [55], by (Copy) 55] x#*(X, 0) >= X because [11], by (Select) 56] x#(X, s(Y)) >= isNat#(Y) because [57], by (Star) 57] x#*(X, s(Y)) >= isNat#(Y) because [58], by (Select) 58] s(Y) >= isNat#(Y) because [59], by (Star) 59] s*(Y) >= isNat#(Y) because s > isNat# and [50], by (Copy) 60] activate#(n!6220!6220plus(X, Y)) >= plus#(X, Y) because [61], by (Star) 61] activate#*(n!6220!6220plus(X, Y)) >= plus#(X, Y) because activate# = plus#, activate# in Mul, [62] and [65], by (Stat) 62] n!6220!6220plus(X, Y) > X because [63], by definition 63] n!6220!6220plus*(X, Y) >= X because [64], by (Select) 64] X >= X by (Meta) 65] n!6220!6220plus(X, Y) > Y because [66], by definition 66] n!6220!6220plus*(X, Y) >= Y because [67], by (Select) 67] Y >= Y by (Meta) 68] activate#(n!6220!6220plus(X, Y)) >= activate#(X) because activate# in Mul and [69], by (Fun) 69] n!6220!6220plus(X, Y) >= X because [63], by (Star) 70] activate#(n!6220!6220plus(X, Y)) >= activate#(Y) because activate# in Mul and [71], by (Fun) 71] n!6220!6220plus(X, Y) >= Y because [66], by (Star) 72] activate#(n!6220!6220s(X)) >= activate#(X) because activate# in Mul and [73], by (Fun) 73] n!6220!6220s(X) >= X because [74], by (Star) 74] n!6220!6220s*(X) >= X because [75], by (Select) 75] X >= X by (Meta) 76] activate#(n!6220!6220x(X, Y)) >= x#(X, Y) because [77], by (Star) 77] activate#*(n!6220!6220x(X, Y)) >= x#(X, Y) because [78], by (Select) 78] n!6220!6220x(X, Y) >= x#(X, Y) because n!6220!6220x = x#, n!6220!6220x in Mul, [79] and [80], by (Fun) 79] X >= X by (Meta) 80] Y >= Y by (Meta) 81] activate#(n!6220!6220x(X, Y)) >= activate#(X) because activate# in Mul and [82], by (Fun) 82] n!6220!6220x(X, Y) >= X because [83], by (Star) 83] n!6220!6220x*(X, Y) >= X because [79], by (Select) 84] activate#(n!6220!6220x(X, Y)) >= activate#(Y) because activate# in Mul and [85], by (Fun) 85] n!6220!6220x(X, Y) >= Y because [86], by (Star) 86] n!6220!6220x*(X, Y) >= Y because [80], by (Select) 87] _|_ >= _|_ by (Bot) 88] _|_ >= _|_ by (Bot) 89] _|_ >= _|_ by (Bot) 90] _|_ >= _|_ by (Bot) 91] _|_ >= _|_ by (Bot) 92] U41(_|_, X) >= X because [93], by (Star) 93] U41*(_|_, X) >= X because [11], by (Select) 94] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [95], [96] and [11], by (Fun) 95] _|_ >= _|_ by (Bot) 96] X >= X by (Meta) 97] U52(_|_, X, Y) >= s(plus(Y, X)) because [98], by (Star) 98] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [99], by (Copy) 99] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [96] and [11], by (Stat) 100] U61 >= 0 because U61 = 0, by (Fun) 101] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [95], [96] and [11], by (Fun) 102] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [103], by (Star) 103] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [104] and [105], by (Copy) 104] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [96] and [11], by (Stat) 105] U72*(_|_, X, Y) >= Y because [11], by (Select) 106] _|_ >= _|_ by (Bot) 107] _|_ >= _|_ by (Bot) 108] _|_ >= _|_ by (Bot) 109] _|_ >= _|_ by (Bot) 110] plus(X, 0) >= U41(_|_, X) because plus = U41, plus in Mul, [11] and [111], by (Fun) 111] 0 >= _|_ by (Bot) 112] plus(X, s(Y)) >= U51(_|_, Y, X) because [113], by (Star) 113] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [11], [47] and [49], by (Stat) 114] x(X, 0) >= U61 because [115], by (Star) 115] x*(X, 0) >= U61 because x > U61, by (Copy) 116] x(X, s(Y)) >= U71(_|_, Y, X) because [117], by (Star) 117] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [11], [47] and [49], by (Stat) 118] 0 >= n!6220!62200 because 0 = n!6220!62200, by (Fun) 119] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [79] and [80], by (Fun) 120] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [121], by (Fun) 121] X >= X by (Meta) 122] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [79] and [80], by (Fun) 123] n!6220!62200 >= 0 because n!6220!62200 = 0, by (Fun) 124] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [79] and [80], by (Fun) 125] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [126], by (Fun) 126] X >= X by (Meta) 127] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [79] and [80], by (Fun) 128] X >= X by (Meta) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_4, R_0, minimal, formative) by (P_5, R_0, minimal, formative), where P_5 consists of: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U51#(tt, X, Y) =#> isNat#(activate(Y)) U51#(tt, X, Y) =#> activate#(Y) U51#(tt, X, Y) =#> activate#(X) U51#(tt, X, Y) =#> activate#(Y) isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) =#> activate#(X) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) plus#(X, 0) =#> U41#(isNat(X), X) plus#(X, 0) =#> isNat#(X) plus#(X, s(Y)) =#> U51#(isNat(Y), Y, X) plus#(X, s(Y)) =#> isNat#(Y) x#(X, 0) =#> isNat#(X) x#(X, s(Y)) =#> isNat#(Y) activate#(n!6220!6220plus(X, Y)) =#> plus#(activate(X), activate(Y)) activate#(n!6220!6220plus(X, Y)) =#> activate#(X) activate#(n!6220!6220plus(X, Y)) =#> activate#(Y) activate#(n!6220!6220s(X)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> x#(activate(X), activate(Y)) activate#(n!6220!6220x(X, Y)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> activate#(Y) 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 place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 6, 7, 8, 9, 10, 11, 12 * 1 : 19, 20, 21, 22, 23, 24, 25 * 2 : 6, 7, 8, 9, 10, 11, 12 * 3 : 19, 20, 21, 22, 23, 24, 25 * 4 : 19, 20, 21, 22, 23, 24, 25 * 5 : 19, 20, 21, 22, 23, 24, 25 * 6 : 0, 1 * 7 : 19, 20, 21, 22, 23, 24, 25 * 8 : 6, 7, 8, 9, 10, 11, 12 * 9 : 19, 20, 21, 22, 23, 24, 25 * 10 : 6, 7, 8, 9, 10, 11, 12 * 11 : 19, 20, 21, 22, 23, 24, 25 * 12 : 19, 20, 21, 22, 23, 24, 25 * 13 : * 14 : 6, 7, 8, 9, 10, 11, 12 * 15 : 2, 3, 4, 5 * 16 : 6, 7, 8, 9, 10, 11, 12 * 17 : 6, 7, 8, 9, 10, 11, 12 * 18 : 6, 7, 8, 9, 10, 11, 12 * 19 : 13, 14, 15, 16 * 20 : 19, 20, 21, 22, 23, 24, 25 * 21 : 19, 20, 21, 22, 23, 24, 25 * 22 : 19, 20, 21, 22, 23, 24, 25 * 23 : 17, 18 * 24 : 19, 20, 21, 22, 23, 24, 25 * 25 : 19, 20, 21, 22, 23, 24, 25 This graph has the following strongly connected components: P_6: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U51#(tt, X, Y) =#> isNat#(activate(Y)) U51#(tt, X, Y) =#> activate#(Y) U51#(tt, X, Y) =#> activate#(X) U51#(tt, X, Y) =#> activate#(Y) isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) =#> activate#(X) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) plus#(X, 0) =#> isNat#(X) plus#(X, s(Y)) =#> U51#(isNat(Y), Y, X) plus#(X, s(Y)) =#> isNat#(Y) x#(X, 0) =#> isNat#(X) x#(X, s(Y)) =#> isNat#(Y) activate#(n!6220!6220plus(X, Y)) =#> plus#(activate(X), activate(Y)) activate#(n!6220!6220plus(X, Y)) =#> activate#(X) activate#(n!6220!6220plus(X, Y)) =#> activate#(Y) activate#(n!6220!6220s(X)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> x#(activate(X), activate(Y)) activate#(n!6220!6220x(X, Y)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> activate#(Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_5, R_0, m, f) by (P_6, R_0, m, f). Thus, the original system is terminating if (P_6, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_6, 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: U11#(tt, X) >? isNat#(activate(X)) U11#(tt, X) >? activate#(X) U51#(tt, X, Y) >? isNat#(activate(Y)) U51#(tt, X, Y) >? activate#(Y) U51#(tt, X, Y) >? activate#(X) U51#(tt, X, Y) >? activate#(Y) isNat#(n!6220!6220plus(X, Y)) >? U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) >? activate#(X) isNat#(n!6220!6220s(X)) >? isNat#(activate(X)) isNat#(n!6220!6220s(X)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? activate#(Y) plus#(X, 0) >? isNat#(X) plus#(X, s(Y)) >? U51#(isNat(Y), Y, X) plus#(X, s(Y)) >? isNat#(Y) x#(X, 0) >? isNat#(X) x#(X, s(Y)) >? isNat#(Y) activate#(n!6220!6220plus(X, Y)) >? plus#(activate(X), activate(Y)) activate#(n!6220!6220plus(X, Y)) >? activate#(X) activate#(n!6220!6220plus(X, Y)) >? activate#(Y) activate#(n!6220!6220s(X)) >? activate#(X) activate#(n!6220!6220x(X, Y)) >? x#(activate(X), activate(Y)) activate#(n!6220!6220x(X, Y)) >? activate#(X) activate#(n!6220!6220x(X, Y)) >? activate#(Y) U11(tt, X) >= U12(isNat(activate(X))) U12(tt) >= tt U21(tt) >= tt U31(tt, X) >= U32(isNat(activate(X))) U32(tt) >= tt U41(tt, X) >= activate(X) U51(tt, X, Y) >= U52(isNat(activate(Y)), activate(X), activate(Y)) U52(tt, X, Y) >= s(plus(activate(Y), activate(X))) U61(tt) >= 0 U71(tt, X, Y) >= U72(isNat(activate(Y)), activate(X), activate(Y)) U72(tt, X, Y) >= plus(x(activate(Y), activate(X)), activate(Y)) isNat(n!6220!62200) >= tt isNat(n!6220!6220plus(X, Y)) >= U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) >= U21(isNat(activate(X))) isNat(n!6220!6220x(X, Y)) >= U31(isNat(activate(X)), activate(Y)) plus(X, 0) >= U41(isNat(X), X) plus(X, s(Y)) >= U51(isNat(Y), Y, X) x(X, 0) >= U61(isNat(X)) x(X, s(Y)) >= U71(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(activate(X), activate(Y)) activate(n!6220!6220s(X)) >= s(activate(X)) activate(n!6220!6220x(X, Y)) >= x(activate(X), activate(Y)) activate(X) >= X Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.) We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U11(x_1, x_2)]] = x_1 [[U11#(x_1, x_2)]] = U11#(x_2) [[U12(x_1)]] = x_1 [[U21(x_1)]] = x_1 [[U31(x_1, x_2)]] = x_1 [[U32(x_1)]] = x_1 [[U41(x_1, x_2)]] = x_2 [[U61(x_1)]] = _|_ [[activate(x_1)]] = x_1 [[isNat(x_1)]] = isNat [[n!6220!62200]] = _|_ We choose Lex = {} and Mul = {U11#, U51, U51#, U52, U71, U72, activate#, isNat, isNat#, n!6220!6220plus, n!6220!6220s, n!6220!6220x, plus, plus#, s, tt, x, x#}, and the following precedence: U71 = U72 = n!6220!6220x = x > U51 = U51# = U52 = n!6220!6220plus = plus = plus# > isNat = n!6220!6220s = s = tt > U11# = isNat# = x# > activate# Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11#(X) >= isNat#(X) U11#(X) >= activate#(X) U51#(tt, X, Y) >= isNat#(Y) U51#(tt, X, Y) >= activate#(Y) U51#(tt, X, Y) >= activate#(X) U51#(tt, X, Y) >= activate#(Y) isNat#(n!6220!6220plus(X, Y)) >= U11#(Y) isNat#(n!6220!6220plus(X, Y)) >= activate#(X) isNat#(n!6220!6220s(X)) >= isNat#(X) isNat#(n!6220!6220s(X)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) >= isNat#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(Y) plus#(X, _|_) >= isNat#(X) plus#(X, s(Y)) >= U51#(isNat, Y, X) plus#(X, s(Y)) >= isNat#(Y) x#(X, _|_) >= isNat#(X) x#(X, s(Y)) >= isNat#(Y) activate#(n!6220!6220plus(X, Y)) > plus#(X, Y) activate#(n!6220!6220plus(X, Y)) >= activate#(X) activate#(n!6220!6220plus(X, Y)) >= activate#(Y) activate#(n!6220!6220s(X)) >= activate#(X) activate#(n!6220!6220x(X, Y)) > x#(X, Y) activate#(n!6220!6220x(X, Y)) >= activate#(X) activate#(n!6220!6220x(X, Y)) >= activate#(Y) tt >= isNat tt >= tt tt >= tt tt >= isNat tt >= tt X >= X U51(tt, X, Y) >= U52(isNat, X, Y) U52(tt, X, Y) >= s(plus(Y, X)) _|_ >= _|_ U71(tt, X, Y) >= U72(isNat, X, Y) U72(tt, X, Y) >= plus(x(Y, X), Y) isNat >= tt isNat >= isNat isNat >= isNat isNat >= isNat plus(X, _|_) >= X plus(X, s(Y)) >= U51(isNat, Y, X) x(X, _|_) >= _|_ x(X, s(Y)) >= U71(isNat, Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220s(X) >= s(X) n!6220!6220x(X, Y) >= x(X, Y) X >= X With these choices, we have: 1] U11#(X) >= isNat#(X) because U11# = isNat#, U11# in Mul and [2], by (Fun) 2] X >= X by (Meta) 3] U11#(X) >= activate#(X) because [4], by (Star) 4] U11#*(X) >= activate#(X) because U11# > activate# and [5], by (Copy) 5] U11#*(X) >= X because [2], by (Select) 6] U51#(tt, X, Y) >= isNat#(Y) because [7], by (Star) 7] U51#*(tt, X, Y) >= isNat#(Y) because U51# > isNat# and [8], by (Copy) 8] U51#*(tt, X, Y) >= Y because [9], by (Select) 9] Y >= Y by (Meta) 10] U51#(tt, X, Y) >= activate#(Y) because [11], by (Star) 11] U51#*(tt, X, Y) >= activate#(Y) because U51# > activate# and [8], by (Copy) 12] U51#(tt, X, Y) >= activate#(X) because [13], by (Star) 13] U51#*(tt, X, Y) >= activate#(X) because U51# > activate# and [14], by (Copy) 14] U51#*(tt, X, Y) >= X because [15], by (Select) 15] X >= X by (Meta) 16] U51#(tt, X, Y) >= activate#(Y) because [11], by (Star) 17] isNat#(n!6220!6220plus(X, Y)) >= U11#(Y) because isNat# = U11#, isNat# in Mul and [18], by (Fun) 18] n!6220!6220plus(X, Y) >= Y because [19], by (Star) 19] n!6220!6220plus*(X, Y) >= Y because [2], by (Select) 20] isNat#(n!6220!6220plus(X, Y)) >= activate#(X) because [21], by (Star) 21] isNat#*(n!6220!6220plus(X, Y)) >= activate#(X) because isNat# > activate# and [22], by (Copy) 22] isNat#*(n!6220!6220plus(X, Y)) >= X because [23], by (Select) 23] n!6220!6220plus(X, Y) >= X because [24], by (Star) 24] n!6220!6220plus*(X, Y) >= X because [25], by (Select) 25] X >= X by (Meta) 26] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [27], by (Fun) 27] n!6220!6220s(X) >= X because [28], by (Star) 28] n!6220!6220s*(X) >= X because [25], by (Select) 29] isNat#(n!6220!6220s(X)) >= activate#(X) because [30], by (Star) 30] isNat#*(n!6220!6220s(X)) >= activate#(X) because [31], by (Select) 31] n!6220!6220s(X) >= activate#(X) because [32], by (Star) 32] n!6220!6220s*(X) >= activate#(X) because n!6220!6220s > activate# and [33], by (Copy) 33] n!6220!6220s*(X) >= X because [25], by (Select) 34] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because isNat# in Mul and [35], by (Fun) 35] n!6220!6220x(X, Y) >= X because [36], by (Star) 36] n!6220!6220x*(X, Y) >= X because [25], by (Select) 37] isNat#(n!6220!6220x(X, Y)) >= activate#(X) because [38], by (Star) 38] isNat#*(n!6220!6220x(X, Y)) >= activate#(X) because isNat# > activate# and [39], by (Copy) 39] isNat#*(n!6220!6220x(X, Y)) >= X because [35], by (Select) 40] isNat#(n!6220!6220x(X, Y)) >= activate#(Y) because [41], by (Star) 41] isNat#*(n!6220!6220x(X, Y)) >= activate#(Y) because isNat# > activate# and [42], by (Copy) 42] isNat#*(n!6220!6220x(X, Y)) >= Y because [43], by (Select) 43] n!6220!6220x(X, Y) >= Y because [44], by (Star) 44] n!6220!6220x*(X, Y) >= Y because [2], by (Select) 45] plus#(X, _|_) >= isNat#(X) because [46], by (Star) 46] plus#*(X, _|_) >= isNat#(X) because plus# > isNat# and [47], by (Copy) 47] plus#*(X, _|_) >= X because [9], by (Select) 48] plus#(X, s(Y)) >= U51#(isNat, Y, X) because [49], by (Star) 49] plus#*(X, s(Y)) >= U51#(isNat, Y, X) because plus# = U51#, plus# in Mul, [50], [51] and [53], by (Stat) 50] X >= X by (Meta) 51] s(Y) > isNat because [52], by definition 52] s*(Y) >= isNat because s = isNat and s in Mul, by (Stat) 53] s(Y) > Y because [54], by definition 54] s*(Y) >= Y because [15], by (Select) 55] plus#(X, s(Y)) >= isNat#(Y) because [56], by (Star) 56] plus#*(X, s(Y)) >= isNat#(Y) because [57], by (Select) 57] s(Y) >= isNat#(Y) because [58], by (Star) 58] s*(Y) >= isNat#(Y) because s > isNat# and [54], by (Copy) 59] x#(X, _|_) >= isNat#(X) because [60], by (Star) 60] x#*(X, _|_) >= isNat#(X) because x# = isNat#, x# in Mul and [50], by (Stat) 61] x#(X, s(Y)) >= isNat#(Y) because [62], by (Star) 62] x#*(X, s(Y)) >= isNat#(Y) because x# = isNat#, x# in Mul and [53], by (Stat) 63] activate#(n!6220!6220plus(X, Y)) > plus#(X, Y) because [64], by definition 64] activate#*(n!6220!6220plus(X, Y)) >= plus#(X, Y) because [65], by (Select) 65] n!6220!6220plus(X, Y) >= plus#(X, Y) because n!6220!6220plus = plus#, n!6220!6220plus in Mul, [66] and [67], by (Fun) 66] X >= X by (Meta) 67] Y >= Y by (Meta) 68] activate#(n!6220!6220plus(X, Y)) >= activate#(X) because [69], by (Star) 69] activate#*(n!6220!6220plus(X, Y)) >= activate#(X) because activate# in Mul and [70], by (Stat) 70] n!6220!6220plus(X, Y) > X because [71], by definition 71] n!6220!6220plus*(X, Y) >= X because [66], by (Select) 72] activate#(n!6220!6220plus(X, Y)) >= activate#(Y) because [73], by (Star) 73] activate#*(n!6220!6220plus(X, Y)) >= activate#(Y) because activate# in Mul and [74], by (Stat) 74] n!6220!6220plus(X, Y) > Y because [75], by definition 75] n!6220!6220plus*(X, Y) >= Y because [67], by (Select) 76] activate#(n!6220!6220s(X)) >= activate#(X) because activate# in Mul and [77], by (Fun) 77] n!6220!6220s(X) >= X because [78], by (Star) 78] n!6220!6220s*(X) >= X because [79], by (Select) 79] X >= X by (Meta) 80] activate#(n!6220!6220x(X, Y)) > x#(X, Y) because [81], by definition 81] activate#*(n!6220!6220x(X, Y)) >= x#(X, Y) because [82], by (Select) 82] n!6220!6220x(X, Y) >= x#(X, Y) because [83], by (Star) 83] n!6220!6220x*(X, Y) >= x#(X, Y) because n!6220!6220x > x#, [84] and [85], by (Copy) 84] n!6220!6220x*(X, Y) >= X because [66], by (Select) 85] n!6220!6220x*(X, Y) >= Y because [67], by (Select) 86] activate#(n!6220!6220x(X, Y)) >= activate#(X) because [87], by (Star) 87] activate#*(n!6220!6220x(X, Y)) >= activate#(X) because activate# in Mul and [88], by (Stat) 88] n!6220!6220x(X, Y) > X because [84], by definition 89] activate#(n!6220!6220x(X, Y)) >= activate#(Y) because activate# in Mul and [90], by (Fun) 90] n!6220!6220x(X, Y) >= Y because [85], by (Star) 91] tt >= isNat because tt = isNat, by (Fun) 92] tt >= tt by (Fun) 93] tt >= tt by (Fun) 94] tt >= isNat because tt = isNat, by (Fun) 95] tt >= tt by (Fun) 96] X >= X by (Meta) 97] U51(tt, X, Y) >= U52(isNat, X, Y) because U51 = U52, U51 in Mul, [98], [99] and [100], by (Fun) 98] tt >= isNat because tt = isNat, by (Fun) 99] X >= X by (Meta) 100] Y >= Y by (Meta) 101] U52(tt, X, Y) >= s(plus(Y, X)) because [102], by (Star) 102] U52*(tt, X, Y) >= s(plus(Y, X)) because U52 > s and [103], by (Copy) 103] U52*(tt, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [99] and [100], by (Stat) 104] _|_ >= _|_ by (Bot) 105] U71(tt, X, Y) >= U72(isNat, X, Y) because U71 = U72, U71 in Mul, [98], [99] and [100], by (Fun) 106] U72(tt, X, Y) >= plus(x(Y, X), Y) because [107], by (Star) 107] U72*(tt, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [108] and [109], by (Copy) 108] U72*(tt, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [99] and [100], by (Stat) 109] U72*(tt, X, Y) >= Y because [100], by (Select) 110] isNat >= tt because isNat = tt, by (Fun) 111] isNat >= isNat because isNat in Mul, by (Fun) 112] isNat >= isNat because isNat in Mul, by (Fun) 113] isNat >= isNat because isNat in Mul, by (Fun) 114] plus(X, _|_) >= X because [115], by (Star) 115] plus*(X, _|_) >= X because [100], by (Select) 116] plus(X, s(Y)) >= U51(isNat, Y, X) because [117], by (Star) 117] plus*(X, s(Y)) >= U51(isNat, Y, X) because plus = U51, plus in Mul, [100], [51] and [53], by (Stat) 118] x(X, _|_) >= _|_ by (Bot) 119] x(X, s(Y)) >= U71(isNat, Y, X) because [120], by (Star) 120] x*(X, s(Y)) >= U71(isNat, Y, X) because x = U71, x in Mul, [100], [51] and [53], by (Stat) 121] _|_ >= _|_ by (Bot) 122] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [66] and [67], by (Fun) 123] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [124], by (Fun) 124] X >= X by (Meta) 125] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [66] and [67], by (Fun) 126] _|_ >= _|_ by (Bot) 127] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [66] and [67], by (Fun) 128] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [129], by (Fun) 129] X >= X by (Meta) 130] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [66] and [67], by (Fun) 131] X >= X by (Meta) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_6, R_0, minimal, formative) by (P_7, R_0, minimal, formative), where P_7 consists of: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U51#(tt, X, Y) =#> isNat#(activate(Y)) U51#(tt, X, Y) =#> activate#(Y) U51#(tt, X, Y) =#> activate#(X) U51#(tt, X, Y) =#> activate#(Y) isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) =#> activate#(X) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) plus#(X, 0) =#> isNat#(X) plus#(X, s(Y)) =#> U51#(isNat(Y), Y, X) plus#(X, s(Y)) =#> isNat#(Y) x#(X, 0) =#> isNat#(X) x#(X, s(Y)) =#> isNat#(Y) activate#(n!6220!6220plus(X, Y)) =#> activate#(X) activate#(n!6220!6220plus(X, Y)) =#> activate#(Y) activate#(n!6220!6220s(X)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> activate#(Y) Thus, the original system is terminating if (P_7, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_7, 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 : 6, 7, 8, 9, 10, 11, 12 * 1 : 18, 19, 20, 21, 22 * 2 : 6, 7, 8, 9, 10, 11, 12 * 3 : 18, 19, 20, 21, 22 * 4 : 18, 19, 20, 21, 22 * 5 : 18, 19, 20, 21, 22 * 6 : 0, 1 * 7 : 18, 19, 20, 21, 22 * 8 : 6, 7, 8, 9, 10, 11, 12 * 9 : 18, 19, 20, 21, 22 * 10 : 6, 7, 8, 9, 10, 11, 12 * 11 : 18, 19, 20, 21, 22 * 12 : 18, 19, 20, 21, 22 * 13 : 6, 7, 8, 9, 10, 11, 12 * 14 : 2, 3, 4, 5 * 15 : 6, 7, 8, 9, 10, 11, 12 * 16 : 6, 7, 8, 9, 10, 11, 12 * 17 : 6, 7, 8, 9, 10, 11, 12 * 18 : 18, 19, 20, 21, 22 * 19 : 18, 19, 20, 21, 22 * 20 : 18, 19, 20, 21, 22 * 21 : 18, 19, 20, 21, 22 * 22 : 18, 19, 20, 21, 22 This graph has the following strongly connected components: P_8: U11#(tt, X) =#> isNat#(activate(X)) isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> isNat#(activate(X)) P_9: activate#(n!6220!6220plus(X, Y)) =#> activate#(X) activate#(n!6220!6220plus(X, Y)) =#> activate#(Y) activate#(n!6220!6220s(X)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> activate#(X) activate#(n!6220!6220x(X, Y)) =#> activate#(Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_7, R_0, m, f) by (P_8, R_0, m, f) and (P_9, R_0, m, f). Thus, the original system is terminating if each of (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(activate#) = 1 Thus, we can orient the dependency pairs as follows: nu(activate#(n!6220!6220plus(X, Y))) = n!6220!6220plus(X, Y) |> X = nu(activate#(X)) nu(activate#(n!6220!6220plus(X, Y))) = n!6220!6220plus(X, Y) |> Y = nu(activate#(Y)) nu(activate#(n!6220!6220s(X))) = n!6220!6220s(X) |> X = nu(activate#(X)) nu(activate#(n!6220!6220x(X, Y))) = n!6220!6220x(X, Y) |> X = nu(activate#(X)) nu(activate#(n!6220!6220x(X, Y))) = n!6220!6220x(X, Y) |> Y = nu(activate#(Y)) 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 (P_8, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_8, 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: U11#(tt, X) >? isNat#(activate(X)) isNat#(n!6220!6220plus(X, Y)) >? U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220s(X)) >? isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) >? isNat#(activate(X)) U11(tt, X) >= U12(isNat(activate(X))) U12(tt) >= tt U21(tt) >= tt U31(tt, X) >= U32(isNat(activate(X))) U32(tt) >= tt U41(tt, X) >= activate(X) U51(tt, X, Y) >= U52(isNat(activate(Y)), activate(X), activate(Y)) U52(tt, X, Y) >= s(plus(activate(Y), activate(X))) U61(tt) >= 0 U71(tt, X, Y) >= U72(isNat(activate(Y)), activate(X), activate(Y)) U72(tt, X, Y) >= plus(x(activate(Y), activate(X)), activate(Y)) isNat(n!6220!62200) >= tt isNat(n!6220!6220plus(X, Y)) >= U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) >= U21(isNat(activate(X))) isNat(n!6220!6220x(X, Y)) >= U31(isNat(activate(X)), activate(Y)) plus(X, 0) >= U41(isNat(X), X) plus(X, s(Y)) >= U51(isNat(Y), Y, X) x(X, 0) >= U61(isNat(X)) x(X, s(Y)) >= U71(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(activate(X), activate(Y)) activate(n!6220!6220s(X)) >= s(activate(X)) activate(n!6220!6220x(X, Y)) >= x(activate(X), activate(Y)) activate(X) >= X Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.) We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U11(x_1, x_2)]] = _|_ [[U11#(x_1, x_2)]] = U11#(x_2) [[U12(x_1)]] = _|_ [[U21(x_1)]] = _|_ [[U31(x_1, x_2)]] = _|_ [[U32(x_1)]] = _|_ [[U41(x_1, x_2)]] = U41(x_2) [[activate(x_1)]] = x_1 [[isNat(x_1)]] = _|_ [[n!6220!62200]] = _|_ [[tt]] = _|_ We choose Lex = {} and Mul = {U11#, U41, U51, U52, U61, U71, U72, isNat#, n!6220!6220plus, n!6220!6220s, n!6220!6220x, plus, s, x}, and the following precedence: U71 = U72 = n!6220!6220x = x > U61 > U51 = U52 = n!6220!6220plus = plus > U41 > U11# = isNat# > n!6220!6220s = s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11#(X) >= isNat#(X) isNat#(n!6220!6220plus(X, Y)) >= U11#(Y) isNat#(n!6220!6220s(X)) >= isNat#(X) isNat#(n!6220!6220x(X, Y)) > isNat#(X) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ U41(X) >= X U51(_|_, X, Y) >= U52(_|_, X, Y) U52(_|_, X, Y) >= s(plus(Y, X)) U61(_|_) >= _|_ U71(_|_, X, Y) >= U72(_|_, X, Y) U72(_|_, X, Y) >= plus(x(Y, X), Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ plus(X, _|_) >= U41(X) plus(X, s(Y)) >= U51(_|_, Y, X) x(X, _|_) >= U61(_|_) x(X, s(Y)) >= U71(_|_, Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220s(X) >= s(X) n!6220!6220x(X, Y) >= x(X, Y) X >= X With these choices, we have: 1] U11#(X) >= isNat#(X) because U11# = isNat#, U11# in Mul and [2], by (Fun) 2] X >= X by (Meta) 3] isNat#(n!6220!6220plus(X, Y)) >= U11#(Y) because isNat# = U11#, isNat# in Mul and [4], by (Fun) 4] n!6220!6220plus(X, Y) >= Y because [5], by (Star) 5] n!6220!6220plus*(X, Y) >= Y because [2], by (Select) 6] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [7], by (Fun) 7] n!6220!6220s(X) >= X because [8], by (Star) 8] n!6220!6220s*(X) >= X because [9], by (Select) 9] X >= X by (Meta) 10] isNat#(n!6220!6220x(X, Y)) > isNat#(X) because [11], by definition 11] isNat#*(n!6220!6220x(X, Y)) >= isNat#(X) because isNat# in Mul and [12], by (Stat) 12] n!6220!6220x(X, Y) > X because [13], by definition 13] n!6220!6220x*(X, Y) >= X because [9], by (Select) 14] _|_ >= _|_ by (Bot) 15] _|_ >= _|_ by (Bot) 16] _|_ >= _|_ by (Bot) 17] _|_ >= _|_ by (Bot) 18] _|_ >= _|_ by (Bot) 19] U41(X) >= X because [20], by (Star) 20] U41*(X) >= X because [21], by (Select) 21] X >= X by (Meta) 22] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [23], [24] and [25], by (Fun) 23] _|_ >= _|_ by (Bot) 24] X >= X by (Meta) 25] Y >= Y by (Meta) 26] U52(_|_, X, Y) >= s(plus(Y, X)) because [27], by (Star) 27] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [28], by (Copy) 28] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [24] and [25], by (Stat) 29] U61(_|_) >= _|_ by (Bot) 30] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [23], [24] and [25], by (Fun) 31] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [32], by (Star) 32] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [33] and [34], by (Copy) 33] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [24] and [25], by (Stat) 34] U72*(_|_, X, Y) >= Y because [25], by (Select) 35] _|_ >= _|_ by (Bot) 36] _|_ >= _|_ by (Bot) 37] _|_ >= _|_ by (Bot) 38] _|_ >= _|_ by (Bot) 39] plus(X, _|_) >= U41(X) because [40], by (Star) 40] plus*(X, _|_) >= U41(X) because plus > U41 and [41], by (Copy) 41] plus*(X, _|_) >= X because [25], by (Select) 42] plus(X, s(Y)) >= U51(_|_, Y, X) because [43], by (Star) 43] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [25], [44] and [46], by (Stat) 44] s(Y) > _|_ because [45], by definition 45] s*(Y) >= _|_ by (Bot) 46] s(Y) > Y because [47], by definition 47] s*(Y) >= Y because [24], by (Select) 48] x(X, _|_) >= U61(_|_) because [49], by (Star) 49] x*(X, _|_) >= U61(_|_) because x > U61 and [50], by (Copy) 50] x*(X, _|_) >= _|_ by (Bot) 51] x(X, s(Y)) >= U71(_|_, Y, X) because [52], by (Star) 52] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [25], [44] and [46], by (Stat) 53] _|_ >= _|_ by (Bot) 54] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [55] and [56], by (Fun) 55] X >= X by (Meta) 56] Y >= Y by (Meta) 57] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [58], by (Fun) 58] X >= X by (Meta) 59] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [55] and [56], by (Fun) 60] _|_ >= _|_ by (Bot) 61] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [62] and [63], by (Fun) 62] X >= X by (Meta) 63] Y >= Y by (Meta) 64] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [65], by (Fun) 65] X >= X by (Meta) 66] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [62] and [63], by (Fun) 67] X >= X by (Meta) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_8, R_0, minimal, formative) by (P_10, R_0, minimal, formative), where P_10 consists of: U11#(tt, X) =#> isNat#(activate(X)) isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) Thus, the original system is terminating if (P_10, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_10, 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: U11#(tt, X) >? isNat#(activate(X)) isNat#(n!6220!6220plus(X, Y)) >? U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220s(X)) >? isNat#(activate(X)) U11(tt, X) >= U12(isNat(activate(X))) U12(tt) >= tt U21(tt) >= tt U31(tt, X) >= U32(isNat(activate(X))) U32(tt) >= tt U41(tt, X) >= activate(X) U51(tt, X, Y) >= U52(isNat(activate(Y)), activate(X), activate(Y)) U52(tt, X, Y) >= s(plus(activate(Y), activate(X))) U61(tt) >= 0 U71(tt, X, Y) >= U72(isNat(activate(Y)), activate(X), activate(Y)) U72(tt, X, Y) >= plus(x(activate(Y), activate(X)), activate(Y)) isNat(n!6220!62200) >= tt isNat(n!6220!6220plus(X, Y)) >= U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) >= U21(isNat(activate(X))) isNat(n!6220!6220x(X, Y)) >= U31(isNat(activate(X)), activate(Y)) plus(X, 0) >= U41(isNat(X), X) plus(X, s(Y)) >= U51(isNat(Y), Y, X) x(X, 0) >= U61(isNat(X)) x(X, s(Y)) >= U71(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(activate(X), activate(Y)) activate(n!6220!6220s(X)) >= s(activate(X)) activate(n!6220!6220x(X, Y)) >= x(activate(X), activate(Y)) activate(X) >= X Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.) We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U11(x_1, x_2)]] = _|_ [[U12(x_1)]] = x_1 [[U21(x_1)]] = _|_ [[U31(x_1, x_2)]] = x_1 [[U32(x_1)]] = _|_ [[U41(x_1, x_2)]] = x_2 [[U61(x_1)]] = _|_ [[activate(x_1)]] = x_1 [[isNat(x_1)]] = _|_ [[n!6220!62200]] = _|_ [[tt]] = _|_ We choose Lex = {} and Mul = {U11#, U51, U52, U71, U72, isNat#, n!6220!6220plus, n!6220!6220s, n!6220!6220x, plus, s, x}, and the following precedence: U71 = U72 = n!6220!6220x = x > U11# = U51 = U52 = n!6220!6220plus = plus > isNat# > n!6220!6220s = s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11#(_|_, X) > isNat#(X) isNat#(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) isNat#(n!6220!6220s(X)) >= isNat#(X) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ X >= X U51(_|_, X, Y) >= U52(_|_, X, Y) U52(_|_, X, Y) >= s(plus(Y, X)) _|_ >= _|_ U71(_|_, X, Y) >= U72(_|_, X, Y) U72(_|_, X, Y) >= plus(x(Y, X), Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ plus(X, _|_) >= X plus(X, s(Y)) >= U51(_|_, Y, X) x(X, _|_) >= _|_ x(X, s(Y)) >= U71(_|_, Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220s(X) >= s(X) n!6220!6220x(X, Y) >= x(X, Y) X >= X With these choices, we have: 1] U11#(_|_, X) > isNat#(X) because [2], by definition 2] U11#*(_|_, X) >= isNat#(X) because U11# > isNat# and [3], by (Copy) 3] U11#*(_|_, X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] isNat#(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because [6], by (Star) 6] isNat#*(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because [7], by (Select) 7] n!6220!6220plus(X, Y) >= U11#(_|_, Y) because n!6220!6220plus = U11#, n!6220!6220plus in Mul, [8] and [9], by (Fun) 8] X >= _|_ by (Bot) 9] Y >= Y by (Meta) 10] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [11], by (Fun) 11] n!6220!6220s(X) >= X because [12], by (Star) 12] n!6220!6220s*(X) >= X because [13], by (Select) 13] X >= X by (Meta) 14] _|_ >= _|_ by (Bot) 15] _|_ >= _|_ by (Bot) 16] _|_ >= _|_ by (Bot) 17] _|_ >= _|_ by (Bot) 18] _|_ >= _|_ by (Bot) 19] X >= X by (Meta) 20] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [21], [22] and [23], by (Fun) 21] _|_ >= _|_ by (Bot) 22] X >= X by (Meta) 23] Y >= Y by (Meta) 24] U52(_|_, X, Y) >= s(plus(Y, X)) because [25], by (Star) 25] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [26], by (Copy) 26] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [22] and [23], by (Stat) 27] _|_ >= _|_ by (Bot) 28] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [21], [22] and [23], by (Fun) 29] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [30], by (Star) 30] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [31] and [32], by (Copy) 31] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [22] and [23], by (Stat) 32] U72*(_|_, X, Y) >= Y because [23], by (Select) 33] _|_ >= _|_ by (Bot) 34] _|_ >= _|_ by (Bot) 35] _|_ >= _|_ by (Bot) 36] _|_ >= _|_ by (Bot) 37] plus(X, _|_) >= X because [38], by (Star) 38] plus*(X, _|_) >= X because [23], by (Select) 39] plus(X, s(Y)) >= U51(_|_, Y, X) because [40], by (Star) 40] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [23], [41] and [43], by (Stat) 41] s(Y) > _|_ because [42], by definition 42] s*(Y) >= _|_ by (Bot) 43] s(Y) > Y because [44], by definition 44] s*(Y) >= Y because [22], by (Select) 45] x(X, _|_) >= _|_ by (Bot) 46] x(X, s(Y)) >= U71(_|_, Y, X) because [47], by (Star) 47] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [23], [41] and [43], by (Stat) 48] _|_ >= _|_ by (Bot) 49] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [50] and [51], by (Fun) 50] X >= X by (Meta) 51] Y >= Y by (Meta) 52] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [53], by (Fun) 53] X >= X by (Meta) 54] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [50] and [51], by (Fun) 55] _|_ >= _|_ by (Bot) 56] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [57] and [58], by (Fun) 57] X >= X by (Meta) 58] Y >= Y by (Meta) 59] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [60], by (Fun) 60] X >= X by (Meta) 61] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [57] and [58], by (Fun) 62] X >= X by (Meta) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_10, R_0, minimal, formative) by (P_11, R_0, minimal, formative), where P_11 consists of: isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) Thus, the original system is terminating if (P_11, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_11, 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 : * 1 : 0, 1 This graph has the following strongly connected components: P_12: isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_11, R_0, m, f) by (P_12, R_0, m, f). Thus, the original system is terminating if (P_12, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_12, 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: isNat#(n!6220!6220s(X)) >? isNat#(activate(X)) U11(tt, X) >= U12(isNat(activate(X))) U12(tt) >= tt U21(tt) >= tt U31(tt, X) >= U32(isNat(activate(X))) U32(tt) >= tt U41(tt, X) >= activate(X) U51(tt, X, Y) >= U52(isNat(activate(Y)), activate(X), activate(Y)) U52(tt, X, Y) >= s(plus(activate(Y), activate(X))) U61(tt) >= 0 U71(tt, X, Y) >= U72(isNat(activate(Y)), activate(X), activate(Y)) U72(tt, X, Y) >= plus(x(activate(Y), activate(X)), activate(Y)) isNat(n!6220!62200) >= tt isNat(n!6220!6220plus(X, Y)) >= U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) >= U21(isNat(activate(X))) isNat(n!6220!6220x(X, Y)) >= U31(isNat(activate(X)), activate(Y)) plus(X, 0) >= U41(isNat(X), X) plus(X, s(Y)) >= U51(isNat(Y), Y, X) x(X, 0) >= U61(isNat(X)) x(X, s(Y)) >= U71(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(activate(X), activate(Y)) activate(n!6220!6220s(X)) >= s(activate(X)) activate(n!6220!6220x(X, Y)) >= x(activate(X), activate(Y)) activate(X) >= X Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.) We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U11(x_1, x_2)]] = x_1 [[U12(x_1)]] = x_1 [[U21(x_1)]] = _|_ [[U31(x_1, x_2)]] = _|_ [[U32(x_1)]] = x_1 [[U41(x_1, x_2)]] = U41(x_2) [[U61(x_1)]] = _|_ [[activate(x_1)]] = x_1 [[isNat(x_1)]] = _|_ [[isNat#(x_1)]] = x_1 [[n!6220!62200]] = _|_ [[tt]] = _|_ We choose Lex = {} and Mul = {U41, U51, U52, U71, U72, n!6220!6220plus, n!6220!6220s, n!6220!6220x, plus, s, x}, and the following precedence: U71 = U72 = n!6220!6220x = x > U41 = U51 = U52 = n!6220!6220plus = plus > n!6220!6220s = s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: n!6220!6220s(X) > X _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ U41(X) >= X U51(_|_, X, Y) >= U52(_|_, X, Y) U52(_|_, X, Y) >= s(plus(Y, X)) _|_ >= _|_ U71(_|_, X, Y) >= U72(_|_, X, Y) U72(_|_, X, Y) >= plus(x(Y, X), Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ plus(X, _|_) >= U41(X) plus(X, s(Y)) >= U51(_|_, Y, X) x(X, _|_) >= _|_ x(X, s(Y)) >= U71(_|_, Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220s(X) >= s(X) n!6220!6220x(X, Y) >= x(X, Y) X >= X With these choices, we have: 1] n!6220!6220s(X) > X because [2], by definition 2] n!6220!6220s*(X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] _|_ >= _|_ by (Bot) 5] _|_ >= _|_ by (Bot) 6] _|_ >= _|_ by (Bot) 7] _|_ >= _|_ by (Bot) 8] _|_ >= _|_ by (Bot) 9] U41(X) >= X because [10], by (Star) 10] U41*(X) >= X because [11], by (Select) 11] X >= X by (Meta) 12] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [13], [14] and [15], by (Fun) 13] _|_ >= _|_ by (Bot) 14] X >= X by (Meta) 15] Y >= Y by (Meta) 16] U52(_|_, X, Y) >= s(plus(Y, X)) because [17], by (Star) 17] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [18], by (Copy) 18] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [14] and [15], by (Stat) 19] _|_ >= _|_ by (Bot) 20] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [13], [14] and [15], by (Fun) 21] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [22], by (Star) 22] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [23] and [24], by (Copy) 23] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [14] and [15], by (Stat) 24] U72*(_|_, X, Y) >= Y because [15], by (Select) 25] _|_ >= _|_ by (Bot) 26] _|_ >= _|_ by (Bot) 27] _|_ >= _|_ by (Bot) 28] _|_ >= _|_ by (Bot) 29] plus(X, _|_) >= U41(X) because [30], by (Star) 30] plus*(X, _|_) >= U41(X) because plus = U41, plus in Mul and [15], by (Stat) 31] plus(X, s(Y)) >= U51(_|_, Y, X) because [32], by (Star) 32] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [15], [33] and [35], by (Stat) 33] s(Y) > _|_ because [34], by definition 34] s*(Y) >= _|_ by (Bot) 35] s(Y) > Y because [36], by definition 36] s*(Y) >= Y because [14], by (Select) 37] x(X, _|_) >= _|_ by (Bot) 38] x(X, s(Y)) >= U71(_|_, Y, X) because [39], by (Star) 39] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [15], [33] and [35], by (Stat) 40] _|_ >= _|_ by (Bot) 41] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [42] and [43], by (Fun) 42] X >= X by (Meta) 43] Y >= Y by (Meta) 44] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [45], by (Fun) 45] X >= X by (Meta) 46] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [42] and [43], by (Fun) 47] _|_ >= _|_ by (Bot) 48] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [49] and [50], by (Fun) 49] X >= X by (Meta) 50] Y >= Y by (Meta) 51] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [52], by (Fun) 52] X >= X by (Meta) 53] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [49] and [50], by (Fun) 54] X >= X by (Meta) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_12, R_0) by ({}, R_0). 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.