/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 a!6220!6220add : [o * o] --> o a!6220!6220dbl : [o] --> o a!6220!6220first : [o * o] --> o a!6220!6220sqr : [o] --> o a!6220!6220terms : [o] --> o add : [o * o] --> o cons : [o * o] --> o dbl : [o] --> o first : [o * o] --> o mark : [o] --> o nil : [] --> o recip : [o] --> o s : [o] --> o sqr : [o] --> o terms : [o] --> o a!6220!6220terms(X) => cons(recip(a!6220!6220sqr(mark(X))), terms(s(X))) a!6220!6220sqr(0) => 0 a!6220!6220sqr(s(X)) => s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) => 0 a!6220!6220dbl(s(X)) => s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) => mark(X) a!6220!6220add(s(X), Y) => s(a!6220!6220add(mark(X), mark(Y))) a!6220!6220first(0, X) => nil a!6220!6220first(s(X), cons(Y, Z)) => cons(mark(Y), first(X, Z)) mark(terms(X)) => a!6220!6220terms(mark(X)) mark(sqr(X)) => a!6220!6220sqr(mark(X)) mark(add(X, Y)) => a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) => a!6220!6220dbl(mark(X)) mark(first(X, Y)) => a!6220!6220first(mark(X), mark(Y)) mark(cons(X, Y)) => cons(mark(X), Y) mark(recip(X)) => recip(mark(X)) mark(s(X)) => s(mark(X)) mark(0) => 0 mark(nil) => nil a!6220!6220terms(X) => terms(X) a!6220!6220sqr(X) => sqr(X) a!6220!6220add(X, Y) => add(X, Y) a!6220!6220dbl(X) => dbl(X) a!6220!6220first(X, Y) => first(X, Y) We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] a!6220!6220terms#(X) =#> a!6220!6220sqr#(mark(X)) 1] a!6220!6220terms#(X) =#> mark#(X) 2] a!6220!6220sqr#(s(X)) =#> a!6220!6220add#(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X))) 3] a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X)) 4] a!6220!6220sqr#(s(X)) =#> mark#(X) 5] a!6220!6220sqr#(s(X)) =#> a!6220!6220dbl#(mark(X)) 6] a!6220!6220sqr#(s(X)) =#> mark#(X) 7] a!6220!6220dbl#(s(X)) =#> a!6220!6220dbl#(mark(X)) 8] a!6220!6220dbl#(s(X)) =#> mark#(X) 9] a!6220!6220add#(0, X) =#> mark#(X) 10] a!6220!6220add#(s(X), Y) =#> a!6220!6220add#(mark(X), mark(Y)) 11] a!6220!6220add#(s(X), Y) =#> mark#(X) 12] a!6220!6220add#(s(X), Y) =#> mark#(Y) 13] a!6220!6220first#(s(X), cons(Y, Z)) =#> mark#(Y) 14] mark#(terms(X)) =#> a!6220!6220terms#(mark(X)) 15] mark#(terms(X)) =#> mark#(X) 16] mark#(sqr(X)) =#> a!6220!6220sqr#(mark(X)) 17] mark#(sqr(X)) =#> mark#(X) 18] mark#(add(X, Y)) =#> a!6220!6220add#(mark(X), mark(Y)) 19] mark#(add(X, Y)) =#> mark#(X) 20] mark#(add(X, Y)) =#> mark#(Y) 21] mark#(dbl(X)) =#> a!6220!6220dbl#(mark(X)) 22] mark#(dbl(X)) =#> mark#(X) 23] mark#(first(X, Y)) =#> a!6220!6220first#(mark(X), mark(Y)) 24] mark#(first(X, Y)) =#> mark#(X) 25] mark#(first(X, Y)) =#> mark#(Y) 26] mark#(cons(X, Y)) =#> mark#(X) 27] mark#(recip(X)) =#> mark#(X) 28] mark#(s(X)) =#> mark#(X) Rules R_0: a!6220!6220terms(X) => cons(recip(a!6220!6220sqr(mark(X))), terms(s(X))) a!6220!6220sqr(0) => 0 a!6220!6220sqr(s(X)) => s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) => 0 a!6220!6220dbl(s(X)) => s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) => mark(X) a!6220!6220add(s(X), Y) => s(a!6220!6220add(mark(X), mark(Y))) a!6220!6220first(0, X) => nil a!6220!6220first(s(X), cons(Y, Z)) => cons(mark(Y), first(X, Z)) mark(terms(X)) => a!6220!6220terms(mark(X)) mark(sqr(X)) => a!6220!6220sqr(mark(X)) mark(add(X, Y)) => a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) => a!6220!6220dbl(mark(X)) mark(first(X, Y)) => a!6220!6220first(mark(X), mark(Y)) mark(cons(X, Y)) => cons(mark(X), Y) mark(recip(X)) => recip(mark(X)) mark(s(X)) => s(mark(X)) mark(0) => 0 mark(nil) => nil a!6220!6220terms(X) => terms(X) a!6220!6220sqr(X) => sqr(X) a!6220!6220add(X, Y) => add(X, Y) a!6220!6220dbl(X) => dbl(X) a!6220!6220first(X, Y) => first(X, Y) Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). The formative rules of (P_0, R_0) are R_1 ::= a!6220!6220terms(X) => cons(recip(a!6220!6220sqr(mark(X))), terms(s(X))) a!6220!6220sqr(0) => 0 a!6220!6220sqr(s(X)) => s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) => 0 a!6220!6220dbl(s(X)) => s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) => mark(X) a!6220!6220add(s(X), Y) => s(a!6220!6220add(mark(X), mark(Y))) a!6220!6220first(s(X), cons(Y, Z)) => cons(mark(Y), first(X, Z)) mark(terms(X)) => a!6220!6220terms(mark(X)) mark(sqr(X)) => a!6220!6220sqr(mark(X)) mark(add(X, Y)) => a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) => a!6220!6220dbl(mark(X)) mark(first(X, Y)) => a!6220!6220first(mark(X), mark(Y)) mark(cons(X, Y)) => cons(mark(X), Y) mark(recip(X)) => recip(mark(X)) mark(s(X)) => s(mark(X)) mark(0) => 0 a!6220!6220terms(X) => terms(X) a!6220!6220sqr(X) => sqr(X) a!6220!6220add(X, Y) => add(X, Y) a!6220!6220dbl(X) => dbl(X) a!6220!6220first(X, Y) => first(X, Y) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_0, R_0, minimal, formative) by (P_0, R_1, minimal, formative). Thus, the original system is terminating if (P_0, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220terms#(X) >? a!6220!6220sqr#(mark(X)) a!6220!6220terms#(X) >? mark#(X) a!6220!6220sqr#(s(X)) >? a!6220!6220add#(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X))) a!6220!6220sqr#(s(X)) >? a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) >? mark#(X) a!6220!6220sqr#(s(X)) >? a!6220!6220dbl#(mark(X)) a!6220!6220sqr#(s(X)) >? mark#(X) a!6220!6220dbl#(s(X)) >? a!6220!6220dbl#(mark(X)) a!6220!6220dbl#(s(X)) >? mark#(X) a!6220!6220add#(0, X) >? mark#(X) a!6220!6220add#(s(X), Y) >? a!6220!6220add#(mark(X), mark(Y)) a!6220!6220add#(s(X), Y) >? mark#(X) a!6220!6220add#(s(X), Y) >? mark#(Y) a!6220!6220first#(s(X), cons(Y, Z)) >? mark#(Y) mark#(terms(X)) >? a!6220!6220terms#(mark(X)) mark#(terms(X)) >? mark#(X) mark#(sqr(X)) >? a!6220!6220sqr#(mark(X)) mark#(sqr(X)) >? mark#(X) mark#(add(X, Y)) >? a!6220!6220add#(mark(X), mark(Y)) mark#(add(X, Y)) >? mark#(X) mark#(add(X, Y)) >? mark#(Y) mark#(dbl(X)) >? a!6220!6220dbl#(mark(X)) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? a!6220!6220first#(mark(X), mark(Y)) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(s(X)) >? mark#(X) a!6220!6220terms(X) >= cons(recip(a!6220!6220sqr(mark(X))), terms(s(X))) a!6220!6220sqr(0) >= 0 a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) >= 0 a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) >= mark(X) a!6220!6220add(s(X), Y) >= s(a!6220!6220add(mark(X), mark(Y))) a!6220!6220first(s(X), cons(Y, Z)) >= cons(mark(Y), first(X, Z)) mark(terms(X)) >= a!6220!6220terms(mark(X)) mark(sqr(X)) >= a!6220!6220sqr(mark(X)) mark(add(X, Y)) >= a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) >= a!6220!6220dbl(mark(X)) mark(first(X, Y)) >= a!6220!6220first(mark(X), mark(Y)) mark(cons(X, Y)) >= cons(mark(X), Y) mark(recip(X)) >= recip(mark(X)) mark(s(X)) >= s(mark(X)) mark(0) >= 0 a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) 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]] = _|_ [[cons(x_1, x_2)]] = x_1 [[mark(x_1)]] = x_1 [[recip(x_1)]] = x_1 We choose Lex = {} and Mul = {a!6220!6220add, a!6220!6220add#, a!6220!6220dbl, a!6220!6220dbl#, a!6220!6220first, a!6220!6220first#, a!6220!6220sqr, a!6220!6220sqr#, a!6220!6220terms, a!6220!6220terms#, add, dbl, first, mark#, s, sqr, terms}, and the following precedence: a!6220!6220terms = a!6220!6220terms# = terms > a!6220!6220sqr = a!6220!6220sqr# = sqr > a!6220!6220add = add > a!6220!6220dbl = dbl > s > a!6220!6220first = first > a!6220!6220first# > a!6220!6220add# = a!6220!6220dbl# = mark# Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a!6220!6220terms#(X) > a!6220!6220sqr#(X) a!6220!6220terms#(X) >= mark#(X) a!6220!6220sqr#(s(X)) >= a!6220!6220add#(a!6220!6220sqr(X), a!6220!6220dbl(X)) a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) a!6220!6220sqr#(s(X)) >= mark#(X) a!6220!6220sqr#(s(X)) >= a!6220!6220dbl#(X) a!6220!6220sqr#(s(X)) >= mark#(X) a!6220!6220dbl#(s(X)) > a!6220!6220dbl#(X) a!6220!6220dbl#(s(X)) > mark#(X) a!6220!6220add#(_|_, X) >= mark#(X) a!6220!6220add#(s(X), Y) >= a!6220!6220add#(X, Y) a!6220!6220add#(s(X), Y) >= mark#(X) a!6220!6220add#(s(X), Y) >= mark#(Y) a!6220!6220first#(s(X), Y) > mark#(Y) mark#(terms(X)) >= a!6220!6220terms#(X) mark#(terms(X)) >= mark#(X) mark#(sqr(X)) >= a!6220!6220sqr#(X) mark#(sqr(X)) >= mark#(X) mark#(add(X, Y)) >= a!6220!6220add#(X, Y) mark#(add(X, Y)) >= mark#(X) mark#(add(X, Y)) >= mark#(Y) mark#(dbl(X)) >= a!6220!6220dbl#(X) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= a!6220!6220first#(X, Y) mark#(first(X, Y)) >= mark#(X) mark#(first(X, Y)) >= mark#(Y) mark#(X) >= mark#(X) mark#(X) >= mark#(X) mark#(s(X)) >= mark#(X) a!6220!6220terms(X) >= a!6220!6220sqr(X) a!6220!6220sqr(_|_) >= _|_ a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) a!6220!6220dbl(_|_) >= _|_ a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) a!6220!6220add(_|_, X) >= X a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) a!6220!6220first(s(X), Y) >= Y terms(X) >= a!6220!6220terms(X) sqr(X) >= a!6220!6220sqr(X) add(X, Y) >= a!6220!6220add(X, Y) dbl(X) >= a!6220!6220dbl(X) first(X, Y) >= a!6220!6220first(X, Y) X >= X X >= X s(X) >= s(X) _|_ >= _|_ a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) With these choices, we have: 1] a!6220!6220terms#(X) > a!6220!6220sqr#(X) because [2], by definition 2] a!6220!6220terms#*(X) >= a!6220!6220sqr#(X) because a!6220!6220terms# > a!6220!6220sqr# and [3], by (Copy) 3] a!6220!6220terms#*(X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] a!6220!6220terms#(X) >= mark#(X) because [6], by (Star) 6] a!6220!6220terms#*(X) >= mark#(X) because a!6220!6220terms# > mark# and [3], by (Copy) 7] a!6220!6220sqr#(s(X)) >= a!6220!6220add#(a!6220!6220sqr(X), a!6220!6220dbl(X)) because [8], by (Star) 8] a!6220!6220sqr#*(s(X)) >= a!6220!6220add#(a!6220!6220sqr(X), a!6220!6220dbl(X)) because a!6220!6220sqr# > a!6220!6220add#, [9] and [13], by (Copy) 9] a!6220!6220sqr#*(s(X)) >= a!6220!6220sqr(X) because a!6220!6220sqr# = a!6220!6220sqr, a!6220!6220sqr# in Mul and [10], by (Stat) 10] s(X) > X because [11], by definition 11] s*(X) >= X because [12], by (Select) 12] X >= X by (Meta) 13] a!6220!6220sqr#*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220sqr# > a!6220!6220dbl and [14], by (Copy) 14] a!6220!6220sqr#*(s(X)) >= X because [15], by (Select) 15] s(X) >= X because [11], by (Star) 16] a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) because [17], by (Star) 17] a!6220!6220sqr#*(s(X)) >= a!6220!6220sqr#(X) because a!6220!6220sqr# in Mul and [10], by (Stat) 18] a!6220!6220sqr#(s(X)) >= mark#(X) because [19], by (Star) 19] a!6220!6220sqr#*(s(X)) >= mark#(X) because a!6220!6220sqr# > mark# and [14], by (Copy) 20] a!6220!6220sqr#(s(X)) >= a!6220!6220dbl#(X) because [21], by (Star) 21] a!6220!6220sqr#*(s(X)) >= a!6220!6220dbl#(X) because a!6220!6220sqr# > a!6220!6220dbl# and [14], by (Copy) 22] a!6220!6220sqr#(s(X)) >= mark#(X) because [19], by (Star) 23] a!6220!6220dbl#(s(X)) > a!6220!6220dbl#(X) because [24], by definition 24] a!6220!6220dbl#*(s(X)) >= a!6220!6220dbl#(X) because a!6220!6220dbl# in Mul and [10], by (Stat) 25] a!6220!6220dbl#(s(X)) > mark#(X) because [26], by definition 26] a!6220!6220dbl#*(s(X)) >= mark#(X) because a!6220!6220dbl# = mark#, a!6220!6220dbl# in Mul and [27], by (Stat) 27] s(X) > X because [11], by definition 28] a!6220!6220add#(_|_, X) >= mark#(X) because [29], by (Star) 29] a!6220!6220add#*(_|_, X) >= mark#(X) because a!6220!6220add# = mark#, a!6220!6220add# in Mul and [30], by (Stat) 30] X >= X by (Meta) 31] a!6220!6220add#(s(X), Y) >= a!6220!6220add#(X, Y) because [32], by (Star) 32] a!6220!6220add#*(s(X), Y) >= a!6220!6220add#(X, Y) because a!6220!6220add# in Mul, [10] and [33], by (Stat) 33] Y >= Y by (Meta) 34] a!6220!6220add#(s(X), Y) >= mark#(X) because [35], by (Star) 35] a!6220!6220add#*(s(X), Y) >= mark#(X) because a!6220!6220add# = mark#, a!6220!6220add# in Mul and [36], by (Stat) 36] s(X) >= X because [11], by (Star) 37] a!6220!6220add#(s(X), Y) >= mark#(Y) because [38], by (Star) 38] a!6220!6220add#*(s(X), Y) >= mark#(Y) because a!6220!6220add# = mark#, a!6220!6220add# in Mul and [33], by (Stat) 39] a!6220!6220first#(s(X), Y) > mark#(Y) because [40], by definition 40] a!6220!6220first#*(s(X), Y) >= mark#(Y) because a!6220!6220first# > mark# and [41], by (Copy) 41] a!6220!6220first#*(s(X), Y) >= Y because [42], by (Select) 42] Y >= Y by (Meta) 43] mark#(terms(X)) >= a!6220!6220terms#(X) because [44], by (Star) 44] mark#*(terms(X)) >= a!6220!6220terms#(X) because [45], by (Select) 45] terms(X) >= a!6220!6220terms#(X) because terms = a!6220!6220terms#, terms in Mul and [46], by (Fun) 46] X >= X by (Meta) 47] mark#(terms(X)) >= mark#(X) because mark# in Mul and [48], by (Fun) 48] terms(X) >= X because [49], by (Star) 49] terms*(X) >= X because [46], by (Select) 50] mark#(sqr(X)) >= a!6220!6220sqr#(X) because [51], by (Star) 51] mark#*(sqr(X)) >= a!6220!6220sqr#(X) because [52], by (Select) 52] sqr(X) >= a!6220!6220sqr#(X) because sqr = a!6220!6220sqr#, sqr in Mul and [46], by (Fun) 53] mark#(sqr(X)) >= mark#(X) because mark# in Mul and [54], by (Fun) 54] sqr(X) >= X because [55], by (Star) 55] sqr*(X) >= X because [46], by (Select) 56] mark#(add(X, Y)) >= a!6220!6220add#(X, Y) because [57], by (Star) 57] mark#*(add(X, Y)) >= a!6220!6220add#(X, Y) because mark# = a!6220!6220add#, mark# in Mul, [58] and [61], by (Stat) 58] add(X, Y) > X because [59], by definition 59] add*(X, Y) >= X because [60], by (Select) 60] X >= X by (Meta) 61] add(X, Y) > Y because [62], by definition 62] add*(X, Y) >= Y because [63], by (Select) 63] Y >= Y by (Meta) 64] mark#(add(X, Y)) >= mark#(X) because mark# in Mul and [65], by (Fun) 65] add(X, Y) >= X because [59], by (Star) 66] mark#(add(X, Y)) >= mark#(Y) because mark# in Mul and [67], by (Fun) 67] add(X, Y) >= Y because [62], by (Star) 68] mark#(dbl(X)) >= a!6220!6220dbl#(X) because mark# = a!6220!6220dbl#, mark# in Mul and [69], by (Fun) 69] dbl(X) >= X because [70], by (Star) 70] dbl*(X) >= X because [46], by (Select) 71] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [69], by (Fun) 72] mark#(first(X, Y)) >= a!6220!6220first#(X, Y) because [73], by (Star) 73] mark#*(first(X, Y)) >= a!6220!6220first#(X, Y) because [74], by (Select) 74] first(X, Y) >= a!6220!6220first#(X, Y) because [75], by (Star) 75] first*(X, Y) >= a!6220!6220first#(X, Y) because first > a!6220!6220first#, [76] and [77], by (Copy) 76] first*(X, Y) >= X because [60], by (Select) 77] first*(X, Y) >= Y because [63], by (Select) 78] mark#(first(X, Y)) >= mark#(X) because mark# in Mul and [79], by (Fun) 79] first(X, Y) >= X because [76], by (Star) 80] mark#(first(X, Y)) >= mark#(Y) because mark# in Mul and [81], by (Fun) 81] first(X, Y) >= Y because [77], by (Star) 82] mark#(X) >= mark#(X) because mark# in Mul and [83], by (Fun) 83] X >= X by (Meta) 84] mark#(X) >= mark#(X) because mark# in Mul and [85], by (Fun) 85] X >= X by (Meta) 86] mark#(s(X)) >= mark#(X) because mark# in Mul and [36], by (Fun) 87] a!6220!6220terms(X) >= a!6220!6220sqr(X) because [88], by (Star) 88] a!6220!6220terms*(X) >= a!6220!6220sqr(X) because a!6220!6220terms > a!6220!6220sqr and [89], by (Copy) 89] a!6220!6220terms*(X) >= X because [4], by (Select) 90] a!6220!6220sqr(_|_) >= _|_ by (Bot) 91] a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because [92], by (Star) 92] a!6220!6220sqr*(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because a!6220!6220sqr > s and [93], by (Copy) 93] a!6220!6220sqr*(s(X)) >= a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X)) because a!6220!6220sqr > a!6220!6220add, [94] and [95], by (Copy) 94] a!6220!6220sqr*(s(X)) >= a!6220!6220sqr(X) because a!6220!6220sqr in Mul and [10], by (Stat) 95] a!6220!6220sqr*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220sqr > a!6220!6220dbl and [96], by (Copy) 96] a!6220!6220sqr*(s(X)) >= X because [36], by (Select) 97] a!6220!6220dbl(_|_) >= _|_ by (Bot) 98] a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) because [99], by (Star) 99] a!6220!6220dbl*(s(X)) >= s(s(a!6220!6220dbl(X))) because a!6220!6220dbl > s and [100], by (Copy) 100] a!6220!6220dbl*(s(X)) >= s(a!6220!6220dbl(X)) because a!6220!6220dbl > s and [101], by (Copy) 101] a!6220!6220dbl*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220dbl in Mul and [10], by (Stat) 102] a!6220!6220add(_|_, X) >= X because [103], by (Star) 103] a!6220!6220add*(_|_, X) >= X because [85], by (Select) 104] a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) because [105], by (Star) 105] a!6220!6220add*(s(X), Y) >= s(a!6220!6220add(X, Y)) because a!6220!6220add > s and [106], by (Copy) 106] a!6220!6220add*(s(X), Y) >= a!6220!6220add(X, Y) because a!6220!6220add in Mul, [10] and [33], by (Stat) 107] a!6220!6220first(s(X), Y) >= Y because [108], by (Star) 108] a!6220!6220first*(s(X), Y) >= Y because [42], by (Select) 109] terms(X) >= a!6220!6220terms(X) because terms = a!6220!6220terms, terms in Mul and [46], by (Fun) 110] sqr(X) >= a!6220!6220sqr(X) because sqr = a!6220!6220sqr, sqr in Mul and [46], by (Fun) 111] add(X, Y) >= a!6220!6220add(X, Y) because add = a!6220!6220add, add in Mul, [112] and [113], by (Fun) 112] X >= X by (Meta) 113] Y >= Y by (Meta) 114] dbl(X) >= a!6220!6220dbl(X) because dbl = a!6220!6220dbl, dbl in Mul and [46], by (Fun) 115] first(X, Y) >= a!6220!6220first(X, Y) because first = a!6220!6220first, first in Mul, [112] and [113], by (Fun) 116] X >= X by (Meta) 117] X >= X by (Meta) 118] s(X) >= s(X) because s in Mul and [46], by (Fun) 119] _|_ >= _|_ by (Bot) 120] a!6220!6220terms(X) >= terms(X) because a!6220!6220terms = terms, a!6220!6220terms in Mul and [46], by (Fun) 121] a!6220!6220sqr(X) >= sqr(X) because a!6220!6220sqr = sqr, a!6220!6220sqr in Mul and [46], by (Fun) 122] a!6220!6220add(X, Y) >= add(X, Y) because a!6220!6220add = add, a!6220!6220add in Mul, [112] and [113], by (Fun) 123] a!6220!6220dbl(X) >= dbl(X) because a!6220!6220dbl = dbl, a!6220!6220dbl in Mul and [46], by (Fun) 124] a!6220!6220first(X, Y) >= first(X, Y) because a!6220!6220first = first, a!6220!6220first in Mul, [112] and [113], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_0, R_1, minimal, formative) by (P_1, R_1, minimal, formative), where P_1 consists of: a!6220!6220terms#(X) =#> mark#(X) a!6220!6220sqr#(s(X)) =#> a!6220!6220add#(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X))) a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) =#> mark#(X) a!6220!6220sqr#(s(X)) =#> a!6220!6220dbl#(mark(X)) a!6220!6220sqr#(s(X)) =#> mark#(X) a!6220!6220add#(0, X) =#> mark#(X) a!6220!6220add#(s(X), Y) =#> a!6220!6220add#(mark(X), mark(Y)) a!6220!6220add#(s(X), Y) =#> mark#(X) a!6220!6220add#(s(X), Y) =#> mark#(Y) mark#(terms(X)) =#> a!6220!6220terms#(mark(X)) mark#(terms(X)) =#> mark#(X) mark#(sqr(X)) =#> a!6220!6220sqr#(mark(X)) mark#(sqr(X)) =#> mark#(X) mark#(add(X, Y)) =#> a!6220!6220add#(mark(X), mark(Y)) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> a!6220!6220dbl#(mark(X)) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> a!6220!6220first#(mark(X), mark(Y)) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) Thus, the original system is terminating if (P_1, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_1, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 1 : 6, 7, 8, 9 * 2 : 1, 2, 3, 4, 5 * 3 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 4 : * 5 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 6 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 7 : 6, 7, 8, 9 * 8 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 9 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 10 : 0 * 11 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 12 : 1, 2, 3, 4, 5 * 13 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 14 : 6, 7, 8, 9 * 15 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 16 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 17 : * 18 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 19 : * 20 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 21 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 22 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 23 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 * 24 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 This graph has the following strongly connected components: P_2: a!6220!6220terms#(X) =#> mark#(X) a!6220!6220sqr#(s(X)) =#> a!6220!6220add#(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X))) a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) =#> mark#(X) a!6220!6220sqr#(s(X)) =#> mark#(X) a!6220!6220add#(0, X) =#> mark#(X) a!6220!6220add#(s(X), Y) =#> a!6220!6220add#(mark(X), mark(Y)) a!6220!6220add#(s(X), Y) =#> mark#(X) a!6220!6220add#(s(X), Y) =#> mark#(Y) mark#(terms(X)) =#> a!6220!6220terms#(mark(X)) mark#(terms(X)) =#> mark#(X) mark#(sqr(X)) =#> a!6220!6220sqr#(mark(X)) mark#(sqr(X)) =#> mark#(X) mark#(add(X, Y)) =#> a!6220!6220add#(mark(X), mark(Y)) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_1, R_1, m, f) by (P_2, R_1, m, f). Thus, the original system is terminating if (P_2, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220terms#(X) >? mark#(X) a!6220!6220sqr#(s(X)) >? a!6220!6220add#(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X))) a!6220!6220sqr#(s(X)) >? a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) >? mark#(X) a!6220!6220sqr#(s(X)) >? mark#(X) a!6220!6220add#(0, X) >? mark#(X) a!6220!6220add#(s(X), Y) >? a!6220!6220add#(mark(X), mark(Y)) a!6220!6220add#(s(X), Y) >? mark#(X) a!6220!6220add#(s(X), Y) >? mark#(Y) mark#(terms(X)) >? a!6220!6220terms#(mark(X)) mark#(terms(X)) >? mark#(X) mark#(sqr(X)) >? a!6220!6220sqr#(mark(X)) mark#(sqr(X)) >? mark#(X) mark#(add(X, Y)) >? a!6220!6220add#(mark(X), mark(Y)) mark#(add(X, Y)) >? mark#(X) mark#(add(X, Y)) >? mark#(Y) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(s(X)) >? mark#(X) a!6220!6220terms(X) >= cons(recip(a!6220!6220sqr(mark(X))), terms(s(X))) a!6220!6220sqr(0) >= 0 a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) >= 0 a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) >= mark(X) a!6220!6220add(s(X), Y) >= s(a!6220!6220add(mark(X), mark(Y))) a!6220!6220first(s(X), cons(Y, Z)) >= cons(mark(Y), first(X, Z)) mark(terms(X)) >= a!6220!6220terms(mark(X)) mark(sqr(X)) >= a!6220!6220sqr(mark(X)) mark(add(X, Y)) >= a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) >= a!6220!6220dbl(mark(X)) mark(first(X, Y)) >= a!6220!6220first(mark(X), mark(Y)) mark(cons(X, Y)) >= cons(mark(X), Y) mark(recip(X)) >= recip(mark(X)) mark(s(X)) >= s(mark(X)) mark(0) >= 0 a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) 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: [[a!6220!6220first(x_1, x_2)]] = a!6220!6220first(x_2, x_1) [[cons(x_1, x_2)]] = cons(x_1) [[first(x_1, x_2)]] = first(x_2, x_1) [[mark(x_1)]] = x_1 We choose Lex = {a!6220!6220first, cons, first, recip} and Mul = {0, a!6220!6220add, a!6220!6220add#, a!6220!6220dbl, a!6220!6220sqr, a!6220!6220sqr#, a!6220!6220terms, a!6220!6220terms#, add, dbl, mark#, s, sqr, terms}, and the following precedence: a!6220!6220first = first > a!6220!6220terms = terms > cons > a!6220!6220dbl = a!6220!6220sqr = a!6220!6220sqr# = dbl = sqr > a!6220!6220add = add > a!6220!6220add# > recip > a!6220!6220terms# = mark# > 0 > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a!6220!6220terms#(X) >= mark#(X) a!6220!6220sqr#(s(X)) > a!6220!6220add#(a!6220!6220sqr(X), a!6220!6220dbl(X)) a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) a!6220!6220sqr#(s(X)) >= mark#(X) a!6220!6220sqr#(s(X)) >= mark#(X) a!6220!6220add#(0, X) >= mark#(X) a!6220!6220add#(s(X), Y) >= a!6220!6220add#(X, Y) a!6220!6220add#(s(X), Y) >= mark#(X) a!6220!6220add#(s(X), Y) >= mark#(Y) mark#(terms(X)) > a!6220!6220terms#(X) mark#(terms(X)) > mark#(X) mark#(sqr(X)) >= a!6220!6220sqr#(X) mark#(sqr(X)) >= mark#(X) mark#(add(X, Y)) > a!6220!6220add#(X, Y) mark#(add(X, Y)) >= mark#(X) mark#(add(X, Y)) >= mark#(Y) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= mark#(X) mark#(first(X, Y)) >= mark#(Y) mark#(cons(X, Y)) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(s(X)) >= mark#(X) a!6220!6220terms(X) >= cons(recip(a!6220!6220sqr(X)), terms(s(X))) a!6220!6220sqr(0) >= 0 a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) a!6220!6220dbl(0) >= 0 a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) a!6220!6220add(0, X) >= X a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) a!6220!6220first(s(X), cons(Y, Z)) >= cons(Y, first(X, Z)) terms(X) >= a!6220!6220terms(X) sqr(X) >= a!6220!6220sqr(X) add(X, Y) >= a!6220!6220add(X, Y) dbl(X) >= a!6220!6220dbl(X) first(X, Y) >= a!6220!6220first(X, Y) cons(X, Y) >= cons(X, Y) recip(X) >= recip(X) s(X) >= s(X) 0 >= 0 a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) With these choices, we have: 1] a!6220!6220terms#(X) >= mark#(X) because a!6220!6220terms# = mark#, a!6220!6220terms# in Mul and [2], by (Fun) 2] X >= X by (Meta) 3] a!6220!6220sqr#(s(X)) > a!6220!6220add#(a!6220!6220sqr(X), a!6220!6220dbl(X)) because [4], by definition 4] a!6220!6220sqr#*(s(X)) >= a!6220!6220add#(a!6220!6220sqr(X), a!6220!6220dbl(X)) because a!6220!6220sqr# > a!6220!6220add#, [5] and [9], by (Copy) 5] a!6220!6220sqr#*(s(X)) >= a!6220!6220sqr(X) because a!6220!6220sqr# = a!6220!6220sqr, a!6220!6220sqr# in Mul and [6], by (Stat) 6] s(X) > X because [7], by definition 7] s*(X) >= X because [8], by (Select) 8] X >= X by (Meta) 9] a!6220!6220sqr#*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220sqr# = a!6220!6220dbl, a!6220!6220sqr# in Mul and [6], by (Stat) 10] a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) because [11], by (Star) 11] a!6220!6220sqr#*(s(X)) >= a!6220!6220sqr#(X) because a!6220!6220sqr# in Mul and [6], by (Stat) 12] a!6220!6220sqr#(s(X)) >= mark#(X) because [13], by (Star) 13] a!6220!6220sqr#*(s(X)) >= mark#(X) because a!6220!6220sqr# > mark# and [14], by (Copy) 14] a!6220!6220sqr#*(s(X)) >= X because [15], by (Select) 15] s(X) >= X because [7], by (Star) 16] a!6220!6220sqr#(s(X)) >= mark#(X) because [13], by (Star) 17] a!6220!6220add#(0, X) >= mark#(X) because [18], by (Star) 18] a!6220!6220add#*(0, X) >= mark#(X) because a!6220!6220add# > mark# and [19], by (Copy) 19] a!6220!6220add#*(0, X) >= X because [8], by (Select) 20] a!6220!6220add#(s(X), Y) >= a!6220!6220add#(X, Y) because a!6220!6220add# in Mul, [21] and [22], by (Fun) 21] s(X) >= X because [7], by (Star) 22] Y >= Y by (Meta) 23] a!6220!6220add#(s(X), Y) >= mark#(X) because [24], by (Star) 24] a!6220!6220add#*(s(X), Y) >= mark#(X) because a!6220!6220add# > mark# and [25], by (Copy) 25] a!6220!6220add#*(s(X), Y) >= X because [21], by (Select) 26] a!6220!6220add#(s(X), Y) >= mark#(Y) because [27], by (Star) 27] a!6220!6220add#*(s(X), Y) >= mark#(Y) because a!6220!6220add# > mark# and [28], by (Copy) 28] a!6220!6220add#*(s(X), Y) >= Y because [22], by (Select) 29] mark#(terms(X)) > a!6220!6220terms#(X) because [30], by definition 30] mark#*(terms(X)) >= a!6220!6220terms#(X) because [31], by (Select) 31] terms(X) >= a!6220!6220terms#(X) because [32], by (Star) 32] terms*(X) >= a!6220!6220terms#(X) because terms > a!6220!6220terms# and [33], by (Copy) 33] terms*(X) >= X because [8], by (Select) 34] mark#(terms(X)) > mark#(X) because [35], by definition 35] mark#*(terms(X)) >= mark#(X) because mark# in Mul and [36], by (Stat) 36] terms(X) > X because [33], by definition 37] mark#(sqr(X)) >= a!6220!6220sqr#(X) because [38], by (Star) 38] mark#*(sqr(X)) >= a!6220!6220sqr#(X) because [39], by (Select) 39] sqr(X) >= a!6220!6220sqr#(X) because sqr = a!6220!6220sqr#, sqr in Mul and [40], by (Fun) 40] X >= X by (Meta) 41] mark#(sqr(X)) >= mark#(X) because [42], by (Star) 42] mark#*(sqr(X)) >= mark#(X) because [43], by (Select) 43] sqr(X) >= mark#(X) because [44], by (Star) 44] sqr*(X) >= mark#(X) because sqr > mark# and [45], by (Copy) 45] sqr*(X) >= X because [40], by (Select) 46] mark#(add(X, Y)) > a!6220!6220add#(X, Y) because [47], by definition 47] mark#*(add(X, Y)) >= a!6220!6220add#(X, Y) because [48], by (Select) 48] add(X, Y) >= a!6220!6220add#(X, Y) because [49], by (Star) 49] add*(X, Y) >= a!6220!6220add#(X, Y) because add > a!6220!6220add#, [50] and [52], by (Copy) 50] add*(X, Y) >= X because [51], by (Select) 51] X >= X by (Meta) 52] add*(X, Y) >= Y because [53], by (Select) 53] Y >= Y by (Meta) 54] mark#(add(X, Y)) >= mark#(X) because [55], by (Star) 55] mark#*(add(X, Y)) >= mark#(X) because [56], by (Select) 56] add(X, Y) >= mark#(X) because [57], by (Star) 57] add*(X, Y) >= mark#(X) because add > mark# and [50], by (Copy) 58] mark#(add(X, Y)) >= mark#(Y) because [59], by (Star) 59] mark#*(add(X, Y)) >= mark#(Y) because mark# in Mul and [60], by (Stat) 60] add(X, Y) > Y because [52], by definition 61] mark#(dbl(X)) >= mark#(X) because [62], by (Star) 62] mark#*(dbl(X)) >= mark#(X) because [63], by (Select) 63] dbl(X) >= mark#(X) because [64], by (Star) 64] dbl*(X) >= mark#(X) because dbl > mark# and [65], by (Copy) 65] dbl*(X) >= X because [40], by (Select) 66] mark#(first(X, Y)) >= mark#(X) because [67], by (Star) 67] mark#*(first(X, Y)) >= mark#(X) because [68], by (Select) 68] first(X, Y) >= mark#(X) because [69], by (Star) 69] first*(X, Y) >= mark#(X) because first > mark# and [70], by (Copy) 70] first*(X, Y) >= X because [51], by (Select) 71] mark#(first(X, Y)) >= mark#(Y) because [72], by (Star) 72] mark#*(first(X, Y)) >= mark#(Y) because mark# in Mul and [73], by (Stat) 73] first(X, Y) > Y because [74], by definition 74] first*(X, Y) >= Y because [53], by (Select) 75] mark#(cons(X, Y)) >= mark#(X) because mark# in Mul and [76], by (Fun) 76] cons(X, Y) >= X because [77], by (Star) 77] cons*(X, Y) >= X because [51], by (Select) 78] mark#(recip(X)) >= mark#(X) because [79], by (Star) 79] mark#*(recip(X)) >= mark#(X) because [80], by (Select) 80] recip(X) >= mark#(X) because [81], by (Star) 81] recip*(X) >= mark#(X) because recip > mark# and [82], by (Copy) 82] recip*(X) >= X because [40], by (Select) 83] mark#(s(X)) >= mark#(X) because mark# in Mul and [21], by (Fun) 84] a!6220!6220terms(X) >= cons(recip(a!6220!6220sqr(X)), terms(s(X))) because [85], by (Star) 85] a!6220!6220terms*(X) >= cons(recip(a!6220!6220sqr(X)), terms(s(X))) because a!6220!6220terms > cons and [86], by (Copy) 86] a!6220!6220terms*(X) >= recip(a!6220!6220sqr(X)) because a!6220!6220terms > recip and [87], by (Copy) 87] a!6220!6220terms*(X) >= a!6220!6220sqr(X) because a!6220!6220terms > a!6220!6220sqr and [88], by (Copy) 88] a!6220!6220terms*(X) >= X because [2], by (Select) 89] a!6220!6220sqr(0) >= 0 because [90], by (Star) 90] a!6220!6220sqr*(0) >= 0 because a!6220!6220sqr > 0, by (Copy) 91] a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because [92], by (Star) 92] a!6220!6220sqr*(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because a!6220!6220sqr > s and [93], by (Copy) 93] a!6220!6220sqr*(s(X)) >= a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X)) because a!6220!6220sqr > a!6220!6220add, [94] and [95], by (Copy) 94] a!6220!6220sqr*(s(X)) >= a!6220!6220sqr(X) because a!6220!6220sqr in Mul and [6], by (Stat) 95] a!6220!6220sqr*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220sqr = a!6220!6220dbl, a!6220!6220sqr in Mul and [6], by (Stat) 96] a!6220!6220dbl(0) >= 0 because [97], by (Star) 97] a!6220!6220dbl*(0) >= 0 because a!6220!6220dbl > 0, by (Copy) 98] a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) because [99], by (Star) 99] a!6220!6220dbl*(s(X)) >= s(s(a!6220!6220dbl(X))) because a!6220!6220dbl > s and [100], by (Copy) 100] a!6220!6220dbl*(s(X)) >= s(a!6220!6220dbl(X)) because a!6220!6220dbl > s and [101], by (Copy) 101] a!6220!6220dbl*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220dbl in Mul and [6], by (Stat) 102] a!6220!6220add(0, X) >= X because [103], by (Star) 103] a!6220!6220add*(0, X) >= X because [40], by (Select) 104] a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) because [105], by (Star) 105] a!6220!6220add*(s(X), Y) >= s(a!6220!6220add(X, Y)) because a!6220!6220add > s and [106], by (Copy) 106] a!6220!6220add*(s(X), Y) >= a!6220!6220add(X, Y) because a!6220!6220add in Mul, [6] and [22], by (Stat) 107] a!6220!6220first(s(X), cons(Y, Z)) >= cons(Y, first(X, Z)) because [108], by (Star) 108] a!6220!6220first*(s(X), cons(Y, Z)) >= cons(Y, first(X, Z)) because [109], by (Select) 109] cons(Y, Z) >= cons(Y, first(X, Z)) because [22], by (Fun) 110] terms(X) >= a!6220!6220terms(X) because terms = a!6220!6220terms, terms in Mul and [40], by (Fun) 111] sqr(X) >= a!6220!6220sqr(X) because sqr = a!6220!6220sqr, sqr in Mul and [40], by (Fun) 112] add(X, Y) >= a!6220!6220add(X, Y) because add = a!6220!6220add, add in Mul, [113] and [114], by (Fun) 113] X >= X by (Meta) 114] Y >= Y by (Meta) 115] dbl(X) >= a!6220!6220dbl(X) because dbl = a!6220!6220dbl, dbl in Mul and [40], by (Fun) 116] first(X, Y) >= a!6220!6220first(X, Y) because first = a!6220!6220first, [113] and [114], by (Fun) 117] cons(X, Y) >= cons(X, Y) because [113], by (Fun) 118] recip(X) >= recip(X) because [40], by (Fun) 119] s(X) >= s(X) because s in Mul and [40], by (Fun) 120] 0 >= 0 by (Fun) 121] a!6220!6220terms(X) >= terms(X) because a!6220!6220terms = terms, a!6220!6220terms in Mul and [40], by (Fun) 122] a!6220!6220sqr(X) >= sqr(X) because a!6220!6220sqr = sqr, a!6220!6220sqr in Mul and [40], by (Fun) 123] a!6220!6220add(X, Y) >= add(X, Y) because a!6220!6220add = add, a!6220!6220add in Mul, [113] and [114], by (Fun) 124] a!6220!6220dbl(X) >= dbl(X) because a!6220!6220dbl = dbl, a!6220!6220dbl in Mul and [40], by (Fun) 125] a!6220!6220first(X, Y) >= first(X, Y) because a!6220!6220first = first, [113] and [114], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_2, R_1, minimal, formative) by (P_3, R_1, minimal, formative), where P_3 consists of: a!6220!6220terms#(X) =#> mark#(X) a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) =#> mark#(X) a!6220!6220sqr#(s(X)) =#> mark#(X) a!6220!6220add#(0, X) =#> mark#(X) a!6220!6220add#(s(X), Y) =#> a!6220!6220add#(mark(X), mark(Y)) a!6220!6220add#(s(X), Y) =#> mark#(X) a!6220!6220add#(s(X), Y) =#> mark#(Y) mark#(sqr(X)) =#> a!6220!6220sqr#(mark(X)) mark#(sqr(X)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) Thus, the original system is terminating if (P_3, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_3, R_1, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 1 : 1, 2, 3 * 2 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 3 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 4 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 5 : 4, 5, 6, 7 * 6 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 7 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 8 : 1, 2, 3 * 9 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 10 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 11 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 12 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 13 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 14 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 15 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 16 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 * 17 : 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 This graph has the following strongly connected components: P_4: a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) =#> mark#(X) a!6220!6220sqr#(s(X)) =#> mark#(X) mark#(sqr(X)) =#> a!6220!6220sqr#(mark(X)) mark#(sqr(X)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) P_5: a!6220!6220add#(s(X), Y) =#> a!6220!6220add#(mark(X), mark(Y)) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_3, R_1, m, f) by (P_4, R_1, m, f) and (P_5, R_1, m, f). Thus, the original system is terminating if each of (P_4, R_1, minimal, formative) and (P_5, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_5, R_1, minimal, formative). The formative rules of (P_5, R_1) are R_2 ::= a!6220!6220sqr(0) => 0 a!6220!6220sqr(s(X)) => s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) => 0 a!6220!6220dbl(s(X)) => s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) => mark(X) a!6220!6220add(s(X), Y) => s(a!6220!6220add(mark(X), mark(Y))) mark(sqr(X)) => a!6220!6220sqr(mark(X)) mark(add(X, Y)) => a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) => a!6220!6220dbl(mark(X)) mark(s(X)) => s(mark(X)) mark(0) => 0 a!6220!6220sqr(X) => sqr(X) a!6220!6220add(X, Y) => add(X, Y) a!6220!6220dbl(X) => dbl(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_5, R_1, minimal, formative) by (P_5, R_2, minimal, formative). Thus, the original system is terminating if each of (P_4, R_1, minimal, formative) and (P_5, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_5, R_2, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220add#(s(X), Y) >? a!6220!6220add#(mark(X), mark(Y)) a!6220!6220sqr(0) >= 0 a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) >= 0 a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) >= mark(X) a!6220!6220add(s(X), Y) >= s(a!6220!6220add(mark(X), mark(Y))) mark(sqr(X)) >= a!6220!6220sqr(mark(X)) mark(add(X, Y)) >= a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) >= a!6220!6220dbl(mark(X)) mark(s(X)) >= s(mark(X)) mark(0) >= 0 a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(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]] = _|_ [[mark(x_1)]] = x_1 We choose Lex = {} and Mul = {a!6220!6220add, a!6220!6220add#, a!6220!6220dbl, a!6220!6220sqr, add, dbl, s, sqr}, and the following precedence: a!6220!6220dbl = a!6220!6220sqr = dbl = sqr > a!6220!6220add = add > a!6220!6220add# > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a!6220!6220add#(s(X), Y) > a!6220!6220add#(X, Y) a!6220!6220sqr(_|_) >= _|_ a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) a!6220!6220dbl(_|_) >= _|_ a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) a!6220!6220add(_|_, X) >= X a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) sqr(X) >= a!6220!6220sqr(X) add(X, Y) >= a!6220!6220add(X, Y) dbl(X) >= a!6220!6220dbl(X) s(X) >= s(X) _|_ >= _|_ a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) With these choices, we have: 1] a!6220!6220add#(s(X), Y) > a!6220!6220add#(X, Y) because [2], by definition 2] a!6220!6220add#*(s(X), Y) >= a!6220!6220add#(X, Y) because a!6220!6220add# in Mul, [3] and [6], by (Stat) 3] s(X) > X because [4], by definition 4] s*(X) >= X because [5], by (Select) 5] X >= X by (Meta) 6] Y >= Y by (Meta) 7] a!6220!6220sqr(_|_) >= _|_ by (Bot) 8] a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because [9], by (Star) 9] a!6220!6220sqr*(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because a!6220!6220sqr > s and [10], by (Copy) 10] a!6220!6220sqr*(s(X)) >= a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X)) because a!6220!6220sqr > a!6220!6220add, [11] and [12], by (Copy) 11] a!6220!6220sqr*(s(X)) >= a!6220!6220sqr(X) because a!6220!6220sqr in Mul and [3], by (Stat) 12] a!6220!6220sqr*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220sqr = a!6220!6220dbl, a!6220!6220sqr in Mul and [3], by (Stat) 13] a!6220!6220dbl(_|_) >= _|_ by (Bot) 14] a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) because [15], by (Star) 15] a!6220!6220dbl*(s(X)) >= s(s(a!6220!6220dbl(X))) because a!6220!6220dbl > s and [16], by (Copy) 16] a!6220!6220dbl*(s(X)) >= s(a!6220!6220dbl(X)) because a!6220!6220dbl > s and [17], by (Copy) 17] a!6220!6220dbl*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220dbl in Mul and [3], by (Stat) 18] a!6220!6220add(_|_, X) >= X because [19], by (Star) 19] a!6220!6220add*(_|_, X) >= X because [5], by (Select) 20] a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) because [21], by (Star) 21] a!6220!6220add*(s(X), Y) >= s(a!6220!6220add(X, Y)) because a!6220!6220add > s and [22], by (Copy) 22] a!6220!6220add*(s(X), Y) >= a!6220!6220add(X, Y) because a!6220!6220add in Mul, [3] and [6], by (Stat) 23] sqr(X) >= a!6220!6220sqr(X) because sqr = a!6220!6220sqr, sqr in Mul and [24], by (Fun) 24] X >= X by (Meta) 25] add(X, Y) >= a!6220!6220add(X, Y) because add = a!6220!6220add, add in Mul, [26] and [27], by (Fun) 26] X >= X by (Meta) 27] Y >= Y by (Meta) 28] dbl(X) >= a!6220!6220dbl(X) because dbl = a!6220!6220dbl, dbl in Mul and [24], by (Fun) 29] s(X) >= s(X) because s in Mul and [24], by (Fun) 30] _|_ >= _|_ by (Bot) 31] a!6220!6220sqr(X) >= sqr(X) because a!6220!6220sqr = sqr, a!6220!6220sqr in Mul and [24], by (Fun) 32] a!6220!6220add(X, Y) >= add(X, Y) because a!6220!6220add = add, a!6220!6220add in Mul, [26] and [27], by (Fun) 33] a!6220!6220dbl(X) >= dbl(X) because a!6220!6220dbl = dbl, a!6220!6220dbl in Mul and [24], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_5, R_2) by ({}, R_2). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if (P_4, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220sqr#(s(X)) >? a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) >? mark#(X) a!6220!6220sqr#(s(X)) >? mark#(X) mark#(sqr(X)) >? a!6220!6220sqr#(mark(X)) mark#(sqr(X)) >? mark#(X) mark#(add(X, Y)) >? mark#(X) mark#(add(X, Y)) >? mark#(Y) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(s(X)) >? mark#(X) a!6220!6220terms(X) >= cons(recip(a!6220!6220sqr(mark(X))), terms(s(X))) a!6220!6220sqr(0) >= 0 a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) >= 0 a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) >= mark(X) a!6220!6220add(s(X), Y) >= s(a!6220!6220add(mark(X), mark(Y))) a!6220!6220first(s(X), cons(Y, Z)) >= cons(mark(Y), first(X, Z)) mark(terms(X)) >= a!6220!6220terms(mark(X)) mark(sqr(X)) >= a!6220!6220sqr(mark(X)) mark(add(X, Y)) >= a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) >= a!6220!6220dbl(mark(X)) mark(first(X, Y)) >= a!6220!6220first(mark(X), mark(Y)) mark(cons(X, Y)) >= cons(mark(X), Y) mark(recip(X)) >= recip(mark(X)) mark(s(X)) >= s(mark(X)) mark(0) >= 0 a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) 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]] = _|_ [[cons(x_1, x_2)]] = x_1 [[mark(x_1)]] = x_1 We choose Lex = {} and Mul = {a!6220!6220add, a!6220!6220dbl, a!6220!6220first, a!6220!6220sqr, a!6220!6220sqr#, a!6220!6220terms, add, dbl, first, mark#, recip, s, sqr, terms}, and the following precedence: a!6220!6220terms = terms > a!6220!6220dbl = a!6220!6220first = a!6220!6220sqr = a!6220!6220sqr# = dbl = first = mark# = recip = sqr > a!6220!6220add = add > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) a!6220!6220sqr#(s(X)) > mark#(X) a!6220!6220sqr#(s(X)) >= mark#(X) mark#(sqr(X)) >= a!6220!6220sqr#(X) mark#(sqr(X)) >= mark#(X) mark#(add(X, Y)) >= mark#(X) mark#(add(X, Y)) >= mark#(Y) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= mark#(X) mark#(first(X, Y)) >= mark#(Y) mark#(X) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(s(X)) >= mark#(X) a!6220!6220terms(X) >= recip(a!6220!6220sqr(X)) a!6220!6220sqr(_|_) >= _|_ a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) a!6220!6220dbl(_|_) >= _|_ a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) a!6220!6220add(_|_, X) >= X a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) a!6220!6220first(s(X), Y) >= Y terms(X) >= a!6220!6220terms(X) sqr(X) >= a!6220!6220sqr(X) add(X, Y) >= a!6220!6220add(X, Y) dbl(X) >= a!6220!6220dbl(X) first(X, Y) >= a!6220!6220first(X, Y) X >= X recip(X) >= recip(X) s(X) >= s(X) _|_ >= _|_ a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) With these choices, we have: 1] a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) because [2], by (Star) 2] a!6220!6220sqr#*(s(X)) >= a!6220!6220sqr#(X) because a!6220!6220sqr# in Mul and [3], by (Stat) 3] s(X) > X because [4], by definition 4] s*(X) >= X because [5], by (Select) 5] X >= X by (Meta) 6] a!6220!6220sqr#(s(X)) > mark#(X) because [7], by definition 7] a!6220!6220sqr#*(s(X)) >= mark#(X) because a!6220!6220sqr# = mark#, a!6220!6220sqr# in Mul and [8], by (Stat) 8] s(X) > X because [4], by definition 9] a!6220!6220sqr#(s(X)) >= mark#(X) because [7], by (Star) 10] mark#(sqr(X)) >= a!6220!6220sqr#(X) because [11], by (Star) 11] mark#*(sqr(X)) >= a!6220!6220sqr#(X) because [12], by (Select) 12] sqr(X) >= a!6220!6220sqr#(X) because sqr = a!6220!6220sqr#, sqr in Mul and [13], by (Fun) 13] X >= X by (Meta) 14] mark#(sqr(X)) >= mark#(X) because [15], by (Star) 15] mark#*(sqr(X)) >= mark#(X) because [16], by (Select) 16] sqr(X) >= mark#(X) because sqr = mark#, sqr in Mul and [13], by (Fun) 17] mark#(add(X, Y)) >= mark#(X) because mark# in Mul and [18], by (Fun) 18] add(X, Y) >= X because [19], by (Star) 19] add*(X, Y) >= X because [20], by (Select) 20] X >= X by (Meta) 21] mark#(add(X, Y)) >= mark#(Y) because mark# in Mul and [22], by (Fun) 22] add(X, Y) >= Y because [23], by (Star) 23] add*(X, Y) >= Y because [24], by (Select) 24] Y >= Y by (Meta) 25] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [26], by (Fun) 26] dbl(X) >= X because [27], by (Star) 27] dbl*(X) >= X because [13], by (Select) 28] mark#(first(X, Y)) >= mark#(X) because [29], by (Star) 29] mark#*(first(X, Y)) >= mark#(X) because [30], by (Select) 30] first(X, Y) >= mark#(X) because [31], by (Star) 31] first*(X, Y) >= mark#(X) because first = mark#, first in Mul and [32], by (Stat) 32] X >= X by (Meta) 33] mark#(first(X, Y)) >= mark#(Y) because mark# in Mul and [34], by (Fun) 34] first(X, Y) >= Y because [35], by (Star) 35] first*(X, Y) >= Y because [24], by (Select) 36] mark#(X) >= mark#(X) because mark# in Mul and [37], by (Fun) 37] X >= X by (Meta) 38] mark#(recip(X)) >= mark#(X) because [39], by (Star) 39] mark#*(recip(X)) >= mark#(X) because [40], by (Select) 40] recip(X) >= mark#(X) because recip = mark#, recip in Mul and [13], by (Fun) 41] mark#(s(X)) >= mark#(X) because [42], by (Star) 42] mark#*(s(X)) >= mark#(X) because mark# in Mul and [8], by (Stat) 43] a!6220!6220terms(X) >= recip(a!6220!6220sqr(X)) because [44], by (Star) 44] a!6220!6220terms*(X) >= recip(a!6220!6220sqr(X)) because a!6220!6220terms > recip and [45], by (Copy) 45] a!6220!6220terms*(X) >= a!6220!6220sqr(X) because a!6220!6220terms > a!6220!6220sqr and [46], by (Copy) 46] a!6220!6220terms*(X) >= X because [47], by (Select) 47] X >= X by (Meta) 48] a!6220!6220sqr(_|_) >= _|_ by (Bot) 49] a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because [50], by (Star) 50] a!6220!6220sqr*(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because a!6220!6220sqr > s and [51], by (Copy) 51] a!6220!6220sqr*(s(X)) >= a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X)) because a!6220!6220sqr > a!6220!6220add, [52] and [53], by (Copy) 52] a!6220!6220sqr*(s(X)) >= a!6220!6220sqr(X) because a!6220!6220sqr in Mul and [3], by (Stat) 53] a!6220!6220sqr*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220sqr = a!6220!6220dbl, a!6220!6220sqr in Mul and [3], by (Stat) 54] a!6220!6220dbl(_|_) >= _|_ by (Bot) 55] a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) because [56], by (Star) 56] a!6220!6220dbl*(s(X)) >= s(s(a!6220!6220dbl(X))) because a!6220!6220dbl > s and [57], by (Copy) 57] a!6220!6220dbl*(s(X)) >= s(a!6220!6220dbl(X)) because a!6220!6220dbl > s and [58], by (Copy) 58] a!6220!6220dbl*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220dbl in Mul and [3], by (Stat) 59] a!6220!6220add(_|_, X) >= X because [60], by (Star) 60] a!6220!6220add*(_|_, X) >= X because [13], by (Select) 61] a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) because [62], by (Star) 62] a!6220!6220add*(s(X), Y) >= s(a!6220!6220add(X, Y)) because a!6220!6220add > s and [63], by (Copy) 63] a!6220!6220add*(s(X), Y) >= a!6220!6220add(X, Y) because a!6220!6220add in Mul, [3] and [64], by (Stat) 64] Y >= Y by (Meta) 65] a!6220!6220first(s(X), Y) >= Y because [66], by (Star) 66] a!6220!6220first*(s(X), Y) >= Y because [67], by (Select) 67] Y >= Y by (Meta) 68] terms(X) >= a!6220!6220terms(X) because terms = a!6220!6220terms, terms in Mul and [13], by (Fun) 69] sqr(X) >= a!6220!6220sqr(X) because sqr = a!6220!6220sqr, sqr in Mul and [13], by (Fun) 70] add(X, Y) >= a!6220!6220add(X, Y) because add = a!6220!6220add, add in Mul, [71] and [72], by (Fun) 71] X >= X by (Meta) 72] Y >= Y by (Meta) 73] dbl(X) >= a!6220!6220dbl(X) because dbl = a!6220!6220dbl, dbl in Mul and [13], by (Fun) 74] first(X, Y) >= a!6220!6220first(X, Y) because first = a!6220!6220first, first in Mul, [71] and [72], by (Fun) 75] X >= X by (Meta) 76] recip(X) >= recip(X) because recip in Mul and [13], by (Fun) 77] s(X) >= s(X) because s in Mul and [13], by (Fun) 78] _|_ >= _|_ by (Bot) 79] a!6220!6220terms(X) >= terms(X) because a!6220!6220terms = terms, a!6220!6220terms in Mul and [13], by (Fun) 80] a!6220!6220sqr(X) >= sqr(X) because a!6220!6220sqr = sqr, a!6220!6220sqr in Mul and [13], by (Fun) 81] a!6220!6220add(X, Y) >= add(X, Y) because a!6220!6220add = add, a!6220!6220add in Mul, [71] and [72], by (Fun) 82] a!6220!6220dbl(X) >= dbl(X) because a!6220!6220dbl = dbl, a!6220!6220dbl in Mul and [13], by (Fun) 83] a!6220!6220first(X, Y) >= first(X, Y) because a!6220!6220first = first, a!6220!6220first in Mul, [71] and [72], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_4, R_1, minimal, formative) by (P_6, R_1, minimal, formative), where P_6 consists of: a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) =#> mark#(X) mark#(sqr(X)) =#> a!6220!6220sqr#(mark(X)) mark#(sqr(X)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) Thus, the original system is terminating if (P_6, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_6, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220sqr#(s(X)) >? a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) >? mark#(X) mark#(sqr(X)) >? a!6220!6220sqr#(mark(X)) mark#(sqr(X)) >? mark#(X) mark#(add(X, Y)) >? mark#(X) mark#(add(X, Y)) >? mark#(Y) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(s(X)) >? mark#(X) a!6220!6220terms(X) >= cons(recip(a!6220!6220sqr(mark(X))), terms(s(X))) a!6220!6220sqr(0) >= 0 a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) >= 0 a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) >= mark(X) a!6220!6220add(s(X), Y) >= s(a!6220!6220add(mark(X), mark(Y))) a!6220!6220first(s(X), cons(Y, Z)) >= cons(mark(Y), first(X, Z)) mark(terms(X)) >= a!6220!6220terms(mark(X)) mark(sqr(X)) >= a!6220!6220sqr(mark(X)) mark(add(X, Y)) >= a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) >= a!6220!6220dbl(mark(X)) mark(first(X, Y)) >= a!6220!6220first(mark(X), mark(Y)) mark(cons(X, Y)) >= cons(mark(X), Y) mark(recip(X)) >= recip(mark(X)) mark(s(X)) >= s(mark(X)) mark(0) >= 0 a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) 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]] = _|_ [[cons(x_1, x_2)]] = x_1 [[mark(x_1)]] = x_1 [[recip(x_1)]] = x_1 We choose Lex = {} and Mul = {a!6220!6220add, a!6220!6220dbl, a!6220!6220first, a!6220!6220sqr, a!6220!6220sqr#, a!6220!6220terms, add, dbl, first, mark#, s, sqr, terms}, and the following precedence: a!6220!6220first = first > a!6220!6220sqr# = mark# > a!6220!6220sqr = a!6220!6220terms = sqr = terms > a!6220!6220dbl = dbl > a!6220!6220add = add > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) a!6220!6220sqr#(s(X)) >= mark#(X) mark#(sqr(X)) >= a!6220!6220sqr#(X) mark#(sqr(X)) >= mark#(X) mark#(add(X, Y)) >= mark#(X) mark#(add(X, Y)) > mark#(Y) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= mark#(X) mark#(first(X, Y)) >= mark#(Y) mark#(X) >= mark#(X) mark#(X) >= mark#(X) mark#(s(X)) >= mark#(X) a!6220!6220terms(X) >= a!6220!6220sqr(X) a!6220!6220sqr(_|_) >= _|_ a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) a!6220!6220dbl(_|_) >= _|_ a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) a!6220!6220add(_|_, X) >= X a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) a!6220!6220first(s(X), Y) >= Y terms(X) >= a!6220!6220terms(X) sqr(X) >= a!6220!6220sqr(X) add(X, Y) >= a!6220!6220add(X, Y) dbl(X) >= a!6220!6220dbl(X) first(X, Y) >= a!6220!6220first(X, Y) X >= X X >= X s(X) >= s(X) _|_ >= _|_ a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) With these choices, we have: 1] a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) because a!6220!6220sqr# in Mul and [2], by (Fun) 2] s(X) >= X because [3], by (Star) 3] s*(X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] a!6220!6220sqr#(s(X)) >= mark#(X) because a!6220!6220sqr# = mark#, a!6220!6220sqr# in Mul and [2], by (Fun) 6] mark#(sqr(X)) >= a!6220!6220sqr#(X) because mark# = a!6220!6220sqr#, mark# in Mul and [7], by (Fun) 7] sqr(X) >= X because [8], by (Star) 8] sqr*(X) >= X because [4], by (Select) 9] mark#(sqr(X)) >= mark#(X) because mark# in Mul and [7], by (Fun) 10] mark#(add(X, Y)) >= mark#(X) because mark# in Mul and [11], by (Fun) 11] add(X, Y) >= X because [12], by (Star) 12] add*(X, Y) >= X because [13], by (Select) 13] X >= X by (Meta) 14] mark#(add(X, Y)) > mark#(Y) because [15], by definition 15] mark#*(add(X, Y)) >= mark#(Y) because mark# in Mul and [16], by (Stat) 16] add(X, Y) > Y because [17], by definition 17] add*(X, Y) >= Y because [18], by (Select) 18] Y >= Y by (Meta) 19] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [20], by (Fun) 20] dbl(X) >= X because [21], by (Star) 21] dbl*(X) >= X because [4], by (Select) 22] mark#(first(X, Y)) >= mark#(X) because mark# in Mul and [23], by (Fun) 23] first(X, Y) >= X because [24], by (Star) 24] first*(X, Y) >= X because [13], by (Select) 25] mark#(first(X, Y)) >= mark#(Y) because mark# in Mul and [26], by (Fun) 26] first(X, Y) >= Y because [27], by (Star) 27] first*(X, Y) >= Y because [18], by (Select) 28] mark#(X) >= mark#(X) because mark# in Mul and [29], by (Fun) 29] X >= X by (Meta) 30] mark#(X) >= mark#(X) because mark# in Mul and [31], by (Fun) 31] X >= X by (Meta) 32] mark#(s(X)) >= mark#(X) because mark# in Mul and [2], by (Fun) 33] a!6220!6220terms(X) >= a!6220!6220sqr(X) because a!6220!6220terms = a!6220!6220sqr, a!6220!6220terms in Mul and [34], by (Fun) 34] X >= X by (Meta) 35] a!6220!6220sqr(_|_) >= _|_ by (Bot) 36] a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because [37], by (Star) 37] a!6220!6220sqr*(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because a!6220!6220sqr > s and [38], by (Copy) 38] a!6220!6220sqr*(s(X)) >= a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X)) because a!6220!6220sqr > a!6220!6220add, [39] and [42], by (Copy) 39] a!6220!6220sqr*(s(X)) >= a!6220!6220sqr(X) because a!6220!6220sqr in Mul and [40], by (Stat) 40] s(X) > X because [41], by definition 41] s*(X) >= X because [31], by (Select) 42] a!6220!6220sqr*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220sqr > a!6220!6220dbl and [43], by (Copy) 43] a!6220!6220sqr*(s(X)) >= X because [2], by (Select) 44] a!6220!6220dbl(_|_) >= _|_ by (Bot) 45] a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) because [46], by (Star) 46] a!6220!6220dbl*(s(X)) >= s(s(a!6220!6220dbl(X))) because a!6220!6220dbl > s and [47], by (Copy) 47] a!6220!6220dbl*(s(X)) >= s(a!6220!6220dbl(X)) because a!6220!6220dbl > s and [48], by (Copy) 48] a!6220!6220dbl*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220dbl in Mul and [40], by (Stat) 49] a!6220!6220add(_|_, X) >= X because [50], by (Star) 50] a!6220!6220add*(_|_, X) >= X because [31], by (Select) 51] a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) because [52], by (Star) 52] a!6220!6220add*(s(X), Y) >= s(a!6220!6220add(X, Y)) because a!6220!6220add > s and [53], by (Copy) 53] a!6220!6220add*(s(X), Y) >= a!6220!6220add(X, Y) because a!6220!6220add in Mul, [40] and [54], by (Stat) 54] Y >= Y by (Meta) 55] a!6220!6220first(s(X), Y) >= Y because [56], by (Star) 56] a!6220!6220first*(s(X), Y) >= Y because [57], by (Select) 57] Y >= Y by (Meta) 58] terms(X) >= a!6220!6220terms(X) because terms = a!6220!6220terms, terms in Mul and [59], by (Fun) 59] X >= X by (Meta) 60] sqr(X) >= a!6220!6220sqr(X) because sqr = a!6220!6220sqr, sqr in Mul and [59], by (Fun) 61] add(X, Y) >= a!6220!6220add(X, Y) because add = a!6220!6220add, add in Mul, [62] and [63], by (Fun) 62] X >= X by (Meta) 63] Y >= Y by (Meta) 64] dbl(X) >= a!6220!6220dbl(X) because dbl = a!6220!6220dbl, dbl in Mul and [59], by (Fun) 65] first(X, Y) >= a!6220!6220first(X, Y) because first = a!6220!6220first, first in Mul, [62] and [63], by (Fun) 66] X >= X by (Meta) 67] X >= X by (Meta) 68] s(X) >= s(X) because s in Mul and [59], by (Fun) 69] _|_ >= _|_ by (Bot) 70] a!6220!6220terms(X) >= terms(X) because a!6220!6220terms = terms, a!6220!6220terms in Mul and [59], by (Fun) 71] a!6220!6220sqr(X) >= sqr(X) because a!6220!6220sqr = sqr, a!6220!6220sqr in Mul and [59], by (Fun) 72] a!6220!6220add(X, Y) >= add(X, Y) because a!6220!6220add = add, a!6220!6220add in Mul, [62] and [63], by (Fun) 73] a!6220!6220dbl(X) >= dbl(X) because a!6220!6220dbl = dbl, a!6220!6220dbl in Mul and [59], by (Fun) 74] a!6220!6220first(X, Y) >= first(X, Y) because a!6220!6220first = first, a!6220!6220first in Mul, [62] and [63], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_6, R_1, minimal, formative) by (P_7, R_1, minimal, formative), where P_7 consists of: a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) =#> mark#(X) mark#(sqr(X)) =#> a!6220!6220sqr#(mark(X)) mark#(sqr(X)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(X) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) Thus, the original system is terminating if (P_7, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_7, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220sqr#(s(X)) >? a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) >? mark#(X) mark#(sqr(X)) >? a!6220!6220sqr#(mark(X)) mark#(sqr(X)) >? mark#(X) mark#(add(X, Y)) >? mark#(X) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(s(X)) >? mark#(X) a!6220!6220terms(X) >= cons(recip(a!6220!6220sqr(mark(X))), terms(s(X))) a!6220!6220sqr(0) >= 0 a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) >= 0 a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) >= mark(X) a!6220!6220add(s(X), Y) >= s(a!6220!6220add(mark(X), mark(Y))) a!6220!6220first(s(X), cons(Y, Z)) >= cons(mark(Y), first(X, Z)) mark(terms(X)) >= a!6220!6220terms(mark(X)) mark(sqr(X)) >= a!6220!6220sqr(mark(X)) mark(add(X, Y)) >= a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) >= a!6220!6220dbl(mark(X)) mark(first(X, Y)) >= a!6220!6220first(mark(X), mark(Y)) mark(cons(X, Y)) >= cons(mark(X), Y) mark(recip(X)) >= recip(mark(X)) mark(s(X)) >= s(mark(X)) mark(0) >= 0 a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) 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: [[cons(x_1, x_2)]] = cons(x_1) [[mark(x_1)]] = x_1 We choose Lex = {recip} and Mul = {0, a!6220!6220add, a!6220!6220dbl, a!6220!6220first, a!6220!6220sqr, a!6220!6220sqr#, a!6220!6220terms, add, cons, dbl, first, mark#, s, sqr, terms}, and the following precedence: a!6220!6220terms = terms > a!6220!6220sqr# = cons = mark# > a!6220!6220dbl = a!6220!6220sqr = dbl = sqr > a!6220!6220add = add > s > recip > 0 > a!6220!6220first = first Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) a!6220!6220sqr#(s(X)) >= mark#(X) mark#(sqr(X)) >= a!6220!6220sqr#(X) mark#(sqr(X)) >= mark#(X) mark#(add(X, Y)) >= mark#(X) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= mark#(X) mark#(first(X, Y)) >= mark#(Y) mark#(cons(X)) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(s(X)) > mark#(X) a!6220!6220terms(X) >= cons(recip(a!6220!6220sqr(X))) a!6220!6220sqr(0) >= 0 a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) a!6220!6220dbl(0) >= 0 a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) a!6220!6220add(0, X) >= X a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) a!6220!6220first(s(X), cons(Y)) >= cons(Y) terms(X) >= a!6220!6220terms(X) sqr(X) >= a!6220!6220sqr(X) add(X, Y) >= a!6220!6220add(X, Y) dbl(X) >= a!6220!6220dbl(X) first(X, Y) >= a!6220!6220first(X, Y) cons(X) >= cons(X) recip(X) >= recip(X) s(X) >= s(X) 0 >= 0 a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) With these choices, we have: 1] a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) because [2], by (Star) 2] a!6220!6220sqr#*(s(X)) >= a!6220!6220sqr#(X) because a!6220!6220sqr# in Mul and [3], by (Stat) 3] s(X) > X because [4], by definition 4] s*(X) >= X because [5], by (Select) 5] X >= X by (Meta) 6] a!6220!6220sqr#(s(X)) >= mark#(X) because [7], by (Star) 7] a!6220!6220sqr#*(s(X)) >= mark#(X) because a!6220!6220sqr# = mark#, a!6220!6220sqr# in Mul and [8], by (Stat) 8] s(X) > X because [4], by definition 9] mark#(sqr(X)) >= a!6220!6220sqr#(X) because mark# = a!6220!6220sqr#, mark# in Mul and [10], by (Fun) 10] sqr(X) >= X because [11], by (Star) 11] sqr*(X) >= X because [5], by (Select) 12] mark#(sqr(X)) >= mark#(X) because mark# in Mul and [10], by (Fun) 13] mark#(add(X, Y)) >= mark#(X) because mark# in Mul and [14], by (Fun) 14] add(X, Y) >= X because [15], by (Star) 15] add*(X, Y) >= X because [16], by (Select) 16] X >= X by (Meta) 17] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [18], by (Fun) 18] dbl(X) >= X because [19], by (Star) 19] dbl*(X) >= X because [5], by (Select) 20] mark#(first(X, Y)) >= mark#(X) because [21], by (Star) 21] mark#*(first(X, Y)) >= mark#(X) because mark# in Mul and [22], by (Stat) 22] first(X, Y) > X because [23], by definition 23] first*(X, Y) >= X because [16], by (Select) 24] mark#(first(X, Y)) >= mark#(Y) because mark# in Mul and [25], by (Fun) 25] first(X, Y) >= Y because [26], by (Star) 26] first*(X, Y) >= Y because [27], by (Select) 27] Y >= Y by (Meta) 28] mark#(cons(X)) >= mark#(X) because [29], by (Star) 29] mark#*(cons(X)) >= mark#(X) because [30], by (Select) 30] cons(X) >= mark#(X) because cons = mark#, cons in Mul and [31], by (Fun) 31] X >= X by (Meta) 32] mark#(recip(X)) >= mark#(X) because mark# in Mul and [33], by (Fun) 33] recip(X) >= X because [34], by (Star) 34] recip*(X) >= X because [5], by (Select) 35] mark#(s(X)) > mark#(X) because [36], by definition 36] mark#*(s(X)) >= mark#(X) because mark# in Mul and [8], by (Stat) 37] a!6220!6220terms(X) >= cons(recip(a!6220!6220sqr(X))) because [38], by (Star) 38] a!6220!6220terms*(X) >= cons(recip(a!6220!6220sqr(X))) because a!6220!6220terms > cons and [39], by (Copy) 39] a!6220!6220terms*(X) >= recip(a!6220!6220sqr(X)) because a!6220!6220terms > recip and [40], by (Copy) 40] a!6220!6220terms*(X) >= a!6220!6220sqr(X) because a!6220!6220terms > a!6220!6220sqr and [41], by (Copy) 41] a!6220!6220terms*(X) >= X because [42], by (Select) 42] X >= X by (Meta) 43] a!6220!6220sqr(0) >= 0 because [44], by (Star) 44] a!6220!6220sqr*(0) >= 0 because a!6220!6220sqr > 0, by (Copy) 45] a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because [46], by (Star) 46] a!6220!6220sqr*(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because a!6220!6220sqr > s and [47], by (Copy) 47] a!6220!6220sqr*(s(X)) >= a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X)) because a!6220!6220sqr > a!6220!6220add, [48] and [49], by (Copy) 48] a!6220!6220sqr*(s(X)) >= a!6220!6220sqr(X) because a!6220!6220sqr in Mul and [3], by (Stat) 49] a!6220!6220sqr*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220sqr = a!6220!6220dbl, a!6220!6220sqr in Mul and [3], by (Stat) 50] a!6220!6220dbl(0) >= 0 because [51], by (Star) 51] a!6220!6220dbl*(0) >= 0 because [52], by (Select) 52] 0 >= 0 by (Fun) 53] a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) because [54], by (Star) 54] a!6220!6220dbl*(s(X)) >= s(s(a!6220!6220dbl(X))) because a!6220!6220dbl > s and [55], by (Copy) 55] a!6220!6220dbl*(s(X)) >= s(a!6220!6220dbl(X)) because a!6220!6220dbl > s and [56], by (Copy) 56] a!6220!6220dbl*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220dbl in Mul and [3], by (Stat) 57] a!6220!6220add(0, X) >= X because [58], by (Star) 58] a!6220!6220add*(0, X) >= X because [5], by (Select) 59] a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) because [60], by (Star) 60] a!6220!6220add*(s(X), Y) >= s(a!6220!6220add(X, Y)) because a!6220!6220add > s and [61], by (Copy) 61] a!6220!6220add*(s(X), Y) >= a!6220!6220add(X, Y) because a!6220!6220add in Mul, [3] and [62], by (Stat) 62] Y >= Y by (Meta) 63] a!6220!6220first(s(X), cons(Y)) >= cons(Y) because [64], by (Star) 64] a!6220!6220first*(s(X), cons(Y)) >= cons(Y) because [65], by (Select) 65] cons(Y) >= cons(Y) because cons in Mul and [62], by (Fun) 66] terms(X) >= a!6220!6220terms(X) because terms = a!6220!6220terms, terms in Mul and [67], by (Fun) 67] X >= X by (Meta) 68] sqr(X) >= a!6220!6220sqr(X) because sqr = a!6220!6220sqr, sqr in Mul and [67], by (Fun) 69] add(X, Y) >= a!6220!6220add(X, Y) because add = a!6220!6220add, add in Mul, [70] and [71], by (Fun) 70] X >= X by (Meta) 71] Y >= Y by (Meta) 72] dbl(X) >= a!6220!6220dbl(X) because dbl = a!6220!6220dbl, dbl in Mul and [67], by (Fun) 73] first(X, Y) >= a!6220!6220first(X, Y) because first = a!6220!6220first, first in Mul, [70] and [71], by (Fun) 74] cons(X) >= cons(X) because cons in Mul and [70], by (Fun) 75] recip(X) >= recip(X) because [67], by (Fun) 76] s(X) >= s(X) because s in Mul and [67], by (Fun) 77] 0 >= 0 by (Fun) 78] a!6220!6220terms(X) >= terms(X) because a!6220!6220terms = terms, a!6220!6220terms in Mul and [67], by (Fun) 79] a!6220!6220sqr(X) >= sqr(X) because a!6220!6220sqr = sqr, a!6220!6220sqr in Mul and [67], by (Fun) 80] a!6220!6220add(X, Y) >= add(X, Y) because a!6220!6220add = add, a!6220!6220add in Mul, [70] and [71], by (Fun) 81] a!6220!6220dbl(X) >= dbl(X) because a!6220!6220dbl = dbl, a!6220!6220dbl in Mul and [67], by (Fun) 82] a!6220!6220first(X, Y) >= first(X, Y) because a!6220!6220first = first, a!6220!6220first in Mul, [70] and [71], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_7, R_1, minimal, formative) by (P_8, R_1, minimal, formative), where P_8 consists of: a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) =#> mark#(X) mark#(sqr(X)) =#> a!6220!6220sqr#(mark(X)) mark#(sqr(X)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(X) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) Thus, the original system is terminating if (P_8, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_8, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220sqr#(s(X)) >? a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) >? mark#(X) mark#(sqr(X)) >? a!6220!6220sqr#(mark(X)) mark#(sqr(X)) >? mark#(X) mark#(add(X, Y)) >? mark#(X) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) a!6220!6220terms(X) >= cons(recip(a!6220!6220sqr(mark(X))), terms(s(X))) a!6220!6220sqr(0) >= 0 a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) >= 0 a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) >= mark(X) a!6220!6220add(s(X), Y) >= s(a!6220!6220add(mark(X), mark(Y))) a!6220!6220first(s(X), cons(Y, Z)) >= cons(mark(Y), first(X, Z)) mark(terms(X)) >= a!6220!6220terms(mark(X)) mark(sqr(X)) >= a!6220!6220sqr(mark(X)) mark(add(X, Y)) >= a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) >= a!6220!6220dbl(mark(X)) mark(first(X, Y)) >= a!6220!6220first(mark(X), mark(Y)) mark(cons(X, Y)) >= cons(mark(X), Y) mark(recip(X)) >= recip(mark(X)) mark(s(X)) >= s(mark(X)) mark(0) >= 0 a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) 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]] = _|_ [[cons(x_1, x_2)]] = x_1 [[mark(x_1)]] = x_1 We choose Lex = {} and Mul = {a!6220!6220add, a!6220!6220dbl, a!6220!6220first, a!6220!6220sqr, a!6220!6220sqr#, a!6220!6220terms, add, dbl, first, mark#, recip, s, sqr, terms}, and the following precedence: a!6220!6220terms = terms > a!6220!6220dbl = a!6220!6220sqr = a!6220!6220sqr# = dbl = sqr > a!6220!6220add = add > mark# > s > a!6220!6220first = first > recip Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) a!6220!6220sqr#(s(X)) >= mark#(X) mark#(sqr(X)) > a!6220!6220sqr#(X) mark#(sqr(X)) >= mark#(X) mark#(add(X, Y)) >= mark#(X) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= mark#(X) mark#(first(X, Y)) >= mark#(Y) mark#(X) >= mark#(X) mark#(recip(X)) >= mark#(X) a!6220!6220terms(X) >= recip(a!6220!6220sqr(X)) a!6220!6220sqr(_|_) >= _|_ a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) a!6220!6220dbl(_|_) >= _|_ a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) a!6220!6220add(_|_, X) >= X a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) a!6220!6220first(s(X), Y) >= Y terms(X) >= a!6220!6220terms(X) sqr(X) >= a!6220!6220sqr(X) add(X, Y) >= a!6220!6220add(X, Y) dbl(X) >= a!6220!6220dbl(X) first(X, Y) >= a!6220!6220first(X, Y) X >= X recip(X) >= recip(X) s(X) >= s(X) _|_ >= _|_ a!6220!6220terms(X) >= terms(X) a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) a!6220!6220first(X, Y) >= first(X, Y) With these choices, we have: 1] a!6220!6220sqr#(s(X)) >= a!6220!6220sqr#(X) because [2], by (Star) 2] a!6220!6220sqr#*(s(X)) >= a!6220!6220sqr#(X) because a!6220!6220sqr# in Mul and [3], by (Stat) 3] s(X) > X because [4], by definition 4] s*(X) >= X because [5], by (Select) 5] X >= X by (Meta) 6] a!6220!6220sqr#(s(X)) >= mark#(X) because [7], by (Star) 7] a!6220!6220sqr#*(s(X)) >= mark#(X) because a!6220!6220sqr# > mark# and [8], by (Copy) 8] a!6220!6220sqr#*(s(X)) >= X because [9], by (Select) 9] s(X) >= X because [4], by (Star) 10] mark#(sqr(X)) > a!6220!6220sqr#(X) because [11], by definition 11] mark#*(sqr(X)) >= a!6220!6220sqr#(X) because [12], by (Select) 12] sqr(X) >= a!6220!6220sqr#(X) because sqr = a!6220!6220sqr#, sqr in Mul and [13], by (Fun) 13] X >= X by (Meta) 14] mark#(sqr(X)) >= mark#(X) because mark# in Mul and [15], by (Fun) 15] sqr(X) >= X because [16], by (Star) 16] sqr*(X) >= X because [13], by (Select) 17] mark#(add(X, Y)) >= mark#(X) because mark# in Mul and [18], by (Fun) 18] add(X, Y) >= X because [19], by (Star) 19] add*(X, Y) >= X because [20], by (Select) 20] X >= X by (Meta) 21] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [22], by (Fun) 22] dbl(X) >= X because [23], by (Star) 23] dbl*(X) >= X because [13], by (Select) 24] mark#(first(X, Y)) >= mark#(X) because mark# in Mul and [25], by (Fun) 25] first(X, Y) >= X because [26], by (Star) 26] first*(X, Y) >= X because [20], by (Select) 27] mark#(first(X, Y)) >= mark#(Y) because mark# in Mul and [28], by (Fun) 28] first(X, Y) >= Y because [29], by (Star) 29] first*(X, Y) >= Y because [30], by (Select) 30] Y >= Y by (Meta) 31] mark#(X) >= mark#(X) because mark# in Mul and [32], by (Fun) 32] X >= X by (Meta) 33] mark#(recip(X)) >= mark#(X) because mark# in Mul and [34], by (Fun) 34] recip(X) >= X because [35], by (Star) 35] recip*(X) >= X because [13], by (Select) 36] a!6220!6220terms(X) >= recip(a!6220!6220sqr(X)) because [37], by (Star) 37] a!6220!6220terms*(X) >= recip(a!6220!6220sqr(X)) because a!6220!6220terms > recip and [38], by (Copy) 38] a!6220!6220terms*(X) >= a!6220!6220sqr(X) because a!6220!6220terms > a!6220!6220sqr and [39], by (Copy) 39] a!6220!6220terms*(X) >= X because [40], by (Select) 40] X >= X by (Meta) 41] a!6220!6220sqr(_|_) >= _|_ by (Bot) 42] a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because [43], by (Star) 43] a!6220!6220sqr*(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because a!6220!6220sqr > s and [44], by (Copy) 44] a!6220!6220sqr*(s(X)) >= a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X)) because a!6220!6220sqr > a!6220!6220add, [45] and [46], by (Copy) 45] a!6220!6220sqr*(s(X)) >= a!6220!6220sqr(X) because a!6220!6220sqr in Mul and [3], by (Stat) 46] a!6220!6220sqr*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220sqr = a!6220!6220dbl, a!6220!6220sqr in Mul and [3], by (Stat) 47] a!6220!6220dbl(_|_) >= _|_ by (Bot) 48] a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) because [49], by (Star) 49] a!6220!6220dbl*(s(X)) >= s(s(a!6220!6220dbl(X))) because a!6220!6220dbl > s and [50], by (Copy) 50] a!6220!6220dbl*(s(X)) >= s(a!6220!6220dbl(X)) because a!6220!6220dbl > s and [51], by (Copy) 51] a!6220!6220dbl*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220dbl in Mul and [3], by (Stat) 52] a!6220!6220add(_|_, X) >= X because [53], by (Star) 53] a!6220!6220add*(_|_, X) >= X because [13], by (Select) 54] a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) because [55], by (Star) 55] a!6220!6220add*(s(X), Y) >= s(a!6220!6220add(X, Y)) because a!6220!6220add > s and [56], by (Copy) 56] a!6220!6220add*(s(X), Y) >= a!6220!6220add(X, Y) because a!6220!6220add in Mul, [3] and [57], by (Stat) 57] Y >= Y by (Meta) 58] a!6220!6220first(s(X), Y) >= Y because [59], by (Star) 59] a!6220!6220first*(s(X), Y) >= Y because [60], by (Select) 60] Y >= Y by (Meta) 61] terms(X) >= a!6220!6220terms(X) because terms = a!6220!6220terms, terms in Mul and [13], by (Fun) 62] sqr(X) >= a!6220!6220sqr(X) because sqr = a!6220!6220sqr, sqr in Mul and [13], by (Fun) 63] add(X, Y) >= a!6220!6220add(X, Y) because add = a!6220!6220add, add in Mul, [64] and [65], by (Fun) 64] X >= X by (Meta) 65] Y >= Y by (Meta) 66] dbl(X) >= a!6220!6220dbl(X) because dbl = a!6220!6220dbl, dbl in Mul and [13], by (Fun) 67] first(X, Y) >= a!6220!6220first(X, Y) because first = a!6220!6220first, first in Mul, [64] and [65], by (Fun) 68] X >= X by (Meta) 69] recip(X) >= recip(X) because recip in Mul and [13], by (Fun) 70] s(X) >= s(X) because s in Mul and [13], by (Fun) 71] _|_ >= _|_ by (Bot) 72] a!6220!6220terms(X) >= terms(X) because a!6220!6220terms = terms, a!6220!6220terms in Mul and [13], by (Fun) 73] a!6220!6220sqr(X) >= sqr(X) because a!6220!6220sqr = sqr, a!6220!6220sqr in Mul and [13], by (Fun) 74] a!6220!6220add(X, Y) >= add(X, Y) because a!6220!6220add = add, a!6220!6220add in Mul, [64] and [65], by (Fun) 75] a!6220!6220dbl(X) >= dbl(X) because a!6220!6220dbl = dbl, a!6220!6220dbl in Mul and [13], by (Fun) 76] a!6220!6220first(X, Y) >= first(X, Y) because a!6220!6220first = first, a!6220!6220first in Mul, [64] and [65], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_8, R_1, minimal, formative) by (P_9, R_1, minimal, formative), where P_9 consists of: a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X)) a!6220!6220sqr#(s(X)) =#> mark#(X) mark#(sqr(X)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(X) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) Thus, the original system is terminating if (P_9, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_9, R_1, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 0, 1 * 1 : 2, 3, 4, 5, 6, 7, 8 * 2 : 2, 3, 4, 5, 6, 7, 8 * 3 : 2, 3, 4, 5, 6, 7, 8 * 4 : 2, 3, 4, 5, 6, 7, 8 * 5 : 2, 3, 4, 5, 6, 7, 8 * 6 : 2, 3, 4, 5, 6, 7, 8 * 7 : 2, 3, 4, 5, 6, 7, 8 * 8 : 2, 3, 4, 5, 6, 7, 8 This graph has the following strongly connected components: P_10: a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X)) P_11: mark#(sqr(X)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(X) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_9, R_1, m, f) by (P_10, R_1, m, f) and (P_11, R_1, m, f). Thus, the original system is terminating if each of (P_10, R_1, minimal, formative) and (P_11, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_11, R_1, minimal, formative). We apply the subterm criterion with the following projection function: nu(mark#) = 1 Thus, we can orient the dependency pairs as follows: nu(mark#(sqr(X))) = sqr(X) |> X = nu(mark#(X)) nu(mark#(add(X, Y))) = add(X, Y) |> X = nu(mark#(X)) nu(mark#(dbl(X))) = dbl(X) |> X = nu(mark#(X)) nu(mark#(first(X, Y))) = first(X, Y) |> X = nu(mark#(X)) nu(mark#(first(X, Y))) = first(X, Y) |> Y = nu(mark#(Y)) nu(mark#(cons(X, Y))) = cons(X, Y) |> X = nu(mark#(X)) nu(mark#(recip(X))) = recip(X) |> X = nu(mark#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_11, R_1, minimal, f) by ({}, R_1, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if (P_10, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_10, R_1, minimal, formative). The formative rules of (P_10, R_1) are exactly R_2: a!6220!6220sqr(0) => 0 a!6220!6220sqr(s(X)) => s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) => 0 a!6220!6220dbl(s(X)) => s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) => mark(X) a!6220!6220add(s(X), Y) => s(a!6220!6220add(mark(X), mark(Y))) mark(sqr(X)) => a!6220!6220sqr(mark(X)) mark(add(X, Y)) => a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) => a!6220!6220dbl(mark(X)) mark(s(X)) => s(mark(X)) mark(0) => 0 a!6220!6220sqr(X) => sqr(X) a!6220!6220add(X, Y) => add(X, Y) a!6220!6220dbl(X) => dbl(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_10, R_1, minimal, formative) by (P_10, R_2, minimal, formative). Thus, the original system is terminating if (P_10, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_10, R_2, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220sqr#(s(X)) >? a!6220!6220sqr#(mark(X)) a!6220!6220sqr(0) >= 0 a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) a!6220!6220dbl(0) >= 0 a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(mark(X)))) a!6220!6220add(0, X) >= mark(X) a!6220!6220add(s(X), Y) >= s(a!6220!6220add(mark(X), mark(Y))) mark(sqr(X)) >= a!6220!6220sqr(mark(X)) mark(add(X, Y)) >= a!6220!6220add(mark(X), mark(Y)) mark(dbl(X)) >= a!6220!6220dbl(mark(X)) mark(s(X)) >= s(mark(X)) mark(0) >= 0 a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(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]] = _|_ [[a!6220!6220sqr#(x_1)]] = x_1 [[mark(x_1)]] = x_1 We choose Lex = {} and Mul = {a!6220!6220add, a!6220!6220dbl, a!6220!6220sqr, add, dbl, s, sqr}, and the following precedence: a!6220!6220sqr = sqr > a!6220!6220add = add > a!6220!6220dbl = dbl > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: s(X) > X a!6220!6220sqr(_|_) >= _|_ a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) a!6220!6220dbl(_|_) >= _|_ a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) a!6220!6220add(_|_, X) >= X a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) sqr(X) >= a!6220!6220sqr(X) add(X, Y) >= a!6220!6220add(X, Y) dbl(X) >= a!6220!6220dbl(X) s(X) >= s(X) _|_ >= _|_ a!6220!6220sqr(X) >= sqr(X) a!6220!6220add(X, Y) >= add(X, Y) a!6220!6220dbl(X) >= dbl(X) With these choices, we have: 1] s(X) > X because [2], by definition 2] s*(X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] a!6220!6220sqr(_|_) >= _|_ by (Bot) 5] a!6220!6220sqr(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because [6], by (Star) 6] a!6220!6220sqr*(s(X)) >= s(a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X))) because a!6220!6220sqr > s and [7], by (Copy) 7] a!6220!6220sqr*(s(X)) >= a!6220!6220add(a!6220!6220sqr(X), a!6220!6220dbl(X)) because a!6220!6220sqr > a!6220!6220add, [8] and [10], by (Copy) 8] a!6220!6220sqr*(s(X)) >= a!6220!6220sqr(X) because a!6220!6220sqr in Mul and [9], by (Stat) 9] s(X) > X because [2], by definition 10] a!6220!6220sqr*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220sqr > a!6220!6220dbl and [11], by (Copy) 11] a!6220!6220sqr*(s(X)) >= X because [12], by (Select) 12] s(X) >= X because [2], by (Star) 13] a!6220!6220dbl(_|_) >= _|_ by (Bot) 14] a!6220!6220dbl(s(X)) >= s(s(a!6220!6220dbl(X))) because [15], by (Star) 15] a!6220!6220dbl*(s(X)) >= s(s(a!6220!6220dbl(X))) because a!6220!6220dbl > s and [16], by (Copy) 16] a!6220!6220dbl*(s(X)) >= s(a!6220!6220dbl(X)) because a!6220!6220dbl > s and [17], by (Copy) 17] a!6220!6220dbl*(s(X)) >= a!6220!6220dbl(X) because a!6220!6220dbl in Mul and [9], by (Stat) 18] a!6220!6220add(_|_, X) >= X because [19], by (Star) 19] a!6220!6220add*(_|_, X) >= X because [3], by (Select) 20] a!6220!6220add(s(X), Y) >= s(a!6220!6220add(X, Y)) because [21], by (Star) 21] a!6220!6220add*(s(X), Y) >= s(a!6220!6220add(X, Y)) because a!6220!6220add > s and [22], by (Copy) 22] a!6220!6220add*(s(X), Y) >= a!6220!6220add(X, Y) because a!6220!6220add in Mul, [9] and [23], by (Stat) 23] Y >= Y by (Meta) 24] sqr(X) >= a!6220!6220sqr(X) because sqr = a!6220!6220sqr, sqr in Mul and [25], by (Fun) 25] X >= X by (Meta) 26] add(X, Y) >= a!6220!6220add(X, Y) because add = a!6220!6220add, add in Mul, [27] and [28], by (Fun) 27] X >= X by (Meta) 28] Y >= Y by (Meta) 29] dbl(X) >= a!6220!6220dbl(X) because dbl = a!6220!6220dbl, dbl in Mul and [25], by (Fun) 30] s(X) >= s(X) because s in Mul and [25], by (Fun) 31] _|_ >= _|_ by (Bot) 32] a!6220!6220sqr(X) >= sqr(X) because a!6220!6220sqr = sqr, a!6220!6220sqr in Mul and [25], by (Fun) 33] a!6220!6220add(X, Y) >= add(X, Y) because a!6220!6220add = add, a!6220!6220add in Mul, [27] and [28], by (Fun) 34] a!6220!6220dbl(X) >= dbl(X) because a!6220!6220dbl = dbl, a!6220!6220dbl in Mul and [25], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_10, R_2) by ({}, R_2). 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.