/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 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))) 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) 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) 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] mark#(terms(X)) =#> active#(terms(mark(X))) 26] mark#(terms(X)) =#> terms#(mark(X)) 27] mark#(terms(X)) =#> mark#(X) 28] mark#(cons(X, Y)) =#> active#(cons(mark(X), Y)) 29] mark#(cons(X, Y)) =#> cons#(mark(X), Y) 30] mark#(cons(X, Y)) =#> mark#(X) 31] mark#(recip(X)) =#> active#(recip(mark(X))) 32] mark#(recip(X)) =#> recip#(mark(X)) 33] mark#(recip(X)) =#> mark#(X) 34] mark#(sqr(X)) =#> active#(sqr(mark(X))) 35] mark#(sqr(X)) =#> sqr#(mark(X)) 36] mark#(sqr(X)) =#> mark#(X) 37] mark#(s(X)) =#> active#(s(mark(X))) 38] mark#(s(X)) =#> s#(mark(X)) 39] mark#(s(X)) =#> mark#(X) 40] mark#(0) =#> active#(0) 41] mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) 42] mark#(add(X, Y)) =#> add#(mark(X), mark(Y)) 43] mark#(add(X, Y)) =#> mark#(X) 44] mark#(add(X, Y)) =#> mark#(Y) 45] mark#(dbl(X)) =#> active#(dbl(mark(X))) 46] mark#(dbl(X)) =#> dbl#(mark(X)) 47] mark#(dbl(X)) =#> mark#(X) 48] mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) 49] mark#(first(X, Y)) =#> first#(mark(X), mark(Y)) 50] mark#(first(X, Y)) =#> mark#(X) 51] mark#(first(X, Y)) =#> mark#(Y) 52] mark#(nil) =#> active#(nil) 53] terms#(mark(X)) =#> terms#(X) 54] terms#(active(X)) =#> terms#(X) 55] cons#(mark(X), Y) =#> cons#(X, Y) 56] cons#(X, mark(Y)) =#> cons#(X, Y) 57] cons#(active(X), Y) =#> cons#(X, Y) 58] cons#(X, active(Y)) =#> cons#(X, Y) 59] recip#(mark(X)) =#> recip#(X) 60] recip#(active(X)) =#> recip#(X) 61] sqr#(mark(X)) =#> sqr#(X) 62] sqr#(active(X)) =#> sqr#(X) 63] s#(mark(X)) =#> s#(X) 64] s#(active(X)) =#> s#(X) 65] add#(mark(X), Y) =#> add#(X, Y) 66] add#(X, mark(Y)) =#> add#(X, Y) 67] add#(active(X), Y) =#> add#(X, Y) 68] add#(X, active(Y)) =#> add#(X, Y) 69] dbl#(mark(X)) =#> dbl#(X) 70] dbl#(active(X)) =#> dbl#(X) 71] first#(mark(X), Y) =#> first#(X, Y) 72] first#(X, mark(Y)) =#> first#(X, Y) 73] first#(active(X), Y) =#> first#(X, Y) 74] first#(X, active(Y)) =#> first#(X, Y) 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))) 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) 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) 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 : 28, 29, 30 * 1 : * 2 : * 3 : 61, 62 * 4 : * 5 : 63, 64 * 6 : 40 * 7 : 37, 38, 39 * 8 : * 9 : * 10 : 61, 62 * 11 : 69, 70 * 12 : 40 * 13 : 37, 38, 39 * 14 : * 15 : * 16 : 69, 70 * 17 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 18 : 37, 38, 39 * 19 : * 20 : 65, 66, 67, 68 * 21 : 52 * 22 : 28, 29, 30 * 23 : 55, 57 * 24 : 71, 72, 73, 74 * 25 : 0, 1, 2, 3, 4, 5 * 26 : 53, 54 * 27 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 28 : * 29 : 55, 56, 57, 58 * 30 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 31 : * 32 : 59, 60 * 33 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 34 : 6, 7, 8, 9, 10, 11 * 35 : 61, 62 * 36 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 37 : * 38 : 63, 64 * 39 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 40 : * 41 : 17, 18, 19, 20 * 42 : 65, 66, 67, 68 * 43 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 44 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 45 : 12, 13, 14, 15, 16 * 46 : 69, 70 * 47 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 48 : 21, 22, 23, 24 * 49 : 71, 72, 73, 74 * 50 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 51 : 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 * 52 : * 53 : 53, 54 * 54 : 53, 54 * 55 : 55, 56, 57, 58 * 56 : 55, 56, 57, 58 * 57 : 55, 56, 57, 58 * 58 : 55, 56, 57, 58 * 59 : 59, 60 * 60 : 59, 60 * 61 : 61, 62 * 62 : 61, 62 * 63 : 63, 64 * 64 : 63, 64 * 65 : 65, 66, 67, 68 * 66 : 65, 66, 67, 68 * 67 : 65, 66, 67, 68 * 68 : 65, 66, 67, 68 * 69 : 69, 70 * 70 : 69, 70 * 71 : 71, 72, 73, 74 * 72 : 71, 72, 73, 74 * 73 : 71, 72, 73, 74 * 74 : 71, 72, 73, 74 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))) 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) 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) 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) and (P_9, 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) 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_10, R_0, minimal, f), where P_10 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_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(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_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) 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_11, R_0, minimal, f), where P_11 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_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(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_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) 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_12, R_0, minimal, f), where P_12 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_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(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_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) 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))) 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) 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))) 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) 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) 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, mark#, recip, s, sqr, terms}, and the following precedence: first > terms > recip > dbl = sqr > 0 > add > s > cons = mark# > active# 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#(add(s(X), Y)) >= mark#(s(add(X, Y))) active#(first(s(X), cons(Y))) >= mark#(cons(Y)) 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) 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) 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) _|_ >= _|_ 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) 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 [3], by (Select) 3] terms(X) >= mark#(cons(recip(sqr(X)))) because [4], by (Star) 4] terms*(X) >= mark#(cons(recip(sqr(X)))) because terms > mark# and [5], by (Copy) 5] terms*(X) >= cons(recip(sqr(X))) because terms > cons and [6], by (Copy) 6] terms*(X) >= recip(sqr(X)) because terms > recip and [7], by (Copy) 7] terms*(X) >= sqr(X) because terms > sqr and [8], by (Copy) 8] terms*(X) >= X because [9], by (Select) 9] X >= X by (Meta) 10] active#(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because [11], by (Star) 11] active#*(sqr(s(X))) >= mark#(s(add(sqr(X), dbl(X)))) because [12], by (Select) 12] sqr(s(X)) >= mark#(s(add(sqr(X), dbl(X)))) because [13], by (Star) 13] sqr*(s(X)) >= mark#(s(add(sqr(X), dbl(X)))) because sqr > mark# and [14], by (Copy) 14] sqr*(s(X)) >= s(add(sqr(X), dbl(X))) because sqr > s and [15], by (Copy) 15] sqr*(s(X)) >= add(sqr(X), dbl(X)) because sqr > add, [16] and [20], by (Copy) 16] sqr*(s(X)) >= sqr(X) because sqr in Mul and [17], by (Stat) 17] s(X) > X because [18], by definition 18] s*(X) >= X because [19], by (Select) 19] X >= X by (Meta) 20] sqr*(s(X)) >= dbl(X) because sqr = dbl, sqr in Mul and [17], by (Stat) 21] active#(dbl(s(X))) >= mark#(s(s(dbl(X)))) because [22], by (Star) 22] active#*(dbl(s(X))) >= mark#(s(s(dbl(X)))) because [23], by (Select) 23] dbl(s(X)) >= mark#(s(s(dbl(X)))) because [24], by (Star) 24] dbl*(s(X)) >= mark#(s(s(dbl(X)))) because dbl > mark# and [25], by (Copy) 25] dbl*(s(X)) >= s(s(dbl(X))) because dbl > s and [26], by (Copy) 26] dbl*(s(X)) >= s(dbl(X)) because dbl > s and [27], by (Copy) 27] dbl*(s(X)) >= dbl(X) because dbl in Mul and [17], by (Stat) 28] active#(add(0, X)) >= mark#(X) because [29], by (Star) 29] active#*(add(0, X)) >= mark#(X) because [30], by (Select) 30] add(0, X) >= mark#(X) because [31], by (Star) 31] add*(0, X) >= mark#(X) because add > mark# and [32], by (Copy) 32] add*(0, X) >= X because [19], by (Select) 33] active#(add(s(X), Y)) >= mark#(s(add(X, Y))) because [34], by (Star) 34] active#*(add(s(X), Y)) >= mark#(s(add(X, Y))) because [35], by (Select) 35] add(s(X), Y) >= mark#(s(add(X, Y))) because [36], by (Star) 36] add*(s(X), Y) >= mark#(s(add(X, Y))) because add > mark# and [37], by (Copy) 37] add*(s(X), Y) >= s(add(X, Y)) because add > s and [38], by (Copy) 38] add*(s(X), Y) >= add(X, Y) because add in Mul, [17] and [39], by (Stat) 39] Y >= Y by (Meta) 40] active#(first(s(X), cons(Y))) >= mark#(cons(Y)) because [41], by (Star) 41] active#*(first(s(X), cons(Y))) >= mark#(cons(Y)) because [42], by (Select) 42] first(s(X), cons(Y)) >= mark#(cons(Y)) because [43], by (Star) 43] first*(s(X), cons(Y)) >= mark#(cons(Y)) because first > mark# and [44], by (Copy) 44] first*(s(X), cons(Y)) >= cons(Y) because [45], by (Select) 45] cons(Y) >= cons(Y) because cons in Mul and [39], by (Fun) 46] mark#(terms(X)) >= active#(terms(X)) because [47], by (Star) 47] mark#*(terms(X)) >= active#(terms(X)) because mark# > active# and [48], by (Copy) 48] mark#*(terms(X)) >= terms(X) because [49], by (Select) 49] terms(X) >= terms(X) because terms in Mul and [50], by (Fun) 50] X >= X by (Meta) 51] mark#(terms(X)) >= mark#(X) because mark# in Mul and [52], by (Fun) 52] terms(X) >= X because [53], by (Star) 53] terms*(X) >= X because [50], by (Select) 54] mark#(cons(X)) >= mark#(X) because [55], by (Star) 55] mark#*(cons(X)) >= mark#(X) because [56], by (Select) 56] cons(X) >= mark#(X) because cons = mark#, cons in Mul and [57], by (Fun) 57] X >= X by (Meta) 58] mark#(recip(X)) >= mark#(X) because mark# in Mul and [59], by (Fun) 59] recip(X) >= X because [60], by (Star) 60] recip*(X) >= X because [50], by (Select) 61] mark#(sqr(X)) >= active#(sqr(X)) because [62], by (Star) 62] mark#*(sqr(X)) >= active#(sqr(X)) because mark# > active# and [63], by (Copy) 63] mark#*(sqr(X)) >= sqr(X) because [64], by (Select) 64] sqr(X) >= sqr(X) because sqr in Mul and [50], by (Fun) 65] mark#(sqr(X)) >= mark#(X) because mark# in Mul and [66], by (Fun) 66] sqr(X) >= X because [67], by (Star) 67] sqr*(X) >= X because [50], by (Select) 68] mark#(s(X)) > mark#(X) because [69], by definition 69] mark#*(s(X)) >= mark#(X) because [70], by (Select) 70] s(X) >= mark#(X) because [71], by (Star) 71] s*(X) >= mark#(X) because s > mark# and [18], by (Copy) 72] mark#(add(X, Y)) >= active#(add(X, Y)) because [73], by (Star) 73] mark#*(add(X, Y)) >= active#(add(X, Y)) because mark# > active# and [74], by (Copy) 74] mark#*(add(X, Y)) >= add(X, Y) because [75], by (Select) 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 mark# in Mul and [79], by (Fun) 79] add(X, Y) >= X because [80], by (Star) 80] add*(X, Y) >= X because [76], by (Select) 81] mark#(add(X, Y)) >= mark#(Y) because [82], by (Star) 82] mark#*(add(X, Y)) >= mark#(Y) because [83], by (Select) 83] add(X, Y) >= mark#(Y) because [84], by (Star) 84] add*(X, Y) >= mark#(Y) because add > mark# and [85], by (Copy) 85] add*(X, Y) >= Y because [77], by (Select) 86] mark#(dbl(X)) >= active#(dbl(X)) because [87], by (Star) 87] mark#*(dbl(X)) >= active#(dbl(X)) because mark# > active# and [88], by (Copy) 88] mark#*(dbl(X)) >= dbl(X) because [89], by (Select) 89] dbl(X) >= dbl(X) because dbl in Mul and [50], by (Fun) 90] mark#(dbl(X)) >= mark#(X) because mark# in Mul and [91], by (Fun) 91] dbl(X) >= X because [92], by (Star) 92] dbl*(X) >= X because [50], by (Select) 93] mark#(first(X, Y)) >= active#(first(X, Y)) because [94], by (Star) 94] mark#*(first(X, Y)) >= active#(first(X, Y)) because mark# > active# and [95], by (Copy) 95] mark#*(first(X, Y)) >= first(X, Y) because [96], by (Select) 96] first(X, Y) >= first(X, Y) because first in Mul, [76] and [77], by (Fun) 97] mark#(first(X, Y)) >= mark#(X) because [98], by (Star) 98] mark#*(first(X, Y)) >= mark#(X) because [99], by (Select) 99] first(X, Y) >= mark#(X) because [100], by (Star) 100] first*(X, Y) >= mark#(X) because first > mark# and [101], by (Copy) 101] first*(X, Y) >= X because [76], by (Select) 102] mark#(first(X, Y)) >= mark#(Y) because mark# in Mul and [103], by (Fun) 103] first(X, Y) >= Y because [104], by (Star) 104] first*(X, Y) >= Y because [77], by (Select) 105] terms(X) >= cons(recip(sqr(X))) because [5], by (Star) 106] sqr(0) >= 0 because [107], by (Star) 107] sqr*(0) >= 0 because [108], by (Select) 108] 0 >= 0 by (Fun) 109] sqr(s(X)) >= s(add(sqr(X), dbl(X))) because [14], by (Star) 110] dbl(0) >= 0 because [111], by (Star) 111] dbl*(0) >= 0 because dbl > 0, by (Copy) 112] dbl(s(X)) >= s(s(dbl(X))) because [25], by (Star) 113] add(0, X) >= X because [32], by (Star) 114] add(s(X), Y) >= s(add(X, Y)) because [37], by (Star) 115] first(0, X) >= _|_ by (Bot) 116] first(s(X), cons(Y)) >= cons(Y) because [44], by (Star) 117] terms(X) >= terms(X) because terms in Mul and [50], by (Fun) 118] cons(X) >= cons(X) because cons in Mul and [76], by (Fun) 119] recip(X) >= recip(X) because recip in Mul and [50], by (Fun) 120] sqr(X) >= sqr(X) because sqr in Mul and [50], by (Fun) 121] s(X) >= s(X) because s in Mul and [50], by (Fun) 122] 0 >= 0 by (Fun) 123] add(X, Y) >= add(X, Y) because add in Mul, [76] and [77], by (Fun) 124] dbl(X) >= dbl(X) because dbl in Mul and [50], by (Fun) 125] first(X, Y) >= first(X, Y) because first in Mul, [76] and [77], by (Fun) 126] _|_ >= _|_ by (Bot) 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) 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_13, R_0, minimal, formative), where P_13 consists of: 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))) 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#(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) Thus, the original system is terminating if (P_13, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_13, R_0, minimal, formative). We 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 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 3 : * 4 : 7 * 5 : * 6 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 7 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 8 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 9 : 0 * 10 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 11 : 2, 3 * 12 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 13 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 14 : 1 * 15 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 16 : 4 * 17 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 18 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 This graph has the following strongly connected components: P_14: active#(add(0, X)) =#> mark#(X) active#(first(s(X), cons(Y, Z))) =#> mark#(cons(Y, first(X, Z))) mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(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)) =#> mark#(X) mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_13, R_0, m, f) by (P_14, R_0, m, f). 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#(add(0, X)) >? mark#(X) active#(first(s(X), cons(Y, Z))) >? mark#(cons(Y, first(X, Z))) mark#(terms(X)) >? mark#(X) mark#(cons(X, Y)) >? mark#(X) mark#(recip(X)) >? mark#(X) mark#(sqr(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)) >? mark#(X) mark#(first(X, Y)) >? active#(first(mark(X), mark(Y))) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) 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))) 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) 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) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 3 active = \y0.y0 active# = \y0.y0 add = \y0y1.3 + y1 + 2y0 cons = \y0y1.y0 dbl = \y0.2 + 2y0 first = \y0y1.y0 + 2y1 mark = \y0.y0 mark# = \y0.1 + y0 nil = 0 recip = \y0.y0 s = \y0.2 sqr = \y0.2y0 terms = \y0.2y0 Using this interpretation, the requirements translate to: [[active#(add(0, _x0))]] = 9 + x0 > 1 + x0 = [[mark#(_x0)]] [[active#(first(s(_x0), cons(_x1, _x2)))]] = 2 + 2x1 > 1 + x1 = [[mark#(cons(_x1, first(_x0, _x2)))]] [[mark#(terms(_x0))]] = 1 + 2x0 >= 1 + x0 = [[mark#(_x0)]] [[mark#(cons(_x0, _x1))]] = 1 + x0 >= 1 + x0 = [[mark#(_x0)]] [[mark#(recip(_x0))]] = 1 + x0 >= 1 + x0 = [[mark#(_x0)]] [[mark#(sqr(_x0))]] = 1 + 2x0 >= 1 + x0 = [[mark#(_x0)]] [[mark#(add(_x0, _x1))]] = 4 + x1 + 2x0 > 3 + x1 + 2x0 = [[active#(add(mark(_x0), mark(_x1)))]] [[mark#(add(_x0, _x1))]] = 4 + x1 + 2x0 > 1 + x0 = [[mark#(_x0)]] [[mark#(add(_x0, _x1))]] = 4 + x1 + 2x0 > 1 + x1 = [[mark#(_x1)]] [[mark#(dbl(_x0))]] = 3 + 2x0 > 1 + x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = 1 + x0 + 2x1 > x0 + 2x1 = [[active#(first(mark(_x0), mark(_x1)))]] [[mark#(first(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x1 = [[mark#(_x1)]] [[active(terms(_x0))]] = 2x0 >= 2x0 = [[mark(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active(sqr(0))]] = 6 >= 3 = [[mark(0)]] [[active(sqr(s(_x0)))]] = 4 >= 2 = [[mark(s(add(sqr(_x0), dbl(_x0))))]] [[active(dbl(0))]] = 8 >= 3 = [[mark(0)]] [[active(dbl(s(_x0)))]] = 6 >= 2 = [[mark(s(s(dbl(_x0))))]] [[active(add(0, _x0))]] = 9 + x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = 7 + x1 >= 2 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = 3 + 2x0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = 2 + 2x1 >= x1 = [[mark(cons(_x1, first(_x0, _x2)))]] [[mark(terms(_x0))]] = 2x0 >= 2x0 = [[active(terms(mark(_x0)))]] [[mark(cons(_x0, _x1))]] = x0 >= x0 = [[active(cons(mark(_x0), _x1))]] [[mark(recip(_x0))]] = x0 >= x0 = [[active(recip(mark(_x0)))]] [[mark(sqr(_x0))]] = 2x0 >= 2x0 = [[active(sqr(mark(_x0)))]] [[mark(s(_x0))]] = 2 >= 2 = [[active(s(mark(_x0)))]] [[mark(0)]] = 3 >= 3 = [[active(0)]] [[mark(add(_x0, _x1))]] = 3 + x1 + 2x0 >= 3 + x1 + 2x0 = [[active(add(mark(_x0), mark(_x1)))]] [[mark(dbl(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[active(dbl(mark(_x0)))]] [[mark(first(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(first(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[terms(mark(_x0))]] = 2x0 >= 2x0 = [[terms(_x0)]] [[terms(active(_x0))]] = 2x0 >= 2x0 = [[terms(_x0)]] [[cons(mark(_x0), _x1)]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = x0 >= x0 = [[cons(_x0, _x1)]] [[recip(mark(_x0))]] = x0 >= x0 = [[recip(_x0)]] [[recip(active(_x0))]] = x0 >= x0 = [[recip(_x0)]] [[sqr(mark(_x0))]] = 2x0 >= 2x0 = [[sqr(_x0)]] [[sqr(active(_x0))]] = 2x0 >= 2x0 = [[sqr(_x0)]] [[s(mark(_x0))]] = 2 >= 2 = [[s(_x0)]] [[s(active(_x0))]] = 2 >= 2 = [[s(_x0)]] [[add(mark(_x0), _x1)]] = 3 + x1 + 2x0 >= 3 + x1 + 2x0 = [[add(_x0, _x1)]] [[add(_x0, mark(_x1))]] = 3 + x1 + 2x0 >= 3 + x1 + 2x0 = [[add(_x0, _x1)]] [[add(active(_x0), _x1)]] = 3 + x1 + 2x0 >= 3 + x1 + 2x0 = [[add(_x0, _x1)]] [[add(_x0, active(_x1))]] = 3 + x1 + 2x0 >= 3 + x1 + 2x0 = [[add(_x0, _x1)]] [[dbl(mark(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[dbl(_x0)]] [[dbl(active(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[dbl(_x0)]] [[first(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[first(_x0, _x1)]] [[first(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[first(_x0, _x1)]] [[first(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[first(_x0, _x1)]] [[first(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[first(_x0, _x1)]] 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: mark#(terms(X)) =#> mark#(X) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) 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 apply the subterm criterion with the following projection function: nu(mark#) = 1 Thus, we can orient the dependency pairs as follows: nu(mark#(terms(X))) = terms(X) |> X = nu(mark#(X)) nu(mark#(cons(X, Y))) = cons(X, Y) |> X = nu(mark#(X)) nu(mark#(recip(X))) = recip(X) |> X = nu(mark#(X)) nu(mark#(sqr(X))) = sqr(X) |> X = nu(mark#(X)) nu(mark#(first(X, Y))) = first(X, Y) |> X = nu(mark#(X)) nu(mark#(first(X, Y))) = first(X, Y) |> Y = nu(mark#(Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_15, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. 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.