/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o active : [o] --> o add : [o * o] --> o cons : [o * o] --> o dbl : [o] --> o first : [o * o] --> o half : [o] --> o mark : [o] --> o nil : [] --> o recip : [o] --> o s : [o] --> o sqr : [o] --> o terms : [o] --> o active(terms(X)) => mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) => mark(0) active(sqr(s(X))) => mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) => mark(0) active(dbl(s(X))) => mark(s(s(dbl(X)))) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(half(0)) => mark(0) active(half(s(0))) => mark(0) active(half(s(s(X)))) => mark(s(half(X))) active(half(dbl(X))) => mark(X) mark(terms(X)) => active(terms(mark(X))) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(recip(X)) => active(recip(mark(X))) mark(sqr(X)) => active(sqr(mark(X))) mark(s(X)) => active(s(mark(X))) mark(0) => active(0) mark(add(X, Y)) => active(add(mark(X), mark(Y))) mark(dbl(X)) => active(dbl(mark(X))) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(half(X)) => active(half(mark(X))) terms(mark(X)) => terms(X) terms(active(X)) => terms(X) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) recip(mark(X)) => recip(X) recip(active(X)) => recip(X) sqr(mark(X)) => sqr(X) sqr(active(X)) => sqr(X) s(mark(X)) => s(X) s(active(X)) => s(X) add(mark(X), Y) => add(X, Y) add(X, mark(Y)) => add(X, Y) add(active(X), Y) => add(X, Y) add(X, active(Y)) => add(X, Y) dbl(mark(X)) => dbl(X) dbl(active(X)) => dbl(X) first(mark(X), Y) => first(X, Y) first(X, mark(Y)) => first(X, Y) first(active(X), Y) => first(X, Y) first(X, active(Y)) => first(X, Y) half(mark(X)) => half(X) half(active(X)) => half(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] active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) 1] active#(terms(X)) =#> cons#(recip(sqr(X)), terms(s(X))) 2] active#(terms(X)) =#> recip#(sqr(X)) 3] active#(terms(X)) =#> sqr#(X) 4] active#(terms(X)) =#> terms#(s(X)) 5] active#(terms(X)) =#> s#(X) 6] active#(sqr(0)) =#> mark#(0) 7] active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) 8] active#(sqr(s(X))) =#> s#(add(sqr(X), dbl(X))) 9] active#(sqr(s(X))) =#> add#(sqr(X), dbl(X)) 10] active#(sqr(s(X))) =#> sqr#(X) 11] active#(sqr(s(X))) =#> dbl#(X) 12] active#(dbl(0)) =#> mark#(0) 13] active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) 14] active#(dbl(s(X))) =#> s#(s(dbl(X))) 15] active#(dbl(s(X))) =#> s#(dbl(X)) 16] active#(dbl(s(X))) =#> dbl#(X) 17] active#(add(0, X)) =#> mark#(X) 18] active#(add(s(X), Y)) =#> mark#(s(add(X, Y))) 19] active#(add(s(X), Y)) =#> s#(add(X, Y)) 20] active#(add(s(X), Y)) =#> add#(X, Y) 21] active#(first(0, X)) =#> mark#(nil) 22] active#(first(s(X), cons(Y, Z))) =#> mark#(cons(Y, first(X, Z))) 23] active#(first(s(X), cons(Y, Z))) =#> cons#(Y, first(X, Z)) 24] active#(first(s(X), cons(Y, Z))) =#> first#(X, Z) 25] active#(half(0)) =#> mark#(0) 26] active#(half(s(0))) =#> mark#(0) 27] active#(half(s(s(X)))) =#> mark#(s(half(X))) 28] active#(half(s(s(X)))) =#> s#(half(X)) 29] active#(half(s(s(X)))) =#> half#(X) 30] active#(half(dbl(X))) =#> mark#(X) 31] mark#(terms(X)) =#> active#(terms(mark(X))) 32] mark#(terms(X)) =#> terms#(mark(X)) 33] mark#(terms(X)) =#> mark#(X) 34] mark#(cons(X, Y)) =#> active#(cons(mark(X), Y)) 35] mark#(cons(X, Y)) =#> cons#(mark(X), Y) 36] mark#(cons(X, Y)) =#> mark#(X) 37] mark#(recip(X)) =#> active#(recip(mark(X))) 38] mark#(recip(X)) =#> recip#(mark(X)) 39] mark#(recip(X)) =#> mark#(X) 40] mark#(sqr(X)) =#> active#(sqr(mark(X))) 41] mark#(sqr(X)) =#> sqr#(mark(X)) 42] mark#(sqr(X)) =#> mark#(X) 43] mark#(s(X)) =#> active#(s(mark(X))) 44] mark#(s(X)) =#> s#(mark(X)) 45] mark#(s(X)) =#> mark#(X) 46] mark#(0) =#> active#(0) 47] mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) 48] mark#(add(X, Y)) =#> add#(mark(X), mark(Y)) 49] mark#(add(X, Y)) =#> mark#(X) 50] mark#(add(X, Y)) =#> mark#(Y) 51] mark#(dbl(X)) =#> active#(dbl(mark(X))) 52] mark#(dbl(X)) =#> dbl#(mark(X)) 53] mark#(dbl(X)) =#> mark#(X) 54] mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) 55] mark#(first(X, Y)) =#> first#(mark(X), mark(Y)) 56] mark#(first(X, Y)) =#> mark#(X) 57] mark#(first(X, Y)) =#> mark#(Y) 58] mark#(nil) =#> active#(nil) 59] mark#(half(X)) =#> active#(half(mark(X))) 60] mark#(half(X)) =#> half#(mark(X)) 61] mark#(half(X)) =#> mark#(X) 62] terms#(mark(X)) =#> terms#(X) 63] terms#(active(X)) =#> terms#(X) 64] cons#(mark(X), Y) =#> cons#(X, Y) 65] cons#(X, mark(Y)) =#> cons#(X, Y) 66] cons#(active(X), Y) =#> cons#(X, Y) 67] cons#(X, active(Y)) =#> cons#(X, Y) 68] recip#(mark(X)) =#> recip#(X) 69] recip#(active(X)) =#> recip#(X) 70] sqr#(mark(X)) =#> sqr#(X) 71] sqr#(active(X)) =#> sqr#(X) 72] s#(mark(X)) =#> s#(X) 73] s#(active(X)) =#> s#(X) 74] add#(mark(X), Y) =#> add#(X, Y) 75] add#(X, mark(Y)) =#> add#(X, Y) 76] add#(active(X), Y) =#> add#(X, Y) 77] add#(X, active(Y)) =#> add#(X, Y) 78] dbl#(mark(X)) =#> dbl#(X) 79] dbl#(active(X)) =#> dbl#(X) 80] first#(mark(X), Y) =#> first#(X, Y) 81] first#(X, mark(Y)) =#> first#(X, Y) 82] first#(active(X), Y) =#> first#(X, Y) 83] first#(X, active(Y)) =#> first#(X, Y) 84] half#(mark(X)) =#> half#(X) 85] half#(active(X)) =#> half#(X) Rules R_0: active(terms(X)) => mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) => mark(0) active(sqr(s(X))) => mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) => mark(0) active(dbl(s(X))) => mark(s(s(dbl(X)))) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(half(0)) => mark(0) active(half(s(0))) => mark(0) active(half(s(s(X)))) => mark(s(half(X))) active(half(dbl(X))) => mark(X) mark(terms(X)) => active(terms(mark(X))) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(recip(X)) => active(recip(mark(X))) mark(sqr(X)) => active(sqr(mark(X))) mark(s(X)) => active(s(mark(X))) mark(0) => active(0) mark(add(X, Y)) => active(add(mark(X), mark(Y))) mark(dbl(X)) => active(dbl(mark(X))) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(half(X)) => active(half(mark(X))) terms(mark(X)) => terms(X) terms(active(X)) => terms(X) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) recip(mark(X)) => recip(X) recip(active(X)) => recip(X) sqr(mark(X)) => sqr(X) sqr(active(X)) => sqr(X) s(mark(X)) => s(X) s(active(X)) => s(X) add(mark(X), Y) => add(X, Y) add(X, mark(Y)) => add(X, Y) add(active(X), Y) => add(X, Y) add(X, active(Y)) => add(X, Y) dbl(mark(X)) => dbl(X) dbl(active(X)) => dbl(X) first(mark(X), Y) => first(X, Y) first(X, mark(Y)) => first(X, Y) first(active(X), Y) => first(X, Y) first(X, active(Y)) => first(X, Y) half(mark(X)) => half(X) half(active(X)) => half(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 : 34, 35, 36 * 1 : * 2 : * 3 : 70, 71 * 4 : * 5 : 72, 73 * 6 : 46 * 7 : 43, 44, 45 * 8 : * 9 : * 10 : 70, 71 * 11 : 78, 79 * 12 : 46 * 13 : 43, 44, 45 * 14 : * 15 : * 16 : 78, 79 * 17 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 18 : 43, 44, 45 * 19 : * 20 : 74, 75, 76, 77 * 21 : 58 * 22 : 34, 35, 36 * 23 : 64, 66 * 24 : 80, 81, 82, 83 * 25 : 46 * 26 : 46 * 27 : 43, 44, 45 * 28 : * 29 : 84, 85 * 30 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 31 : 0, 1, 2, 3, 4, 5 * 32 : 62, 63 * 33 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 34 : * 35 : 64, 65, 66, 67 * 36 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 37 : * 38 : 68, 69 * 39 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 40 : 6, 7, 8, 9, 10, 11 * 41 : 70, 71 * 42 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 43 : * 44 : 72, 73 * 45 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 46 : * 47 : 17, 18, 19, 20 * 48 : 74, 75, 76, 77 * 49 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 50 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 51 : 12, 13, 14, 15, 16 * 52 : 78, 79 * 53 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 54 : 21, 22, 23, 24 * 55 : 80, 81, 82, 83 * 56 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 57 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 58 : * 59 : 25, 26, 27, 28, 29, 30 * 60 : 84, 85 * 61 : 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 * 62 : 62, 63 * 63 : 62, 63 * 64 : 64, 65, 66, 67 * 65 : 64, 65, 66, 67 * 66 : 64, 65, 66, 67 * 67 : 64, 65, 66, 67 * 68 : 68, 69 * 69 : 68, 69 * 70 : 70, 71 * 71 : 70, 71 * 72 : 72, 73 * 73 : 72, 73 * 74 : 74, 75, 76, 77 * 75 : 74, 75, 76, 77 * 76 : 74, 75, 76, 77 * 77 : 74, 75, 76, 77 * 78 : 78, 79 * 79 : 78, 79 * 80 : 80, 81, 82, 83 * 81 : 80, 81, 82, 83 * 82 : 80, 81, 82, 83 * 83 : 80, 81, 82, 83 * 84 : 84, 85 * 85 : 84, 85 This graph has the following strongly connected components: P_1: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(add(s(X), Y)) =#> mark#(s(add(X, Y))) active#(first(s(X), cons(Y, Z))) =#> mark#(cons(Y, first(X, Z))) active#(half(s(s(X)))) =#> mark#(s(half(X))) active#(half(dbl(X))) =#> mark#(X) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(sqr(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(half(X)) =#> active#(half(mark(X))) mark#(half(X)) =#> mark#(X) P_2: terms#(mark(X)) =#> terms#(X) terms#(active(X)) =#> terms#(X) P_3: cons#(mark(X), Y) =#> cons#(X, Y) cons#(X, mark(Y)) =#> cons#(X, Y) cons#(active(X), Y) =#> cons#(X, Y) cons#(X, active(Y)) =#> cons#(X, Y) P_4: recip#(mark(X)) =#> recip#(X) recip#(active(X)) =#> recip#(X) P_5: sqr#(mark(X)) =#> sqr#(X) sqr#(active(X)) =#> sqr#(X) P_6: s#(mark(X)) =#> s#(X) s#(active(X)) =#> s#(X) P_7: add#(mark(X), Y) =#> add#(X, Y) add#(X, mark(Y)) =#> add#(X, Y) add#(active(X), Y) =#> add#(X, Y) add#(X, active(Y)) =#> add#(X, Y) P_8: dbl#(mark(X)) =#> dbl#(X) dbl#(active(X)) =#> dbl#(X) P_9: first#(mark(X), Y) =#> first#(X, Y) first#(X, mark(Y)) =#> first#(X, Y) first#(active(X), Y) =#> first#(X, Y) first#(X, active(Y)) =#> first#(X, Y) P_10: half#(mark(X)) =#> half#(X) half#(active(X)) =#> half#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f), (P_2, R_0, m, f), (P_3, R_0, m, f), (P_4, R_0, m, f), (P_5, R_0, m, f), (P_6, R_0, m, f), (P_7, R_0, m, f), (P_8, R_0, m, f), (P_9, R_0, m, f) and (P_10, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative), (P_9, R_0, minimal, formative) and (P_10, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_10, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(half#) = 1 Thus, we can orient the dependency pairs as follows: nu(half#(mark(X))) = mark(X) |> X = nu(half#(X)) nu(half#(active(X))) = active(X) |> X = nu(half#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_10, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative) and (P_9, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_9, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(first#) = 1 Thus, we can orient the dependency pairs as follows: nu(first#(mark(X), Y)) = mark(X) |> X = nu(first#(X, Y)) nu(first#(X, mark(Y))) = X = X = nu(first#(X, Y)) nu(first#(active(X), Y)) = active(X) |> X = nu(first#(X, Y)) nu(first#(X, active(Y))) = X = X = nu(first#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_9, R_0, minimal, f) by (P_11, R_0, minimal, f), where P_11 contains: first#(X, mark(Y)) =#> first#(X, Y) first#(X, active(Y)) =#> first#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative) and (P_11, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_11, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(first#) = 2 Thus, we can orient the dependency pairs as follows: nu(first#(X, mark(Y))) = mark(Y) |> Y = nu(first#(X, Y)) nu(first#(X, active(Y))) = active(Y) |> Y = nu(first#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_11, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative) and (P_8, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_8, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(dbl#) = 1 Thus, we can orient the dependency pairs as follows: nu(dbl#(mark(X))) = mark(X) |> X = nu(dbl#(X)) nu(dbl#(active(X))) = active(X) |> X = nu(dbl#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_8, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative) and (P_7, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_7, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(add#) = 1 Thus, we can orient the dependency pairs as follows: nu(add#(mark(X), Y)) = mark(X) |> X = nu(add#(X, Y)) nu(add#(X, mark(Y))) = X = X = nu(add#(X, Y)) nu(add#(active(X), Y)) = active(X) |> X = nu(add#(X, Y)) nu(add#(X, active(Y))) = X = X = nu(add#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_7, R_0, minimal, f) by (P_12, R_0, minimal, f), where P_12 contains: add#(X, mark(Y)) =#> add#(X, Y) add#(X, active(Y)) =#> add#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative) and (P_12, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_12, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(add#) = 2 Thus, we can orient the dependency pairs as follows: nu(add#(X, mark(Y))) = mark(Y) |> Y = nu(add#(X, Y)) nu(add#(X, active(Y))) = active(Y) |> Y = nu(add#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_12, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative) and (P_6, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_6, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(s#) = 1 Thus, we can orient the dependency pairs as follows: nu(s#(mark(X))) = mark(X) |> X = nu(s#(X)) nu(s#(active(X))) = active(X) |> X = nu(s#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_6, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative) and (P_5, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_5, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(sqr#) = 1 Thus, we can orient the dependency pairs as follows: nu(sqr#(mark(X))) = mark(X) |> X = nu(sqr#(X)) nu(sqr#(active(X))) = active(X) |> X = nu(sqr#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_5, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative) and (P_4, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(recip#) = 1 Thus, we can orient the dependency pairs as follows: nu(recip#(mark(X))) = mark(X) |> X = nu(recip#(X)) nu(recip#(active(X))) = active(X) |> X = nu(recip#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_4, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative) and (P_3, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_3, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(cons#) = 1 Thus, we can orient the dependency pairs as follows: nu(cons#(mark(X), Y)) = mark(X) |> X = nu(cons#(X, Y)) nu(cons#(X, mark(Y))) = X = X = nu(cons#(X, Y)) nu(cons#(active(X), Y)) = active(X) |> X = nu(cons#(X, Y)) nu(cons#(X, active(Y))) = X = X = nu(cons#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_3, R_0, minimal, f) by (P_13, R_0, minimal, f), where P_13 contains: cons#(X, mark(Y)) =#> cons#(X, Y) cons#(X, active(Y)) =#> cons#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative) and (P_13, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_13, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(cons#) = 2 Thus, we can orient the dependency pairs as follows: nu(cons#(X, mark(Y))) = mark(Y) |> Y = nu(cons#(X, Y)) nu(cons#(X, active(Y))) = active(Y) |> Y = nu(cons#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_13, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(terms#) = 1 Thus, we can orient the dependency pairs as follows: nu(terms#(mark(X))) = mark(X) |> X = nu(terms#(X)) nu(terms#(active(X))) = active(X) |> X = nu(terms#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_2, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) >? mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(add(s(X), Y)) >? mark#(s(add(X, Y))) active#(first(s(X), cons(Y, Z))) >? mark#(cons(Y, first(X, Z))) active#(half(s(s(X)))) >? mark#(s(half(X))) active#(half(dbl(X))) >? mark#(X) mark#(terms(X)) >? active#(terms(mark(X))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(sqr(X)) >? active#(sqr(mark(X))) mark#(sqr(X)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(add(X, Y)) >? mark#(X) mark#(add(X, Y)) >? mark#(Y) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? active#(first(mark(X), mark(Y))) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) mark#(half(X)) >? active#(half(mark(X))) mark#(half(X)) >? mark#(X) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) sqr(mark(X)) >= sqr(X) sqr(active(X)) >= sqr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) first(mark(X), Y) >= first(X, Y) first(X, mark(Y)) >= first(X, Y) first(active(X), Y) >= first(X, Y) first(X, active(Y)) >= first(X, Y) half(mark(X)) >= half(X) half(active(X)) >= half(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]] = _|_ [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = cons(x_1) [[mark(x_1)]] = x_1 [[nil]] = _|_ We choose Lex = {} and Mul = {active#, add, cons, dbl, first, half, mark#, recip, s, sqr, terms}, and the following precedence: first > half > terms > sqr > cons > dbl > add > active# = mark# = recip > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(terms(X)) >= mark#(cons(recip(sqr(X)))) active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(add(_|_, X)) >= mark#(X) active#(add(s(X), Y)) > mark#(s(add(X, Y))) active#(first(s(X), cons(Y))) >= mark#(cons(Y)) active#(half(s(s(X)))) >= mark#(s(half(X))) active#(half(dbl(X))) >= mark#(X) mark#(terms(X)) >= active#(terms(X)) mark#(terms(X)) >= mark#(X) mark#(cons(X)) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(sqr(X)) >= active#(sqr(X)) mark#(sqr(X)) >= mark#(X) mark#(s(X)) >= mark#(X) mark#(add(X, Y)) >= active#(add(X, Y)) mark#(add(X, Y)) >= mark#(X) mark#(add(X, Y)) >= mark#(Y) mark#(dbl(X)) >= active#(dbl(X)) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= active#(first(X, Y)) mark#(first(X, Y)) >= mark#(X) mark#(first(X, Y)) >= mark#(Y) mark#(half(X)) >= active#(half(X)) mark#(half(X)) >= mark#(X) terms(X) >= cons(recip(sqr(X))) sqr(_|_) >= _|_ sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(_|_) >= _|_ dbl(s(X)) >= s(s(dbl(X))) add(_|_, X) >= X add(s(X), Y) >= s(add(X, Y)) first(_|_, X) >= _|_ first(s(X), cons(Y)) >= cons(Y) half(_|_) >= _|_ half(s(_|_)) >= _|_ half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms(X) >= terms(X) cons(X) >= cons(X) recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) _|_ >= _|_ add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) _|_ >= _|_ half(X) >= half(X) terms(X) >= terms(X) terms(X) >= terms(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) recip(X) >= recip(X) recip(X) >= recip(X) sqr(X) >= sqr(X) sqr(X) >= sqr(X) s(X) >= s(X) s(X) >= s(X) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(terms(X)) >= mark#(cons(recip(sqr(X)))) because [2], by (Star) 2] active#*(terms(X)) >= mark#(cons(recip(sqr(X)))) because active# = mark#, active# in Mul and [3], by (Stat) 3] terms(X) > cons(recip(sqr(X))) because [4], by definition 4] terms*(X) >= cons(recip(sqr(X))) because terms > cons and [5], by (Copy) 5] terms*(X) >= recip(sqr(X)) because terms > recip and [6], by (Copy) 6] terms*(X) >= sqr(X) because terms > sqr and [7], by (Copy) 7] terms*(X) >= X because [8], by (Select) 8] X >= X by (Meta) 9] active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because active# = mark#, active# in Mul and [10], by (Fun) 10] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [11], by (Star) 11] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [12], by (Copy) 12] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [13] and [17], by (Copy) 13] sqr*(s(X)) >= sqr(X) because sqr in Mul and [14], by (Stat) 14] s(X) > X because [15], by definition 15] s*(X) >= X because [16], by (Select) 16] X >= X by (Meta) 17] sqr*(s(X)) >= dbl(X) because sqr > dbl and [18], by (Copy) 18] sqr*(s(X)) >= X because [19], by (Select) 19] s(X) >= X because [15], by (Star) 20] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because [21], by (Star) 21] active#*(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [22], by (Stat) 22] dbl(s(X)) > s(s(dbl(X))) because [23], by definition 23] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [24], by (Copy) 24] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [25], by (Copy) 25] dbl*(s(X)) >= dbl(X) because dbl in Mul and [14], by (Stat) 26] active#(add(_|_, X)) >= mark#(X) because active# = mark#, active# in Mul and [27], by (Fun) 27] add(_|_, X) >= X because [28], by (Star) 28] add*(_|_, X) >= X because [16], by (Select) 29] active#(add(s(X), Y)) > mark#(s(add(X, Y))) because [30], by definition 30] active#*(add(s(X), Y)) >= mark#(s(add(X, Y))) because active# = mark#, active# in Mul and [31], by (Stat) 31] add(s(X), Y) > s(add(X, Y)) because [32], by definition 32] add*(s(X), Y) >= s(add(X, Y)) because add > s and [33], by (Copy) 33] add*(s(X), Y) >= add(X, Y) because add in Mul, [14] and [34], by (Stat) 34] Y >= Y by (Meta) 35] active#(first(s(X), cons(Y))) >= mark#(cons(Y)) because active# = mark#, active# in Mul and [36], by (Fun) 36] first(s(X), cons(Y)) >= cons(Y) because [37], by (Star) 37] first*(s(X), cons(Y)) >= cons(Y) because first > cons and [38], by (Copy) 38] first*(s(X), cons(Y)) >= Y because [39], by (Select) 39] cons(Y) >= Y because [40], by (Star) 40] cons*(Y) >= Y because [34], by (Select) 41] active#(half(s(s(X)))) >= mark#(s(half(X))) because [42], by (Star) 42] active#*(half(s(s(X)))) >= mark#(s(half(X))) because [43], by (Select) 43] half(s(s(X))) >= mark#(s(half(X))) because [44], by (Star) 44] half*(s(s(X))) >= mark#(s(half(X))) because half > mark# and [45], by (Copy) 45] half*(s(s(X))) >= s(half(X)) because half > s and [46], by (Copy) 46] half*(s(s(X))) >= half(X) because half in Mul and [47], by (Stat) 47] s(s(X)) > X because [48], by definition 48] s*(s(X)) >= X because [19], by (Select) 49] active#(half(dbl(X))) >= mark#(X) because active# = mark#, active# in Mul and [50], by (Fun) 50] half(dbl(X)) >= X because [51], by (Star) 51] half*(dbl(X)) >= X because [52], by (Select) 52] dbl(X) >= X because [53], by (Star) 53] dbl*(X) >= X because [16], by (Select) 54] mark#(terms(X)) >= active#(terms(X)) because mark# = active#, mark# in Mul and [55], by (Fun) 55] terms(X) >= terms(X) because terms in Mul and [56], by (Fun) 56] X >= X by (Meta) 57] mark#(terms(X)) >= mark#(X) because mark# in Mul and [58], by (Fun) 58] terms(X) >= X because [59], by (Star) 59] terms*(X) >= X because [56], by (Select) 60] mark#(cons(X)) >= mark#(X) because mark# in Mul and [61], by (Fun) 61] cons(X) >= X because [62], by (Star) 62] cons*(X) >= X because [63], by (Select) 63] X >= X by (Meta) 64] mark#(recip(X)) >= mark#(X) because [65], by (Star) 65] mark#*(recip(X)) >= mark#(X) because [66], by (Select) 66] recip(X) >= mark#(X) because recip = mark#, recip in Mul and [56], by (Fun) 67] mark#(sqr(X)) >= active#(sqr(X)) because mark# = active#, mark# in Mul and [68], by (Fun) 68] sqr(X) >= sqr(X) because sqr in Mul and [56], by (Fun) 69] mark#(sqr(X)) >= mark#(X) because mark# in Mul and [70], by (Fun) 70] sqr(X) >= X because [71], by (Star) 71] sqr*(X) >= X because [56], by (Select) 72] mark#(s(X)) >= mark#(X) because mark# in Mul and [73], by (Fun) 73] s(X) >= X because [15], by (Star) 74] mark#(add(X, Y)) >= active#(add(X, Y)) because mark# = active#, mark# in Mul and [75], by (Fun) 75] add(X, Y) >= add(X, Y) because add in Mul, [76] and [77], by (Fun) 76] X >= X by (Meta) 77] Y >= Y by (Meta) 78] mark#(add(X, Y)) >= mark#(X) because [79], by (Star) 79] mark#*(add(X, Y)) >= mark#(X) because [80], by (Select) 80] add(X, Y) >= mark#(X) because [81], by (Star) 81] add*(X, Y) >= mark#(X) because add > mark# and [82], by (Copy) 82] add*(X, Y) >= X because [76], by (Select) 83] mark#(add(X, Y)) >= mark#(Y) because mark# in Mul and [84], by (Fun) 84] add(X, Y) >= Y because [85], by (Star) 85] add*(X, Y) >= Y because [77], by (Select) 86] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [87], by (Fun) 87] dbl(X) >= dbl(X) because dbl in Mul and [56], by (Fun) 88] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [89], by (Fun) 89] dbl(X) >= X because [53], by (Star) 90] mark#(first(X, Y)) >= active#(first(X, Y)) because mark# = active#, mark# in Mul and [91], by (Fun) 91] first(X, Y) >= first(X, Y) because first in Mul, [76] and [77], by (Fun) 92] mark#(first(X, Y)) >= mark#(X) because mark# in Mul and [93], by (Fun) 93] first(X, Y) >= X because [94], by (Star) 94] first*(X, Y) >= X because [76], by (Select) 95] mark#(first(X, Y)) >= mark#(Y) because mark# in Mul and [96], by (Fun) 96] first(X, Y) >= Y because [97], by (Star) 97] first*(X, Y) >= Y because [77], by (Select) 98] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [99], by (Fun) 99] half(X) >= half(X) because half in Mul and [56], by (Fun) 100] mark#(half(X)) >= mark#(X) because mark# in Mul and [101], by (Fun) 101] half(X) >= X because [102], by (Star) 102] half*(X) >= X because [56], by (Select) 103] terms(X) >= cons(recip(sqr(X))) because [4], by (Star) 104] sqr(_|_) >= _|_ by (Bot) 105] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [11], by (Star) 106] dbl(_|_) >= _|_ by (Bot) 107] dbl(s(X)) >= s(s(dbl(X))) because [23], by (Star) 108] add(_|_, X) >= X because [28], by (Star) 109] add(s(X), Y) >= s(add(X, Y)) because [32], by (Star) 110] first(_|_, X) >= _|_ by (Bot) 111] first(s(X), cons(Y)) >= cons(Y) because [37], by (Star) 112] half(_|_) >= _|_ by (Bot) 113] half(s(_|_)) >= _|_ by (Bot) 114] half(s(s(X))) >= s(half(X)) because [45], by (Star) 115] half(dbl(X)) >= X because [51], by (Star) 116] terms(X) >= terms(X) because terms in Mul and [56], by (Fun) 117] cons(X) >= cons(X) because cons in Mul and [76], by (Fun) 118] recip(X) >= recip(X) because recip in Mul and [56], by (Fun) 119] sqr(X) >= sqr(X) because sqr in Mul and [56], by (Fun) 120] s(X) >= s(X) because s in Mul and [56], by (Fun) 121] _|_ >= _|_ by (Bot) 122] add(X, Y) >= add(X, Y) because add in Mul, [76] and [77], by (Fun) 123] dbl(X) >= dbl(X) because dbl in Mul and [56], by (Fun) 124] first(X, Y) >= first(X, Y) because first in Mul, [76] and [77], by (Fun) 125] _|_ >= _|_ by (Bot) 126] half(X) >= half(X) because half in Mul and [56], by (Fun) 127] terms(X) >= terms(X) because terms in Mul and [128], by (Fun) 128] X >= X by (Meta) 129] terms(X) >= terms(X) because terms in Mul and [130], by (Fun) 130] X >= X by (Meta) 131] cons(X) >= cons(X) because cons in Mul and [132], by (Fun) 132] X >= X by (Meta) 133] cons(X) >= cons(X) because cons in Mul and [76], by (Fun) 134] cons(X) >= cons(X) because cons in Mul and [135], by (Fun) 135] X >= X by (Meta) 136] cons(X) >= cons(X) because cons in Mul and [76], by (Fun) 137] recip(X) >= recip(X) because recip in Mul and [128], by (Fun) 138] recip(X) >= recip(X) because recip in Mul and [130], by (Fun) 139] sqr(X) >= sqr(X) because sqr in Mul and [128], by (Fun) 140] sqr(X) >= sqr(X) because sqr in Mul and [130], by (Fun) 141] s(X) >= s(X) because s in Mul and [128], by (Fun) 142] s(X) >= s(X) because s in Mul and [130], by (Fun) 143] add(X, Y) >= add(X, Y) because add in Mul, [132] and [77], by (Fun) 144] add(X, Y) >= add(X, Y) because add in Mul, [76] and [145], by (Fun) 145] Y >= Y by (Meta) 146] add(X, Y) >= add(X, Y) because add in Mul, [135] and [77], by (Fun) 147] add(X, Y) >= add(X, Y) because add in Mul, [76] and [148], by (Fun) 148] Y >= Y by (Meta) 149] dbl(X) >= dbl(X) because dbl in Mul and [128], by (Fun) 150] dbl(X) >= dbl(X) because dbl in Mul and [130], by (Fun) 151] first(X, Y) >= first(X, Y) because first in Mul, [132] and [77], by (Fun) 152] first(X, Y) >= first(X, Y) because first in Mul, [76] and [145], by (Fun) 153] first(X, Y) >= first(X, Y) because first in Mul, [135] and [77], by (Fun) 154] first(X, Y) >= first(X, Y) because first in Mul, [76] and [148], by (Fun) 155] half(X) >= half(X) because half in Mul and [128], by (Fun) 156] half(X) >= half(X) because half in Mul and [130], by (Fun) 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_14, R_0, minimal, formative), where P_14 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(first(s(X), cons(Y, Z))) =#> mark#(cons(Y, first(X, Z))) active#(half(s(s(X)))) =#> mark#(s(half(X))) active#(half(dbl(X))) =#> mark#(X) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(sqr(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(half(X)) =#> active#(half(mark(X))) mark#(half(X)) =#> mark#(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: active#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) >? mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(first(s(X), cons(Y, Z))) >? mark#(cons(Y, first(X, Z))) active#(half(s(s(X)))) >? mark#(s(half(X))) active#(half(dbl(X))) >? mark#(X) mark#(terms(X)) >? active#(terms(mark(X))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(sqr(X)) >? active#(sqr(mark(X))) mark#(sqr(X)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(add(X, Y)) >? mark#(X) mark#(add(X, Y)) >? mark#(Y) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? active#(first(mark(X), mark(Y))) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) mark#(half(X)) >? active#(half(mark(X))) mark#(half(X)) >? mark#(X) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) sqr(mark(X)) >= sqr(X) sqr(active(X)) >= sqr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) first(mark(X), Y) >= first(X, Y) first(X, mark(Y)) >= first(X, Y) first(active(X), Y) >= first(X, Y) first(X, active(Y)) >= first(X, Y) half(mark(X)) >= half(X) half(active(X)) >= half(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]] = _|_ [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = x_1 [[mark(x_1)]] = x_1 [[nil]] = _|_ We choose Lex = {} and Mul = {active#, add, dbl, first, half, mark#, recip, s, sqr, terms}, and the following precedence: terms > recip > active# = mark# > first > half > sqr > add > dbl > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(terms(X)) >= mark#(recip(sqr(X))) active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(add(_|_, X)) >= mark#(X) active#(first(s(X), Y)) >= mark#(Y) active#(half(s(s(X)))) >= mark#(s(half(X))) active#(half(dbl(X))) > mark#(X) mark#(terms(X)) >= active#(terms(X)) mark#(terms(X)) >= mark#(X) mark#(X) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(sqr(X)) >= active#(sqr(X)) mark#(sqr(X)) >= mark#(X) mark#(s(X)) >= mark#(X) mark#(add(X, Y)) >= active#(add(X, Y)) mark#(add(X, Y)) >= mark#(X) mark#(add(X, Y)) >= mark#(Y) mark#(dbl(X)) >= active#(dbl(X)) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= active#(first(X, Y)) mark#(first(X, Y)) >= mark#(X) mark#(first(X, Y)) >= mark#(Y) mark#(half(X)) >= active#(half(X)) mark#(half(X)) >= mark#(X) terms(X) >= recip(sqr(X)) sqr(_|_) >= _|_ sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(_|_) >= _|_ dbl(s(X)) >= s(s(dbl(X))) add(_|_, X) >= X add(s(X), Y) >= s(add(X, Y)) first(_|_, X) >= _|_ first(s(X), Y) >= Y half(_|_) >= _|_ half(s(_|_)) >= _|_ half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms(X) >= terms(X) X >= X recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) _|_ >= _|_ add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) _|_ >= _|_ half(X) >= half(X) terms(X) >= terms(X) terms(X) >= terms(X) X >= X X >= X X >= X X >= X recip(X) >= recip(X) recip(X) >= recip(X) sqr(X) >= sqr(X) sqr(X) >= sqr(X) s(X) >= s(X) s(X) >= s(X) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(terms(X)) >= mark#(recip(sqr(X))) because active# = mark#, active# in Mul and [2], by (Fun) 2] terms(X) >= recip(sqr(X)) because [3], by (Star) 3] terms*(X) >= recip(sqr(X)) because terms > recip and [4], by (Copy) 4] terms*(X) >= sqr(X) because terms > sqr and [5], by (Copy) 5] terms*(X) >= X because [6], by (Select) 6] X >= X by (Meta) 7] active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because active# = mark#, active# in Mul and [8], by (Fun) 8] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [9], by (Star) 9] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [10], by (Copy) 10] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [11] and [15], by (Copy) 11] sqr*(s(X)) >= sqr(X) because sqr in Mul and [12], by (Stat) 12] s(X) > X because [13], by definition 13] s*(X) >= X because [14], by (Select) 14] X >= X by (Meta) 15] sqr*(s(X)) >= dbl(X) because sqr > dbl and [16], by (Copy) 16] sqr*(s(X)) >= X because [17], by (Select) 17] s(X) >= X because [13], by (Star) 18] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [19], by (Fun) 19] dbl(s(X)) >= s(s(dbl(X))) because [20], by (Star) 20] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [21], by (Copy) 21] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [22], by (Copy) 22] dbl*(s(X)) >= dbl(X) because dbl in Mul and [12], by (Stat) 23] active#(add(_|_, X)) >= mark#(X) because active# = mark#, active# in Mul and [24], by (Fun) 24] add(_|_, X) >= X because [25], by (Star) 25] add*(_|_, X) >= X because [14], by (Select) 26] active#(first(s(X), Y)) >= mark#(Y) because active# = mark#, active# in Mul and [27], by (Fun) 27] first(s(X), Y) >= Y because [28], by (Star) 28] first*(s(X), Y) >= Y because [29], by (Select) 29] Y >= Y by (Meta) 30] active#(half(s(s(X)))) >= mark#(s(half(X))) because active# = mark#, active# in Mul and [31], by (Fun) 31] half(s(s(X))) >= s(half(X)) because [32], by (Star) 32] half*(s(s(X))) >= s(half(X)) because half > s and [33], by (Copy) 33] half*(s(s(X))) >= half(X) because half in Mul and [34], by (Stat) 34] s(s(X)) > X because [35], by definition 35] s*(s(X)) >= X because [17], by (Select) 36] active#(half(dbl(X))) > mark#(X) because [37], by definition 37] active#*(half(dbl(X))) >= mark#(X) because active# = mark#, active# in Mul and [38], by (Stat) 38] half(dbl(X)) > X because [39], by definition 39] half*(dbl(X)) >= X because [40], by (Select) 40] dbl(X) >= X because [41], by (Star) 41] dbl*(X) >= X because [14], by (Select) 42] mark#(terms(X)) >= active#(terms(X)) because mark# = active#, mark# in Mul and [43], by (Fun) 43] terms(X) >= terms(X) because terms in Mul and [44], by (Fun) 44] X >= X by (Meta) 45] mark#(terms(X)) >= mark#(X) because mark# in Mul and [46], by (Fun) 46] terms(X) >= X because [47], by (Star) 47] terms*(X) >= X because [44], by (Select) 48] mark#(X) >= mark#(X) because mark# in Mul and [49], by (Fun) 49] X >= X by (Meta) 50] mark#(recip(X)) >= mark#(X) because mark# in Mul and [51], by (Fun) 51] recip(X) >= X because [52], by (Star) 52] recip*(X) >= X because [44], by (Select) 53] mark#(sqr(X)) >= active#(sqr(X)) because mark# = active#, mark# in Mul and [54], by (Fun) 54] sqr(X) >= sqr(X) because sqr in Mul and [44], by (Fun) 55] mark#(sqr(X)) >= mark#(X) because mark# in Mul and [56], by (Fun) 56] sqr(X) >= X because [57], by (Star) 57] sqr*(X) >= X because [44], by (Select) 58] mark#(s(X)) >= mark#(X) because mark# in Mul and [59], by (Fun) 59] s(X) >= X because [13], by (Star) 60] mark#(add(X, Y)) >= active#(add(X, Y)) because mark# = active#, mark# in Mul and [61], by (Fun) 61] add(X, Y) >= add(X, Y) because add in Mul, [62] and [63], by (Fun) 62] X >= X by (Meta) 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 [66], by (Star) 66] add*(X, Y) >= X because [62], by (Select) 67] mark#(add(X, Y)) >= mark#(Y) because mark# in Mul and [68], by (Fun) 68] add(X, Y) >= Y because [69], by (Star) 69] add*(X, Y) >= Y because [63], by (Select) 70] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [71], by (Fun) 71] dbl(X) >= dbl(X) because dbl in Mul and [44], by (Fun) 72] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [73], by (Fun) 73] dbl(X) >= X because [41], by (Star) 74] mark#(first(X, Y)) >= active#(first(X, Y)) because mark# = active#, mark# in Mul and [75], by (Fun) 75] first(X, Y) >= first(X, Y) because first in Mul, [62] and [63], by (Fun) 76] mark#(first(X, Y)) >= mark#(X) because [77], by (Star) 77] mark#*(first(X, Y)) >= mark#(X) because mark# in Mul and [78], by (Stat) 78] first(X, Y) > X because [79], by definition 79] first*(X, Y) >= X because [62], by (Select) 80] mark#(first(X, Y)) >= mark#(Y) because mark# in Mul and [81], by (Fun) 81] first(X, Y) >= Y because [82], by (Star) 82] first*(X, Y) >= Y because [63], by (Select) 83] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [84], by (Fun) 84] half(X) >= half(X) because half in Mul and [44], by (Fun) 85] mark#(half(X)) >= mark#(X) because mark# in Mul and [86], by (Fun) 86] half(X) >= X because [87], by (Star) 87] half*(X) >= X because [44], by (Select) 88] terms(X) >= recip(sqr(X)) because [3], by (Star) 89] sqr(_|_) >= _|_ by (Bot) 90] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [9], by (Star) 91] dbl(_|_) >= _|_ by (Bot) 92] dbl(s(X)) >= s(s(dbl(X))) because [20], by (Star) 93] add(_|_, X) >= X because [25], by (Star) 94] add(s(X), Y) >= s(add(X, Y)) because [95], by (Star) 95] add*(s(X), Y) >= s(add(X, Y)) because add > s and [96], by (Copy) 96] add*(s(X), Y) >= add(X, Y) because add in Mul, [12] and [97], by (Stat) 97] Y >= Y by (Meta) 98] first(_|_, X) >= _|_ by (Bot) 99] first(s(X), Y) >= Y because [28], by (Star) 100] half(_|_) >= _|_ by (Bot) 101] half(s(_|_)) >= _|_ by (Bot) 102] half(s(s(X))) >= s(half(X)) because [32], by (Star) 103] half(dbl(X)) >= X because [39], by (Star) 104] terms(X) >= terms(X) because terms in Mul and [44], by (Fun) 105] X >= X by (Meta) 106] recip(X) >= recip(X) because recip in Mul and [44], by (Fun) 107] sqr(X) >= sqr(X) because sqr in Mul and [44], by (Fun) 108] s(X) >= s(X) because s in Mul and [44], by (Fun) 109] _|_ >= _|_ by (Bot) 110] add(X, Y) >= add(X, Y) because add in Mul, [62] and [63], by (Fun) 111] dbl(X) >= dbl(X) because dbl in Mul and [44], by (Fun) 112] first(X, Y) >= first(X, Y) because first in Mul, [62] and [63], by (Fun) 113] _|_ >= _|_ by (Bot) 114] half(X) >= half(X) because half in Mul and [44], by (Fun) 115] terms(X) >= terms(X) because terms in Mul and [116], by (Fun) 116] X >= X by (Meta) 117] terms(X) >= terms(X) because terms in Mul and [118], by (Fun) 118] X >= X by (Meta) 119] X >= X by (Meta) 120] X >= X by (Meta) 121] X >= X by (Meta) 122] X >= X by (Meta) 123] recip(X) >= recip(X) because recip in Mul and [116], by (Fun) 124] recip(X) >= recip(X) because recip in Mul and [118], by (Fun) 125] sqr(X) >= sqr(X) because sqr in Mul and [116], by (Fun) 126] sqr(X) >= sqr(X) because sqr in Mul and [118], by (Fun) 127] s(X) >= s(X) because s in Mul and [116], by (Fun) 128] s(X) >= s(X) because s in Mul and [118], by (Fun) 129] add(X, Y) >= add(X, Y) because add in Mul, [130] and [63], by (Fun) 130] X >= X by (Meta) 131] add(X, Y) >= add(X, Y) because add in Mul, [62] and [132], by (Fun) 132] Y >= Y by (Meta) 133] add(X, Y) >= add(X, Y) because add in Mul, [134] and [63], by (Fun) 134] X >= X by (Meta) 135] add(X, Y) >= add(X, Y) because add in Mul, [62] and [136], by (Fun) 136] Y >= Y by (Meta) 137] dbl(X) >= dbl(X) because dbl in Mul and [116], by (Fun) 138] dbl(X) >= dbl(X) because dbl in Mul and [118], by (Fun) 139] first(X, Y) >= first(X, Y) because first in Mul, [130] and [63], by (Fun) 140] first(X, Y) >= first(X, Y) because first in Mul, [62] and [132], by (Fun) 141] first(X, Y) >= first(X, Y) because first in Mul, [134] and [63], by (Fun) 142] first(X, Y) >= first(X, Y) because first in Mul, [62] and [136], by (Fun) 143] half(X) >= half(X) because half in Mul and [116], by (Fun) 144] half(X) >= half(X) because half in Mul and [118], by (Fun) 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: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(first(s(X), cons(Y, Z))) =#> mark#(cons(Y, first(X, Z))) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(sqr(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(half(X)) =#> active#(half(mark(X))) mark#(half(X)) =#> mark#(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: active#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) >? mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(first(s(X), cons(Y, Z))) >? mark#(cons(Y, first(X, Z))) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(terms(X)) >? active#(terms(mark(X))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(sqr(X)) >? active#(sqr(mark(X))) mark#(sqr(X)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(add(X, Y)) >? mark#(X) mark#(add(X, Y)) >? mark#(Y) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? active#(first(mark(X), mark(Y))) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) mark#(half(X)) >? active#(half(mark(X))) mark#(half(X)) >? mark#(X) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) sqr(mark(X)) >= sqr(X) sqr(active(X)) >= sqr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) first(mark(X), Y) >= first(X, Y) first(X, mark(Y)) >= first(X, Y) first(active(X), Y) >= first(X, Y) first(X, active(Y)) >= first(X, Y) half(mark(X)) >= half(X) half(active(X)) >= half(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]] = _|_ [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = cons(x_1) [[mark(x_1)]] = x_1 [[nil]] = _|_ We choose Lex = {} and Mul = {active#, add, cons, dbl, first, half, mark#, recip, s, sqr, terms}, and the following precedence: half > terms > dbl = sqr > first > cons > add > active# = mark# = s > recip Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(terms(X)) >= mark#(cons(recip(sqr(X)))) active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(add(_|_, X)) >= mark#(X) active#(first(s(X), cons(Y))) >= mark#(cons(Y)) active#(half(s(s(X)))) >= mark#(s(half(X))) mark#(terms(X)) >= active#(terms(X)) mark#(terms(X)) >= mark#(X) mark#(cons(X)) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(sqr(X)) >= active#(sqr(X)) mark#(sqr(X)) > mark#(X) mark#(s(X)) >= mark#(X) mark#(add(X, Y)) >= active#(add(X, Y)) mark#(add(X, Y)) >= mark#(X) mark#(add(X, Y)) >= mark#(Y) mark#(dbl(X)) >= active#(dbl(X)) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= active#(first(X, Y)) mark#(first(X, Y)) >= mark#(X) mark#(first(X, Y)) >= mark#(Y) mark#(half(X)) >= active#(half(X)) mark#(half(X)) >= mark#(X) terms(X) >= cons(recip(sqr(X))) sqr(_|_) >= _|_ sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(_|_) >= _|_ dbl(s(X)) >= s(s(dbl(X))) add(_|_, X) >= X add(s(X), Y) >= s(add(X, Y)) first(_|_, X) >= _|_ first(s(X), cons(Y)) >= cons(Y) half(_|_) >= _|_ half(s(_|_)) >= _|_ half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms(X) >= terms(X) cons(X) >= cons(X) recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) _|_ >= _|_ add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) _|_ >= _|_ half(X) >= half(X) terms(X) >= terms(X) terms(X) >= terms(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) recip(X) >= recip(X) recip(X) >= recip(X) sqr(X) >= sqr(X) sqr(X) >= sqr(X) s(X) >= s(X) s(X) >= s(X) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(terms(X)) >= mark#(cons(recip(sqr(X)))) because active# = mark#, active# in Mul and [2], by (Fun) 2] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 3] terms*(X) >= cons(recip(sqr(X))) because terms > cons and [4], by (Copy) 4] terms*(X) >= recip(sqr(X)) because terms > recip and [5], by (Copy) 5] terms*(X) >= sqr(X) because terms > sqr and [6], by (Copy) 6] terms*(X) >= X because [7], by (Select) 7] X >= X by (Meta) 8] active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because active# = mark#, active# in Mul and [9], by (Fun) 9] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [10], by (Star) 10] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [11], by (Copy) 11] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [12] and [16], by (Copy) 12] sqr*(s(X)) >= sqr(X) because sqr in Mul and [13], by (Stat) 13] s(X) > X because [14], by definition 14] s*(X) >= X because [15], by (Select) 15] X >= X by (Meta) 16] sqr*(s(X)) >= dbl(X) because sqr = dbl, sqr in Mul and [13], by (Stat) 17] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [18], by (Fun) 18] dbl(s(X)) >= s(s(dbl(X))) because [19], by (Star) 19] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [20], by (Copy) 20] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [21], by (Copy) 21] dbl*(s(X)) >= dbl(X) because dbl in Mul and [13], by (Stat) 22] active#(add(_|_, X)) >= mark#(X) because [23], by (Star) 23] active#*(add(_|_, X)) >= mark#(X) because active# = mark#, active# in Mul and [24], by (Stat) 24] add(_|_, X) > X because [25], by definition 25] add*(_|_, X) >= X because [15], by (Select) 26] active#(first(s(X), cons(Y))) >= mark#(cons(Y)) because active# = mark#, active# in Mul and [27], by (Fun) 27] first(s(X), cons(Y)) >= cons(Y) because [28], by (Star) 28] first*(s(X), cons(Y)) >= cons(Y) because first > cons and [29], by (Copy) 29] first*(s(X), cons(Y)) >= Y because [30], by (Select) 30] cons(Y) >= Y because [31], by (Star) 31] cons*(Y) >= Y because [32], by (Select) 32] Y >= Y by (Meta) 33] active#(half(s(s(X)))) >= mark#(s(half(X))) because active# = mark#, active# in Mul and [34], by (Fun) 34] half(s(s(X))) >= s(half(X)) because [35], by (Star) 35] half*(s(s(X))) >= s(half(X)) because half > s and [36], by (Copy) 36] half*(s(s(X))) >= half(X) because half in Mul and [37], by (Stat) 37] s(s(X)) > X because [38], by definition 38] s*(s(X)) >= X because [39], by (Select) 39] s(X) >= X because [14], by (Star) 40] mark#(terms(X)) >= active#(terms(X)) because mark# = active#, mark# in Mul and [41], by (Fun) 41] terms(X) >= terms(X) because terms in Mul and [42], by (Fun) 42] X >= X by (Meta) 43] mark#(terms(X)) >= mark#(X) because mark# in Mul and [44], by (Fun) 44] terms(X) >= X because [45], by (Star) 45] terms*(X) >= X because [42], by (Select) 46] mark#(cons(X)) >= mark#(X) because [47], by (Star) 47] mark#*(cons(X)) >= mark#(X) because [48], by (Select) 48] cons(X) >= mark#(X) because [49], by (Star) 49] cons*(X) >= mark#(X) because cons > mark# and [50], by (Copy) 50] cons*(X) >= X because [51], by (Select) 51] X >= X by (Meta) 52] mark#(recip(X)) >= mark#(X) because [53], by (Star) 53] mark#*(recip(X)) >= mark#(X) because mark# in Mul and [54], by (Stat) 54] recip(X) > X because [55], by definition 55] recip*(X) >= X because [42], by (Select) 56] mark#(sqr(X)) >= active#(sqr(X)) because mark# = active#, mark# in Mul and [57], by (Fun) 57] sqr(X) >= sqr(X) because sqr in Mul and [42], by (Fun) 58] mark#(sqr(X)) > mark#(X) because [59], by definition 59] mark#*(sqr(X)) >= mark#(X) because [60], by (Select) 60] sqr(X) >= mark#(X) because [61], by (Star) 61] sqr*(X) >= mark#(X) because sqr > mark# and [62], by (Copy) 62] sqr*(X) >= X because [42], by (Select) 63] mark#(s(X)) >= mark#(X) because [64], by (Star) 64] mark#*(s(X)) >= mark#(X) because [65], by (Select) 65] s(X) >= mark#(X) because s = mark#, s in Mul and [42], by (Fun) 66] mark#(add(X, Y)) >= active#(add(X, Y)) because mark# = active#, mark# in Mul and [67], by (Fun) 67] add(X, Y) >= add(X, Y) because add in Mul, [68] and [69], by (Fun) 68] X >= X by (Meta) 69] Y >= Y by (Meta) 70] mark#(add(X, Y)) >= mark#(X) because [71], by (Star) 71] mark#*(add(X, Y)) >= mark#(X) because [72], by (Select) 72] add(X, Y) >= mark#(X) because [73], by (Star) 73] add*(X, Y) >= mark#(X) because add > mark# and [74], by (Copy) 74] add*(X, Y) >= X because [68], by (Select) 75] mark#(add(X, Y)) >= mark#(Y) because [76], by (Star) 76] mark#*(add(X, Y)) >= mark#(Y) because mark# in Mul and [77], by (Stat) 77] add(X, Y) > Y because [78], by definition 78] add*(X, Y) >= Y because [69], by (Select) 79] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [80], by (Fun) 80] dbl(X) >= dbl(X) because dbl in Mul and [42], by (Fun) 81] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [82], by (Fun) 82] dbl(X) >= X because [83], by (Star) 83] dbl*(X) >= X because [42], by (Select) 84] mark#(first(X, Y)) >= active#(first(X, Y)) because mark# = active#, mark# in Mul and [85], by (Fun) 85] first(X, Y) >= first(X, Y) because first in Mul, [68] and [69], by (Fun) 86] mark#(first(X, Y)) >= mark#(X) because mark# in Mul and [87], by (Fun) 87] first(X, Y) >= X because [88], by (Star) 88] first*(X, Y) >= X because [68], by (Select) 89] mark#(first(X, Y)) >= mark#(Y) because mark# in Mul and [90], by (Fun) 90] first(X, Y) >= Y because [91], by (Star) 91] first*(X, Y) >= Y because [69], by (Select) 92] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [93], by (Fun) 93] half(X) >= half(X) because half in Mul and [42], by (Fun) 94] mark#(half(X)) >= mark#(X) because mark# in Mul and [95], by (Fun) 95] half(X) >= X because [96], by (Star) 96] half*(X) >= X because [42], by (Select) 97] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 98] sqr(_|_) >= _|_ by (Bot) 99] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [10], by (Star) 100] dbl(_|_) >= _|_ by (Bot) 101] dbl(s(X)) >= s(s(dbl(X))) because [19], by (Star) 102] add(_|_, X) >= X because [25], by (Star) 103] add(s(X), Y) >= s(add(X, Y)) because [104], by (Star) 104] add*(s(X), Y) >= s(add(X, Y)) because add > s and [105], by (Copy) 105] add*(s(X), Y) >= add(X, Y) because add in Mul, [13] and [106], by (Stat) 106] Y >= Y by (Meta) 107] first(_|_, X) >= _|_ by (Bot) 108] first(s(X), cons(Y)) >= cons(Y) because [28], by (Star) 109] half(_|_) >= _|_ by (Bot) 110] half(s(_|_)) >= _|_ by (Bot) 111] half(s(s(X))) >= s(half(X)) because [35], by (Star) 112] half(dbl(X)) >= X because [113], by (Star) 113] half*(dbl(X)) >= X because [82], by (Select) 114] terms(X) >= terms(X) because terms in Mul and [42], by (Fun) 115] cons(X) >= cons(X) because cons in Mul and [68], by (Fun) 116] recip(X) >= recip(X) because recip in Mul and [42], by (Fun) 117] sqr(X) >= sqr(X) because sqr in Mul and [42], by (Fun) 118] s(X) >= s(X) because s in Mul and [42], by (Fun) 119] _|_ >= _|_ by (Bot) 120] add(X, Y) >= add(X, Y) because add in Mul, [68] and [69], by (Fun) 121] dbl(X) >= dbl(X) because dbl in Mul and [42], by (Fun) 122] first(X, Y) >= first(X, Y) because first in Mul, [68] and [69], by (Fun) 123] _|_ >= _|_ by (Bot) 124] half(X) >= half(X) because half in Mul and [42], by (Fun) 125] terms(X) >= terms(X) because terms in Mul and [126], by (Fun) 126] X >= X by (Meta) 127] terms(X) >= terms(X) because terms in Mul and [128], by (Fun) 128] X >= X by (Meta) 129] cons(X) >= cons(X) because cons in Mul and [130], by (Fun) 130] X >= X by (Meta) 131] cons(X) >= cons(X) because cons in Mul and [68], by (Fun) 132] cons(X) >= cons(X) because cons in Mul and [133], by (Fun) 133] X >= X by (Meta) 134] cons(X) >= cons(X) because cons in Mul and [68], by (Fun) 135] recip(X) >= recip(X) because recip in Mul and [126], by (Fun) 136] recip(X) >= recip(X) because recip in Mul and [128], by (Fun) 137] sqr(X) >= sqr(X) because sqr in Mul and [126], by (Fun) 138] sqr(X) >= sqr(X) because sqr in Mul and [128], by (Fun) 139] s(X) >= s(X) because s in Mul and [126], by (Fun) 140] s(X) >= s(X) because s in Mul and [128], by (Fun) 141] add(X, Y) >= add(X, Y) because add in Mul, [130] and [69], by (Fun) 142] add(X, Y) >= add(X, Y) because add in Mul, [68] and [143], by (Fun) 143] Y >= Y by (Meta) 144] add(X, Y) >= add(X, Y) because add in Mul, [133] and [69], by (Fun) 145] add(X, Y) >= add(X, Y) because add in Mul, [68] and [146], by (Fun) 146] Y >= Y by (Meta) 147] dbl(X) >= dbl(X) because dbl in Mul and [126], by (Fun) 148] dbl(X) >= dbl(X) because dbl in Mul and [128], by (Fun) 149] first(X, Y) >= first(X, Y) because first in Mul, [130] and [69], by (Fun) 150] first(X, Y) >= first(X, Y) because first in Mul, [68] and [143], by (Fun) 151] first(X, Y) >= first(X, Y) because first in Mul, [133] and [69], by (Fun) 152] first(X, Y) >= first(X, Y) because first in Mul, [68] and [146], by (Fun) 153] half(X) >= half(X) because half in Mul and [126], by (Fun) 154] half(X) >= half(X) because half in Mul and [128], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_15, R_0, minimal, formative) by (P_16, R_0, minimal, formative), where P_16 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(first(s(X), cons(Y, Z))) =#> mark#(cons(Y, first(X, Z))) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) mark#(half(X)) =#> active#(half(mark(X))) mark#(half(X)) =#> mark#(X) Thus, the original system is terminating if (P_16, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_16, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) >? mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(first(s(X), cons(Y, Z))) >? mark#(cons(Y, first(X, Z))) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(terms(X)) >? active#(terms(mark(X))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(sqr(X)) >? active#(sqr(mark(X))) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(add(X, Y)) >? mark#(X) mark#(add(X, Y)) >? mark#(Y) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? active#(first(mark(X), mark(Y))) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) mark#(half(X)) >? active#(half(mark(X))) mark#(half(X)) >? mark#(X) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) sqr(mark(X)) >= sqr(X) sqr(active(X)) >= sqr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) first(mark(X), Y) >= first(X, Y) first(X, mark(Y)) >= first(X, Y) first(active(X), Y) >= first(X, Y) first(X, active(Y)) >= first(X, Y) half(mark(X)) >= half(X) half(active(X)) >= half(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]] = _|_ [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = cons(x_1) [[mark(x_1)]] = x_1 [[nil]] = _|_ We choose Lex = {recip} and Mul = {active#, add, cons, dbl, first, half, mark#, s, sqr, terms}, and the following precedence: first > active# = mark# = terms > cons > sqr > add > dbl > half = s > recip Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(terms(X)) >= mark#(cons(recip(sqr(X)))) active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(add(_|_, X)) >= mark#(X) active#(first(s(X), cons(Y))) >= mark#(cons(Y)) active#(half(s(s(X)))) >= mark#(s(half(X))) mark#(terms(X)) >= active#(terms(X)) mark#(terms(X)) >= mark#(X) mark#(cons(X)) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(sqr(X)) >= active#(sqr(X)) mark#(s(X)) >= mark#(X) mark#(add(X, Y)) >= active#(add(X, Y)) mark#(add(X, Y)) >= mark#(X) mark#(add(X, Y)) >= mark#(Y) mark#(dbl(X)) >= active#(dbl(X)) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= active#(first(X, Y)) mark#(first(X, Y)) >= mark#(X) mark#(first(X, Y)) > mark#(Y) mark#(half(X)) >= active#(half(X)) mark#(half(X)) >= mark#(X) terms(X) >= cons(recip(sqr(X))) sqr(_|_) >= _|_ sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(_|_) >= _|_ dbl(s(X)) >= s(s(dbl(X))) add(_|_, X) >= X add(s(X), Y) >= s(add(X, Y)) first(_|_, X) >= _|_ first(s(X), cons(Y)) >= cons(Y) half(_|_) >= _|_ half(s(_|_)) >= _|_ half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms(X) >= terms(X) cons(X) >= cons(X) recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) _|_ >= _|_ add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) _|_ >= _|_ half(X) >= half(X) terms(X) >= terms(X) terms(X) >= terms(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) recip(X) >= recip(X) recip(X) >= recip(X) sqr(X) >= sqr(X) sqr(X) >= sqr(X) s(X) >= s(X) s(X) >= s(X) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(terms(X)) >= mark#(cons(recip(sqr(X)))) because active# = mark#, active# in Mul and [2], by (Fun) 2] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 3] terms*(X) >= cons(recip(sqr(X))) because terms > cons and [4], by (Copy) 4] terms*(X) >= recip(sqr(X)) because terms > recip and [5], by (Copy) 5] terms*(X) >= sqr(X) because terms > sqr and [6], by (Copy) 6] terms*(X) >= X because [7], by (Select) 7] X >= X by (Meta) 8] active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because active# = mark#, active# in Mul and [9], by (Fun) 9] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [10], by (Star) 10] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [11], by (Copy) 11] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [12] and [16], by (Copy) 12] sqr*(s(X)) >= sqr(X) because sqr in Mul and [13], by (Stat) 13] s(X) > X because [14], by definition 14] s*(X) >= X because [15], by (Select) 15] X >= X by (Meta) 16] sqr*(s(X)) >= dbl(X) because sqr > dbl and [17], by (Copy) 17] sqr*(s(X)) >= X because [18], by (Select) 18] s(X) >= X because [14], by (Star) 19] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [20], by (Fun) 20] dbl(s(X)) >= s(s(dbl(X))) because [21], by (Star) 21] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [22], by (Copy) 22] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [23], by (Copy) 23] dbl*(s(X)) >= dbl(X) because dbl in Mul and [13], by (Stat) 24] active#(add(_|_, X)) >= mark#(X) because active# = mark#, active# in Mul and [25], by (Fun) 25] add(_|_, X) >= X because [26], by (Star) 26] add*(_|_, X) >= X because [15], by (Select) 27] active#(first(s(X), cons(Y))) >= mark#(cons(Y)) because active# = mark#, active# in Mul and [28], by (Fun) 28] first(s(X), cons(Y)) >= cons(Y) because [29], by (Star) 29] first*(s(X), cons(Y)) >= cons(Y) because [30], by (Select) 30] cons(Y) >= cons(Y) because cons in Mul and [31], by (Fun) 31] Y >= Y by (Meta) 32] active#(half(s(s(X)))) >= mark#(s(half(X))) because active# = mark#, active# in Mul and [33], by (Fun) 33] half(s(s(X))) >= s(half(X)) because [34], by (Star) 34] half*(s(s(X))) >= s(half(X)) because half = s, half in Mul and [35], by (Stat) 35] s(s(X)) > half(X) because [36], by definition 36] s*(s(X)) >= half(X) because s = half, s in Mul and [13], by (Stat) 37] mark#(terms(X)) >= active#(terms(X)) because mark# = active#, mark# in Mul and [38], by (Fun) 38] terms(X) >= terms(X) because terms in Mul and [39], by (Fun) 39] X >= X by (Meta) 40] mark#(terms(X)) >= mark#(X) because [41], by (Star) 41] mark#*(terms(X)) >= mark#(X) because [42], by (Select) 42] terms(X) >= mark#(X) because terms = mark#, terms in Mul and [39], by (Fun) 43] mark#(cons(X)) >= mark#(X) because mark# in Mul and [44], by (Fun) 44] cons(X) >= X because [45], by (Star) 45] cons*(X) >= X because [46], by (Select) 46] X >= X by (Meta) 47] mark#(recip(X)) >= mark#(X) because mark# in Mul and [48], by (Fun) 48] recip(X) >= X because [49], by (Star) 49] recip*(X) >= X because [39], by (Select) 50] mark#(sqr(X)) >= active#(sqr(X)) because mark# = active#, mark# in Mul and [51], by (Fun) 51] sqr(X) >= sqr(X) because sqr in Mul and [39], by (Fun) 52] mark#(s(X)) >= mark#(X) because mark# in Mul and [53], by (Fun) 53] s(X) >= X because [14], by (Star) 54] mark#(add(X, Y)) >= active#(add(X, Y)) because mark# = active#, mark# in Mul and [55], by (Fun) 55] add(X, Y) >= add(X, Y) because add in Mul, [56] and [57], by (Fun) 56] X >= X by (Meta) 57] Y >= Y by (Meta) 58] mark#(add(X, Y)) >= mark#(X) because mark# in Mul and [59], by (Fun) 59] add(X, Y) >= X because [60], by (Star) 60] add*(X, Y) >= X because [56], by (Select) 61] mark#(add(X, Y)) >= mark#(Y) because mark# in Mul and [62], by (Fun) 62] add(X, Y) >= Y because [63], by (Star) 63] add*(X, Y) >= Y because [57], by (Select) 64] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [65], by (Fun) 65] dbl(X) >= dbl(X) because dbl in Mul and [39], by (Fun) 66] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [67], by (Fun) 67] dbl(X) >= X because [68], by (Star) 68] dbl*(X) >= X because [39], by (Select) 69] mark#(first(X, Y)) >= active#(first(X, Y)) because mark# = active#, mark# in Mul and [70], by (Fun) 70] first(X, Y) >= first(X, Y) because first in Mul, [56] and [57], by (Fun) 71] mark#(first(X, Y)) >= mark#(X) because mark# in Mul and [72], by (Fun) 72] first(X, Y) >= X because [73], by (Star) 73] first*(X, Y) >= X because [56], by (Select) 74] mark#(first(X, Y)) > mark#(Y) because [75], by definition 75] mark#*(first(X, Y)) >= mark#(Y) because [76], by (Select) 76] first(X, Y) >= mark#(Y) because [77], by (Star) 77] first*(X, Y) >= mark#(Y) because first > mark# and [78], by (Copy) 78] first*(X, Y) >= Y because [57], by (Select) 79] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [80], by (Fun) 80] half(X) >= half(X) because half in Mul and [39], by (Fun) 81] mark#(half(X)) >= mark#(X) because mark# in Mul and [82], by (Fun) 82] half(X) >= X because [83], by (Star) 83] half*(X) >= X because [39], by (Select) 84] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 85] sqr(_|_) >= _|_ by (Bot) 86] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [10], by (Star) 87] dbl(_|_) >= _|_ by (Bot) 88] dbl(s(X)) >= s(s(dbl(X))) because [21], by (Star) 89] add(_|_, X) >= X because [26], by (Star) 90] add(s(X), Y) >= s(add(X, Y)) because [91], by (Star) 91] add*(s(X), Y) >= s(add(X, Y)) because add > s and [92], by (Copy) 92] add*(s(X), Y) >= add(X, Y) because add in Mul, [13] and [31], by (Stat) 93] first(_|_, X) >= _|_ by (Bot) 94] first(s(X), cons(Y)) >= cons(Y) because [29], by (Star) 95] half(_|_) >= _|_ by (Bot) 96] half(s(_|_)) >= _|_ by (Bot) 97] half(s(s(X))) >= s(half(X)) because [34], by (Star) 98] half(dbl(X)) >= X because [99], by (Star) 99] half*(dbl(X)) >= X because [67], by (Select) 100] terms(X) >= terms(X) because terms in Mul and [39], by (Fun) 101] cons(X) >= cons(X) because cons in Mul and [56], by (Fun) 102] recip(X) >= recip(X) because [39], by (Fun) 103] sqr(X) >= sqr(X) because sqr in Mul and [39], by (Fun) 104] s(X) >= s(X) because s in Mul and [39], by (Fun) 105] _|_ >= _|_ by (Bot) 106] add(X, Y) >= add(X, Y) because add in Mul, [56] and [57], by (Fun) 107] dbl(X) >= dbl(X) because dbl in Mul and [39], by (Fun) 108] first(X, Y) >= first(X, Y) because first in Mul, [56] and [57], by (Fun) 109] _|_ >= _|_ by (Bot) 110] half(X) >= half(X) because half in Mul and [39], by (Fun) 111] terms(X) >= terms(X) because terms in Mul and [112], by (Fun) 112] X >= X by (Meta) 113] terms(X) >= terms(X) because terms in Mul and [114], by (Fun) 114] X >= X by (Meta) 115] cons(X) >= cons(X) because cons in Mul and [116], by (Fun) 116] X >= X by (Meta) 117] cons(X) >= cons(X) because cons in Mul and [56], by (Fun) 118] cons(X) >= cons(X) because cons in Mul and [119], by (Fun) 119] X >= X by (Meta) 120] cons(X) >= cons(X) because cons in Mul and [56], by (Fun) 121] recip(X) >= recip(X) because [112], by (Fun) 122] recip(X) >= recip(X) because [114], by (Fun) 123] sqr(X) >= sqr(X) because sqr in Mul and [112], by (Fun) 124] sqr(X) >= sqr(X) because sqr in Mul and [114], by (Fun) 125] s(X) >= s(X) because s in Mul and [112], by (Fun) 126] s(X) >= s(X) because s in Mul and [114], by (Fun) 127] add(X, Y) >= add(X, Y) because add in Mul, [116] and [57], by (Fun) 128] add(X, Y) >= add(X, Y) because add in Mul, [56] and [129], by (Fun) 129] Y >= Y by (Meta) 130] add(X, Y) >= add(X, Y) because add in Mul, [119] and [57], by (Fun) 131] add(X, Y) >= add(X, Y) because add in Mul, [56] and [132], by (Fun) 132] Y >= Y by (Meta) 133] dbl(X) >= dbl(X) because dbl in Mul and [112], by (Fun) 134] dbl(X) >= dbl(X) because dbl in Mul and [114], by (Fun) 135] first(X, Y) >= first(X, Y) because first in Mul, [116] and [57], by (Fun) 136] first(X, Y) >= first(X, Y) because first in Mul, [56] and [129], by (Fun) 137] first(X, Y) >= first(X, Y) because first in Mul, [119] and [57], by (Fun) 138] first(X, Y) >= first(X, Y) because first in Mul, [56] and [132], by (Fun) 139] half(X) >= half(X) because half in Mul and [112], by (Fun) 140] half(X) >= half(X) because half in Mul 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_16, R_0, minimal, formative) by (P_17, R_0, minimal, formative), where P_17 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(first(s(X), cons(Y, Z))) =#> mark#(cons(Y, first(X, Z))) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) mark#(first(X, Y)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) mark#(half(X)) =#> mark#(X) Thus, the original system is terminating if (P_17, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_17, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) >? mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(first(s(X), cons(Y, Z))) >? mark#(cons(Y, first(X, Z))) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(terms(X)) >? active#(terms(mark(X))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(sqr(X)) >? active#(sqr(mark(X))) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(add(X, Y)) >? mark#(X) mark#(add(X, Y)) >? mark#(Y) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? active#(first(mark(X), mark(Y))) mark#(first(X, Y)) >? mark#(X) mark#(half(X)) >? active#(half(mark(X))) mark#(half(X)) >? mark#(X) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) sqr(mark(X)) >= sqr(X) sqr(active(X)) >= sqr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) first(mark(X), Y) >= first(X, Y) first(X, mark(Y)) >= first(X, Y) first(active(X), Y) >= first(X, Y) first(X, active(Y)) >= first(X, Y) half(mark(X)) >= half(X) half(active(X)) >= half(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: [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = cons(x_1) [[mark(x_1)]] = x_1 We choose Lex = {recip} and Mul = {0, active#, add, cons, dbl, first, half, mark#, nil, s, sqr, terms}, and the following precedence: first > terms > cons > sqr > recip > active# = add = mark# > dbl > nil > s > half > 0 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(terms(X)) >= mark#(cons(recip(sqr(X)))) active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(add(0, X)) >= mark#(X) active#(first(s(X), cons(Y))) > mark#(cons(Y)) active#(half(s(s(X)))) >= mark#(s(half(X))) mark#(terms(X)) >= active#(terms(X)) mark#(terms(X)) >= mark#(X) mark#(cons(X)) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(sqr(X)) >= active#(sqr(X)) mark#(s(X)) >= mark#(X) mark#(add(X, Y)) >= active#(add(X, Y)) mark#(add(X, Y)) >= mark#(X) mark#(add(X, Y)) >= mark#(Y) mark#(dbl(X)) >= active#(dbl(X)) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= active#(first(X, Y)) mark#(first(X, Y)) >= mark#(X) mark#(half(X)) >= active#(half(X)) mark#(half(X)) >= mark#(X) terms(X) >= cons(recip(sqr(X))) sqr(0) >= 0 sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(0) >= 0 dbl(s(X)) >= s(s(dbl(X))) add(0, X) >= X add(s(X), Y) >= s(add(X, Y)) first(0, X) >= nil first(s(X), cons(Y)) >= cons(Y) half(0) >= 0 half(s(0)) >= 0 half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms(X) >= terms(X) cons(X) >= cons(X) recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) 0 >= 0 add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) nil >= nil half(X) >= half(X) terms(X) >= terms(X) terms(X) >= terms(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) recip(X) >= recip(X) recip(X) >= recip(X) sqr(X) >= sqr(X) sqr(X) >= sqr(X) s(X) >= s(X) s(X) >= s(X) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(terms(X)) >= mark#(cons(recip(sqr(X)))) because active# = mark#, active# in Mul and [2], by (Fun) 2] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 3] terms*(X) >= cons(recip(sqr(X))) because terms > cons and [4], by (Copy) 4] terms*(X) >= recip(sqr(X)) because terms > recip and [5], by (Copy) 5] terms*(X) >= sqr(X) because terms > sqr and [6], by (Copy) 6] terms*(X) >= X because [7], by (Select) 7] X >= X by (Meta) 8] active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because active# = mark#, active# in Mul and [9], by (Fun) 9] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [10], by (Star) 10] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [11], by (Copy) 11] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [12] and [16], by (Copy) 12] sqr*(s(X)) >= sqr(X) because sqr in Mul and [13], by (Stat) 13] s(X) > X because [14], by definition 14] s*(X) >= X because [15], by (Select) 15] X >= X by (Meta) 16] sqr*(s(X)) >= dbl(X) because sqr > dbl and [17], by (Copy) 17] sqr*(s(X)) >= X because [18], by (Select) 18] s(X) >= X because [14], by (Star) 19] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [20], by (Fun) 20] dbl(s(X)) >= s(s(dbl(X))) because [21], by (Star) 21] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [22], by (Copy) 22] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [23], by (Copy) 23] dbl*(s(X)) >= dbl(X) because dbl in Mul and [13], by (Stat) 24] active#(add(0, X)) >= mark#(X) because active# = mark#, active# in Mul and [25], by (Fun) 25] add(0, X) >= X because [26], by (Star) 26] add*(0, X) >= X because [15], by (Select) 27] active#(first(s(X), cons(Y))) > mark#(cons(Y)) because [28], by definition 28] active#*(first(s(X), cons(Y))) >= mark#(cons(Y)) because active# = mark#, active# in Mul and [29], by (Stat) 29] first(s(X), cons(Y)) > cons(Y) because [30], by definition 30] first*(s(X), cons(Y)) >= cons(Y) because [31], by (Select) 31] cons(Y) >= cons(Y) because cons in Mul and [32], by (Fun) 32] Y >= Y by (Meta) 33] active#(half(s(s(X)))) >= mark#(s(half(X))) because active# = mark#, active# in Mul and [34], by (Fun) 34] half(s(s(X))) >= s(half(X)) because [35], by (Star) 35] half*(s(s(X))) >= s(half(X)) because [36], by (Select) 36] s(s(X)) >= s(half(X)) because s in Mul and [37], by (Fun) 37] s(X) >= half(X) because [38], by (Star) 38] s*(X) >= half(X) because s > half and [14], by (Copy) 39] mark#(terms(X)) >= active#(terms(X)) because mark# = active#, mark# in Mul and [40], by (Fun) 40] terms(X) >= terms(X) because terms in Mul and [41], by (Fun) 41] X >= X by (Meta) 42] mark#(terms(X)) >= mark#(X) because [43], by (Star) 43] mark#*(terms(X)) >= mark#(X) because mark# in Mul and [44], by (Stat) 44] terms(X) > X because [45], by definition 45] terms*(X) >= X because [41], by (Select) 46] mark#(cons(X)) >= mark#(X) because mark# in Mul and [47], by (Fun) 47] cons(X) >= X because [48], by (Star) 48] cons*(X) >= X because [49], by (Select) 49] X >= X by (Meta) 50] mark#(recip(X)) >= mark#(X) because [51], by (Star) 51] mark#*(recip(X)) >= mark#(X) because mark# in Mul and [52], by (Stat) 52] recip(X) > X because [53], by definition 53] recip*(X) >= X because [41], by (Select) 54] mark#(sqr(X)) >= active#(sqr(X)) because mark# = active#, mark# in Mul and [55], by (Fun) 55] sqr(X) >= sqr(X) because sqr in Mul and [41], by (Fun) 56] mark#(s(X)) >= mark#(X) because [57], by (Star) 57] mark#*(s(X)) >= mark#(X) because mark# in Mul and [13], by (Stat) 58] mark#(add(X, Y)) >= active#(add(X, Y)) because mark# = active#, mark# in Mul and [59], by (Fun) 59] add(X, Y) >= add(X, Y) because add in Mul, [60] and [61], by (Fun) 60] X >= X by (Meta) 61] Y >= Y by (Meta) 62] mark#(add(X, Y)) >= mark#(X) because [63], by (Star) 63] mark#*(add(X, Y)) >= mark#(X) because [64], by (Select) 64] add(X, Y) >= mark#(X) because [65], by (Star) 65] add*(X, Y) >= mark#(X) because add = mark#, add in Mul and [60], by (Stat) 66] mark#(add(X, Y)) >= mark#(Y) because mark# in Mul and [67], by (Fun) 67] add(X, Y) >= Y because [68], by (Star) 68] add*(X, Y) >= Y because [61], by (Select) 69] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [70], by (Fun) 70] dbl(X) >= dbl(X) because dbl in Mul and [41], by (Fun) 71] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [72], by (Fun) 72] dbl(X) >= X because [73], by (Star) 73] dbl*(X) >= X because [41], by (Select) 74] mark#(first(X, Y)) >= active#(first(X, Y)) because mark# = active#, mark# in Mul and [75], by (Fun) 75] first(X, Y) >= first(X, Y) because first in Mul, [60] and [61], by (Fun) 76] mark#(first(X, Y)) >= mark#(X) because mark# in Mul and [77], by (Fun) 77] first(X, Y) >= X because [78], by (Star) 78] first*(X, Y) >= X because [60], by (Select) 79] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [80], by (Fun) 80] half(X) >= half(X) because half in Mul and [41], by (Fun) 81] mark#(half(X)) >= mark#(X) because mark# in Mul and [82], by (Fun) 82] half(X) >= X because [83], by (Star) 83] half*(X) >= X because [41], by (Select) 84] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 85] sqr(0) >= 0 because [86], by (Star) 86] sqr*(0) >= 0 because sqr > 0, by (Copy) 87] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [10], by (Star) 88] dbl(0) >= 0 because [89], by (Star) 89] dbl*(0) >= 0 because dbl > 0, by (Copy) 90] dbl(s(X)) >= s(s(dbl(X))) because [21], by (Star) 91] add(0, X) >= X because [26], by (Star) 92] add(s(X), Y) >= s(add(X, Y)) because [93], by (Star) 93] add*(s(X), Y) >= s(add(X, Y)) because add > s and [94], by (Copy) 94] add*(s(X), Y) >= add(X, Y) because add in Mul, [13] and [32], by (Stat) 95] first(0, X) >= nil because [96], by (Star) 96] first*(0, X) >= nil because first > nil, by (Copy) 97] first(s(X), cons(Y)) >= cons(Y) because [30], by (Star) 98] half(0) >= 0 because [99], by (Star) 99] half*(0) >= 0 because half > 0, by (Copy) 100] half(s(0)) >= 0 because [101], by (Star) 101] half*(s(0)) >= 0 because half > 0, by (Copy) 102] half(s(s(X))) >= s(half(X)) because [35], by (Star) 103] half(dbl(X)) >= X because [104], by (Star) 104] half*(dbl(X)) >= X because [72], by (Select) 105] terms(X) >= terms(X) because terms in Mul and [41], by (Fun) 106] cons(X) >= cons(X) because cons in Mul and [60], by (Fun) 107] recip(X) >= recip(X) because [41], by (Fun) 108] sqr(X) >= sqr(X) because sqr in Mul and [41], by (Fun) 109] s(X) >= s(X) because s in Mul and [41], by (Fun) 110] 0 >= 0 by (Fun) 111] add(X, Y) >= add(X, Y) because add in Mul, [60] and [61], by (Fun) 112] dbl(X) >= dbl(X) because dbl in Mul and [41], by (Fun) 113] first(X, Y) >= first(X, Y) because first in Mul, [60] and [61], by (Fun) 114] nil >= nil by (Fun) 115] half(X) >= half(X) because half in Mul and [41], by (Fun) 116] terms(X) >= terms(X) because terms in Mul and [117], by (Fun) 117] X >= X by (Meta) 118] terms(X) >= terms(X) because terms in Mul and [119], by (Fun) 119] X >= X by (Meta) 120] cons(X) >= cons(X) because cons in Mul and [121], by (Fun) 121] X >= X by (Meta) 122] cons(X) >= cons(X) because cons in Mul and [60], by (Fun) 123] cons(X) >= cons(X) because cons in Mul and [124], by (Fun) 124] X >= X by (Meta) 125] cons(X) >= cons(X) because cons in Mul and [60], by (Fun) 126] recip(X) >= recip(X) because [117], by (Fun) 127] recip(X) >= recip(X) because [119], by (Fun) 128] sqr(X) >= sqr(X) because sqr in Mul and [117], by (Fun) 129] sqr(X) >= sqr(X) because sqr in Mul and [119], by (Fun) 130] s(X) >= s(X) because s in Mul and [117], by (Fun) 131] s(X) >= s(X) because s in Mul and [119], by (Fun) 132] add(X, Y) >= add(X, Y) because add in Mul, [121] and [61], by (Fun) 133] add(X, Y) >= add(X, Y) because add in Mul, [60] and [134], by (Fun) 134] Y >= Y by (Meta) 135] add(X, Y) >= add(X, Y) because add in Mul, [124] and [61], by (Fun) 136] add(X, Y) >= add(X, Y) because add in Mul, [60] and [137], by (Fun) 137] Y >= Y by (Meta) 138] dbl(X) >= dbl(X) because dbl in Mul and [117], by (Fun) 139] dbl(X) >= dbl(X) because dbl in Mul and [119], by (Fun) 140] first(X, Y) >= first(X, Y) because first in Mul, [121] and [61], by (Fun) 141] first(X, Y) >= first(X, Y) because first in Mul, [60] and [134], by (Fun) 142] first(X, Y) >= first(X, Y) because first in Mul, [124] and [61], by (Fun) 143] first(X, Y) >= first(X, Y) because first in Mul, [60] and [137], by (Fun) 144] half(X) >= half(X) because half in Mul and [117], by (Fun) 145] half(X) >= half(X) because half in Mul and [119], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_17, R_0, minimal, formative) by (P_18, R_0, minimal, formative), where P_18 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) mark#(first(X, Y)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) mark#(half(X)) =#> mark#(X) Thus, the original system is terminating if (P_18, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_18, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 7 * 1 : 10 * 2 : 10 * 3 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 4 : 10 * 5 : 0 * 6 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 7 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 8 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 9 : 1 * 10 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 11 : 3 * 12 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 13 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 14 : 2 * 15 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 16 : * 17 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 * 18 : 4 * 19 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 This graph has the following strongly connected components: P_19: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(add(X, Y)) =#> mark#(Y) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) mark#(half(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_18, R_0, m, f) by (P_19, R_0, m, f). Thus, the original system is terminating if (P_19, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_19, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) >? mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(terms(X)) >? active#(terms(mark(X))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(sqr(X)) >? active#(sqr(mark(X))) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(add(X, Y)) >? mark#(X) mark#(add(X, Y)) >? mark#(Y) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? mark#(X) mark#(half(X)) >? active#(half(mark(X))) mark#(half(X)) >? mark#(X) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) sqr(mark(X)) >= sqr(X) sqr(active(X)) >= sqr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) first(mark(X), Y) >= first(X, Y) first(X, mark(Y)) >= first(X, Y) first(active(X), Y) >= first(X, Y) first(X, active(Y)) >= first(X, Y) half(mark(X)) >= half(X) half(active(X)) >= half(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]] = _|_ [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = cons(x_1) [[mark(x_1)]] = x_1 [[nil]] = _|_ We choose Lex = {} and Mul = {active#, add, cons, dbl, first, half, mark#, recip, s, sqr, terms}, and the following precedence: terms > dbl = sqr > add > recip > first > active# = mark# = s > half > cons Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(terms(X)) >= mark#(cons(recip(sqr(X)))) active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(add(_|_, X)) >= mark#(X) active#(half(s(s(X)))) >= mark#(s(half(X))) mark#(terms(X)) >= active#(terms(X)) mark#(terms(X)) >= mark#(X) mark#(cons(X)) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(sqr(X)) >= active#(sqr(X)) mark#(s(X)) >= mark#(X) mark#(add(X, Y)) >= active#(add(X, Y)) mark#(add(X, Y)) >= mark#(X) mark#(add(X, Y)) > mark#(Y) mark#(dbl(X)) >= active#(dbl(X)) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) >= mark#(X) mark#(half(X)) >= active#(half(X)) mark#(half(X)) >= mark#(X) terms(X) >= cons(recip(sqr(X))) sqr(_|_) >= _|_ sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(_|_) >= _|_ dbl(s(X)) >= s(s(dbl(X))) add(_|_, X) >= X add(s(X), Y) >= s(add(X, Y)) first(_|_, X) >= _|_ first(s(X), cons(Y)) >= cons(Y) half(_|_) >= _|_ half(s(_|_)) >= _|_ half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms(X) >= terms(X) cons(X) >= cons(X) recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) _|_ >= _|_ add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) _|_ >= _|_ half(X) >= half(X) terms(X) >= terms(X) terms(X) >= terms(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) recip(X) >= recip(X) recip(X) >= recip(X) sqr(X) >= sqr(X) sqr(X) >= sqr(X) s(X) >= s(X) s(X) >= s(X) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(terms(X)) >= mark#(cons(recip(sqr(X)))) because active# = mark#, active# in Mul and [2], by (Fun) 2] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 3] terms*(X) >= cons(recip(sqr(X))) because terms > cons and [4], by (Copy) 4] terms*(X) >= recip(sqr(X)) because terms > recip and [5], by (Copy) 5] terms*(X) >= sqr(X) because terms > sqr and [6], by (Copy) 6] terms*(X) >= X because [7], by (Select) 7] X >= X by (Meta) 8] active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because active# = mark#, active# in Mul and [9], by (Fun) 9] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [10], by (Star) 10] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [11], by (Copy) 11] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [12] and [16], by (Copy) 12] sqr*(s(X)) >= sqr(X) because sqr in Mul and [13], by (Stat) 13] s(X) > X because [14], by definition 14] s*(X) >= X because [15], by (Select) 15] X >= X by (Meta) 16] sqr*(s(X)) >= dbl(X) because sqr = dbl, sqr in Mul and [13], by (Stat) 17] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [18], by (Fun) 18] dbl(s(X)) >= s(s(dbl(X))) because [19], by (Star) 19] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [20], by (Copy) 20] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [21], by (Copy) 21] dbl*(s(X)) >= dbl(X) because dbl in Mul and [13], by (Stat) 22] active#(add(_|_, X)) >= mark#(X) because active# = mark#, active# in Mul and [23], by (Fun) 23] add(_|_, X) >= X because [24], by (Star) 24] add*(_|_, X) >= X because [15], by (Select) 25] active#(half(s(s(X)))) >= mark#(s(half(X))) because active# = mark#, active# in Mul and [26], by (Fun) 26] half(s(s(X))) >= s(half(X)) because [27], by (Star) 27] half*(s(s(X))) >= s(half(X)) because [28], by (Select) 28] s(s(X)) >= s(half(X)) because s in Mul and [29], by (Fun) 29] s(X) >= half(X) because [30], by (Star) 30] s*(X) >= half(X) because s > half and [14], by (Copy) 31] mark#(terms(X)) >= active#(terms(X)) because mark# = active#, mark# in Mul and [32], by (Fun) 32] terms(X) >= terms(X) because terms in Mul and [33], by (Fun) 33] X >= X by (Meta) 34] mark#(terms(X)) >= mark#(X) because mark# in Mul and [35], by (Fun) 35] terms(X) >= X because [36], by (Star) 36] terms*(X) >= X because [33], by (Select) 37] mark#(cons(X)) >= mark#(X) because mark# in Mul and [38], by (Fun) 38] cons(X) >= X because [39], by (Star) 39] cons*(X) >= X because [40], by (Select) 40] X >= X by (Meta) 41] mark#(recip(X)) >= mark#(X) because [42], by (Star) 42] mark#*(recip(X)) >= mark#(X) because mark# in Mul and [43], by (Stat) 43] recip(X) > X because [44], by definition 44] recip*(X) >= X because [33], by (Select) 45] mark#(sqr(X)) >= active#(sqr(X)) because mark# = active#, mark# in Mul and [46], by (Fun) 46] sqr(X) >= sqr(X) because sqr in Mul and [33], by (Fun) 47] mark#(s(X)) >= mark#(X) because [48], by (Star) 48] mark#*(s(X)) >= mark#(X) because [49], by (Select) 49] s(X) >= mark#(X) because s = mark#, s in Mul and [33], by (Fun) 50] mark#(add(X, Y)) >= active#(add(X, Y)) because mark# = active#, mark# in Mul and [51], by (Fun) 51] add(X, Y) >= add(X, Y) because add in Mul, [52] and [53], by (Fun) 52] X >= X by (Meta) 53] Y >= Y by (Meta) 54] mark#(add(X, Y)) >= mark#(X) because mark# in Mul and [55], by (Fun) 55] add(X, Y) >= X because [56], by (Star) 56] add*(X, Y) >= X because [52], by (Select) 57] mark#(add(X, Y)) > mark#(Y) because [58], by definition 58] mark#*(add(X, Y)) >= mark#(Y) because mark# in Mul and [59], by (Stat) 59] add(X, Y) > Y because [60], by definition 60] add*(X, Y) >= Y because [53], by (Select) 61] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [62], by (Fun) 62] dbl(X) >= dbl(X) because dbl in Mul and [33], by (Fun) 63] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [64], by (Fun) 64] dbl(X) >= X because [65], by (Star) 65] dbl*(X) >= X because [33], 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 [52], by (Select) 71] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [72], by (Fun) 72] half(X) >= half(X) because half in Mul and [33], by (Fun) 73] mark#(half(X)) >= mark#(X) because mark# in Mul and [74], by (Fun) 74] half(X) >= X because [75], by (Star) 75] half*(X) >= X because [33], by (Select) 76] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 77] sqr(_|_) >= _|_ by (Bot) 78] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [10], by (Star) 79] dbl(_|_) >= _|_ by (Bot) 80] dbl(s(X)) >= s(s(dbl(X))) because [19], by (Star) 81] add(_|_, X) >= X because [24], by (Star) 82] add(s(X), Y) >= s(add(X, Y)) because [83], by (Star) 83] add*(s(X), Y) >= s(add(X, Y)) because add > s and [84], by (Copy) 84] add*(s(X), Y) >= add(X, Y) because add in Mul, [13] and [85], by (Stat) 85] Y >= Y by (Meta) 86] first(_|_, X) >= _|_ by (Bot) 87] first(s(X), cons(Y)) >= cons(Y) because [88], by (Star) 88] first*(s(X), cons(Y)) >= cons(Y) because first > cons and [89], by (Copy) 89] first*(s(X), cons(Y)) >= Y because [90], by (Select) 90] cons(Y) >= Y because [91], by (Star) 91] cons*(Y) >= Y because [85], by (Select) 92] half(_|_) >= _|_ by (Bot) 93] half(s(_|_)) >= _|_ by (Bot) 94] half(s(s(X))) >= s(half(X)) because [27], by (Star) 95] half(dbl(X)) >= X because [96], by (Star) 96] half*(dbl(X)) >= X because [64], by (Select) 97] terms(X) >= terms(X) because terms in Mul and [33], by (Fun) 98] cons(X) >= cons(X) because cons in Mul and [52], by (Fun) 99] recip(X) >= recip(X) because recip in Mul and [33], by (Fun) 100] sqr(X) >= sqr(X) because sqr in Mul and [33], by (Fun) 101] s(X) >= s(X) because s in Mul and [33], by (Fun) 102] _|_ >= _|_ by (Bot) 103] add(X, Y) >= add(X, Y) because add in Mul, [52] and [53], by (Fun) 104] dbl(X) >= dbl(X) because dbl in Mul and [33], by (Fun) 105] first(X, Y) >= first(X, Y) because first in Mul, [52] and [53], by (Fun) 106] _|_ >= _|_ by (Bot) 107] half(X) >= half(X) because half in Mul and [33], by (Fun) 108] terms(X) >= terms(X) because terms in Mul and [109], by (Fun) 109] X >= X by (Meta) 110] terms(X) >= terms(X) because terms in Mul and [111], by (Fun) 111] X >= X by (Meta) 112] cons(X) >= cons(X) because cons in Mul and [113], by (Fun) 113] X >= X by (Meta) 114] cons(X) >= cons(X) because cons in Mul and [52], by (Fun) 115] cons(X) >= cons(X) because cons in Mul and [116], by (Fun) 116] X >= X by (Meta) 117] cons(X) >= cons(X) because cons in Mul and [52], by (Fun) 118] recip(X) >= recip(X) because recip in Mul and [109], by (Fun) 119] recip(X) >= recip(X) because recip in Mul and [111], by (Fun) 120] sqr(X) >= sqr(X) because sqr in Mul and [109], by (Fun) 121] sqr(X) >= sqr(X) because sqr in Mul and [111], by (Fun) 122] s(X) >= s(X) because s in Mul and [109], by (Fun) 123] s(X) >= s(X) because s in Mul and [111], by (Fun) 124] add(X, Y) >= add(X, Y) because add in Mul, [113] and [53], by (Fun) 125] add(X, Y) >= add(X, Y) because add in Mul, [52] and [126], by (Fun) 126] Y >= Y by (Meta) 127] add(X, Y) >= add(X, Y) because add in Mul, [116] and [53], by (Fun) 128] add(X, Y) >= add(X, Y) because add in Mul, [52] and [129], by (Fun) 129] Y >= Y by (Meta) 130] dbl(X) >= dbl(X) because dbl in Mul and [109], by (Fun) 131] dbl(X) >= dbl(X) because dbl in Mul and [111], by (Fun) 132] first(X, Y) >= first(X, Y) because first in Mul, [113] and [53], by (Fun) 133] first(X, Y) >= first(X, Y) because first in Mul, [52] and [126], by (Fun) 134] first(X, Y) >= first(X, Y) because first in Mul, [116] and [53], by (Fun) 135] first(X, Y) >= first(X, Y) because first in Mul, [52] and [129], by (Fun) 136] half(X) >= half(X) because half in Mul and [109], by (Fun) 137] half(X) >= half(X) because half in Mul and [111], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_19, R_0, minimal, formative) by (P_20, R_0, minimal, formative), where P_20 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) mark#(half(X)) =#> mark#(X) Thus, the original system is terminating if (P_20, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_20, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) >? mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(terms(X)) >? active#(terms(mark(X))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(sqr(X)) >? active#(sqr(mark(X))) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(add(X, Y)) >? mark#(X) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(first(X, Y)) >? mark#(X) mark#(half(X)) >? active#(half(mark(X))) mark#(half(X)) >? mark#(X) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) sqr(mark(X)) >= sqr(X) sqr(active(X)) >= sqr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) first(mark(X), Y) >= first(X, Y) first(X, mark(Y)) >= first(X, Y) first(active(X), Y) >= first(X, Y) first(X, active(Y)) >= first(X, Y) half(mark(X)) >= half(X) half(active(X)) >= half(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: [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = cons(x_1) [[mark(x_1)]] = x_1 [[nil]] = _|_ We choose Lex = {} and Mul = {0, active#, add, cons, dbl, first, half, mark#, recip, s, sqr, terms}, and the following precedence: first > terms > dbl = sqr > cons > active# = mark# > recip > add > half = s > 0 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(terms(X)) >= mark#(cons(recip(sqr(X)))) active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(add(0, X)) >= mark#(X) active#(half(s(s(X)))) >= mark#(s(half(X))) mark#(terms(X)) >= active#(terms(X)) mark#(terms(X)) >= mark#(X) mark#(cons(X)) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(sqr(X)) >= active#(sqr(X)) mark#(s(X)) >= mark#(X) mark#(add(X, Y)) >= active#(add(X, Y)) mark#(add(X, Y)) >= mark#(X) mark#(dbl(X)) >= active#(dbl(X)) mark#(dbl(X)) >= mark#(X) mark#(first(X, Y)) > mark#(X) mark#(half(X)) >= active#(half(X)) mark#(half(X)) >= mark#(X) terms(X) >= cons(recip(sqr(X))) sqr(0) >= 0 sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(0) >= 0 dbl(s(X)) >= s(s(dbl(X))) add(0, X) >= X add(s(X), Y) >= s(add(X, Y)) first(0, X) >= _|_ first(s(X), cons(Y)) >= cons(Y) half(0) >= 0 half(s(0)) >= 0 half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms(X) >= terms(X) cons(X) >= cons(X) recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) 0 >= 0 add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) _|_ >= _|_ half(X) >= half(X) terms(X) >= terms(X) terms(X) >= terms(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) recip(X) >= recip(X) recip(X) >= recip(X) sqr(X) >= sqr(X) sqr(X) >= sqr(X) s(X) >= s(X) s(X) >= s(X) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) first(X, Y) >= first(X, Y) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(terms(X)) >= mark#(cons(recip(sqr(X)))) because active# = mark#, active# in Mul and [2], by (Fun) 2] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 3] terms*(X) >= cons(recip(sqr(X))) because terms > cons and [4], by (Copy) 4] terms*(X) >= recip(sqr(X)) because terms > recip and [5], by (Copy) 5] terms*(X) >= sqr(X) because terms > sqr and [6], by (Copy) 6] terms*(X) >= X because [7], by (Select) 7] X >= X by (Meta) 8] active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because active# = mark#, active# in Mul and [9], by (Fun) 9] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [10], by (Star) 10] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [11], by (Copy) 11] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [12] and [16], by (Copy) 12] sqr*(s(X)) >= sqr(X) because sqr in Mul and [13], by (Stat) 13] s(X) > X because [14], by definition 14] s*(X) >= X because [15], by (Select) 15] X >= X by (Meta) 16] sqr*(s(X)) >= dbl(X) because sqr = dbl, sqr in Mul and [13], by (Stat) 17] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [18], by (Fun) 18] dbl(s(X)) >= s(s(dbl(X))) because [19], by (Star) 19] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [20], by (Copy) 20] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [21], by (Copy) 21] dbl*(s(X)) >= dbl(X) because dbl in Mul and [13], by (Stat) 22] active#(add(0, X)) >= mark#(X) because active# = mark#, active# in Mul and [23], by (Fun) 23] add(0, X) >= X because [24], by (Star) 24] add*(0, X) >= X because [15], by (Select) 25] active#(half(s(s(X)))) >= mark#(s(half(X))) because active# = mark#, active# in Mul and [26], by (Fun) 26] half(s(s(X))) >= s(half(X)) because half = s, half in Mul and [27], by (Fun) 27] s(s(X)) >= half(X) because s = half, s in Mul and [28], by (Fun) 28] s(X) >= X because [14], by (Star) 29] mark#(terms(X)) >= active#(terms(X)) because mark# = active#, mark# in Mul and [30], by (Fun) 30] terms(X) >= terms(X) because terms in Mul and [31], by (Fun) 31] X >= X by (Meta) 32] mark#(terms(X)) >= mark#(X) because mark# in Mul and [33], by (Fun) 33] terms(X) >= X because [34], by (Star) 34] terms*(X) >= X because [31], by (Select) 35] mark#(cons(X)) >= mark#(X) because mark# in Mul and [36], by (Fun) 36] cons(X) >= X because [37], by (Star) 37] cons*(X) >= X because [38], by (Select) 38] X >= X by (Meta) 39] mark#(recip(X)) >= mark#(X) because mark# in Mul and [40], by (Fun) 40] recip(X) >= X because [41], by (Star) 41] recip*(X) >= X because [31], by (Select) 42] mark#(sqr(X)) >= active#(sqr(X)) because mark# = active#, mark# in Mul and [43], by (Fun) 43] sqr(X) >= sqr(X) because sqr in Mul and [31], by (Fun) 44] mark#(s(X)) >= mark#(X) because mark# in Mul and [28], by (Fun) 45] mark#(add(X, Y)) >= active#(add(X, Y)) because mark# = active#, mark# in Mul and [46], by (Fun) 46] add(X, Y) >= add(X, Y) because add in Mul, [47] and [48], by (Fun) 47] X >= X by (Meta) 48] Y >= Y by (Meta) 49] mark#(add(X, Y)) >= mark#(X) because mark# in Mul and [50], by (Fun) 50] add(X, Y) >= X because [51], by (Star) 51] add*(X, Y) >= X because [47], by (Select) 52] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [53], by (Fun) 53] dbl(X) >= dbl(X) because dbl in Mul and [31], by (Fun) 54] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [55], by (Fun) 55] dbl(X) >= X because [56], by (Star) 56] dbl*(X) >= X because [31], by (Select) 57] mark#(first(X, Y)) > mark#(X) because [58], by definition 58] mark#*(first(X, Y)) >= mark#(X) because mark# in Mul and [59], by (Stat) 59] first(X, Y) > X because [60], by definition 60] first*(X, Y) >= X because [47], by (Select) 61] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [62], by (Fun) 62] half(X) >= half(X) because half in Mul and [31], by (Fun) 63] mark#(half(X)) >= mark#(X) because mark# in Mul and [64], by (Fun) 64] half(X) >= X because [65], by (Star) 65] half*(X) >= X because [31], by (Select) 66] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 67] sqr(0) >= 0 because [68], by (Star) 68] sqr*(0) >= 0 because [69], by (Select) 69] 0 >= 0 by (Fun) 70] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [10], by (Star) 71] dbl(0) >= 0 because [72], by (Star) 72] dbl*(0) >= 0 because [69], by (Select) 73] dbl(s(X)) >= s(s(dbl(X))) because [19], by (Star) 74] add(0, X) >= X because [24], by (Star) 75] add(s(X), Y) >= s(add(X, Y)) because [76], by (Star) 76] add*(s(X), Y) >= s(add(X, Y)) because add > s and [77], by (Copy) 77] add*(s(X), Y) >= add(X, Y) because add in Mul, [13] and [78], by (Stat) 78] Y >= Y by (Meta) 79] first(0, X) >= _|_ by (Bot) 80] first(s(X), cons(Y)) >= cons(Y) because [81], by (Star) 81] first*(s(X), cons(Y)) >= cons(Y) because [82], by (Select) 82] cons(Y) >= cons(Y) because cons in Mul and [78], by (Fun) 83] half(0) >= 0 because [84], by (Star) 84] half*(0) >= 0 because [69], by (Select) 85] half(s(0)) >= 0 because [86], by (Star) 86] half*(s(0)) >= 0 because [87], by (Select) 87] s(0) >= 0 because [88], by (Star) 88] s*(0) >= 0 because s > 0, by (Copy) 89] half(s(s(X))) >= s(half(X)) because half = s, half in Mul and [27], by (Fun) 90] half(dbl(X)) >= X because [91], by (Star) 91] half*(dbl(X)) >= X because [55], by (Select) 92] terms(X) >= terms(X) because terms in Mul and [31], by (Fun) 93] cons(X) >= cons(X) because cons in Mul and [47], by (Fun) 94] recip(X) >= recip(X) because recip in Mul and [31], by (Fun) 95] sqr(X) >= sqr(X) because sqr in Mul and [31], by (Fun) 96] s(X) >= s(X) because s in Mul and [31], by (Fun) 97] 0 >= 0 by (Fun) 98] add(X, Y) >= add(X, Y) because add in Mul, [47] and [48], by (Fun) 99] dbl(X) >= dbl(X) because dbl in Mul and [31], by (Fun) 100] first(X, Y) >= first(X, Y) because first in Mul, [47] and [48], by (Fun) 101] _|_ >= _|_ by (Bot) 102] half(X) >= half(X) because half in Mul and [31], by (Fun) 103] terms(X) >= terms(X) because terms in Mul and [104], by (Fun) 104] X >= X by (Meta) 105] terms(X) >= terms(X) because terms in Mul and [106], by (Fun) 106] X >= X by (Meta) 107] cons(X) >= cons(X) because cons in Mul and [108], by (Fun) 108] X >= X by (Meta) 109] cons(X) >= cons(X) because cons in Mul and [47], by (Fun) 110] cons(X) >= cons(X) because cons in Mul and [111], by (Fun) 111] X >= X by (Meta) 112] cons(X) >= cons(X) because cons in Mul and [47], by (Fun) 113] recip(X) >= recip(X) because recip in Mul and [104], by (Fun) 114] recip(X) >= recip(X) because recip in Mul and [106], by (Fun) 115] sqr(X) >= sqr(X) because sqr in Mul and [104], by (Fun) 116] sqr(X) >= sqr(X) because sqr in Mul and [106], by (Fun) 117] s(X) >= s(X) because s in Mul and [104], by (Fun) 118] s(X) >= s(X) because s in Mul and [106], by (Fun) 119] add(X, Y) >= add(X, Y) because add in Mul, [108] and [48], by (Fun) 120] add(X, Y) >= add(X, Y) because add in Mul, [47] and [121], by (Fun) 121] Y >= Y by (Meta) 122] add(X, Y) >= add(X, Y) because add in Mul, [111] and [48], by (Fun) 123] add(X, Y) >= add(X, Y) because add in Mul, [47] and [124], by (Fun) 124] Y >= Y by (Meta) 125] dbl(X) >= dbl(X) because dbl in Mul and [104], by (Fun) 126] dbl(X) >= dbl(X) because dbl in Mul and [106], by (Fun) 127] first(X, Y) >= first(X, Y) because first in Mul, [108] and [48], by (Fun) 128] first(X, Y) >= first(X, Y) because first in Mul, [47] and [121], by (Fun) 129] first(X, Y) >= first(X, Y) because first in Mul, [111] and [48], by (Fun) 130] first(X, Y) >= first(X, Y) because first in Mul, [47] and [124], by (Fun) 131] half(X) >= half(X) because half in Mul and [104], by (Fun) 132] half(X) >= half(X) because half in Mul and [106], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_20, R_0, minimal, formative) by (P_21, R_0, minimal, formative), where P_21 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) mark#(half(X)) =#> mark#(X) Thus, the original system is terminating if (P_21, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_21, R_0, minimal, formative). The formative rules of (P_21, R_0) are R_1 ::= active(terms(X)) => mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) => mark(0) active(sqr(s(X))) => mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) => mark(0) active(dbl(s(X))) => mark(s(s(dbl(X)))) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(half(0)) => mark(0) active(half(s(0))) => mark(0) active(half(s(s(X)))) => mark(s(half(X))) active(half(dbl(X))) => mark(X) mark(terms(X)) => active(terms(mark(X))) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(recip(X)) => active(recip(mark(X))) mark(sqr(X)) => active(sqr(mark(X))) mark(s(X)) => active(s(mark(X))) mark(0) => active(0) mark(add(X, Y)) => active(add(mark(X), mark(Y))) mark(dbl(X)) => active(dbl(mark(X))) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(half(X)) => active(half(mark(X))) terms(mark(X)) => terms(X) terms(active(X)) => terms(X) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) recip(mark(X)) => recip(X) recip(active(X)) => recip(X) sqr(mark(X)) => sqr(X) sqr(active(X)) => sqr(X) s(mark(X)) => s(X) s(active(X)) => s(X) add(mark(X), Y) => add(X, Y) add(X, mark(Y)) => add(X, Y) add(active(X), Y) => add(X, Y) add(X, active(Y)) => add(X, Y) dbl(mark(X)) => dbl(X) dbl(active(X)) => dbl(X) half(mark(X)) => half(X) half(active(X)) => half(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_21, R_0, minimal, formative) by (P_21, R_1, minimal, formative). Thus, the original system is terminating if (P_21, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_21, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) >? mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(terms(X)) >? active#(terms(mark(X))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(sqr(X)) >? active#(sqr(mark(X))) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(add(X, Y)) >? mark#(X) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(half(X)) >? active#(half(mark(X))) mark#(half(X)) >? mark#(X) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) sqr(mark(X)) >= sqr(X) sqr(active(X)) >= sqr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) half(mark(X)) >= half(X) half(active(X)) >= half(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]] = _|_ [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = x_1 [[first(x_1, x_2)]] = first(x_2, x_1) [[mark(x_1)]] = x_1 [[nil]] = _|_ We choose Lex = {first} and Mul = {active#, add, dbl, half, mark#, recip, s, sqr, terms}, and the following precedence: terms > dbl = sqr > add > first > half = s > active# = mark# = recip Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(terms(X)) >= mark#(recip(sqr(X))) active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(add(_|_, X)) >= mark#(X) active#(half(s(s(X)))) >= mark#(s(half(X))) mark#(terms(X)) >= active#(terms(X)) mark#(terms(X)) >= mark#(X) mark#(X) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(sqr(X)) >= active#(sqr(X)) mark#(s(X)) >= mark#(X) mark#(add(X, Y)) >= active#(add(X, Y)) mark#(add(X, Y)) >= mark#(X) mark#(dbl(X)) >= active#(dbl(X)) mark#(dbl(X)) >= mark#(X) mark#(half(X)) >= active#(half(X)) mark#(half(X)) > mark#(X) terms(X) >= recip(sqr(X)) sqr(_|_) >= _|_ sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(_|_) >= _|_ dbl(s(X)) >= s(s(dbl(X))) add(_|_, X) >= X add(s(X), Y) >= s(add(X, Y)) first(_|_, X) >= _|_ first(s(X), Y) >= Y half(_|_) >= _|_ half(s(_|_)) >= _|_ half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms(X) >= terms(X) X >= X recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) _|_ >= _|_ add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) _|_ >= _|_ half(X) >= half(X) terms(X) >= terms(X) terms(X) >= terms(X) X >= X X >= X X >= X X >= X recip(X) >= recip(X) recip(X) >= recip(X) sqr(X) >= sqr(X) sqr(X) >= sqr(X) s(X) >= s(X) s(X) >= s(X) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) dbl(X) >= dbl(X) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(terms(X)) >= mark#(recip(sqr(X))) because active# = mark#, active# in Mul and [2], by (Fun) 2] terms(X) >= recip(sqr(X)) because [3], by (Star) 3] terms*(X) >= recip(sqr(X)) because terms > recip and [4], by (Copy) 4] terms*(X) >= sqr(X) because terms > sqr and [5], by (Copy) 5] terms*(X) >= X because [6], by (Select) 6] X >= X by (Meta) 7] active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because active# = mark#, active# in Mul and [8], by (Fun) 8] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [9], by (Star) 9] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [10], by (Copy) 10] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [11] and [15], by (Copy) 11] sqr*(s(X)) >= sqr(X) because sqr in Mul and [12], by (Stat) 12] s(X) > X because [13], by definition 13] s*(X) >= X because [14], by (Select) 14] X >= X by (Meta) 15] sqr*(s(X)) >= dbl(X) because sqr = dbl, sqr in Mul and [12], by (Stat) 16] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [17], by (Fun) 17] dbl(s(X)) >= s(s(dbl(X))) because [18], by (Star) 18] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [19], by (Copy) 19] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [20], by (Copy) 20] dbl*(s(X)) >= dbl(X) because dbl in Mul and [12], by (Stat) 21] active#(add(_|_, X)) >= mark#(X) because active# = mark#, active# in Mul and [22], by (Fun) 22] add(_|_, X) >= X because [23], by (Star) 23] add*(_|_, X) >= X because [14], by (Select) 24] active#(half(s(s(X)))) >= mark#(s(half(X))) because active# = mark#, active# in Mul and [25], by (Fun) 25] half(s(s(X))) >= s(half(X)) because half = s, half in Mul and [26], by (Fun) 26] s(s(X)) >= half(X) because [27], by (Star) 27] s*(s(X)) >= half(X) because s = half, s in Mul and [12], by (Stat) 28] mark#(terms(X)) >= active#(terms(X)) because mark# = active#, mark# in Mul and [29], by (Fun) 29] terms(X) >= terms(X) because terms in Mul and [30], by (Fun) 30] X >= X by (Meta) 31] mark#(terms(X)) >= mark#(X) because [32], by (Star) 32] mark#*(terms(X)) >= mark#(X) because mark# in Mul and [33], by (Stat) 33] terms(X) > X because [34], by definition 34] terms*(X) >= X because [30], by (Select) 35] mark#(X) >= mark#(X) because mark# in Mul and [36], by (Fun) 36] X >= X by (Meta) 37] mark#(recip(X)) >= mark#(X) because [38], by (Star) 38] mark#*(recip(X)) >= mark#(X) because [39], by (Select) 39] recip(X) >= mark#(X) because recip = mark#, recip in Mul and [30], by (Fun) 40] mark#(sqr(X)) >= active#(sqr(X)) because mark# = active#, mark# in Mul and [41], by (Fun) 41] sqr(X) >= sqr(X) because sqr in Mul and [30], by (Fun) 42] mark#(s(X)) >= mark#(X) because mark# in Mul and [43], by (Fun) 43] s(X) >= X because [13], by (Star) 44] mark#(add(X, Y)) >= active#(add(X, Y)) because mark# = active#, mark# in Mul and [45], by (Fun) 45] add(X, Y) >= add(X, Y) because add in Mul, [46] and [47], by (Fun) 46] X >= X by (Meta) 47] Y >= Y by (Meta) 48] mark#(add(X, Y)) >= mark#(X) because mark# in Mul and [49], by (Fun) 49] add(X, Y) >= X because [50], by (Star) 50] add*(X, Y) >= X because [46], by (Select) 51] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [52], by (Fun) 52] dbl(X) >= dbl(X) because dbl in Mul and [30], by (Fun) 53] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [54], by (Fun) 54] dbl(X) >= X because [55], by (Star) 55] dbl*(X) >= X because [30], by (Select) 56] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [57], by (Fun) 57] half(X) >= half(X) because half in Mul and [30], by (Fun) 58] mark#(half(X)) > mark#(X) because [59], by definition 59] mark#*(half(X)) >= mark#(X) because mark# in Mul and [60], by (Stat) 60] half(X) > X because [61], by definition 61] half*(X) >= X because [30], by (Select) 62] terms(X) >= recip(sqr(X)) because [3], by (Star) 63] sqr(_|_) >= _|_ by (Bot) 64] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [9], by (Star) 65] dbl(_|_) >= _|_ by (Bot) 66] dbl(s(X)) >= s(s(dbl(X))) because [18], by (Star) 67] add(_|_, X) >= X because [23], by (Star) 68] add(s(X), Y) >= s(add(X, Y)) because [69], by (Star) 69] add*(s(X), Y) >= s(add(X, Y)) because add > s and [70], by (Copy) 70] add*(s(X), Y) >= add(X, Y) because add in Mul, [12] and [71], by (Stat) 71] Y >= Y by (Meta) 72] first(_|_, X) >= _|_ by (Bot) 73] first(s(X), Y) >= Y because [74], by (Star) 74] first*(s(X), Y) >= Y because [75], by (Select) 75] Y >= Y by (Meta) 76] half(_|_) >= _|_ by (Bot) 77] half(s(_|_)) >= _|_ by (Bot) 78] half(s(s(X))) >= s(half(X)) because half = s, half in Mul and [26], by (Fun) 79] half(dbl(X)) >= X because [80], by (Star) 80] half*(dbl(X)) >= X because [54], by (Select) 81] terms(X) >= terms(X) because terms in Mul and [30], by (Fun) 82] X >= X by (Meta) 83] recip(X) >= recip(X) because recip in Mul and [30], by (Fun) 84] sqr(X) >= sqr(X) because sqr in Mul and [30], by (Fun) 85] s(X) >= s(X) because s in Mul and [30], by (Fun) 86] _|_ >= _|_ by (Bot) 87] add(X, Y) >= add(X, Y) because add in Mul, [46] and [47], by (Fun) 88] dbl(X) >= dbl(X) because dbl in Mul and [30], by (Fun) 89] first(X, Y) >= first(X, Y) because [46] and [47], by (Fun) 90] _|_ >= _|_ by (Bot) 91] half(X) >= half(X) because half in Mul and [30], by (Fun) 92] terms(X) >= terms(X) because terms in Mul and [93], by (Fun) 93] X >= X by (Meta) 94] terms(X) >= terms(X) because terms in Mul and [95], by (Fun) 95] X >= X by (Meta) 96] X >= X by (Meta) 97] X >= X by (Meta) 98] X >= X by (Meta) 99] X >= X by (Meta) 100] recip(X) >= recip(X) because recip in Mul and [93], by (Fun) 101] recip(X) >= recip(X) because recip in Mul and [95], by (Fun) 102] sqr(X) >= sqr(X) because sqr in Mul and [93], by (Fun) 103] sqr(X) >= sqr(X) because sqr in Mul and [95], by (Fun) 104] s(X) >= s(X) because s in Mul and [93], by (Fun) 105] s(X) >= s(X) because s in Mul and [95], by (Fun) 106] add(X, Y) >= add(X, Y) because add in Mul, [107] and [47], by (Fun) 107] X >= X by (Meta) 108] add(X, Y) >= add(X, Y) because add in Mul, [46] and [109], by (Fun) 109] Y >= Y by (Meta) 110] add(X, Y) >= add(X, Y) because add in Mul, [111] and [47], by (Fun) 111] X >= X by (Meta) 112] add(X, Y) >= add(X, Y) because add in Mul, [46] and [113], by (Fun) 113] Y >= Y by (Meta) 114] dbl(X) >= dbl(X) because dbl in Mul and [93], by (Fun) 115] dbl(X) >= dbl(X) because dbl in Mul and [95], by (Fun) 116] half(X) >= half(X) because half in Mul and [93], by (Fun) 117] half(X) >= half(X) because half in Mul and [95], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_21, R_1, minimal, formative) by (P_22, R_1, minimal, formative), where P_22 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) =#> mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) Thus, the original system is terminating if (P_22, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_22, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) active#(sqr(s(X))) >? mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(terms(X)) >? active#(terms(mark(X))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(sqr(X)) >? active#(sqr(mark(X))) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(add(X, Y)) >? mark#(X) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(half(X)) >? active#(half(mark(X))) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) sqr(mark(X)) >= sqr(X) sqr(active(X)) >= sqr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) half(mark(X)) >= half(X) half(active(X)) >= half(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]] = _|_ [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = cons(x_1) [[mark(x_1)]] = x_1 We choose Lex = {recip} and Mul = {active#, add, cons, dbl, first, half, mark#, nil, s, sqr, terms}, and the following precedence: terms > first > active# = mark# > recip > sqr > add > dbl > half = s > nil > cons Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(terms(X)) >= mark#(cons(recip(sqr(X)))) active#(sqr(s(X))) > mark#(s(add(sqr(X), dbl(X)))) active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(add(_|_, X)) >= mark#(X) active#(half(s(s(X)))) >= mark#(s(half(X))) mark#(terms(X)) >= active#(terms(X)) mark#(terms(X)) >= mark#(X) mark#(cons(X)) >= mark#(X) mark#(recip(X)) >= mark#(X) mark#(sqr(X)) >= active#(sqr(X)) mark#(s(X)) >= mark#(X) mark#(add(X, Y)) >= active#(add(X, Y)) mark#(add(X, Y)) >= mark#(X) mark#(dbl(X)) >= active#(dbl(X)) mark#(dbl(X)) >= mark#(X) mark#(half(X)) >= active#(half(X)) terms(X) >= cons(recip(sqr(X))) sqr(_|_) >= _|_ sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(_|_) >= _|_ dbl(s(X)) >= s(s(dbl(X))) add(_|_, X) >= X add(s(X), Y) >= s(add(X, Y)) first(_|_, X) >= nil first(s(X), cons(Y)) >= cons(Y) half(_|_) >= _|_ half(s(_|_)) >= _|_ half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms(X) >= terms(X) cons(X) >= cons(X) recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) _|_ >= _|_ add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) nil >= nil half(X) >= half(X) terms(X) >= terms(X) terms(X) >= terms(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) recip(X) >= recip(X) recip(X) >= recip(X) sqr(X) >= sqr(X) sqr(X) >= sqr(X) s(X) >= s(X) s(X) >= s(X) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) dbl(X) >= dbl(X) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(terms(X)) >= mark#(cons(recip(sqr(X)))) because active# = mark#, active# in Mul and [2], by (Fun) 2] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 3] terms*(X) >= cons(recip(sqr(X))) because terms > cons and [4], by (Copy) 4] terms*(X) >= recip(sqr(X)) because terms > recip and [5], by (Copy) 5] terms*(X) >= sqr(X) because terms > sqr and [6], by (Copy) 6] terms*(X) >= X because [7], by (Select) 7] X >= X by (Meta) 8] active#(sqr(s(X))) > mark#(s(add(sqr(X), dbl(X)))) because [9], by definition 9] active#*(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because active# = mark#, active# in Mul and [10], by (Stat) 10] sqr(s(X)) > s(add(sqr(X), dbl(X))) because [11], by definition 11] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [12], by (Copy) 12] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [13] and [17], by (Copy) 13] sqr*(s(X)) >= sqr(X) because sqr in Mul and [14], by (Stat) 14] s(X) > X because [15], by definition 15] s*(X) >= X because [16], by (Select) 16] X >= X by (Meta) 17] sqr*(s(X)) >= dbl(X) because sqr > dbl and [18], by (Copy) 18] sqr*(s(X)) >= X because [19], by (Select) 19] s(X) >= X because [15], by (Star) 20] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [21], by (Fun) 21] dbl(s(X)) >= s(s(dbl(X))) because [22], by (Star) 22] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [23], by (Copy) 23] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [24], by (Copy) 24] dbl*(s(X)) >= dbl(X) because dbl in Mul and [14], by (Stat) 25] active#(add(_|_, X)) >= mark#(X) because [26], by (Star) 26] active#*(add(_|_, X)) >= mark#(X) because active# = mark#, active# in Mul and [27], by (Stat) 27] add(_|_, X) > X because [28], by definition 28] add*(_|_, X) >= X because [16], by (Select) 29] active#(half(s(s(X)))) >= mark#(s(half(X))) because active# = mark#, active# in Mul and [30], by (Fun) 30] half(s(s(X))) >= s(half(X)) because [31], by (Star) 31] half*(s(s(X))) >= s(half(X)) because half = s, half in Mul and [32], by (Stat) 32] s(s(X)) > half(X) because [33], by definition 33] s*(s(X)) >= half(X) because s = half, s in Mul and [14], by (Stat) 34] mark#(terms(X)) >= active#(terms(X)) because mark# = active#, mark# in Mul and [35], by (Fun) 35] terms(X) >= terms(X) because terms in Mul and [36], by (Fun) 36] X >= X by (Meta) 37] mark#(terms(X)) >= mark#(X) because mark# in Mul and [38], by (Fun) 38] terms(X) >= X because [39], by (Star) 39] terms*(X) >= X because [36], by (Select) 40] mark#(cons(X)) >= mark#(X) because mark# in Mul and [41], by (Fun) 41] cons(X) >= X because [42], by (Star) 42] cons*(X) >= X because [43], by (Select) 43] X >= X by (Meta) 44] mark#(recip(X)) >= mark#(X) because mark# in Mul and [45], by (Fun) 45] recip(X) >= X because [46], by (Star) 46] recip*(X) >= X because [36], by (Select) 47] mark#(sqr(X)) >= active#(sqr(X)) because mark# = active#, mark# in Mul and [48], by (Fun) 48] sqr(X) >= sqr(X) because sqr in Mul and [36], by (Fun) 49] mark#(s(X)) >= mark#(X) because [50], by (Star) 50] mark#*(s(X)) >= mark#(X) because mark# in Mul and [14], by (Stat) 51] mark#(add(X, Y)) >= active#(add(X, Y)) because mark# = active#, mark# in Mul and [52], by (Fun) 52] add(X, Y) >= add(X, Y) because add in Mul, [53] and [54], by (Fun) 53] X >= X by (Meta) 54] Y >= Y by (Meta) 55] mark#(add(X, Y)) >= mark#(X) because mark# in Mul and [56], by (Fun) 56] add(X, Y) >= X because [57], by (Star) 57] add*(X, Y) >= X because [53], by (Select) 58] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [59], by (Fun) 59] dbl(X) >= dbl(X) because dbl in Mul and [36], by (Fun) 60] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [61], by (Fun) 61] dbl(X) >= X because [62], by (Star) 62] dbl*(X) >= X because [36], by (Select) 63] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [64], by (Fun) 64] half(X) >= half(X) because half in Mul and [36], by (Fun) 65] terms(X) >= cons(recip(sqr(X))) because [3], by (Star) 66] sqr(_|_) >= _|_ by (Bot) 67] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [11], by (Star) 68] dbl(_|_) >= _|_ by (Bot) 69] dbl(s(X)) >= s(s(dbl(X))) because [22], by (Star) 70] add(_|_, X) >= X because [28], by (Star) 71] add(s(X), Y) >= s(add(X, Y)) because [72], by (Star) 72] add*(s(X), Y) >= s(add(X, Y)) because add > s and [73], by (Copy) 73] add*(s(X), Y) >= add(X, Y) because add in Mul, [14] and [74], by (Stat) 74] Y >= Y by (Meta) 75] first(_|_, X) >= nil because [76], by (Star) 76] first*(_|_, X) >= nil because first > nil, by (Copy) 77] first(s(X), cons(Y)) >= cons(Y) because [78], by (Star) 78] first*(s(X), cons(Y)) >= cons(Y) because first > cons and [79], by (Copy) 79] first*(s(X), cons(Y)) >= Y because [80], by (Select) 80] cons(Y) >= Y because [81], by (Star) 81] cons*(Y) >= Y because [74], by (Select) 82] half(_|_) >= _|_ by (Bot) 83] half(s(_|_)) >= _|_ by (Bot) 84] half(s(s(X))) >= s(half(X)) because [31], by (Star) 85] half(dbl(X)) >= X because [86], by (Star) 86] half*(dbl(X)) >= X because [61], by (Select) 87] terms(X) >= terms(X) because terms in Mul and [36], by (Fun) 88] cons(X) >= cons(X) because cons in Mul and [53], by (Fun) 89] recip(X) >= recip(X) because [36], by (Fun) 90] sqr(X) >= sqr(X) because sqr in Mul and [36], by (Fun) 91] s(X) >= s(X) because s in Mul and [36], by (Fun) 92] _|_ >= _|_ by (Bot) 93] add(X, Y) >= add(X, Y) because add in Mul, [53] and [54], by (Fun) 94] dbl(X) >= dbl(X) because dbl in Mul and [36], by (Fun) 95] first(X, Y) >= first(X, Y) because first in Mul, [53] and [54], by (Fun) 96] nil >= nil by (Fun) 97] half(X) >= half(X) because half in Mul and [36], by (Fun) 98] terms(X) >= terms(X) because terms in Mul and [99], by (Fun) 99] X >= X by (Meta) 100] terms(X) >= terms(X) because terms in Mul and [101], by (Fun) 101] X >= X by (Meta) 102] cons(X) >= cons(X) because cons in Mul and [103], by (Fun) 103] X >= X by (Meta) 104] cons(X) >= cons(X) because cons in Mul and [53], by (Fun) 105] cons(X) >= cons(X) because cons in Mul and [106], by (Fun) 106] X >= X by (Meta) 107] cons(X) >= cons(X) because cons in Mul and [53], by (Fun) 108] recip(X) >= recip(X) because [99], by (Fun) 109] recip(X) >= recip(X) because [101], by (Fun) 110] sqr(X) >= sqr(X) because sqr in Mul and [99], by (Fun) 111] sqr(X) >= sqr(X) because sqr in Mul and [101], by (Fun) 112] s(X) >= s(X) because s in Mul and [99], by (Fun) 113] s(X) >= s(X) because s in Mul and [101], by (Fun) 114] add(X, Y) >= add(X, Y) because add in Mul, [103] and [54], by (Fun) 115] add(X, Y) >= add(X, Y) because add in Mul, [53] and [116], by (Fun) 116] Y >= Y by (Meta) 117] add(X, Y) >= add(X, Y) because add in Mul, [106] and [54], by (Fun) 118] add(X, Y) >= add(X, Y) because add in Mul, [53] and [119], by (Fun) 119] Y >= Y by (Meta) 120] dbl(X) >= dbl(X) because dbl in Mul and [99], by (Fun) 121] dbl(X) >= dbl(X) because dbl in Mul and [101], by (Fun) 122] half(X) >= half(X) because half in Mul and [99], by (Fun) 123] half(X) >= half(X) because half in Mul and [101], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_22, R_1, minimal, formative) by (P_23, R_1, minimal, formative), where P_23 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> active#(sqr(mark(X))) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) Thus, the original system is terminating if (P_23, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_23, 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 : 6 * 1 : 9 * 2 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 3 : 9 * 4 : 0 * 5 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 6 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 7 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 8 : * 9 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 10 : 2 * 11 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 12 : 1 * 13 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 * 14 : 3 This graph has the following strongly connected components: P_24: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(add(X, Y)) =#> mark#(X) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_23, R_1, m, f) by (P_24, R_1, m, f). Thus, the original system is terminating if (P_24, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_24, R_1, minimal, formative). The formative rules of (P_24, R_1) are R_2 ::= active(terms(X)) => mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) => mark(0) active(sqr(s(X))) => mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) => mark(0) active(dbl(s(X))) => mark(s(s(dbl(X)))) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(half(0)) => mark(0) active(half(s(0))) => mark(0) active(half(s(s(X)))) => mark(s(half(X))) active(half(dbl(X))) => mark(X) mark(terms(X)) => active(terms(mark(X))) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(recip(X)) => active(recip(mark(X))) mark(sqr(X)) => active(sqr(mark(X))) mark(s(X)) => active(s(mark(X))) mark(0) => active(0) mark(add(X, Y)) => active(add(mark(X), mark(Y))) mark(dbl(X)) => active(dbl(mark(X))) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(half(X)) => active(half(mark(X))) terms(mark(X)) => terms(X) terms(active(X)) => terms(X) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) recip(mark(X)) => recip(X) recip(active(X)) => recip(X) s(mark(X)) => s(X) s(active(X)) => s(X) add(mark(X), Y) => add(X, Y) add(X, mark(Y)) => add(X, Y) add(active(X), Y) => add(X, Y) add(X, active(Y)) => add(X, Y) dbl(mark(X)) => dbl(X) dbl(active(X)) => dbl(X) half(mark(X)) => half(X) half(active(X)) => half(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_24, R_1, minimal, formative) by (P_24, R_2, minimal, formative). Thus, the original system is terminating if (P_24, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_24, R_2, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(terms(X)) >? active#(terms(mark(X))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(add(X, Y)) >? mark#(X) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(half(X)) >? active#(half(mark(X))) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) half(mark(X)) >= half(X) half(active(X)) >= half(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: [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = cons(x_1) [[mark(x_1)]] = x_1 [[nil]] = _|_ We choose Lex = {} and Mul = {0, active#, add, cons, dbl, first, half, mark#, recip, s, sqr, terms}, and the following precedence: terms > sqr > add > 0 > active# = mark# > cons = first > recip > dbl > s > half Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(terms(X)) > mark#(cons(recip(sqr(X)))) active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(add(0, X)) >= mark#(X) active#(half(s(s(X)))) >= mark#(s(half(X))) mark#(terms(X)) >= active#(terms(X)) mark#(terms(X)) >= mark#(X) mark#(cons(X)) > mark#(X) mark#(recip(X)) >= mark#(X) mark#(s(X)) >= mark#(X) mark#(add(X, Y)) >= active#(add(X, Y)) mark#(add(X, Y)) > mark#(X) mark#(dbl(X)) >= active#(dbl(X)) mark#(dbl(X)) >= mark#(X) mark#(half(X)) >= active#(half(X)) terms(X) >= cons(recip(sqr(X))) sqr(0) >= 0 sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(0) >= 0 dbl(s(X)) >= s(s(dbl(X))) add(0, X) >= X add(s(X), Y) >= s(add(X, Y)) first(0, X) >= _|_ first(s(X), cons(Y)) >= cons(Y) half(0) >= 0 half(s(0)) >= 0 half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms(X) >= terms(X) cons(X) >= cons(X) recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) 0 >= 0 add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) first(X, Y) >= first(X, Y) _|_ >= _|_ half(X) >= half(X) terms(X) >= terms(X) terms(X) >= terms(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) cons(X) >= cons(X) recip(X) >= recip(X) recip(X) >= recip(X) s(X) >= s(X) s(X) >= s(X) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) dbl(X) >= dbl(X) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(terms(X)) > mark#(cons(recip(sqr(X)))) because [2], by definition 2] active#*(terms(X)) >= mark#(cons(recip(sqr(X)))) because active# = mark#, active# in Mul and [3], by (Stat) 3] terms(X) > cons(recip(sqr(X))) because [4], by definition 4] terms*(X) >= cons(recip(sqr(X))) because terms > cons and [5], by (Copy) 5] terms*(X) >= recip(sqr(X)) because terms > recip and [6], by (Copy) 6] terms*(X) >= sqr(X) because terms > sqr and [7], by (Copy) 7] terms*(X) >= X because [8], by (Select) 8] X >= X by (Meta) 9] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [10], by (Fun) 10] dbl(s(X)) >= s(s(dbl(X))) because [11], by (Star) 11] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [12], by (Copy) 12] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [13], by (Copy) 13] dbl*(s(X)) >= dbl(X) because dbl in Mul and [14], by (Stat) 14] s(X) > X because [15], by definition 15] s*(X) >= X because [16], by (Select) 16] X >= X by (Meta) 17] active#(add(0, X)) >= mark#(X) because active# = mark#, active# in Mul and [18], by (Fun) 18] add(0, X) >= X because [19], by (Star) 19] add*(0, X) >= X because [16], by (Select) 20] active#(half(s(s(X)))) >= mark#(s(half(X))) because active# = mark#, active# in Mul and [21], by (Fun) 21] half(s(s(X))) >= s(half(X)) because [22], by (Star) 22] half*(s(s(X))) >= s(half(X)) because [23], by (Select) 23] s(s(X)) >= s(half(X)) because s in Mul and [24], by (Fun) 24] s(X) >= half(X) because [25], by (Star) 25] s*(X) >= half(X) because s > half and [15], by (Copy) 26] mark#(terms(X)) >= active#(terms(X)) because mark# = active#, mark# in Mul and [27], by (Fun) 27] terms(X) >= terms(X) because terms in Mul and [28], by (Fun) 28] X >= X by (Meta) 29] mark#(terms(X)) >= mark#(X) because mark# in Mul and [30], by (Fun) 30] terms(X) >= X because [31], by (Star) 31] terms*(X) >= X because [28], by (Select) 32] mark#(cons(X)) > mark#(X) because [33], by definition 33] mark#*(cons(X)) >= mark#(X) because mark# in Mul and [34], by (Stat) 34] cons(X) > X because [35], by definition 35] cons*(X) >= X because [36], by (Select) 36] X >= X by (Meta) 37] mark#(recip(X)) >= mark#(X) because [38], by (Star) 38] mark#*(recip(X)) >= mark#(X) because mark# in Mul and [39], by (Stat) 39] recip(X) > X because [40], by definition 40] recip*(X) >= X because [28], by (Select) 41] mark#(s(X)) >= mark#(X) because mark# in Mul and [42], by (Fun) 42] s(X) >= X because [15], by (Star) 43] mark#(add(X, Y)) >= active#(add(X, Y)) because mark# = active#, mark# in Mul and [44], by (Fun) 44] add(X, Y) >= add(X, Y) because add in Mul, [45] and [46], by (Fun) 45] X >= X by (Meta) 46] Y >= Y by (Meta) 47] mark#(add(X, Y)) > mark#(X) because [48], by definition 48] mark#*(add(X, Y)) >= mark#(X) because [49], by (Select) 49] add(X, Y) >= mark#(X) because [50], by (Star) 50] add*(X, Y) >= mark#(X) because add > mark# and [51], by (Copy) 51] add*(X, Y) >= X because [45], by (Select) 52] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [53], by (Fun) 53] dbl(X) >= dbl(X) because dbl in Mul and [28], by (Fun) 54] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [55], by (Fun) 55] dbl(X) >= X because [56], by (Star) 56] dbl*(X) >= X because [28], by (Select) 57] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [58], by (Fun) 58] half(X) >= half(X) because half in Mul and [28], by (Fun) 59] terms(X) >= cons(recip(sqr(X))) because [4], by (Star) 60] sqr(0) >= 0 because [61], by (Star) 61] sqr*(0) >= 0 because [62], by (Select) 62] 0 >= 0 by (Fun) 63] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [64], by (Star) 64] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [65], by (Copy) 65] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [66] and [67], by (Copy) 66] sqr*(s(X)) >= sqr(X) because sqr in Mul and [14], by (Stat) 67] sqr*(s(X)) >= dbl(X) because sqr > dbl and [68], by (Copy) 68] sqr*(s(X)) >= X because [42], by (Select) 69] dbl(0) >= 0 because [70], by (Star) 70] dbl*(0) >= 0 because [62], by (Select) 71] dbl(s(X)) >= s(s(dbl(X))) because [11], by (Star) 72] add(0, X) >= X because [19], by (Star) 73] add(s(X), Y) >= s(add(X, Y)) because [74], by (Star) 74] add*(s(X), Y) >= s(add(X, Y)) because add > s and [75], by (Copy) 75] add*(s(X), Y) >= add(X, Y) because add in Mul, [14] and [76], by (Stat) 76] Y >= Y by (Meta) 77] first(0, X) >= _|_ by (Bot) 78] first(s(X), cons(Y)) >= cons(Y) because [79], by (Star) 79] first*(s(X), cons(Y)) >= cons(Y) because first = cons, first in Mul and [80], by (Stat) 80] cons(Y) >= Y because [81], by (Star) 81] cons*(Y) >= Y because [76], by (Select) 82] half(0) >= 0 because [83], by (Star) 83] half*(0) >= 0 because [62], by (Select) 84] half(s(0)) >= 0 because [85], by (Star) 85] half*(s(0)) >= 0 because [86], by (Select) 86] s(0) >= 0 because [87], by (Star) 87] s*(0) >= 0 because [62], by (Select) 88] half(s(s(X))) >= s(half(X)) because [22], by (Star) 89] half(dbl(X)) >= X because [90], by (Star) 90] half*(dbl(X)) >= X because [55], by (Select) 91] terms(X) >= terms(X) because terms in Mul and [28], by (Fun) 92] cons(X) >= cons(X) because cons in Mul and [45], by (Fun) 93] recip(X) >= recip(X) because recip in Mul and [28], by (Fun) 94] sqr(X) >= sqr(X) because sqr in Mul and [28], by (Fun) 95] s(X) >= s(X) because s in Mul and [28], by (Fun) 96] 0 >= 0 by (Fun) 97] add(X, Y) >= add(X, Y) because add in Mul, [45] and [46], by (Fun) 98] dbl(X) >= dbl(X) because dbl in Mul and [28], by (Fun) 99] first(X, Y) >= first(X, Y) because first in Mul, [45] and [46], by (Fun) 100] _|_ >= _|_ by (Bot) 101] half(X) >= half(X) because half in Mul and [28], by (Fun) 102] terms(X) >= terms(X) because terms in Mul and [103], by (Fun) 103] X >= X by (Meta) 104] terms(X) >= terms(X) because terms in Mul and [105], by (Fun) 105] X >= X by (Meta) 106] cons(X) >= cons(X) because cons in Mul and [107], by (Fun) 107] X >= X by (Meta) 108] cons(X) >= cons(X) because cons in Mul and [45], by (Fun) 109] cons(X) >= cons(X) because cons in Mul and [110], by (Fun) 110] X >= X by (Meta) 111] cons(X) >= cons(X) because cons in Mul and [45], by (Fun) 112] recip(X) >= recip(X) because recip in Mul and [103], by (Fun) 113] recip(X) >= recip(X) because recip in Mul and [105], by (Fun) 114] s(X) >= s(X) because s in Mul and [103], by (Fun) 115] s(X) >= s(X) because s in Mul and [105], by (Fun) 116] add(X, Y) >= add(X, Y) because add in Mul, [107] and [46], by (Fun) 117] add(X, Y) >= add(X, Y) because add in Mul, [45] and [118], by (Fun) 118] Y >= Y by (Meta) 119] add(X, Y) >= add(X, Y) because add in Mul, [110] and [46], by (Fun) 120] add(X, Y) >= add(X, Y) because add in Mul, [45] and [121], by (Fun) 121] Y >= Y by (Meta) 122] dbl(X) >= dbl(X) because dbl in Mul and [103], by (Fun) 123] dbl(X) >= dbl(X) because dbl in Mul and [105], by (Fun) 124] half(X) >= half(X) because half in Mul and [103], by (Fun) 125] half(X) >= half(X) because half in Mul and [105], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_24, R_2, minimal, formative) by (P_25, R_2, minimal, formative), where P_25 consists of: active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> active#(terms(mark(X))) mark#(terms(X)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) Thus, the original system is terminating if (P_25, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_25, R_2, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 6 * 1 : 3, 4, 5, 6, 7, 8, 9, 10 * 2 : 6 * 3 : * 4 : 3, 4, 5, 6, 7, 8, 9, 10 * 5 : 3, 4, 5, 6, 7, 8, 9, 10 * 6 : 3, 4, 5, 6, 7, 8, 9, 10 * 7 : 1 * 8 : 0 * 9 : 3, 4, 5, 6, 7, 8, 9, 10 * 10 : 2 This graph has the following strongly connected components: P_26: active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(add(0, X)) =#> mark#(X) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_25, R_2, m, f) by (P_26, R_2, m, f). Thus, the original system is terminating if (P_26, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_26, R_2, minimal, formative). The formative rules of (P_26, R_2) are R_3 ::= active(terms(X)) => mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) => mark(0) active(sqr(s(X))) => mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) => mark(0) active(dbl(s(X))) => mark(s(s(dbl(X)))) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(half(0)) => mark(0) active(half(s(0))) => mark(0) active(half(s(s(X)))) => mark(s(half(X))) active(half(dbl(X))) => mark(X) mark(terms(X)) => active(terms(mark(X))) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(recip(X)) => active(recip(mark(X))) mark(sqr(X)) => active(sqr(mark(X))) mark(s(X)) => active(s(mark(X))) mark(0) => active(0) mark(add(X, Y)) => active(add(mark(X), mark(Y))) mark(dbl(X)) => active(dbl(mark(X))) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(half(X)) => active(half(mark(X))) terms(mark(X)) => terms(X) terms(active(X)) => terms(X) recip(mark(X)) => recip(X) recip(active(X)) => recip(X) s(mark(X)) => s(X) s(active(X)) => s(X) add(mark(X), Y) => add(X, Y) add(X, mark(Y)) => add(X, Y) add(active(X), Y) => add(X, Y) add(X, active(Y)) => add(X, Y) dbl(mark(X)) => dbl(X) dbl(active(X)) => dbl(X) half(mark(X)) => half(X) half(active(X)) => half(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_26, R_2, minimal, formative) by (P_26, R_3, minimal, formative). Thus, the original system is terminating if (P_26, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_26, R_3, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(add(0, X)) >? mark#(X) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(terms(X)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), mark(Y))) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(half(X)) >? active#(half(mark(X))) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) add(mark(X), Y) >= add(X, Y) add(X, mark(Y)) >= add(X, Y) add(active(X), Y) >= add(X, Y) add(X, active(Y)) >= add(X, Y) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) half(mark(X)) >= half(X) half(active(X)) >= half(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 active# = \y0.y0 add = \y0y1.2 + y1 cons = \y0y1.0 dbl = \y0.y0 first = \y0y1.0 half = \y0.y0 mark = \y0.y0 mark# = \y0.y0 nil = 0 recip = \y0.y0 s = \y0.y0 sqr = \y0.2 + y0 terms = \y0.y0 Using this interpretation, the requirements translate to: [[active#(dbl(s(_x0)))]] = x0 >= x0 = [[mark#(s(s(dbl(_x0))))]] [[active#(add(0, _x0))]] = 2 + x0 > x0 = [[mark#(_x0)]] [[active#(half(s(s(_x0))))]] = x0 >= x0 = [[mark#(s(half(_x0)))]] [[mark#(terms(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(recip(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(s(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(add(_x0, _x1))]] = 2 + x1 >= 2 + x1 = [[active#(add(mark(_x0), mark(_x1)))]] [[mark#(dbl(_x0))]] = x0 >= x0 = [[active#(dbl(mark(_x0)))]] [[mark#(dbl(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(half(_x0))]] = x0 >= x0 = [[active#(half(mark(_x0)))]] [[active(terms(_x0))]] = x0 >= 0 = [[mark(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active(sqr(0))]] = 2 >= 0 = [[mark(0)]] [[active(sqr(s(_x0)))]] = 2 + x0 >= 2 + x0 = [[mark(s(add(sqr(_x0), dbl(_x0))))]] [[active(dbl(0))]] = 0 >= 0 = [[mark(0)]] [[active(dbl(s(_x0)))]] = x0 >= x0 = [[mark(s(s(dbl(_x0))))]] [[active(add(0, _x0))]] = 2 + x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = 2 + x1 >= 2 + x1 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = 0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = 0 >= 0 = [[mark(cons(_x1, first(_x0, _x2)))]] [[active(half(0))]] = 0 >= 0 = [[mark(0)]] [[active(half(s(0)))]] = 0 >= 0 = [[mark(0)]] [[active(half(s(s(_x0))))]] = x0 >= x0 = [[mark(s(half(_x0)))]] [[active(half(dbl(_x0)))]] = x0 >= x0 = [[mark(_x0)]] [[mark(terms(_x0))]] = x0 >= x0 = [[active(terms(mark(_x0)))]] [[mark(cons(_x0, _x1))]] = 0 >= 0 = [[active(cons(mark(_x0), _x1))]] [[mark(recip(_x0))]] = x0 >= x0 = [[active(recip(mark(_x0)))]] [[mark(sqr(_x0))]] = 2 + x0 >= 2 + x0 = [[active(sqr(mark(_x0)))]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(add(_x0, _x1))]] = 2 + x1 >= 2 + x1 = [[active(add(mark(_x0), mark(_x1)))]] [[mark(dbl(_x0))]] = x0 >= x0 = [[active(dbl(mark(_x0)))]] [[mark(first(_x0, _x1))]] = 0 >= 0 = [[active(first(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(half(_x0))]] = x0 >= x0 = [[active(half(mark(_x0)))]] [[terms(mark(_x0))]] = x0 >= x0 = [[terms(_x0)]] [[terms(active(_x0))]] = x0 >= x0 = [[terms(_x0)]] [[recip(mark(_x0))]] = x0 >= x0 = [[recip(_x0)]] [[recip(active(_x0))]] = x0 >= x0 = [[recip(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[add(mark(_x0), _x1)]] = 2 + x1 >= 2 + x1 = [[add(_x0, _x1)]] [[add(_x0, mark(_x1))]] = 2 + x1 >= 2 + x1 = [[add(_x0, _x1)]] [[add(active(_x0), _x1)]] = 2 + x1 >= 2 + x1 = [[add(_x0, _x1)]] [[add(_x0, active(_x1))]] = 2 + x1 >= 2 + x1 = [[add(_x0, _x1)]] [[dbl(mark(_x0))]] = x0 >= x0 = [[dbl(_x0)]] [[dbl(active(_x0))]] = x0 >= x0 = [[dbl(_x0)]] [[half(mark(_x0))]] = x0 >= x0 = [[half(_x0)]] [[half(active(_x0))]] = x0 >= x0 = [[half(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_26, R_3, minimal, formative) by (P_27, R_3, minimal, formative), where P_27 consists of: active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) Thus, the original system is terminating if (P_27, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_27, R_3, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 4 * 1 : 4 * 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 : * 6 : 0 * 7 : 2, 3, 4, 5, 6, 7, 8 * 8 : 1 This graph has the following strongly connected components: P_28: active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(terms(X)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_27, R_3, m, f) by (P_28, R_3, m, f). Thus, the original system is terminating if (P_28, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_28, R_3, minimal, formative). The formative rules of (P_28, R_3) are R_4 ::= active(terms(X)) => mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) => mark(0) active(sqr(s(X))) => mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) => mark(0) active(dbl(s(X))) => mark(s(s(dbl(X)))) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(half(0)) => mark(0) active(half(s(0))) => mark(0) active(half(s(s(X)))) => mark(s(half(X))) active(half(dbl(X))) => mark(X) mark(terms(X)) => active(terms(mark(X))) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(recip(X)) => active(recip(mark(X))) mark(sqr(X)) => active(sqr(mark(X))) mark(s(X)) => active(s(mark(X))) mark(0) => active(0) mark(add(X, Y)) => active(add(mark(X), mark(Y))) mark(dbl(X)) => active(dbl(mark(X))) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(half(X)) => active(half(mark(X))) terms(mark(X)) => terms(X) terms(active(X)) => terms(X) recip(mark(X)) => recip(X) recip(active(X)) => recip(X) s(mark(X)) => s(X) s(active(X)) => s(X) dbl(mark(X)) => dbl(X) dbl(active(X)) => dbl(X) half(mark(X)) => half(X) half(active(X)) => half(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_28, R_3, minimal, formative) by (P_28, R_4, minimal, formative). Thus, the original system is terminating if (P_28, R_4, minimal, formative) is finite. We consider the dependency pair problem (P_28, R_4, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(terms(X)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(half(X)) >? active#(half(mark(X))) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) terms(mark(X)) >= terms(X) terms(active(X)) >= terms(X) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) half(mark(X)) >= half(X) half(active(X)) >= half(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 active# = \y0.y0 add = \y0y1.y1 cons = \y0y1.0 dbl = \y0.2y0 first = \y0y1.0 half = \y0.2y0 mark = \y0.y0 mark# = \y0.y0 nil = 0 recip = \y0.2y0 s = \y0.y0 sqr = \y0.2y0 terms = \y0.1 + 2y0 Using this interpretation, the requirements translate to: [[active#(dbl(s(_x0)))]] = 2x0 >= 2x0 = [[mark#(s(s(dbl(_x0))))]] [[active#(half(s(s(_x0))))]] = 2x0 >= 2x0 = [[mark#(s(half(_x0)))]] [[mark#(terms(_x0))]] = 1 + 2x0 > x0 = [[mark#(_x0)]] [[mark#(recip(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] [[mark#(s(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(dbl(_x0))]] = 2x0 >= 2x0 = [[active#(dbl(mark(_x0)))]] [[mark#(dbl(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] [[mark#(half(_x0))]] = 2x0 >= 2x0 = [[active#(half(mark(_x0)))]] [[active(terms(_x0))]] = 1 + 2x0 >= 0 = [[mark(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active(sqr(0))]] = 0 >= 0 = [[mark(0)]] [[active(sqr(s(_x0)))]] = 2x0 >= 2x0 = [[mark(s(add(sqr(_x0), dbl(_x0))))]] [[active(dbl(0))]] = 0 >= 0 = [[mark(0)]] [[active(dbl(s(_x0)))]] = 2x0 >= 2x0 = [[mark(s(s(dbl(_x0))))]] [[active(add(0, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = x1 >= x1 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = 0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = 0 >= 0 = [[mark(cons(_x1, first(_x0, _x2)))]] [[active(half(0))]] = 0 >= 0 = [[mark(0)]] [[active(half(s(0)))]] = 0 >= 0 = [[mark(0)]] [[active(half(s(s(_x0))))]] = 2x0 >= 2x0 = [[mark(s(half(_x0)))]] [[active(half(dbl(_x0)))]] = 4x0 >= x0 = [[mark(_x0)]] [[mark(terms(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[active(terms(mark(_x0)))]] [[mark(cons(_x0, _x1))]] = 0 >= 0 = [[active(cons(mark(_x0), _x1))]] [[mark(recip(_x0))]] = 2x0 >= 2x0 = [[active(recip(mark(_x0)))]] [[mark(sqr(_x0))]] = 2x0 >= 2x0 = [[active(sqr(mark(_x0)))]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(add(_x0, _x1))]] = x1 >= x1 = [[active(add(mark(_x0), mark(_x1)))]] [[mark(dbl(_x0))]] = 2x0 >= 2x0 = [[active(dbl(mark(_x0)))]] [[mark(first(_x0, _x1))]] = 0 >= 0 = [[active(first(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(half(_x0))]] = 2x0 >= 2x0 = [[active(half(mark(_x0)))]] [[terms(mark(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[terms(_x0)]] [[terms(active(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[terms(_x0)]] [[recip(mark(_x0))]] = 2x0 >= 2x0 = [[recip(_x0)]] [[recip(active(_x0))]] = 2x0 >= 2x0 = [[recip(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[dbl(mark(_x0))]] = 2x0 >= 2x0 = [[dbl(_x0)]] [[dbl(active(_x0))]] = 2x0 >= 2x0 = [[dbl(_x0)]] [[half(mark(_x0))]] = 2x0 >= 2x0 = [[half(_x0)]] [[half(active(_x0))]] = 2x0 >= 2x0 = [[half(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_28, R_4, minimal, formative) by (P_29, R_4, minimal, formative), where P_29 consists of: active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(recip(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) Thus, the original system is terminating if (P_29, R_4, minimal, formative) is finite. We consider the dependency pair problem (P_29, R_4, minimal, formative). The formative rules of (P_29, R_4) are R_5 ::= active(terms(X)) => mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) => mark(0) active(sqr(s(X))) => mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) => mark(0) active(dbl(s(X))) => mark(s(s(dbl(X)))) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(half(0)) => mark(0) active(half(s(0))) => mark(0) active(half(s(s(X)))) => mark(s(half(X))) active(half(dbl(X))) => mark(X) mark(terms(X)) => active(terms(mark(X))) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(recip(X)) => active(recip(mark(X))) mark(sqr(X)) => active(sqr(mark(X))) mark(s(X)) => active(s(mark(X))) mark(0) => active(0) mark(add(X, Y)) => active(add(mark(X), mark(Y))) mark(dbl(X)) => active(dbl(mark(X))) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(half(X)) => active(half(mark(X))) recip(mark(X)) => recip(X) recip(active(X)) => recip(X) s(mark(X)) => s(X) s(active(X)) => s(X) dbl(mark(X)) => dbl(X) dbl(active(X)) => dbl(X) half(mark(X)) => half(X) half(active(X)) => half(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_29, R_4, minimal, formative) by (P_29, R_5, minimal, formative). Thus, the original system is terminating if (P_29, R_5, minimal, formative) is finite. We consider the dependency pair problem (P_29, R_5, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(recip(X)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(half(X)) >? active#(half(mark(X))) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) recip(mark(X)) >= recip(X) recip(active(X)) >= recip(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) half(mark(X)) >= half(X) half(active(X)) >= half(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 active# = \y0.1 + 2y0 add = \y0y1.y1 cons = \y0y1.0 dbl = \y0.y0 first = \y0y1.0 half = \y0.2y0 mark = \y0.y0 mark# = \y0.1 + 2y0 nil = 0 recip = \y0.1 + y0 s = \y0.y0 sqr = \y0.y0 terms = \y0.0 Using this interpretation, the requirements translate to: [[active#(dbl(s(_x0)))]] = 1 + 2x0 >= 1 + 2x0 = [[mark#(s(s(dbl(_x0))))]] [[active#(half(s(s(_x0))))]] = 1 + 4x0 >= 1 + 4x0 = [[mark#(s(half(_x0)))]] [[mark#(recip(_x0))]] = 3 + 2x0 > 1 + 2x0 = [[mark#(_x0)]] [[mark#(s(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[mark#(_x0)]] [[mark#(dbl(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[active#(dbl(mark(_x0)))]] [[mark#(dbl(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[mark#(_x0)]] [[mark#(half(_x0))]] = 1 + 4x0 >= 1 + 4x0 = [[active#(half(mark(_x0)))]] [[active(terms(_x0))]] = 0 >= 0 = [[mark(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active(sqr(0))]] = 0 >= 0 = [[mark(0)]] [[active(sqr(s(_x0)))]] = x0 >= x0 = [[mark(s(add(sqr(_x0), dbl(_x0))))]] [[active(dbl(0))]] = 0 >= 0 = [[mark(0)]] [[active(dbl(s(_x0)))]] = x0 >= x0 = [[mark(s(s(dbl(_x0))))]] [[active(add(0, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = x1 >= x1 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = 0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = 0 >= 0 = [[mark(cons(_x1, first(_x0, _x2)))]] [[active(half(0))]] = 0 >= 0 = [[mark(0)]] [[active(half(s(0)))]] = 0 >= 0 = [[mark(0)]] [[active(half(s(s(_x0))))]] = 2x0 >= 2x0 = [[mark(s(half(_x0)))]] [[active(half(dbl(_x0)))]] = 2x0 >= x0 = [[mark(_x0)]] [[mark(terms(_x0))]] = 0 >= 0 = [[active(terms(mark(_x0)))]] [[mark(cons(_x0, _x1))]] = 0 >= 0 = [[active(cons(mark(_x0), _x1))]] [[mark(recip(_x0))]] = 1 + x0 >= 1 + x0 = [[active(recip(mark(_x0)))]] [[mark(sqr(_x0))]] = x0 >= x0 = [[active(sqr(mark(_x0)))]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(add(_x0, _x1))]] = x1 >= x1 = [[active(add(mark(_x0), mark(_x1)))]] [[mark(dbl(_x0))]] = x0 >= x0 = [[active(dbl(mark(_x0)))]] [[mark(first(_x0, _x1))]] = 0 >= 0 = [[active(first(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(half(_x0))]] = 2x0 >= 2x0 = [[active(half(mark(_x0)))]] [[recip(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[recip(_x0)]] [[recip(active(_x0))]] = 1 + x0 >= 1 + x0 = [[recip(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[dbl(mark(_x0))]] = x0 >= x0 = [[dbl(_x0)]] [[dbl(active(_x0))]] = x0 >= x0 = [[dbl(_x0)]] [[half(mark(_x0))]] = 2x0 >= 2x0 = [[half(_x0)]] [[half(active(_x0))]] = 2x0 >= 2x0 = [[half(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_29, R_5, minimal, formative) by (P_30, R_5, minimal, formative), where P_30 consists of: active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(s(X)) =#> mark#(X) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(dbl(X)) =#> mark#(X) mark#(half(X)) =#> active#(half(mark(X))) Thus, the original system is terminating if (P_30, R_5, minimal, formative) is finite. We consider the dependency pair problem (P_30, R_5, minimal, formative). The formative rules of (P_30, R_5) are R_6 ::= active(terms(X)) => mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) => mark(0) active(sqr(s(X))) => mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) => mark(0) active(dbl(s(X))) => mark(s(s(dbl(X)))) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(half(0)) => mark(0) active(half(s(0))) => mark(0) active(half(s(s(X)))) => mark(s(half(X))) active(half(dbl(X))) => mark(X) mark(terms(X)) => active(terms(mark(X))) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(recip(X)) => active(recip(mark(X))) mark(sqr(X)) => active(sqr(mark(X))) mark(s(X)) => active(s(mark(X))) mark(0) => active(0) mark(add(X, Y)) => active(add(mark(X), mark(Y))) mark(dbl(X)) => active(dbl(mark(X))) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(half(X)) => active(half(mark(X))) s(mark(X)) => s(X) s(active(X)) => s(X) dbl(mark(X)) => dbl(X) dbl(active(X)) => dbl(X) half(mark(X)) => half(X) half(active(X)) => half(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_30, R_5, minimal, formative) by (P_30, R_6, minimal, formative). Thus, the original system is terminating if (P_30, R_6, minimal, formative) is finite. We consider the dependency pair problem (P_30, R_6, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(s(X)) >? mark#(X) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(dbl(X)) >? mark#(X) mark#(half(X)) >? active#(half(mark(X))) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) s(mark(X)) >= s(X) s(active(X)) >= s(X) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) half(mark(X)) >= half(X) half(active(X)) >= half(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 1 active = \y0.y0 active# = \y0.2y0 add = \y0y1.y1 cons = \y0y1.0 dbl = \y0.1 + y0 first = \y0y1.0 half = \y0.2y0 mark = \y0.y0 mark# = \y0.2y0 nil = 0 recip = \y0.0 s = \y0.y0 sqr = \y0.1 + y0 terms = \y0.2 Using this interpretation, the requirements translate to: [[active#(dbl(s(_x0)))]] = 2 + 2x0 >= 2 + 2x0 = [[mark#(s(s(dbl(_x0))))]] [[active#(half(s(s(_x0))))]] = 4x0 >= 4x0 = [[mark#(s(half(_x0)))]] [[mark#(s(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(dbl(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[active#(dbl(mark(_x0)))]] [[mark#(dbl(_x0))]] = 2 + 2x0 > 2x0 = [[mark#(_x0)]] [[mark#(half(_x0))]] = 4x0 >= 4x0 = [[active#(half(mark(_x0)))]] [[active(terms(_x0))]] = 2 >= 0 = [[mark(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active(sqr(0))]] = 2 >= 1 = [[mark(0)]] [[active(sqr(s(_x0)))]] = 1 + x0 >= 1 + x0 = [[mark(s(add(sqr(_x0), dbl(_x0))))]] [[active(dbl(0))]] = 2 >= 1 = [[mark(0)]] [[active(dbl(s(_x0)))]] = 1 + x0 >= 1 + x0 = [[mark(s(s(dbl(_x0))))]] [[active(add(0, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = x1 >= x1 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = 0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = 0 >= 0 = [[mark(cons(_x1, first(_x0, _x2)))]] [[active(half(0))]] = 2 >= 1 = [[mark(0)]] [[active(half(s(0)))]] = 2 >= 1 = [[mark(0)]] [[active(half(s(s(_x0))))]] = 2x0 >= 2x0 = [[mark(s(half(_x0)))]] [[active(half(dbl(_x0)))]] = 2 + 2x0 >= x0 = [[mark(_x0)]] [[mark(terms(_x0))]] = 2 >= 2 = [[active(terms(mark(_x0)))]] [[mark(cons(_x0, _x1))]] = 0 >= 0 = [[active(cons(mark(_x0), _x1))]] [[mark(recip(_x0))]] = 0 >= 0 = [[active(recip(mark(_x0)))]] [[mark(sqr(_x0))]] = 1 + x0 >= 1 + x0 = [[active(sqr(mark(_x0)))]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(0)]] = 1 >= 1 = [[active(0)]] [[mark(add(_x0, _x1))]] = x1 >= x1 = [[active(add(mark(_x0), mark(_x1)))]] [[mark(dbl(_x0))]] = 1 + x0 >= 1 + x0 = [[active(dbl(mark(_x0)))]] [[mark(first(_x0, _x1))]] = 0 >= 0 = [[active(first(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(half(_x0))]] = 2x0 >= 2x0 = [[active(half(mark(_x0)))]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[dbl(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[dbl(_x0)]] [[dbl(active(_x0))]] = 1 + x0 >= 1 + x0 = [[dbl(_x0)]] [[half(mark(_x0))]] = 2x0 >= 2x0 = [[half(_x0)]] [[half(active(_x0))]] = 2x0 >= 2x0 = [[half(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_30, R_6, minimal, formative) by (P_31, R_6, minimal, formative), where P_31 consists of: active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(s(X)) =#> mark#(X) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(half(X)) =#> active#(half(mark(X))) Thus, the original system is terminating if (P_31, R_6, minimal, formative) is finite. We consider the dependency pair problem (P_31, R_6, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(dbl(s(X))) >? mark#(s(s(dbl(X)))) active#(half(s(s(X)))) >? mark#(s(half(X))) mark#(s(X)) >? mark#(X) mark#(dbl(X)) >? active#(dbl(mark(X))) mark#(half(X)) >? active#(half(mark(X))) active(terms(X)) >= mark(cons(recip(sqr(X)), terms(s(X)))) active(sqr(0)) >= mark(0) active(sqr(s(X))) >= mark(s(add(sqr(X), dbl(X)))) active(dbl(0)) >= mark(0) active(dbl(s(X))) >= mark(s(s(dbl(X)))) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(half(0)) >= mark(0) active(half(s(0))) >= mark(0) active(half(s(s(X)))) >= mark(s(half(X))) active(half(dbl(X))) >= mark(X) mark(terms(X)) >= active(terms(mark(X))) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(recip(X)) >= active(recip(mark(X))) mark(sqr(X)) >= active(sqr(mark(X))) mark(s(X)) >= active(s(mark(X))) mark(0) >= active(0) mark(add(X, Y)) >= active(add(mark(X), mark(Y))) mark(dbl(X)) >= active(dbl(mark(X))) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(half(X)) >= active(half(mark(X))) s(mark(X)) >= s(X) s(active(X)) >= s(X) dbl(mark(X)) >= dbl(X) dbl(active(X)) >= dbl(X) half(mark(X)) >= half(X) half(active(X)) >= half(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]] = _|_ [[active(x_1)]] = x_1 [[cons(x_1, x_2)]] = x_2 [[first(x_1, x_2)]] = _|_ [[mark(x_1)]] = x_1 [[nil]] = _|_ [[terms(x_1)]] = terms We choose Lex = {recip} and Mul = {active#, add, dbl, half, mark#, s, sqr, terms}, and the following precedence: recip > sqr > add > dbl > active# = mark# > half = s > terms Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) active#(half(s(s(X)))) >= mark#(s(half(X))) mark#(s(X)) > mark#(X) mark#(dbl(X)) >= active#(dbl(X)) mark#(half(X)) >= active#(half(X)) terms >= terms sqr(_|_) >= _|_ sqr(s(X)) >= s(add(sqr(X), dbl(X))) dbl(_|_) >= _|_ dbl(s(X)) >= s(s(dbl(X))) add(_|_, X) >= X add(s(X), Y) >= s(add(X, Y)) _|_ >= _|_ _|_ >= _|_ half(_|_) >= _|_ half(s(_|_)) >= _|_ half(s(s(X))) >= s(half(X)) half(dbl(X)) >= X terms >= terms X >= X recip(X) >= recip(X) sqr(X) >= sqr(X) s(X) >= s(X) _|_ >= _|_ add(X, Y) >= add(X, Y) dbl(X) >= dbl(X) _|_ >= _|_ _|_ >= _|_ half(X) >= half(X) s(X) >= s(X) s(X) >= s(X) dbl(X) >= dbl(X) dbl(X) >= dbl(X) half(X) >= half(X) half(X) >= half(X) With these choices, we have: 1] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because active# = mark#, active# in Mul and [2], by (Fun) 2] dbl(s(X)) >= s(s(dbl(X))) because [3], by (Star) 3] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [4], by (Copy) 4] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [5], by (Copy) 5] dbl*(s(X)) >= dbl(X) because dbl 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] active#(half(s(s(X)))) >= mark#(s(half(X))) because active# = mark#, active# in Mul and [10], by (Fun) 10] half(s(s(X))) >= s(half(X)) because half = s, half in Mul and [11], by (Fun) 11] s(s(X)) >= half(X) because s = half, s in Mul and [12], by (Fun) 12] s(X) >= X because [7], by (Star) 13] mark#(s(X)) > mark#(X) because [14], by definition 14] mark#*(s(X)) >= mark#(X) because mark# in Mul and [6], by (Stat) 15] mark#(dbl(X)) >= active#(dbl(X)) because mark# = active#, mark# in Mul and [16], by (Fun) 16] dbl(X) >= dbl(X) because dbl in Mul and [17], by (Fun) 17] X >= X by (Meta) 18] mark#(half(X)) >= active#(half(X)) because mark# = active#, mark# in Mul and [19], by (Fun) 19] half(X) >= half(X) because half in Mul and [17], by (Fun) 20] terms >= terms because terms in Mul, by (Fun) 21] sqr(_|_) >= _|_ by (Bot) 22] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [23], by (Star) 23] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [24], by (Copy) 24] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [25] and [26], by (Copy) 25] sqr*(s(X)) >= sqr(X) because sqr in Mul and [6], by (Stat) 26] sqr*(s(X)) >= dbl(X) because sqr > dbl and [27], by (Copy) 27] sqr*(s(X)) >= X because [12], by (Select) 28] dbl(_|_) >= _|_ by (Bot) 29] dbl(s(X)) >= s(s(dbl(X))) because [3], by (Star) 30] add(_|_, X) >= X because [31], by (Star) 31] add*(_|_, X) >= X because [17], by (Select) 32] add(s(X), Y) >= s(add(X, Y)) because [33], by (Star) 33] add*(s(X), Y) >= s(add(X, Y)) because add > s and [34], by (Copy) 34] add*(s(X), Y) >= add(X, Y) because add in Mul, [6] and [35], by (Stat) 35] Y >= Y by (Meta) 36] _|_ >= _|_ by (Bot) 37] _|_ >= _|_ by (Bot) 38] half(_|_) >= _|_ by (Bot) 39] half(s(_|_)) >= _|_ by (Bot) 40] half(s(s(X))) >= s(half(X)) because half = s, half in Mul and [11], by (Fun) 41] half(dbl(X)) >= X because [42], by (Star) 42] half*(dbl(X)) >= X because [43], by (Select) 43] dbl(X) >= X because [44], by (Star) 44] dbl*(X) >= X because [17], by (Select) 45] terms >= terms because terms in Mul, by (Fun) 46] X >= X by (Meta) 47] recip(X) >= recip(X) because [17], by (Fun) 48] sqr(X) >= sqr(X) because sqr in Mul and [17], by (Fun) 49] s(X) >= s(X) because s in Mul and [17], by (Fun) 50] _|_ >= _|_ by (Bot) 51] add(X, Y) >= add(X, Y) because add in Mul, [52] and [53], by (Fun) 52] X >= X by (Meta) 53] Y >= Y by (Meta) 54] dbl(X) >= dbl(X) because dbl in Mul and [17], by (Fun) 55] _|_ >= _|_ by (Bot) 56] _|_ >= _|_ by (Bot) 57] half(X) >= half(X) because half in Mul and [17], by (Fun) 58] s(X) >= s(X) because s in Mul and [59], by (Fun) 59] X >= X by (Meta) 60] s(X) >= s(X) because s in Mul and [61], by (Fun) 61] X >= X by (Meta) 62] dbl(X) >= dbl(X) because dbl in Mul and [59], by (Fun) 63] dbl(X) >= dbl(X) because dbl in Mul and [61], by (Fun) 64] half(X) >= half(X) because half in Mul and [59], by (Fun) 65] half(X) >= half(X) because half in Mul and [61], by (Fun) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_31, R_6, minimal, formative) by (P_32, R_6, minimal, formative), where P_32 consists of: active#(dbl(s(X))) =#> mark#(s(s(dbl(X)))) active#(half(s(s(X)))) =#> mark#(s(half(X))) mark#(dbl(X)) =#> active#(dbl(mark(X))) mark#(half(X)) =#> active#(half(mark(X))) Thus, the original system is terminating if (P_32, R_6, minimal, formative) is finite. We consider the dependency pair problem (P_32, R_6, 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 : * 2 : 0 * 3 : 1 This graph has no strongly connected components. By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem. 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.