/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(X, Y) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220x(X, Y)) => x(X, 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#(X, Y) 48] activate#(n!6220!6220s(X)) =#> s#(X) 49] activate#(n!6220!6220x(X, Y)) =#> x#(X, 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(X, Y) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220x(X, Y)) => x(X, 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 * 3 : * 4 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 5 : 46, 47, 48, 49 * 6 : 46, 47, 48, 49 * 7 : 12, 13, 14, 15 * 8 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 9 : 46, 47, 48, 49 * 10 : 46, 47, 48, 49 * 11 : 46, 47, 48, 49 * 12 : * 13 : 38, 39, 40, 41 * 14 : 46, 47, 48, 49 * 15 : 46, 47, 48, 49 * 16 : * 17 : 22, 23, 24, 25, 26 * 18 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 19 : 46, 47, 48, 49 * 20 : 46, 47, 48, 49 * 21 : 46, 47, 48, 49 * 22 : 38, 39, 40, 41 * 23 : 42, 43, 44, 45 * 24 : 46, 47, 48, 49 * 25 : 46, 47, 48, 49 * 26 : 46, 47, 48, 49 * 27 : 0, 1, 2 * 28 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 29 : 46, 47, 48, 49 * 30 : 46, 47, 48, 49 * 31 : * 32 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 33 : 46, 47, 48, 49 * 34 : 3, 4, 5 * 35 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 * 36 : 46, 47, 48, 49 * 37 : 46, 47, 48, 49 * 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 : * 49 : 42, 43, 44, 45 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#(X, Y) activate#(n!6220!6220x(X, Y)) =#> x#(X, Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f). 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#(X, Y) activate#(n!6220!6220x(X, Y)) >? x#(X, 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, 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)]] = _|_ [[U32(x_1)]] = x_1 [[U41(x_1, x_2)]] = x_2 [[activate(x_1)]] = x_1 [[isNat(x_1)]] = _|_ [[n!6220!62200]] = _|_ [[tt]] = _|_ We choose Lex = {} and Mul = {U11#, U31#, U41#, U51, U51#, U52, U52#, U61, 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# > U51 = U52 = n!6220!6220plus = plus > U31# > n!6220!6220s = s > U11# > U41# = U51# = U52# = activate# = plus# > isNat# > U61 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!6220x(X, Y)) >= x#(X, Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ 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, _|_) >= 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 [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 [8], by (Star) 8] U31#*(_|_, X) >= isNat#(X) because U31# > isNat# and [9], by (Copy) 9] U31#*(_|_, X) >= X because [4], by (Select) 10] U31#(_|_, X) >= activate#(X) because [11], by (Star) 11] U31#*(_|_, X) >= activate#(X) because U31# > activate# and [9], by (Copy) 12] U41#(_|_, X) >= activate#(X) because [13], by (Star) 13] U41#*(_|_, X) >= activate#(X) because U41# = activate#, U41# in Mul and [14], by (Stat) 14] X >= X by (Meta) 15] U51#(_|_, X, Y) >= U52#(_|_, X, Y) because U51# = U52#, U51# in Mul, [16], [17] and [18], by (Fun) 16] _|_ >= _|_ by (Bot) 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# and [21], by (Copy) 21] U51#*(_|_, X, Y) >= Y because [18], by (Select) 22] U51#(_|_, X, Y) >= activate#(Y) because [23], by (Star) 23] U51#*(_|_, X, Y) >= activate#(Y) because U51# = activate#, U51# in Mul and [18], by (Stat) 24] U51#(_|_, X, Y) >= activate#(X) because [25], by (Star) 25] U51#*(_|_, X, Y) >= activate#(X) because U51# = activate#, U51# in Mul and [17], by (Stat) 26] U51#(_|_, X, Y) >= activate#(Y) because [23], by (Star) 27] U52#(_|_, X, Y) >= plus#(Y, X) because [28], by (Star) 28] U52#*(_|_, X, Y) >= plus#(Y, X) because U52# = plus#, U52# in Mul, [17] and [18], by (Stat) 29] U52#(_|_, X, Y) >= activate#(Y) because [30], by (Star) 30] U52#*(_|_, X, Y) >= activate#(Y) because U52# = activate#, U52# in Mul and [18], by (Stat) 31] U52#(_|_, X, Y) >= activate#(X) because [32], by (Star) 32] U52#*(_|_, X, Y) >= activate#(X) because U52# = activate#, U52# in Mul and [17], by (Stat) 33] U71#(_|_, X, Y) >= U72#(_|_, X, Y) because U71# = U72#, U71# in Mul, [16], [17] and [18], by (Fun) 34] U71#(_|_, X, Y) >= isNat#(Y) because [35], by (Star) 35] U71#*(_|_, X, Y) >= isNat#(Y) because U71# > isNat# and [36], by (Copy) 36] U71#*(_|_, X, Y) >= Y because [18], by (Select) 37] U71#(_|_, X, Y) >= activate#(Y) because [38], by (Star) 38] U71#*(_|_, X, Y) >= activate#(Y) because U71# > activate# and [36], by (Copy) 39] U71#(_|_, X, Y) >= activate#(X) because [40], by (Star) 40] U71#*(_|_, X, Y) >= activate#(X) because U71# > activate# and [41], by (Copy) 41] U71#*(_|_, X, Y) >= X because [17], by (Select) 42] U71#(_|_, X, Y) >= activate#(Y) because [38], by (Star) 43] U72#(_|_, X, Y) >= plus#(x(Y, X), Y) because [44], by (Star) 44] U72#*(_|_, X, Y) >= plus#(x(Y, X), Y) because U72# > plus#, [45] and [46], by (Copy) 45] U72#*(_|_, X, Y) >= x(Y, X) because U72# = x, U72# in Mul, [17] and [18], by (Stat) 46] U72#*(_|_, X, Y) >= Y because [18], by (Select) 47] U72#(_|_, X, Y) >= x#(Y, X) because [48], by (Star) 48] U72#*(_|_, X, Y) >= x#(Y, X) because U72# = x#, U72# in Mul, [17] and [18], by (Stat) 49] U72#(_|_, X, Y) >= activate#(Y) because [50], by (Star) 50] U72#*(_|_, X, Y) >= activate#(Y) because U72# > activate# and [46], by (Copy) 51] U72#(_|_, X, Y) >= activate#(X) because [52], by (Star) 52] U72#*(_|_, X, Y) >= activate#(X) because U72# > activate# and [53], by (Copy) 53] U72#*(_|_, X, Y) >= X because [17], by (Select) 54] U72#(_|_, X, Y) >= activate#(Y) because [50], by (Star) 55] isNat#(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because [56], by (Star) 56] isNat#*(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because [57], by (Select) 57] n!6220!6220plus(X, Y) >= U11#(_|_, Y) because [58], by (Star) 58] n!6220!6220plus*(X, Y) >= U11#(_|_, Y) because n!6220!6220plus > U11#, [59] and [60], by (Copy) 59] n!6220!6220plus*(X, Y) >= _|_ by (Bot) 60] n!6220!6220plus*(X, Y) >= Y because [4], by (Select) 61] isNat#(n!6220!6220plus(X, Y)) >= isNat#(X) because isNat# in Mul and [62], by (Fun) 62] n!6220!6220plus(X, Y) >= X because [63], by (Star) 63] n!6220!6220plus*(X, Y) >= X because [64], by (Select) 64] X >= X by (Meta) 65] isNat#(n!6220!6220plus(X, Y)) >= activate#(X) because [66], by (Star) 66] isNat#*(n!6220!6220plus(X, Y)) >= activate#(X) because [67], by (Select) 67] n!6220!6220plus(X, Y) >= activate#(X) because [68], by (Star) 68] n!6220!6220plus*(X, Y) >= activate#(X) because n!6220!6220plus > activate# and [69], by (Copy) 69] n!6220!6220plus*(X, Y) >= X because [64], by (Select) 70] isNat#(n!6220!6220plus(X, Y)) >= activate#(Y) because [71], by (Star) 71] isNat#*(n!6220!6220plus(X, Y)) >= activate#(Y) because [72], by (Select) 72] n!6220!6220plus(X, Y) >= activate#(Y) because [73], by (Star) 73] n!6220!6220plus*(X, Y) >= activate#(Y) because n!6220!6220plus > activate# and [60], by (Copy) 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 [64], by (Select) 77] isNat#(n!6220!6220s(X)) >= activate#(X) because [78], by (Star) 78] isNat#*(n!6220!6220s(X)) >= activate#(X) because [79], by (Select) 79] n!6220!6220s(X) >= activate#(X) because [80], by (Star) 80] n!6220!6220s*(X) >= activate#(X) because n!6220!6220s > activate# and [81], by (Copy) 81] n!6220!6220s*(X) >= X because [64], by (Select) 82] isNat#(n!6220!6220x(X, Y)) > U31#(_|_, Y) because [83], by definition 83] isNat#*(n!6220!6220x(X, Y)) >= U31#(_|_, Y) because [84], by (Select) 84] n!6220!6220x(X, Y) >= U31#(_|_, Y) because [85], by (Star) 85] n!6220!6220x*(X, Y) >= U31#(_|_, Y) because n!6220!6220x > U31#, [86] and [87], by (Copy) 86] n!6220!6220x*(X, Y) >= _|_ by (Bot) 87] n!6220!6220x*(X, Y) >= Y because [4], by (Select) 88] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because isNat# in Mul and [89], by (Fun) 89] n!6220!6220x(X, Y) >= X because [90], by (Star) 90] n!6220!6220x*(X, Y) >= X because [64], by (Select) 91] isNat#(n!6220!6220x(X, Y)) >= activate#(X) because [92], by (Star) 92] isNat#*(n!6220!6220x(X, Y)) >= activate#(X) because [93], by (Select) 93] n!6220!6220x(X, Y) >= activate#(X) because [94], by (Star) 94] n!6220!6220x*(X, Y) >= activate#(X) because n!6220!6220x > activate# and [95], by (Copy) 95] n!6220!6220x*(X, Y) >= X because [64], by (Select) 96] isNat#(n!6220!6220x(X, Y)) >= activate#(Y) because [97], by (Star) 97] isNat#*(n!6220!6220x(X, Y)) >= activate#(Y) because [98], by (Select) 98] n!6220!6220x(X, Y) >= activate#(Y) because [99], by (Star) 99] n!6220!6220x*(X, Y) >= activate#(Y) because n!6220!6220x > activate# and [87], by (Copy) 100] plus#(X, _|_) >= U41#(_|_, X) because plus# = U41#, plus# in Mul, [18] and [101], by (Fun) 101] _|_ >= _|_ by (Bot) 102] plus#(X, _|_) >= isNat#(X) because [103], by (Star) 103] plus#*(X, _|_) >= isNat#(X) because plus# > isNat# and [104], by (Copy) 104] plus#*(X, _|_) >= X because [18], by (Select) 105] plus#(X, s(Y)) > U51#(_|_, Y, X) because [106], by definition 106] plus#*(X, s(Y)) >= U51#(_|_, Y, X) because plus# = U51#, plus# in Mul, [18], [107] and [109], by (Stat) 107] s(Y) > _|_ because [108], by definition 108] s*(Y) >= _|_ by (Bot) 109] s(Y) > Y because [110], by definition 110] s*(Y) >= Y because [17], by (Select) 111] plus#(X, s(Y)) >= isNat#(Y) because [112], by (Star) 112] plus#*(X, s(Y)) >= isNat#(Y) because [113], by (Select) 113] s(Y) >= isNat#(Y) because [114], by (Star) 114] s*(Y) >= isNat#(Y) because s > isNat# and [110], by (Copy) 115] x#(X, _|_) >= isNat#(X) because [116], by (Star) 116] x#*(X, _|_) >= isNat#(X) because x# > isNat# and [117], by (Copy) 117] x#*(X, _|_) >= X because [18], by (Select) 118] x#(X, s(Y)) >= U71#(_|_, Y, X) because [119], by (Star) 119] x#*(X, s(Y)) >= U71#(_|_, Y, X) because x# = U71#, x# in Mul, [18], [107] and [109], by (Stat) 120] x#(X, s(Y)) >= isNat#(Y) because [121], by (Star) 121] x#*(X, s(Y)) >= isNat#(Y) because [113], by (Select) 122] activate#(n!6220!6220plus(X, Y)) > plus#(X, Y) because [123], by definition 123] activate#*(n!6220!6220plus(X, Y)) >= plus#(X, Y) because [124], by (Select) 124] n!6220!6220plus(X, Y) >= plus#(X, Y) because [125], by (Star) 125] n!6220!6220plus*(X, Y) >= plus#(X, Y) because n!6220!6220plus > plus#, [126] and [128], by (Copy) 126] n!6220!6220plus*(X, Y) >= X because [127], by (Select) 127] X >= X by (Meta) 128] n!6220!6220plus*(X, Y) >= Y because [129], by (Select) 129] Y >= Y by (Meta) 130] activate#(n!6220!6220x(X, Y)) >= x#(X, Y) because [131], by (Star) 131] activate#*(n!6220!6220x(X, Y)) >= x#(X, Y) because [132], by (Select) 132] n!6220!6220x(X, Y) >= x#(X, Y) because n!6220!6220x = x#, n!6220!6220x in Mul, [133] and [134], by (Fun) 133] X >= X by (Meta) 134] Y >= Y by (Meta) 135] _|_ >= _|_ by (Bot) 136] _|_ >= _|_ by (Bot) 137] _|_ >= _|_ by (Bot) 138] _|_ >= _|_ by (Bot) 139] _|_ >= _|_ by (Bot) 140] X >= X by (Meta) 141] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [16], [17] and [18], by (Fun) 142] U52(_|_, X, Y) >= s(plus(Y, X)) because [143], by (Star) 143] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [144], by (Copy) 144] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [17] and [18], by (Stat) 145] U61(_|_) >= _|_ by (Bot) 146] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [16], [17] and [18], by (Fun) 147] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [148], by (Star) 148] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [149] and [150], by (Copy) 149] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [17] and [18], by (Stat) 150] U72*(_|_, X, Y) >= Y because [140], by (Select) 151] _|_ >= _|_ by (Bot) 152] _|_ >= _|_ by (Bot) 153] _|_ >= _|_ by (Bot) 154] _|_ >= _|_ by (Bot) 155] plus(X, _|_) >= X because [156], by (Star) 156] plus*(X, _|_) >= X because [140], by (Select) 157] plus(X, s(Y)) >= U51(_|_, Y, X) because [158], by (Star) 158] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [18], [107] and [109], by (Stat) 159] x(X, _|_) >= U61(_|_) because [160], by (Star) 160] x*(X, _|_) >= U61(_|_) because x > U61 and [161], by (Copy) 161] x*(X, _|_) >= _|_ by (Bot) 162] x(X, s(Y)) >= U71(_|_, Y, X) because [163], by (Star) 163] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [18], [107] and [109], by (Stat) 164] _|_ >= _|_ by (Bot) 165] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [133] and [134], by (Fun) 166] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [167], by (Fun) 167] X >= X by (Meta) 168] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [133] and [134], by (Fun) 169] _|_ >= _|_ by (Bot) 170] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [133] and [134], by (Fun) 171] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [167], by (Fun) 172] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [133] and [134], by (Fun) 173] 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) 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)) =#> 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)) =#> 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!6220x(X, Y)) =#> x#(X, 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 place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 1 : 38 * 2 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 3 : 38 * 4 : 38 * 5 : 10, 11, 12 * 6 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 7 : 38 * 8 : 38 * 9 : 38 * 10 : 32, 33, 34 * 11 : 38 * 12 : 38 * 13 : 18, 19, 20, 21, 22 * 14 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 15 : 38 * 16 : 38 * 17 : 38 * 18 : 32, 33, 34 * 19 : 35, 36, 37 * 20 : 38 * 21 : 38 * 22 : 38 * 23 : 0, 1 * 24 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 25 : 38 * 26 : 38 * 27 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 28 : 38 * 29 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 30 : 38 * 31 : 38 * 32 : 4 * 33 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 34 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 35 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 36 : 13, 14, 15, 16, 17 * 37 : 23, 24, 25, 26, 27, 28, 29, 30, 31 * 38 : 35, 36, 37 This graph has the following strongly connected components: P_3: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U41#(tt, X) =#> 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)) =#> 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)) =#> 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!6220x(X, Y)) =#> x#(X, Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_2, R_0, m, f) by (P_3, R_0, m, f). 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 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) 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)) >? 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)) >? 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!6220x(X, Y)) >? x#(X, 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, 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)]] = x_1 [[U21(x_1)]] = x_1 [[U31(x_1, x_2)]] = _|_ [[U32(x_1)]] = 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#, U41#, U51, 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# > U51 = U52 = n!6220!6220plus = plus > n!6220!6220s = s > U11# = U41# = isNat# = plus# > 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) U41#(_|_, X) >= 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)) >= 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)) >= isNat#(Y) x#(X, _|_) >= isNat#(X) x#(X, s(Y)) >= U71#(_|_, Y, X) x#(X, s(Y)) >= isNat#(Y) activate#(n!6220!6220x(X, Y)) >= x#(X, 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 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] U41#(_|_, X) >= activate#(X) because [7], by (Star) 7] U41#*(_|_, X) >= activate#(X) because U41# > activate# and [8], by (Copy) 8] U41#*(_|_, X) >= X because [9], by (Select) 9] X >= X by (Meta) 10] U71#(_|_, X, Y) >= U72#(_|_, X, Y) because U71# = U72#, U71# in Mul, [11], [12] and [13], by (Fun) 11] _|_ >= _|_ by (Bot) 12] X >= X by (Meta) 13] Y >= Y by (Meta) 14] U71#(_|_, X, Y) >= isNat#(Y) because [15], by (Star) 15] U71#*(_|_, X, Y) >= isNat#(Y) because U71# > isNat# and [16], by (Copy) 16] U71#*(_|_, X, Y) >= Y because [13], by (Select) 17] U71#(_|_, X, Y) >= activate#(Y) because [18], by (Star) 18] U71#*(_|_, X, Y) >= activate#(Y) because U71# > activate# and [16], by (Copy) 19] U71#(_|_, X, Y) >= activate#(X) because [20], by (Star) 20] U71#*(_|_, X, Y) >= activate#(X) because U71# > activate# and [21], by (Copy) 21] U71#*(_|_, X, Y) >= X because [12], by (Select) 22] U71#(_|_, X, Y) >= activate#(Y) because [18], by (Star) 23] U72#(_|_, X, Y) >= plus#(x(Y, X), Y) because [24], by (Star) 24] U72#*(_|_, X, Y) >= plus#(x(Y, X), Y) because U72# > plus#, [25] and [26], by (Copy) 25] U72#*(_|_, X, Y) >= x(Y, X) because U72# = x, U72# in Mul, [12] and [13], by (Stat) 26] U72#*(_|_, X, Y) >= Y because [13], by (Select) 27] U72#(_|_, X, Y) >= x#(Y, X) because [28], by (Star) 28] U72#*(_|_, X, Y) >= x#(Y, X) because U72# = x#, U72# in Mul, [12] and [13], by (Stat) 29] U72#(_|_, X, Y) >= activate#(Y) because [30], by (Star) 30] U72#*(_|_, X, Y) >= activate#(Y) because U72# > activate# and [26], by (Copy) 31] U72#(_|_, X, Y) >= activate#(X) because [32], by (Star) 32] U72#*(_|_, X, Y) >= activate#(X) because U72# > activate# and [33], by (Copy) 33] U72#*(_|_, X, Y) >= X because [12], by (Select) 34] U72#(_|_, X, Y) > activate#(Y) because [35], by definition 35] U72#*(_|_, X, Y) >= activate#(Y) because U72# > activate# and [26], by (Copy) 36] isNat#(n!6220!6220plus(X, Y)) >= U11#(Y) because isNat# = U11#, isNat# in Mul and [37], by (Fun) 37] n!6220!6220plus(X, Y) >= Y because [38], by (Star) 38] n!6220!6220plus*(X, Y) >= Y because [2], by (Select) 39] isNat#(n!6220!6220plus(X, Y)) >= isNat#(X) because isNat# in Mul and [40], by (Fun) 40] n!6220!6220plus(X, Y) >= X because [41], by (Star) 41] n!6220!6220plus*(X, Y) >= X because [42], by (Select) 42] X >= X by (Meta) 43] isNat#(n!6220!6220plus(X, Y)) >= activate#(X) because [44], by (Star) 44] isNat#*(n!6220!6220plus(X, Y)) >= activate#(X) because isNat# > activate# and [45], by (Copy) 45] isNat#*(n!6220!6220plus(X, Y)) >= X because [40], by (Select) 46] isNat#(n!6220!6220plus(X, Y)) >= activate#(Y) because [47], by (Star) 47] isNat#*(n!6220!6220plus(X, Y)) >= activate#(Y) because isNat# > activate# and [48], by (Copy) 48] isNat#*(n!6220!6220plus(X, Y)) >= Y because [37], by (Select) 49] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [50], by (Fun) 50] n!6220!6220s(X) >= X because [51], by (Star) 51] n!6220!6220s*(X) >= X because [42], by (Select) 52] isNat#(n!6220!6220s(X)) >= activate#(X) because [53], by (Star) 53] isNat#*(n!6220!6220s(X)) >= activate#(X) because isNat# > activate# and [54], by (Copy) 54] isNat#*(n!6220!6220s(X)) >= X because [50], by (Select) 55] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because isNat# in Mul and [56], by (Fun) 56] n!6220!6220x(X, Y) >= X because [57], by (Star) 57] n!6220!6220x*(X, Y) >= X because [42], by (Select) 58] isNat#(n!6220!6220x(X, Y)) >= activate#(X) because [59], by (Star) 59] isNat#*(n!6220!6220x(X, Y)) >= activate#(X) because isNat# > activate# and [60], by (Copy) 60] isNat#*(n!6220!6220x(X, Y)) >= X because [56], by (Select) 61] isNat#(n!6220!6220x(X, Y)) >= activate#(Y) because [62], by (Star) 62] isNat#*(n!6220!6220x(X, Y)) >= activate#(Y) because isNat# > activate# and [63], by (Copy) 63] isNat#*(n!6220!6220x(X, Y)) >= Y because [64], by (Select) 64] n!6220!6220x(X, Y) >= Y because [65], by (Star) 65] n!6220!6220x*(X, Y) >= Y because [2], by (Select) 66] plus#(X, _|_) >= U41#(_|_, X) because plus# = U41#, plus# in Mul, [13] and [67], by (Fun) 67] _|_ >= _|_ by (Bot) 68] plus#(X, _|_) >= isNat#(X) because [69], by (Star) 69] plus#*(X, _|_) >= isNat#(X) because plus# = isNat#, plus# in Mul and [13], by (Stat) 70] plus#(X, s(Y)) >= isNat#(Y) because [71], by (Star) 71] plus#*(X, s(Y)) >= isNat#(Y) because plus# = isNat#, plus# in Mul and [72], by (Stat) 72] s(Y) > Y because [73], by definition 73] s*(Y) >= Y because [12], by (Select) 74] x#(X, _|_) >= isNat#(X) because [75], by (Star) 75] x#*(X, _|_) >= isNat#(X) because x# > isNat# and [76], by (Copy) 76] x#*(X, _|_) >= X because [13], by (Select) 77] x#(X, s(Y)) >= U71#(_|_, Y, X) because [78], by (Star) 78] x#*(X, s(Y)) >= U71#(_|_, Y, X) because x# = U71#, x# in Mul, [13], [79] and [72], by (Stat) 79] s(Y) > _|_ because [80], by definition 80] s*(Y) >= _|_ by (Bot) 81] x#(X, s(Y)) >= isNat#(Y) because [82], by (Star) 82] x#*(X, s(Y)) >= isNat#(Y) because x# > isNat# and [83], by (Copy) 83] x#*(X, s(Y)) >= Y because [84], by (Select) 84] s(Y) >= Y because [73], by (Star) 85] activate#(n!6220!6220x(X, Y)) >= x#(X, Y) because [86], by (Star) 86] activate#*(n!6220!6220x(X, Y)) >= x#(X, Y) because [87], by (Select) 87] n!6220!6220x(X, Y) >= x#(X, Y) because n!6220!6220x = x#, n!6220!6220x in Mul, [88] and [89], by (Fun) 88] X >= X by (Meta) 89] Y >= Y by (Meta) 90] _|_ >= _|_ by (Bot) 91] _|_ >= _|_ by (Bot) 92] _|_ >= _|_ by (Bot) 93] _|_ >= _|_ by (Bot) 94] _|_ >= _|_ by (Bot) 95] X >= X by (Meta) 96] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [11], [12] and [13], by (Fun) 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, [12] and [13], by (Stat) 100] _|_ >= _|_ by (Bot) 101] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [11], [12] and [13], 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, [12] and [13], by (Stat) 105] U72*(_|_, X, Y) >= Y because [95], by (Select) 106] _|_ >= _|_ by (Bot) 107] _|_ >= _|_ by (Bot) 108] _|_ >= _|_ by (Bot) 109] _|_ >= _|_ by (Bot) 110] plus(X, _|_) >= X because [111], by (Star) 111] plus*(X, _|_) >= X because [95], by (Select) 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, [13], [79] and [72], by (Stat) 114] x(X, _|_) >= _|_ by (Bot) 115] x(X, s(Y)) >= U71(_|_, Y, X) because [116], by (Star) 116] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [13], [79] and [72], by (Stat) 117] _|_ >= _|_ by (Bot) 118] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [88] and [89], by (Fun) 119] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [120], by (Fun) 120] X >= X by (Meta) 121] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [88] and [89], by (Fun) 122] _|_ >= _|_ by (Bot) 123] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [88] and [89], by (Fun) 124] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [120], by (Fun) 125] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [88] and [89], by (Fun) 126] 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_3, R_0, minimal, formative) by (P_4, R_0, minimal, formative), where P_4 consists of: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U41#(tt, X) =#> 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) 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)) =#> 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)) =#> 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!6220x(X, Y)) =#> x#(X, Y) Thus, the original system is terminating if (P_4, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_0, minimal, formative). We 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) 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) 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)) >? 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)) >? 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!6220x(X, Y)) >? x#(X, 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, 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 [[U61(x_1)]] = _|_ [[activate(x_1)]] = x_1 [[isNat(x_1)]] = _|_ [[n!6220!62200]] = _|_ [[tt]] = _|_ We choose Lex = {U11#, activate#, isNat#} and Mul = {U41, U41#, U51, U52, U71, U71#, U72, U72#, 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# > plus# > U41# > U11# = activate# = isNat# > U51 = U52 = n!6220!6220plus = plus > U41 > 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) U41#(_|_, X) >= 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) 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)) >= 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)) >= isNat#(Y) x#(X, _|_) >= isNat#(X) x#(X, s(Y)) >= U71#(_|_, Y, X) x#(X, s(Y)) >= isNat#(Y) activate#(n!6220!6220x(X, Y)) >= x#(X, Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ 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] U11#(_|_, X) >= isNat#(X) because U11# = isNat# and [2], by (Fun) 2] X >= X by (Meta) 3] U11#(_|_, X) >= activate#(X) because U11# = activate# and [2], by (Fun) 4] U41#(_|_, X) >= activate#(X) because [5], by (Star) 5] U41#*(_|_, X) >= activate#(X) because U41# > activate# and [6], by (Copy) 6] U41#*(_|_, X) >= X because [7], by (Select) 7] X >= X by (Meta) 8] U71#(_|_, X, Y) >= U72#(_|_, X, Y) because U71# = U72#, U71# in Mul, [9], [10] and [11], by (Fun) 9] _|_ >= _|_ by (Bot) 10] X >= X by (Meta) 11] Y >= Y by (Meta) 12] U71#(_|_, X, Y) >= isNat#(Y) because [13], by (Star) 13] U71#*(_|_, X, Y) >= isNat#(Y) because U71# > isNat# and [14], by (Copy) 14] U71#*(_|_, X, Y) >= Y because [11], by (Select) 15] U71#(_|_, X, Y) >= activate#(Y) because [16], by (Star) 16] U71#*(_|_, X, Y) >= activate#(Y) because U71# > activate# and [14], by (Copy) 17] U71#(_|_, X, Y) >= activate#(X) because [18], by (Star) 18] U71#*(_|_, X, Y) >= activate#(X) because U71# > activate# and [19], by (Copy) 19] U71#*(_|_, X, Y) >= X because [10], by (Select) 20] U71#(_|_, X, Y) >= activate#(Y) because [16], by (Star) 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, [10] and [11], by (Stat) 24] U72#*(_|_, X, Y) >= Y because [11], by (Select) 25] U72#(_|_, X, Y) >= x#(Y, X) because [26], by (Star) 26] U72#*(_|_, X, Y) >= x#(Y, X) because U72# = x#, U72# in Mul, [10] and [11], by (Stat) 27] U72#(_|_, X, Y) >= activate#(Y) because [28], by (Star) 28] U72#*(_|_, X, Y) >= activate#(Y) because U72# > activate# and [24], by (Copy) 29] U72#(_|_, X, Y) >= activate#(X) because [30], by (Star) 30] U72#*(_|_, X, Y) >= activate#(X) because U72# > activate# and [31], by (Copy) 31] U72#*(_|_, X, Y) >= X because [10], by (Select) 32] isNat#(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because isNat# = U11# and [33], by (Fun) 33] n!6220!6220plus(X, Y) >= Y because [34], by (Star) 34] n!6220!6220plus*(X, Y) >= Y because [2], by (Select) 35] isNat#(n!6220!6220plus(X, Y)) >= isNat#(X) because [36], by (Fun) 36] n!6220!6220plus(X, Y) >= X because [37], by (Star) 37] n!6220!6220plus*(X, Y) >= X because [38], by (Select) 38] X >= X by (Meta) 39] isNat#(n!6220!6220plus(X, Y)) >= activate#(X) because isNat# = activate# and [36], by (Fun) 40] isNat#(n!6220!6220plus(X, Y)) >= activate#(Y) because isNat# = activate# and [33], by (Fun) 41] isNat#(n!6220!6220s(X)) >= isNat#(X) because [42], by (Fun) 42] n!6220!6220s(X) >= X because [43], by (Star) 43] n!6220!6220s*(X) >= X because [38], by (Select) 44] isNat#(n!6220!6220s(X)) >= activate#(X) because isNat# = activate# and [42], by (Fun) 45] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because [46], by (Fun) 46] n!6220!6220x(X, Y) >= X because [47], by (Star) 47] n!6220!6220x*(X, Y) >= X because [38], by (Select) 48] isNat#(n!6220!6220x(X, Y)) >= activate#(X) because isNat# = activate# and [46], by (Fun) 49] isNat#(n!6220!6220x(X, Y)) >= activate#(Y) because isNat# = activate# and [50], by (Fun) 50] n!6220!6220x(X, Y) >= Y because [51], by (Star) 51] n!6220!6220x*(X, Y) >= Y because [2], by (Select) 52] plus#(X, _|_) >= U41#(_|_, X) because [53], by (Star) 53] plus#*(X, _|_) >= U41#(_|_, X) because plus# > U41#, [54] and [55], by (Copy) 54] plus#*(X, _|_) >= _|_ by (Bot) 55] plus#*(X, _|_) >= X because [11], by (Select) 56] plus#(X, _|_) > isNat#(X) because [57], by definition 57] plus#*(X, _|_) >= isNat#(X) because plus# > isNat# and [55], by (Copy) 58] plus#(X, s(Y)) >= isNat#(Y) because [59], by (Star) 59] plus#*(X, s(Y)) >= isNat#(Y) because plus# > isNat# and [60], by (Copy) 60] plus#*(X, s(Y)) >= Y because [61], by (Select) 61] s(Y) >= Y because [62], by (Star) 62] s*(Y) >= Y because [10], by (Select) 63] x#(X, _|_) >= isNat#(X) because [64], by (Star) 64] x#*(X, _|_) >= isNat#(X) because x# > isNat# and [65], by (Copy) 65] x#*(X, _|_) >= X because [11], by (Select) 66] x#(X, s(Y)) >= U71#(_|_, Y, X) because [67], by (Star) 67] x#*(X, s(Y)) >= U71#(_|_, Y, X) because x# = U71#, x# in Mul, [11], [68] and [70], by (Stat) 68] s(Y) > _|_ because [69], by definition 69] s*(Y) >= _|_ by (Bot) 70] s(Y) > Y because [71], by definition 71] s*(Y) >= Y because [10], by (Select) 72] x#(X, s(Y)) >= isNat#(Y) because [73], by (Star) 73] x#*(X, s(Y)) >= isNat#(Y) because x# > isNat# and [74], by (Copy) 74] x#*(X, s(Y)) >= Y because [61], by (Select) 75] activate#(n!6220!6220x(X, Y)) >= x#(X, Y) because [76], by (Star) 76] activate#*(n!6220!6220x(X, Y)) >= x#(X, Y) because [77], by (Select) 77] n!6220!6220x(X, Y) >= x#(X, Y) because n!6220!6220x = x#, n!6220!6220x in Mul, [78] and [79], by (Fun) 78] X >= X by (Meta) 79] Y >= Y by (Meta) 80] _|_ >= _|_ by (Bot) 81] _|_ >= _|_ by (Bot) 82] _|_ >= _|_ by (Bot) 83] _|_ >= _|_ by (Bot) 84] _|_ >= _|_ by (Bot) 85] U41(_|_, X) >= X because [86], by (Star) 86] U41*(_|_, X) >= X because [11], by (Select) 87] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [9], [10] and [11], by (Fun) 88] U52(_|_, X, Y) >= s(plus(Y, X)) because [89], by (Star) 89] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [90], by (Copy) 90] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [10] and [11], by (Stat) 91] _|_ >= _|_ by (Bot) 92] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [9], [10] and [11], by (Fun) 93] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [94], by (Star) 94] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [95] and [96], by (Copy) 95] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [10] and [11], by (Stat) 96] U72*(_|_, X, Y) >= Y because [11], by (Select) 97] _|_ >= _|_ by (Bot) 98] _|_ >= _|_ by (Bot) 99] _|_ >= _|_ by (Bot) 100] _|_ >= _|_ by (Bot) 101] plus(X, _|_) >= U41(_|_, X) because [102], by (Star) 102] plus*(X, _|_) >= U41(_|_, X) because plus > U41, [103] and [104], by (Copy) 103] plus*(X, _|_) >= _|_ by (Bot) 104] plus*(X, _|_) >= X because [11], by (Select) 105] plus(X, s(Y)) >= U51(_|_, Y, X) because [106], by (Star) 106] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [11], [68] and [70], by (Stat) 107] x(X, _|_) >= _|_ by (Bot) 108] x(X, s(Y)) >= U71(_|_, Y, X) because [109], by (Star) 109] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [11], [68] and [70], by (Stat) 110] _|_ >= _|_ by (Bot) 111] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [78] and [79], by (Fun) 112] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [113], by (Fun) 113] X >= X by (Meta) 114] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [78] and [79], by (Fun) 115] _|_ >= _|_ by (Bot) 116] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [78] and [79], by (Fun) 117] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [113], by (Fun) 118] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [78] and [79], by (Fun) 119] 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) U41#(tt, X) =#> 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) 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)) =#> 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, 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!6220x(X, Y)) =#> x#(X, 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 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) 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) 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)) >? 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, 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!6220x(X, Y)) >? x#(X, 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, 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)]] = _|_ [[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#, U41#, U51, 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# = U41# = isNat# = plus# > U51 = U52 = n!6220!6220plus = plus > n!6220!6220s = s > 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) U41#(_|_, X) > 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) 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)) >= isNat#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(Y) plus#(X, _|_) >= U41#(_|_, 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!6220x(X, Y)) >= x#(X, 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#, 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# and [6], by (Copy) 6] U11#*(_|_, X) >= X because [3], by (Select) 7] U41#(_|_, X) > activate#(X) because [8], by definition 8] U41#*(_|_, X) >= activate#(X) because U41# > activate# and [9], by (Copy) 9] U41#*(_|_, X) >= X because [10], by (Select) 10] X >= X by (Meta) 11] U71#(_|_, X, Y) >= U72#(_|_, X, Y) because U71# = U72#, U71# in Mul, [12], [13] and [14], by (Fun) 12] _|_ >= _|_ by (Bot) 13] X >= X by (Meta) 14] Y >= Y by (Meta) 15] U71#(_|_, X, Y) >= isNat#(Y) because [16], by (Star) 16] U71#*(_|_, X, Y) >= isNat#(Y) because U71# > isNat# and [17], by (Copy) 17] U71#*(_|_, X, Y) >= Y because [14], by (Select) 18] U71#(_|_, X, Y) >= activate#(Y) because [19], by (Star) 19] U71#*(_|_, X, Y) >= activate#(Y) because U71# > activate# and [17], by (Copy) 20] U71#(_|_, X, Y) >= activate#(X) because [21], by (Star) 21] U71#*(_|_, X, Y) >= activate#(X) because U71# > activate# and [22], by (Copy) 22] U71#*(_|_, X, Y) >= X because [13], by (Select) 23] U71#(_|_, X, Y) >= activate#(Y) because [19], by (Star) 24] U72#(_|_, X, Y) >= plus#(x(Y, X), Y) because [25], by (Star) 25] U72#*(_|_, X, Y) >= plus#(x(Y, X), Y) because U72# > plus#, [26] and [27], by (Copy) 26] U72#*(_|_, X, Y) >= x(Y, X) because U72# = x, U72# in Mul, [13] and [14], by (Stat) 27] U72#*(_|_, X, Y) >= Y because [14], by (Select) 28] U72#(_|_, X, Y) >= x#(Y, X) because [29], by (Star) 29] U72#*(_|_, X, Y) >= x#(Y, X) because U72# = x#, U72# in Mul, [13] and [14], by (Stat) 30] U72#(_|_, X, Y) >= activate#(Y) because [31], by (Star) 31] U72#*(_|_, X, Y) >= activate#(Y) because U72# > activate# and [27], by (Copy) 32] U72#(_|_, X, Y) >= activate#(X) because [33], by (Star) 33] U72#*(_|_, X, Y) >= activate#(X) because U72# > activate# and [34], by (Copy) 34] U72#*(_|_, X, Y) >= X because [13], by (Select) 35] isNat#(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because [36], by (Star) 36] isNat#*(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because isNat# = U11#, isNat# in Mul, [37] and [39], by (Stat) 37] n!6220!6220plus(X, Y) > _|_ because [38], by definition 38] n!6220!6220plus*(X, Y) >= _|_ by (Bot) 39] n!6220!6220plus(X, Y) > Y because [40], by definition 40] n!6220!6220plus*(X, Y) >= Y because [3], by (Select) 41] isNat#(n!6220!6220plus(X, Y)) >= isNat#(X) because isNat# in Mul and [42], by (Fun) 42] n!6220!6220plus(X, Y) >= X because [43], by (Star) 43] n!6220!6220plus*(X, Y) >= X because [44], by (Select) 44] X >= X by (Meta) 45] isNat#(n!6220!6220plus(X, Y)) >= activate#(X) because [46], by (Star) 46] isNat#*(n!6220!6220plus(X, Y)) >= activate#(X) because [47], by (Select) 47] n!6220!6220plus(X, Y) >= activate#(X) because [48], by (Star) 48] n!6220!6220plus*(X, Y) >= activate#(X) because n!6220!6220plus > activate# and [49], by (Copy) 49] n!6220!6220plus*(X, Y) >= X because [44], by (Select) 50] isNat#(n!6220!6220plus(X, Y)) >= activate#(Y) because [51], by (Star) 51] isNat#*(n!6220!6220plus(X, Y)) >= activate#(Y) because [52], by (Select) 52] n!6220!6220plus(X, Y) >= activate#(Y) because [53], by (Star) 53] n!6220!6220plus*(X, Y) >= activate#(Y) because n!6220!6220plus > activate# and [40], by (Copy) 54] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [55], by (Fun) 55] n!6220!6220s(X) >= X because [56], by (Star) 56] n!6220!6220s*(X) >= X because [44], by (Select) 57] isNat#(n!6220!6220s(X)) >= activate#(X) because [58], by (Star) 58] isNat#*(n!6220!6220s(X)) >= activate#(X) because isNat# > activate# and [59], by (Copy) 59] isNat#*(n!6220!6220s(X)) >= X because [55], by (Select) 60] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because isNat# in Mul and [61], by (Fun) 61] n!6220!6220x(X, Y) >= X because [62], by (Star) 62] n!6220!6220x*(X, Y) >= X because [44], by (Select) 63] isNat#(n!6220!6220x(X, Y)) >= activate#(X) because [64], by (Star) 64] isNat#*(n!6220!6220x(X, Y)) >= activate#(X) because isNat# > activate# and [65], by (Copy) 65] isNat#*(n!6220!6220x(X, Y)) >= X because [61], by (Select) 66] isNat#(n!6220!6220x(X, Y)) >= activate#(Y) because [67], by (Star) 67] isNat#*(n!6220!6220x(X, Y)) >= activate#(Y) because isNat# > activate# and [68], by (Copy) 68] isNat#*(n!6220!6220x(X, Y)) >= Y because [69], by (Select) 69] n!6220!6220x(X, Y) >= Y because [70], by (Star) 70] n!6220!6220x*(X, Y) >= Y because [3], by (Select) 71] plus#(X, _|_) >= U41#(_|_, X) because plus# = U41#, plus# in Mul, [14] and [72], by (Fun) 72] _|_ >= _|_ by (Bot) 73] plus#(X, s(Y)) >= isNat#(Y) because [74], by (Star) 74] plus#*(X, s(Y)) >= isNat#(Y) because plus# = isNat#, plus# in Mul and [75], by (Stat) 75] s(Y) > Y because [76], by definition 76] s*(Y) >= Y because [13], by (Select) 77] x#(X, _|_) >= isNat#(X) because [78], by (Star) 78] x#*(X, _|_) >= isNat#(X) because x# > isNat# and [79], by (Copy) 79] x#*(X, _|_) >= X because [14], by (Select) 80] x#(X, s(Y)) >= U71#(_|_, Y, X) because [81], by (Star) 81] x#*(X, s(Y)) >= U71#(_|_, Y, X) because x# = U71#, x# in Mul, [14], [82] and [75], by (Stat) 82] s(Y) > _|_ because [83], by definition 83] s*(Y) >= _|_ by (Bot) 84] x#(X, s(Y)) >= isNat#(Y) because [85], by (Star) 85] x#*(X, s(Y)) >= isNat#(Y) because x# > isNat# and [86], by (Copy) 86] x#*(X, s(Y)) >= Y because [87], by (Select) 87] s(Y) >= Y because [76], by (Star) 88] activate#(n!6220!6220x(X, Y)) >= x#(X, Y) because [89], by (Star) 89] activate#*(n!6220!6220x(X, Y)) >= x#(X, Y) because [90], by (Select) 90] n!6220!6220x(X, Y) >= x#(X, Y) because n!6220!6220x = x#, n!6220!6220x in Mul, [91] and [92], by (Fun) 91] X >= X by (Meta) 92] Y >= Y by (Meta) 93] _|_ >= _|_ by (Bot) 94] _|_ >= _|_ by (Bot) 95] _|_ >= _|_ by (Bot) 96] _|_ >= _|_ by (Bot) 97] _|_ >= _|_ by (Bot) 98] X >= X by (Meta) 99] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [12], [13] and [14], by (Fun) 100] U52(_|_, X, Y) >= s(plus(Y, X)) because [101], by (Star) 101] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [102], by (Copy) 102] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [13] and [14], by (Stat) 103] _|_ >= _|_ by (Bot) 104] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [12], [13] and [14], by (Fun) 105] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [106], by (Star) 106] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [107] and [108], by (Copy) 107] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [13] and [14], by (Stat) 108] U72*(_|_, X, Y) >= Y because [98], by (Select) 109] _|_ >= _|_ by (Bot) 110] _|_ >= _|_ by (Bot) 111] _|_ >= _|_ by (Bot) 112] _|_ >= _|_ by (Bot) 113] plus(X, _|_) >= X because [114], by (Star) 114] plus*(X, _|_) >= X because [98], by (Select) 115] plus(X, s(Y)) >= U51(_|_, Y, X) because [116], by (Star) 116] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [14], [82] and [75], by (Stat) 117] x(X, _|_) >= _|_ by (Bot) 118] x(X, s(Y)) >= U71(_|_, Y, X) because [119], by (Star) 119] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [14], [82] and [75], by (Stat) 120] _|_ >= _|_ by (Bot) 121] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [91] and [92], by (Fun) 122] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [123], by (Fun) 123] X >= X by (Meta) 124] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [91] and [92], by (Fun) 125] _|_ >= _|_ by (Bot) 126] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [91] and [92], by (Fun) 127] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [123], by (Fun) 128] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [91] and [92], by (Fun) 129] 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_5, R_0, minimal, formative) by (P_6, R_0, minimal, formative), where P_6 consists of: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> 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) 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)) =#> 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, 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!6220x(X, Y)) =#> x#(X, Y) 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 place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 11, 12, 13, 14, 15, 16, 17, 18, 19 * 1 : 25 * 2 : 7, 8, 9, 10 * 3 : 11, 12, 13, 14, 15, 16, 17, 18, 19 * 4 : 25 * 5 : 25 * 6 : 25 * 7 : 20, 21 * 8 : 22, 23, 24 * 9 : 25 * 10 : 25 * 11 : 0, 1 * 12 : 11, 12, 13, 14, 15, 16, 17, 18, 19 * 13 : 25 * 14 : 25 * 15 : 11, 12, 13, 14, 15, 16, 17, 18, 19 * 16 : 25 * 17 : 11, 12, 13, 14, 15, 16, 17, 18, 19 * 18 : 25 * 19 : 25 * 20 : * 21 : 11, 12, 13, 14, 15, 16, 17, 18, 19 * 22 : 11, 12, 13, 14, 15, 16, 17, 18, 19 * 23 : 2, 3, 4, 5, 6 * 24 : 11, 12, 13, 14, 15, 16, 17, 18, 19 * 25 : 22, 23, 24 This graph has the following strongly connected components: P_7: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> 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) 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)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) 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!6220x(X, Y)) =#> x#(X, Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_6, R_0, m, f) by (P_7, R_0, m, f). 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 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) 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) 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)) >? isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? activate#(Y) 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!6220x(X, Y)) >? x#(X, 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, 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)]] = _|_ [[U21(x_1)]] = 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]] = _|_ [[plus#(x_1, x_2)]] = plus#(x_2) [[tt]] = _|_ We choose Lex = {} and Mul = {U11#, U41, U51, U52, U61, 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 = U72 = n!6220!6220x = x > U11# = U71# = U72# = activate# = isNat# = plus# = x# > U51 = U52 = n!6220!6220plus = plus > U41 > n!6220!6220s = s > U61 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) 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#(Y) U72#(_|_, X, Y) >= x#(Y, X) U72#(_|_, X, Y) >= activate#(Y) U72#(_|_, X, Y) >= activate#(X) 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)) >= isNat#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(Y) plus#(s(X)) >= isNat#(X) x#(X, _|_) >= isNat#(X) x#(X, s(Y)) >= U71#(_|_, Y, X) x#(X, s(Y)) >= isNat#(Y) activate#(n!6220!6220x(X, Y)) >= x#(X, Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ 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 [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] U71#(_|_, X, Y) >= U72#(_|_, X, Y) because U71# = U72#, U71# in Mul, [7], [8] and [9], by (Fun) 7] _|_ >= _|_ by (Bot) 8] X >= X by (Meta) 9] Y >= Y by (Meta) 10] U71#(_|_, X, Y) >= isNat#(Y) because [11], by (Star) 11] U71#*(_|_, X, Y) >= isNat#(Y) because U71# = isNat#, U71# in Mul and [9], by (Stat) 12] U71#(_|_, X, Y) >= activate#(Y) because [13], by (Star) 13] U71#*(_|_, X, Y) >= activate#(Y) because U71# = activate#, U71# in Mul and [9], by (Stat) 14] U71#(_|_, X, Y) >= activate#(X) because [15], by (Star) 15] U71#*(_|_, X, Y) >= activate#(X) because U71# = activate#, U71# in Mul and [8], by (Stat) 16] U71#(_|_, X, Y) >= activate#(Y) because [13], by (Star) 17] U72#(_|_, X, Y) >= plus#(Y) because [18], by (Star) 18] U72#*(_|_, X, Y) >= plus#(Y) because U72# = plus#, U72# in Mul and [9], by (Stat) 19] U72#(_|_, X, Y) >= x#(Y, X) because [20], by (Star) 20] U72#*(_|_, X, Y) >= x#(Y, X) because U72# = x#, U72# in Mul, [8] and [9], by (Stat) 21] U72#(_|_, X, Y) >= activate#(Y) because [22], by (Star) 22] U72#*(_|_, X, Y) >= activate#(Y) because U72# = activate#, U72# in Mul and [9], by (Stat) 23] U72#(_|_, X, Y) >= activate#(X) because [24], by (Star) 24] U72#*(_|_, X, Y) >= activate#(X) because U72# = activate#, U72# in Mul and [8], by (Stat) 25] isNat#(n!6220!6220plus(X, Y)) > U11#(_|_, Y) because [26], by definition 26] isNat#*(n!6220!6220plus(X, Y)) >= U11#(_|_, Y) because isNat# = U11#, isNat# in Mul, [27] and [29], by (Stat) 27] n!6220!6220plus(X, Y) > _|_ because [28], by definition 28] n!6220!6220plus*(X, Y) >= _|_ by (Bot) 29] n!6220!6220plus(X, Y) > Y because [30], by definition 30] n!6220!6220plus*(X, Y) >= Y because [3], by (Select) 31] isNat#(n!6220!6220plus(X, Y)) >= isNat#(X) because isNat# in Mul and [32], by (Fun) 32] n!6220!6220plus(X, Y) >= X because [33], by (Star) 33] n!6220!6220plus*(X, Y) >= X because [34], by (Select) 34] X >= X by (Meta) 35] isNat#(n!6220!6220plus(X, Y)) >= activate#(X) because isNat# = activate#, isNat# in Mul and [32], by (Fun) 36] isNat#(n!6220!6220plus(X, Y)) >= activate#(Y) because isNat# = activate#, isNat# in Mul and [37], by (Fun) 37] n!6220!6220plus(X, Y) >= Y because [30], by (Star) 38] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [39], by (Fun) 39] n!6220!6220s(X) >= X because [40], by (Star) 40] n!6220!6220s*(X) >= X because [34], by (Select) 41] isNat#(n!6220!6220s(X)) >= activate#(X) because isNat# = activate#, isNat# in Mul and [39], by (Fun) 42] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because isNat# in Mul and [43], by (Fun) 43] n!6220!6220x(X, Y) >= X because [44], by (Star) 44] n!6220!6220x*(X, Y) >= X because [34], by (Select) 45] isNat#(n!6220!6220x(X, Y)) >= activate#(X) because isNat# = activate#, isNat# in Mul and [43], by (Fun) 46] isNat#(n!6220!6220x(X, Y)) >= activate#(Y) because isNat# = activate#, isNat# in Mul and [47], by (Fun) 47] n!6220!6220x(X, Y) >= Y because [48], by (Star) 48] n!6220!6220x*(X, Y) >= Y because [3], by (Select) 49] plus#(s(X)) >= isNat#(X) because plus# = isNat#, plus# in Mul and [50], by (Fun) 50] s(X) >= X because [51], by (Star) 51] s*(X) >= X because [8], by (Select) 52] x#(X, _|_) >= isNat#(X) because [53], by (Star) 53] x#*(X, _|_) >= isNat#(X) because x# = isNat#, x# in Mul and [9], by (Stat) 54] x#(X, s(Y)) >= U71#(_|_, Y, X) because [55], by (Star) 55] x#*(X, s(Y)) >= U71#(_|_, Y, X) because x# = U71#, x# in Mul, [9], [56] and [58], by (Stat) 56] s(Y) > _|_ because [57], by definition 57] s*(Y) >= _|_ by (Bot) 58] s(Y) > Y because [59], by definition 59] s*(Y) >= Y because [8], by (Select) 60] x#(X, s(Y)) >= isNat#(Y) because [61], by (Star) 61] x#*(X, s(Y)) >= isNat#(Y) because x# = isNat#, x# in Mul and [58], by (Stat) 62] activate#(n!6220!6220x(X, Y)) >= x#(X, Y) because [63], by (Star) 63] activate#*(n!6220!6220x(X, Y)) >= x#(X, Y) because activate# = x#, activate# in Mul, [64] and [67], by (Stat) 64] n!6220!6220x(X, Y) > X because [65], by definition 65] n!6220!6220x*(X, Y) >= X because [66], by (Select) 66] X >= X by (Meta) 67] n!6220!6220x(X, Y) > Y because [68], by definition 68] n!6220!6220x*(X, Y) >= Y because [69], by (Select) 69] Y >= Y by (Meta) 70] _|_ >= _|_ by (Bot) 71] _|_ >= _|_ by (Bot) 72] _|_ >= _|_ by (Bot) 73] _|_ >= _|_ by (Bot) 74] _|_ >= _|_ by (Bot) 75] U41(X) >= X because [76], by (Star) 76] U41*(X) >= X because [9], by (Select) 77] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [7], [8] and [9], by (Fun) 78] U52(_|_, X, Y) >= s(plus(Y, X)) because [79], by (Star) 79] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [80], by (Copy) 80] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [8] and [9], by (Stat) 81] U61(_|_) >= _|_ by (Bot) 82] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [7], [8] and [9], by (Fun) 83] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [84], by (Star) 84] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [85] and [86], by (Copy) 85] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [8] and [9], by (Stat) 86] U72*(_|_, X, Y) >= Y because [9], by (Select) 87] _|_ >= _|_ by (Bot) 88] _|_ >= _|_ by (Bot) 89] _|_ >= _|_ by (Bot) 90] _|_ >= _|_ by (Bot) 91] plus(X, _|_) >= U41(X) because [92], by (Star) 92] plus*(X, _|_) >= U41(X) because plus > U41 and [93], by (Copy) 93] plus*(X, _|_) >= X because [9], by (Select) 94] plus(X, s(Y)) >= U51(_|_, Y, X) because [95], by (Star) 95] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [9], [56] and [58], by (Stat) 96] x(X, _|_) >= U61(_|_) because [97], by (Star) 97] x*(X, _|_) >= U61(_|_) because x > U61 and [98], by (Copy) 98] x*(X, _|_) >= _|_ by (Bot) 99] x(X, s(Y)) >= U71(_|_, Y, X) because [100], by (Star) 100] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [9], [56] and [58], by (Stat) 101] _|_ >= _|_ by (Bot) 102] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [103] and [104], by (Fun) 103] X >= X by (Meta) 104] Y >= Y by (Meta) 105] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [106], by (Fun) 106] X >= X by (Meta) 107] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [103] and [104], by (Fun) 108] _|_ >= _|_ by (Bot) 109] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [103] and [104], by (Fun) 110] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [106], by (Fun) 111] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [103] and [104], by (Fun) 112] 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_7, R_0, minimal, formative) by (P_8, R_0, minimal, formative), where P_8 consists of: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> 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) 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)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) 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!6220x(X, Y)) =#> x#(X, Y) 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 place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 11, 12, 13, 14, 15, 16, 17, 18 * 1 : 23 * 2 : 7, 8, 9, 10 * 3 : 11, 12, 13, 14, 15, 16, 17, 18 * 4 : 23 * 5 : 23 * 6 : 23 * 7 : 19 * 8 : 20, 21, 22 * 9 : 23 * 10 : 23 * 11 : 11, 12, 13, 14, 15, 16, 17, 18 * 12 : 23 * 13 : 23 * 14 : 11, 12, 13, 14, 15, 16, 17, 18 * 15 : 23 * 16 : 11, 12, 13, 14, 15, 16, 17, 18 * 17 : 23 * 18 : 23 * 19 : 11, 12, 13, 14, 15, 16, 17, 18 * 20 : 11, 12, 13, 14, 15, 16, 17, 18 * 21 : 2, 3, 4, 5, 6 * 22 : 11, 12, 13, 14, 15, 16, 17, 18 * 23 : 20, 21, 22 This graph has the following strongly connected components: P_9: 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) 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)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) 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!6220x(X, Y)) =#> x#(X, Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_8, R_0, m, f) by (P_9, R_0, m, f). Thus, the original system is terminating if (P_9, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_9, 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: 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) 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)) >? isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? activate#(Y) 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!6220x(X, Y)) >? x#(X, 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, 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)]] = _|_ [[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 = {U51, 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# > U51 = U52 = n!6220!6220plus = plus > activate# = isNat# = n!6220!6220s = s > plus# Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 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) 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)) >= isNat#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(X) isNat#(n!6220!6220x(X, Y)) >= activate#(Y) 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!6220x(X, Y)) >= x#(X, 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] U71#(_|_, X, Y) >= U72#(_|_, X, Y) because U71# = U72#, U71# in Mul, [2], [3] and [4], by (Fun) 2] _|_ >= _|_ by (Bot) 3] X >= X by (Meta) 4] Y >= Y by (Meta) 5] U71#(_|_, X, Y) >= isNat#(Y) because [6], by (Star) 6] U71#*(_|_, X, Y) >= isNat#(Y) because U71# > isNat# and [7], by (Copy) 7] U71#*(_|_, X, Y) >= Y because [4], by (Select) 8] U71#(_|_, X, Y) >= activate#(Y) because [9], by (Star) 9] U71#*(_|_, X, Y) >= activate#(Y) because U71# > activate# and [7], by (Copy) 10] U71#(_|_, X, Y) >= activate#(X) because [11], by (Star) 11] U71#*(_|_, X, Y) >= activate#(X) because U71# > activate# and [12], by (Copy) 12] U71#*(_|_, X, Y) >= X because [3], by (Select) 13] U71#(_|_, X, Y) >= activate#(Y) because [9], by (Star) 14] U72#(_|_, X, Y) >= plus#(x(Y, X), Y) because [15], by (Star) 15] U72#*(_|_, X, Y) >= plus#(x(Y, X), Y) because U72# > plus#, [16] and [17], by (Copy) 16] U72#*(_|_, X, Y) >= x(Y, X) because U72# = x, U72# in Mul, [3] and [4], by (Stat) 17] U72#*(_|_, X, Y) >= Y because [4], by (Select) 18] U72#(_|_, X, Y) >= x#(Y, X) because [19], by (Star) 19] U72#*(_|_, X, Y) >= x#(Y, X) because U72# = x#, U72# in Mul, [3] and [4], by (Stat) 20] U72#(_|_, X, Y) >= activate#(Y) because [21], by (Star) 21] U72#*(_|_, X, Y) >= activate#(Y) because U72# > activate# and [17], by (Copy) 22] U72#(_|_, X, Y) >= activate#(X) because [23], by (Star) 23] U72#*(_|_, X, Y) >= activate#(X) because U72# > activate# and [24], by (Copy) 24] U72#*(_|_, X, Y) >= X because [3], by (Select) 25] isNat#(n!6220!6220plus(X, Y)) >= isNat#(X) because [26], by (Star) 26] isNat#*(n!6220!6220plus(X, Y)) >= isNat#(X) because isNat# in Mul and [27], by (Stat) 27] n!6220!6220plus(X, Y) > X because [28], by definition 28] n!6220!6220plus*(X, Y) >= X because [29], by (Select) 29] X >= X by (Meta) 30] isNat#(n!6220!6220plus(X, Y)) >= activate#(X) because [31], by (Star) 31] isNat#*(n!6220!6220plus(X, Y)) >= activate#(X) because isNat# = activate#, isNat# in Mul and [32], by (Stat) 32] n!6220!6220plus(X, Y) > X because [28], by definition 33] isNat#(n!6220!6220plus(X, Y)) >= activate#(Y) because isNat# = activate#, isNat# in Mul and [34], by (Fun) 34] n!6220!6220plus(X, Y) >= Y because [35], by (Star) 35] n!6220!6220plus*(X, Y) >= Y because [36], by (Select) 36] Y >= Y by (Meta) 37] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [38], by (Fun) 38] n!6220!6220s(X) >= X because [39], by (Star) 39] n!6220!6220s*(X) >= X because [29], by (Select) 40] isNat#(n!6220!6220s(X)) >= activate#(X) because isNat# = activate#, isNat# in Mul and [38], by (Fun) 41] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because [42], by (Star) 42] isNat#*(n!6220!6220x(X, Y)) >= isNat#(X) because [43], by (Select) 43] n!6220!6220x(X, Y) >= isNat#(X) because [44], by (Star) 44] n!6220!6220x*(X, Y) >= isNat#(X) because n!6220!6220x > isNat# and [45], by (Copy) 45] n!6220!6220x*(X, Y) >= X because [29], by (Select) 46] isNat#(n!6220!6220x(X, Y)) >= activate#(X) because [47], by (Star) 47] isNat#*(n!6220!6220x(X, Y)) >= activate#(X) because [48], by (Select) 48] n!6220!6220x(X, Y) >= activate#(X) because [49], by (Star) 49] n!6220!6220x*(X, Y) >= activate#(X) because n!6220!6220x > activate# and [45], by (Copy) 50] isNat#(n!6220!6220x(X, Y)) >= activate#(Y) because [51], by (Star) 51] isNat#*(n!6220!6220x(X, Y)) >= activate#(Y) because [52], by (Select) 52] n!6220!6220x(X, Y) >= activate#(Y) because [53], by (Star) 53] n!6220!6220x*(X, Y) >= activate#(Y) because n!6220!6220x > activate# and [54], by (Copy) 54] n!6220!6220x*(X, Y) >= Y because [36], 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 s = isNat#, s in Mul and [3], by (Fun) 58] x#(X, _|_) >= isNat#(X) because [59], by (Star) 59] x#*(X, _|_) >= isNat#(X) because x# > isNat# and [60], by (Copy) 60] x#*(X, _|_) >= X because [4], by (Select) 61] x#(X, s(Y)) > U71#(_|_, Y, X) because [62], by definition 62] x#*(X, s(Y)) >= U71#(_|_, Y, X) because x# = U71#, x# in Mul, [4], [63] and [65], by (Stat) 63] s(Y) > _|_ because [64], by definition 64] s*(Y) >= _|_ by (Bot) 65] s(Y) > Y because [66], by definition 66] s*(Y) >= Y because [3], by (Select) 67] x#(X, s(Y)) >= isNat#(Y) because [68], by (Star) 68] x#*(X, s(Y)) >= isNat#(Y) because [57], by (Select) 69] activate#(n!6220!6220x(X, Y)) >= x#(X, Y) because [70], by (Star) 70] activate#*(n!6220!6220x(X, Y)) >= x#(X, Y) because [71], by (Select) 71] n!6220!6220x(X, Y) >= x#(X, Y) because n!6220!6220x = x#, n!6220!6220x in Mul, [72] and [73], by (Fun) 72] X >= X by (Meta) 73] Y >= Y by (Meta) 74] _|_ >= _|_ by (Bot) 75] _|_ >= _|_ by (Bot) 76] _|_ >= _|_ by (Bot) 77] _|_ >= _|_ by (Bot) 78] _|_ >= _|_ by (Bot) 79] X >= X by (Meta) 80] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [2], [3] and [4], by (Fun) 81] U52(_|_, X, Y) >= s(plus(Y, X)) because [82], by (Star) 82] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [83], by (Copy) 83] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [3] and [4], by (Stat) 84] _|_ >= _|_ by (Bot) 85] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [2], [3] and [4], by (Fun) 86] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [87], by (Star) 87] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [88] and [89], by (Copy) 88] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [3] and [4], by (Stat) 89] U72*(_|_, X, Y) >= Y because [79], by (Select) 90] _|_ >= _|_ by (Bot) 91] _|_ >= _|_ by (Bot) 92] _|_ >= _|_ by (Bot) 93] _|_ >= _|_ by (Bot) 94] plus(X, _|_) >= X because [95], by (Star) 95] plus*(X, _|_) >= X because [79], by (Select) 96] plus(X, s(Y)) >= U51(_|_, Y, X) because [97], by (Star) 97] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [4], [63] and [65], by (Stat) 98] x(X, _|_) >= _|_ by (Bot) 99] x(X, s(Y)) >= U71(_|_, Y, X) because [100], by (Star) 100] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [4], [63] and [65], by (Stat) 101] _|_ >= _|_ by (Bot) 102] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [72] and [73], by (Fun) 103] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [104], by (Fun) 104] X >= X by (Meta) 105] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [72] and [73], by (Fun) 106] _|_ >= _|_ by (Bot) 107] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [72] and [73], by (Fun) 108] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [104], by (Fun) 109] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [72] and [73], by (Fun) 110] 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_9, R_0, minimal, formative) by (P_10, R_0, minimal, formative), where P_10 consists of: 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) 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)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) plus#(X, s(Y)) =#> isNat#(Y) x#(X, 0) =#> isNat#(X) x#(X, s(Y)) =#> isNat#(Y) activate#(n!6220!6220x(X, Y)) =#> x#(X, Y) 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 place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 5, 6, 7, 8 * 1 : 9, 10, 11, 12, 13, 14, 15, 16 * 2 : 20 * 3 : 20 * 4 : 20 * 5 : 17 * 6 : 18, 19 * 7 : 20 * 8 : 20 * 9 : 9, 10, 11, 12, 13, 14, 15, 16 * 10 : 20 * 11 : 20 * 12 : 9, 10, 11, 12, 13, 14, 15, 16 * 13 : 20 * 14 : 9, 10, 11, 12, 13, 14, 15, 16 * 15 : 20 * 16 : 20 * 17 : 9, 10, 11, 12, 13, 14, 15, 16 * 18 : 9, 10, 11, 12, 13, 14, 15, 16 * 19 : 9, 10, 11, 12, 13, 14, 15, 16 * 20 : 18, 19 This graph has the following strongly connected components: P_11: 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)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) x#(X, 0) =#> isNat#(X) x#(X, s(Y)) =#> isNat#(Y) activate#(n!6220!6220x(X, Y)) =#> x#(X, Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_10, R_0, m, f) by (P_11, R_0, m, f). 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 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!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)) >? isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) >? activate#(X) isNat#(n!6220!6220x(X, Y)) >? activate#(Y) x#(X, 0) >? isNat#(X) x#(X, s(Y)) >? isNat#(Y) activate#(n!6220!6220x(X, Y)) >? x#(X, 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, 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)]] = _|_ [[U21(x_1)]] = x_1 [[U31(x_1, x_2)]] = _|_ [[U32(x_1)]] = _|_ [[U41(x_1, x_2)]] = x_2 [[U61(x_1)]] = x_1 [[activate(x_1)]] = x_1 [[activate#(x_1)]] = x_1 [[isNat(x_1)]] = _|_ [[n!6220!62200]] = _|_ [[tt]] = _|_ We choose Lex = {} and Mul = {U51, U52, U71, U72, isNat#, n!6220!6220plus, n!6220!6220s, n!6220!6220x, plus, s, x, x#}, and the following precedence: U71 = U72 = n!6220!6220x = x > U51 = U52 = isNat# = n!6220!6220plus = plus = x# > n!6220!6220s = s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: isNat#(n!6220!6220plus(X, Y)) >= isNat#(X) isNat#(n!6220!6220plus(X, Y)) > X isNat#(n!6220!6220plus(X, Y)) >= Y isNat#(n!6220!6220s(X)) >= isNat#(X) isNat#(n!6220!6220s(X)) >= X isNat#(n!6220!6220x(X, Y)) >= isNat#(X) isNat#(n!6220!6220x(X, Y)) >= X isNat#(n!6220!6220x(X, Y)) >= Y x#(X, _|_) >= isNat#(X) x#(X, s(Y)) >= isNat#(Y) n!6220!6220x(X, Y) > x#(X, 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] isNat#(n!6220!6220plus(X, Y)) >= isNat#(X) because [2], by (Star) 2] isNat#*(n!6220!6220plus(X, Y)) >= isNat#(X) because [3], by (Select) 3] n!6220!6220plus(X, Y) >= isNat#(X) because [4], by (Star) 4] n!6220!6220plus*(X, Y) >= isNat#(X) because n!6220!6220plus = isNat#, n!6220!6220plus in Mul and [5], by (Stat) 5] X >= X by (Meta) 6] isNat#(n!6220!6220plus(X, Y)) > X because [7], by definition 7] isNat#*(n!6220!6220plus(X, Y)) >= X because [8], by (Select) 8] n!6220!6220plus(X, Y) >= X because [9], by (Star) 9] n!6220!6220plus*(X, Y) >= X because [5], by (Select) 10] isNat#(n!6220!6220plus(X, Y)) >= Y because [11], by (Star) 11] isNat#*(n!6220!6220plus(X, Y)) >= Y because [12], by (Select) 12] n!6220!6220plus(X, Y) >= Y because [13], by (Star) 13] n!6220!6220plus*(X, Y) >= Y because [14], by (Select) 14] Y >= Y by (Meta) 15] isNat#(n!6220!6220s(X)) >= isNat#(X) because isNat# in Mul and [16], by (Fun) 16] n!6220!6220s(X) >= X because [17], by (Star) 17] n!6220!6220s*(X) >= X because [5], by (Select) 18] isNat#(n!6220!6220s(X)) >= X because [19], by (Star) 19] isNat#*(n!6220!6220s(X)) >= X because [16], by (Select) 20] isNat#(n!6220!6220x(X, Y)) >= isNat#(X) because [21], by (Star) 21] isNat#*(n!6220!6220x(X, Y)) >= isNat#(X) because [22], by (Select) 22] n!6220!6220x(X, Y) >= isNat#(X) because [23], by (Star) 23] n!6220!6220x*(X, Y) >= isNat#(X) because n!6220!6220x > isNat# and [24], by (Copy) 24] n!6220!6220x*(X, Y) >= X because [5], by (Select) 25] isNat#(n!6220!6220x(X, Y)) >= X because [26], by (Star) 26] isNat#*(n!6220!6220x(X, Y)) >= X because [27], by (Select) 27] n!6220!6220x(X, Y) >= X because [24], by (Star) 28] isNat#(n!6220!6220x(X, Y)) >= Y because [29], by (Star) 29] isNat#*(n!6220!6220x(X, Y)) >= Y because [30], by (Select) 30] n!6220!6220x(X, Y) >= Y because [31], by (Star) 31] n!6220!6220x*(X, Y) >= Y because [14], by (Select) 32] x#(X, _|_) >= isNat#(X) because [33], by (Star) 33] x#*(X, _|_) >= isNat#(X) because x# = isNat#, x# in Mul and [34], by (Stat) 34] X >= X by (Meta) 35] x#(X, s(Y)) >= isNat#(Y) because [36], by (Star) 36] x#*(X, s(Y)) >= isNat#(Y) because x# = isNat#, x# in Mul and [37], by (Stat) 37] s(Y) > Y because [38], by definition 38] s*(Y) >= Y because [39], by (Select) 39] Y >= Y by (Meta) 40] n!6220!6220x(X, Y) > x#(X, Y) because [41], by definition 41] n!6220!6220x*(X, Y) >= x#(X, Y) because n!6220!6220x > x#, [42] and [44], by (Copy) 42] n!6220!6220x*(X, Y) >= X because [43], by (Select) 43] X >= X by (Meta) 44] n!6220!6220x*(X, Y) >= Y because [45], by (Select) 45] Y >= Y by (Meta) 46] _|_ >= _|_ by (Bot) 47] _|_ >= _|_ by (Bot) 48] _|_ >= _|_ by (Bot) 49] _|_ >= _|_ by (Bot) 50] _|_ >= _|_ by (Bot) 51] X >= X by (Meta) 52] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [53], [54] and [55], by (Fun) 53] _|_ >= _|_ by (Bot) 54] X >= X by (Meta) 55] Y >= Y by (Meta) 56] U52(_|_, X, Y) >= s(plus(Y, X)) because [57], by (Star) 57] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [58], by (Copy) 58] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [54] and [55], by (Stat) 59] _|_ >= _|_ by (Bot) 60] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [53], [54] and [55], by (Fun) 61] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [62], by (Star) 62] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [63] and [64], by (Copy) 63] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [54] and [55], by (Stat) 64] U72*(_|_, X, Y) >= Y because [55], by (Select) 65] _|_ >= _|_ by (Bot) 66] _|_ >= _|_ by (Bot) 67] _|_ >= _|_ by (Bot) 68] _|_ >= _|_ by (Bot) 69] plus(X, _|_) >= X because [70], by (Star) 70] plus*(X, _|_) >= X because [55], by (Select) 71] plus(X, s(Y)) >= U51(_|_, Y, X) because [72], by (Star) 72] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [55], [73] and [37], by (Stat) 73] s(Y) > _|_ because [74], by definition 74] s*(Y) >= _|_ by (Bot) 75] x(X, _|_) >= _|_ by (Bot) 76] x(X, s(Y)) >= U71(_|_, Y, X) because [77], by (Star) 77] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [55], [73] and [37], by (Stat) 78] _|_ >= _|_ by (Bot) 79] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [80] and [81], by (Fun) 80] X >= X by (Meta) 81] Y >= Y by (Meta) 82] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [83], by (Fun) 83] X >= X by (Meta) 84] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [80] and [81], by (Fun) 85] _|_ >= _|_ by (Bot) 86] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [80] and [81], by (Fun) 87] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [83], by (Fun) 88] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [80] and [81], by (Fun) 89] 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_11, R_0, minimal, formative) by (P_12, R_0, minimal, formative), where P_12 consists of: isNat#(n!6220!6220plus(X, Y)) =#> isNat#(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)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> activate#(X) isNat#(n!6220!6220x(X, Y)) =#> activate#(Y) x#(X, 0) =#> isNat#(X) x#(X, s(Y)) =#> isNat#(Y) 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 place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 0, 1, 2, 3, 4, 5, 6 * 1 : * 2 : 0, 1, 2, 3, 4, 5, 6 * 3 : * 4 : 0, 1, 2, 3, 4, 5, 6 * 5 : * 6 : * 7 : 0, 1, 2, 3, 4, 5, 6 * 8 : 0, 1, 2, 3, 4, 5, 6 This graph has the following strongly connected components: P_13: isNat#(n!6220!6220plus(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) =#> isNat#(activate(X)) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_12, R_0, m, f) by (P_13, R_0, m, f). Thus, the original system is terminating if (P_13, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_13, 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!6220plus(X, Y)) >? isNat#(activate(X)) 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, Y) activate(X) >= X We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: U41(x_1,x_2) = U41(x_2) U51(x_1,x_2,x_3) = U51(x_2x_3) U52(x_1,x_2,x_3) = U52(x_2x_3) U61(x_1) = U61() U71(x_1,x_2,x_3) = U71(x_2x_3) U72(x_1,x_2,x_3) = U72(x_2x_3) This leaves the following ordering requirements: isNat#(n!6220!6220plus(X, Y)) >= isNat#(activate(X)) isNat#(n!6220!6220s(X)) >= isNat#(activate(X)) isNat#(n!6220!6220x(X, Y)) > isNat#(activate(X)) 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)) 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, Y) activate(X) >= X The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.0 U12 = \y0.0 U21 = \y0.0 U31 = \y0y1.0 U32 = \y0.0 U41 = \y0y1.y1 U51 = \y0y1y2.y2 U52 = \y0y1y2.y2 U61 = \y0.0 U71 = \y0y1y2.1 + 2y2 U72 = \y0y1y2.1 + 2y2 activate = \y0.y0 isNat = \y0.0 isNat# = \y0.2y0 n!6220!62200 = 0 n!6220!6220plus = \y0y1.y0 n!6220!6220s = \y0.y0 n!6220!6220x = \y0y1.1 + 2y0 plus = \y0y1.y0 s = \y0.y0 tt = 0 x = \y0y1.1 + 2y0 Using this interpretation, the requirements translate to: [[isNat#(n!6220!6220plus(_x0, _x1))]] = 2x0 >= 2x0 = [[isNat#(activate(_x0))]] [[isNat#(n!6220!6220s(_x0))]] = 2x0 >= 2x0 = [[isNat#(activate(_x0))]] [[isNat#(n!6220!6220x(_x0, _x1))]] = 2 + 4x0 > 2x0 = [[isNat#(activate(_x0))]] [[U41(tt, _x0)]] = x0 >= x0 = [[activate(_x0)]] [[U51(tt, _x0, _x1)]] = x1 >= x1 = [[U52(isNat(activate(_x1)), activate(_x0), activate(_x1))]] [[U52(tt, _x0, _x1)]] = x1 >= x1 = [[s(plus(activate(_x1), activate(_x0)))]] [[U61(tt)]] = 0 >= 0 = [[0]] [[U71(tt, _x0, _x1)]] = 1 + 2x1 >= 1 + 2x1 = [[U72(isNat(activate(_x1)), activate(_x0), activate(_x1))]] [[U72(tt, _x0, _x1)]] = 1 + 2x1 >= 1 + 2x1 = [[plus(x(activate(_x1), activate(_x0)), activate(_x1))]] [[plus(_x0, 0)]] = x0 >= x0 = [[U41(isNat(_x0), _x0)]] [[plus(_x0, s(_x1))]] = x0 >= x0 = [[U51(isNat(_x1), _x1, _x0)]] [[x(_x0, 0)]] = 1 + 2x0 >= 0 = [[U61(isNat(_x0))]] [[x(_x0, s(_x1))]] = 1 + 2x0 >= 1 + 2x0 = [[U71(isNat(_x1), _x1, _x0)]] [[0]] = 0 >= 0 = [[n!6220!62200]] [[plus(_x0, _x1)]] = x0 >= x0 = [[n!6220!6220plus(_x0, _x1)]] [[s(_x0)]] = x0 >= x0 = [[n!6220!6220s(_x0)]] [[x(_x0, _x1)]] = 1 + 2x0 >= 1 + 2x0 = [[n!6220!6220x(_x0, _x1)]] [[activate(n!6220!62200)]] = 0 >= 0 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = x0 >= x0 = [[plus(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = x0 >= x0 = [[s(_x0)]] [[activate(n!6220!6220x(_x0, _x1))]] = 1 + 2x0 >= 1 + 2x0 = [[x(_x0, _x1)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_13, R_0, minimal, formative) by (P_14, R_0, minimal, formative), where P_14 consists of: isNat#(n!6220!6220plus(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) Thus, the original system is terminating if (P_14, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_14, 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!6220plus(X, Y)) >? isNat#(activate(X)) 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, 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)]] = _|_ [[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)]] = _|_ [[n!6220!62200]] = _|_ [[tt]] = _|_ We choose Lex = {} and Mul = {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 > 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: isNat#(n!6220!6220plus(X, Y)) > isNat#(X) 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] isNat#(n!6220!6220plus(X, Y)) > isNat#(X) because [2], by definition 2] isNat#*(n!6220!6220plus(X, Y)) >= isNat#(X) because isNat# in Mul and [3], by (Stat) 3] n!6220!6220plus(X, Y) > X because [4], by definition 4] n!6220!6220plus*(X, Y) >= X because [5], by (Select) 5] X >= X by (Meta) 6] isNat#(n!6220!6220s(X)) >= isNat#(X) because [7], by (Star) 7] isNat#*(n!6220!6220s(X)) >= isNat#(X) because [8], by (Select) 8] n!6220!6220s(X) >= isNat#(X) because n!6220!6220s = isNat#, n!6220!6220s in Mul and [9], by (Fun) 9] X >= X by (Meta) 10] _|_ >= _|_ by (Bot) 11] _|_ >= _|_ by (Bot) 12] _|_ >= _|_ by (Bot) 13] _|_ >= _|_ by (Bot) 14] _|_ >= _|_ by (Bot) 15] X >= X by (Meta) 16] U51(_|_, X, Y) >= U52(_|_, X, Y) because U51 = U52, U51 in Mul, [17], [18] and [19], by (Fun) 17] _|_ >= _|_ by (Bot) 18] X >= X by (Meta) 19] Y >= Y by (Meta) 20] U52(_|_, X, Y) >= s(plus(Y, X)) because [21], by (Star) 21] U52*(_|_, X, Y) >= s(plus(Y, X)) because U52 > s and [22], by (Copy) 22] U52*(_|_, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [18] and [19], by (Stat) 23] _|_ >= _|_ by (Bot) 24] U71(_|_, X, Y) >= U72(_|_, X, Y) because U71 = U72, U71 in Mul, [17], [18] and [19], by (Fun) 25] U72(_|_, X, Y) >= plus(x(Y, X), Y) because [26], by (Star) 26] U72*(_|_, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [27] and [28], by (Copy) 27] U72*(_|_, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [18] and [19], by (Stat) 28] U72*(_|_, X, Y) >= Y because [19], by (Select) 29] _|_ >= _|_ by (Bot) 30] _|_ >= _|_ by (Bot) 31] _|_ >= _|_ by (Bot) 32] _|_ >= _|_ by (Bot) 33] plus(X, _|_) >= X because [34], by (Star) 34] plus*(X, _|_) >= X because [19], by (Select) 35] plus(X, s(Y)) >= U51(_|_, Y, X) because [36], by (Star) 36] plus*(X, s(Y)) >= U51(_|_, Y, X) because plus = U51, plus in Mul, [19], [37] and [39], by (Stat) 37] s(Y) > _|_ because [38], by definition 38] s*(Y) >= _|_ by (Bot) 39] s(Y) > Y because [40], by definition 40] s*(Y) >= Y because [18], by (Select) 41] x(X, _|_) >= _|_ by (Bot) 42] x(X, s(Y)) >= U71(_|_, Y, X) because [43], by (Star) 43] x*(X, s(Y)) >= U71(_|_, Y, X) because x = U71, x in Mul, [19], [37] and [39], by (Stat) 44] _|_ >= _|_ by (Bot) 45] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [46] and [47], by (Fun) 46] X >= X by (Meta) 47] Y >= Y by (Meta) 48] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [49], by (Fun) 49] X >= X by (Meta) 50] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [46] and [47], by (Fun) 51] _|_ >= _|_ by (Bot) 52] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [46] and [47], by (Fun) 53] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [49], by (Fun) 54] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [46] and [47], by (Fun) 55] 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_14, R_0, minimal, formative) by (P_15, R_0, minimal, formative), where P_15 consists of: isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) Thus, the original system is terminating if (P_15, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_15, 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(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220x(X, Y)) >= x(X, 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)]] = U31 [[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 = {U31, U51, U52, U71, U72, isNat, isNat#, n!6220!6220plus, n!6220!6220s, n!6220!6220x, plus, s, tt, x}, and the following precedence: U71 = U72 = n!6220!6220x = x > U51 = U52 = n!6220!6220plus = plus > isNat# = n!6220!6220s = s > U31 = isNat = tt Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: isNat#(n!6220!6220s(X)) > isNat#(X) tt >= isNat tt >= tt tt >= tt U31 >= 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 >= U31 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] isNat#(n!6220!6220s(X)) > isNat#(X) because [2], by definition 2] isNat#*(n!6220!6220s(X)) >= isNat#(X) because [3], by (Select) 3] n!6220!6220s(X) >= isNat#(X) because n!6220!6220s = isNat#, n!6220!6220s in Mul and [4], by (Fun) 4] X >= X by (Meta) 5] tt >= isNat because tt = isNat, by (Fun) 6] tt >= tt by (Fun) 7] tt >= tt by (Fun) 8] U31 >= isNat because U31 = isNat and U31 in Mul, by (Fun) 9] tt >= tt by (Fun) 10] X >= X by (Meta) 11] U51(tt, X, Y) >= U52(isNat, X, Y) because U51 = U52, U51 in Mul, [12], [13] and [14], by (Fun) 12] tt >= isNat because tt = isNat, by (Fun) 13] X >= X by (Meta) 14] Y >= Y by (Meta) 15] U52(tt, X, Y) >= s(plus(Y, X)) because [16], by (Star) 16] U52*(tt, X, Y) >= s(plus(Y, X)) because U52 > s and [17], by (Copy) 17] U52*(tt, X, Y) >= plus(Y, X) because U52 = plus, U52 in Mul, [13] and [14], by (Stat) 18] _|_ >= _|_ by (Bot) 19] U71(tt, X, Y) >= U72(isNat, X, Y) because U71 = U72, U71 in Mul, [12], [13] and [14], by (Fun) 20] U72(tt, X, Y) >= plus(x(Y, X), Y) because [21], by (Star) 21] U72*(tt, X, Y) >= plus(x(Y, X), Y) because U72 > plus, [22] and [23], by (Copy) 22] U72*(tt, X, Y) >= x(Y, X) because U72 = x, U72 in Mul, [13] and [14], by (Stat) 23] U72*(tt, X, Y) >= Y because [14], by (Select) 24] isNat >= tt because isNat = tt, by (Fun) 25] isNat >= isNat because isNat in Mul, by (Fun) 26] isNat >= isNat because isNat in Mul, by (Fun) 27] isNat >= U31 because isNat = U31 and isNat in Mul, by (Fun) 28] plus(X, _|_) >= X because [29], by (Star) 29] plus*(X, _|_) >= X because [14], by (Select) 30] plus(X, s(Y)) >= U51(isNat, Y, X) because [31], by (Star) 31] plus*(X, s(Y)) >= U51(isNat, Y, X) because plus = U51, plus in Mul, [14], [32] and [34], by (Stat) 32] s(Y) > isNat because [33], by definition 33] s*(Y) >= isNat because s > isNat, by (Copy) 34] s(Y) > Y because [35], by definition 35] s*(Y) >= Y because [13], by (Select) 36] x(X, _|_) >= _|_ by (Bot) 37] x(X, s(Y)) >= U71(isNat, Y, X) because [38], by (Star) 38] x*(X, s(Y)) >= U71(isNat, Y, X) because x = U71, x in Mul, [14], [32] and [34], by (Stat) 39] _|_ >= _|_ by (Bot) 40] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [41] and [42], by (Fun) 41] X >= X by (Meta) 42] Y >= Y by (Meta) 43] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [44], by (Fun) 44] X >= X by (Meta) 45] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, x in Mul, [41] and [42], by (Fun) 46] _|_ >= _|_ by (Bot) 47] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [41] and [42], by (Fun) 48] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [44], by (Fun) 49] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, n!6220!6220x in Mul, [41] and [42], by (Fun) 50] 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_15, 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.