/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(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(X)) 38] mark#(s(X)) =#> s#(X) 39] mark#(0) =#> active#(0) 40] mark#(add(X, Y)) =#> active#(add(mark(X), mark(Y))) 41] mark#(add(X, Y)) =#> add#(mark(X), mark(Y)) 42] mark#(add(X, Y)) =#> mark#(X) 43] mark#(add(X, Y)) =#> mark#(Y) 44] mark#(dbl(X)) =#> active#(dbl(mark(X))) 45] mark#(dbl(X)) =#> dbl#(mark(X)) 46] mark#(dbl(X)) =#> mark#(X) 47] mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) 48] mark#(first(X, Y)) =#> first#(mark(X), mark(Y)) 49] mark#(first(X, Y)) =#> mark#(X) 50] mark#(first(X, Y)) =#> mark#(Y) 51] mark#(nil) =#> active#(nil) 52] terms#(mark(X)) =#> terms#(X) 53] terms#(active(X)) =#> terms#(X) 54] cons#(mark(X), Y) =#> cons#(X, Y) 55] cons#(X, mark(Y)) =#> cons#(X, Y) 56] cons#(active(X), Y) =#> cons#(X, Y) 57] cons#(X, active(Y)) =#> cons#(X, Y) 58] recip#(mark(X)) =#> recip#(X) 59] recip#(active(X)) =#> recip#(X) 60] sqr#(mark(X)) =#> sqr#(X) 61] sqr#(active(X)) =#> sqr#(X) 62] s#(mark(X)) =#> s#(X) 63] s#(active(X)) =#> s#(X) 64] add#(mark(X), Y) =#> add#(X, Y) 65] add#(X, mark(Y)) =#> add#(X, Y) 66] add#(active(X), Y) =#> add#(X, Y) 67] add#(X, active(Y)) =#> add#(X, Y) 68] dbl#(mark(X)) =#> dbl#(X) 69] dbl#(active(X)) =#> dbl#(X) 70] first#(mark(X), Y) =#> first#(X, Y) 71] first#(X, mark(Y)) =#> first#(X, Y) 72] first#(active(X), Y) =#> first#(X, Y) 73] 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(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 : 60, 61 * 4 : * 5 : 62, 63 * 6 : 39 * 7 : 37, 38 * 8 : * 9 : * 10 : 60, 61 * 11 : 68, 69 * 12 : 39 * 13 : 37, 38 * 14 : * 15 : * 16 : 68, 69 * 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 * 18 : 37, 38 * 19 : * 20 : 64, 65, 66, 67 * 21 : 51 * 22 : 28, 29, 30 * 23 : 54, 56 * 24 : 70, 71, 72, 73 * 25 : 0, 1, 2, 3, 4, 5 * 26 : 52, 53 * 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 * 28 : * 29 : 54, 55, 56, 57 * 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 * 31 : * 32 : 58, 59 * 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 * 34 : 6, 7, 8, 9, 10, 11 * 35 : 60, 61 * 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 * 37 : * 38 : 62, 63 * 39 : * 40 : 17, 18, 19, 20 * 41 : 64, 65, 66, 67 * 42 : 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 * 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 * 44 : 12, 13, 14, 15, 16 * 45 : 68, 69 * 46 : 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 * 47 : 21, 22, 23, 24 * 48 : 70, 71, 72, 73 * 49 : 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 * 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 * 51 : * 52 : 52, 53 * 53 : 52, 53 * 54 : 54, 55, 56, 57 * 55 : 54, 55, 56, 57 * 56 : 54, 55, 56, 57 * 57 : 54, 55, 56, 57 * 58 : 58, 59 * 59 : 58, 59 * 60 : 60, 61 * 61 : 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, 72, 73 * 71 : 70, 71, 72, 73 * 72 : 70, 71, 72, 73 * 73 : 70, 71, 72, 73 This graph has the following strongly connected components: P_1: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) active#(add(0, X)) =#> mark#(X) 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)) =#> 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) 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#(add(0, X)) >? mark#(X) 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)) >? 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(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 = 1 active = \y0.y0 active# = \y0.y0 add = \y0y1.y0 + y1 cons = \y0y1.y0 dbl = \y0.2y0 first = \y0y1.y0 + 2y1 mark = \y0.y0 mark# = \y0.y0 nil = 0 recip = \y0.2y0 s = \y0.0 sqr = \y0.y0 terms = \y0.2y0 Using this interpretation, the requirements translate to: [[active#(terms(_x0))]] = 2x0 >= 2x0 = [[mark#(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active#(add(0, _x0))]] = 1 + x0 > x0 = [[mark#(_x0)]] [[active#(first(s(_x0), cons(_x1, _x2)))]] = 2x1 >= x1 = [[mark#(cons(_x1, first(_x0, _x2)))]] [[mark#(terms(_x0))]] = 2x0 >= 2x0 = [[active#(terms(mark(_x0)))]] [[mark#(terms(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] [[mark#(cons(_x0, _x1))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(recip(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] [[mark#(sqr(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(add(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active#(add(mark(_x0), mark(_x1)))]] [[mark#(add(_x0, _x1))]] = x0 + x1 >= x0 = [[mark#(_x0)]] [[mark#(add(_x0, _x1))]] = x0 + x1 >= x1 = [[mark#(_x1)]] [[mark#(dbl(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active#(first(mark(_x0), mark(_x1)))]] [[mark#(first(_x0, _x1))]] = x0 + 2x1 >= x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = x0 + 2x1 >= x1 = [[mark#(_x1)]] [[active(terms(_x0))]] = 2x0 >= 2x0 = [[mark(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active(sqr(0))]] = 1 >= 1 = [[mark(0)]] [[active(sqr(s(_x0)))]] = 0 >= 0 = [[mark(s(add(sqr(_x0), dbl(_x0))))]] [[active(dbl(0))]] = 2 >= 1 = [[mark(0)]] [[active(dbl(s(_x0)))]] = 0 >= 0 = [[mark(s(s(dbl(_x0))))]] [[active(add(0, _x0))]] = 1 + x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = x1 >= 0 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = 1 + 2x0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = 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))]] = 2x0 >= 2x0 = [[active(recip(mark(_x0)))]] [[mark(sqr(_x0))]] = x0 >= x0 = [[active(sqr(mark(_x0)))]] [[mark(s(_x0))]] = 0 >= 0 = [[active(s(_x0))]] [[mark(0)]] = 1 >= 1 = [[active(0)]] [[mark(add(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(add(mark(_x0), mark(_x1)))]] [[mark(dbl(_x0))]] = 2x0 >= 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))]] = 2x0 >= 2x0 = [[recip(_x0)]] [[recip(active(_x0))]] = 2x0 >= 2x0 = [[recip(_x0)]] [[sqr(mark(_x0))]] = x0 >= x0 = [[sqr(_x0)]] [[sqr(active(_x0))]] = x0 >= x0 = [[sqr(_x0)]] [[s(mark(_x0))]] = 0 >= 0 = [[s(_x0)]] [[s(active(_x0))]] = 0 >= 0 = [[s(_x0)]] [[add(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[add(_x0, _x1)]] [[add(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[add(_x0, _x1)]] [[add(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[add(_x0, _x1)]] [[add(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[add(_x0, _x1)]] [[dbl(mark(_x0))]] = 2x0 >= 2x0 = [[dbl(_x0)]] [[dbl(active(_x0))]] = 2x0 >= 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_1, R_0, minimal, formative) by (P_13, R_0, minimal, formative), where P_13 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) 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)) =#> 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) 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 : 4 * 1 : 4 * 2 : 0 * 3 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 4 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 5 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 6 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 7 : * 8 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 9 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 10 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 11 : 1 * 12 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 13 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 This graph has the following strongly connected components: P_14: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(X)))) 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)) =#> mark#(X) 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#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(X)))) 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)) >? mark#(X) 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(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 = 2 active = \y0.y0 active# = \y0.2y0 add = \y0y1.1 + 2y1 + 3y0 cons = \y0y1.y0 dbl = \y0.y0 first = \y0y1.y0 + y1 mark = \y0.y0 mark# = \y0.2y0 nil = 0 recip = \y0.y0 s = \y0.1 sqr = \y0.y0 terms = \y0.y0 Using this interpretation, the requirements translate to: [[active#(terms(_x0))]] = 2x0 >= 2x0 = [[mark#(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active#(first(s(_x0), cons(_x1, _x2)))]] = 2 + 2x1 > 2x1 = [[mark#(cons(_x1, first(_x0, _x2)))]] [[mark#(terms(_x0))]] = 2x0 >= 2x0 = [[active#(terms(mark(_x0)))]] [[mark#(terms(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(cons(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(recip(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(sqr(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(add(_x0, _x1))]] = 2 + 4x1 + 6x0 > 2x0 = [[mark#(_x0)]] [[mark#(add(_x0, _x1))]] = 2 + 4x1 + 6x0 > 2x1 = [[mark#(_x1)]] [[mark#(dbl(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active#(first(mark(_x0), mark(_x1)))]] [[mark#(first(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = 2x0 + 2x1 >= 2x1 = [[mark#(_x1)]] [[active(terms(_x0))]] = x0 >= x0 = [[mark(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active(sqr(0))]] = 2 >= 2 = [[mark(0)]] [[active(sqr(s(_x0)))]] = 1 >= 1 = [[mark(s(add(sqr(_x0), dbl(_x0))))]] [[active(dbl(0))]] = 2 >= 2 = [[mark(0)]] [[active(dbl(s(_x0)))]] = 1 >= 1 = [[mark(s(s(dbl(_x0))))]] [[active(add(0, _x0))]] = 7 + 2x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = 4 + 2x1 >= 1 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = 2 + x0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = 1 + x1 >= x1 = [[mark(cons(_x1, first(_x0, _x2)))]] [[mark(terms(_x0))]] = x0 >= x0 = [[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))]] = x0 >= x0 = [[active(sqr(mark(_x0)))]] [[mark(s(_x0))]] = 1 >= 1 = [[active(s(_x0))]] [[mark(0)]] = 2 >= 2 = [[active(0)]] [[mark(add(_x0, _x1))]] = 1 + 2x1 + 3x0 >= 1 + 2x1 + 3x0 = [[active(add(mark(_x0), mark(_x1)))]] [[mark(dbl(_x0))]] = x0 >= x0 = [[active(dbl(mark(_x0)))]] [[mark(first(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(first(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[terms(mark(_x0))]] = x0 >= x0 = [[terms(_x0)]] [[terms(active(_x0))]] = x0 >= x0 = [[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))]] = x0 >= x0 = [[sqr(_x0)]] [[sqr(active(_x0))]] = x0 >= x0 = [[sqr(_x0)]] [[s(mark(_x0))]] = 1 >= 1 = [[s(_x0)]] [[s(active(_x0))]] = 1 >= 1 = [[s(_x0)]] [[add(mark(_x0), _x1)]] = 1 + 2x1 + 3x0 >= 1 + 2x1 + 3x0 = [[add(_x0, _x1)]] [[add(_x0, mark(_x1))]] = 1 + 2x1 + 3x0 >= 1 + 2x1 + 3x0 = [[add(_x0, _x1)]] [[add(active(_x0), _x1)]] = 1 + 2x1 + 3x0 >= 1 + 2x1 + 3x0 = [[add(_x0, _x1)]] [[add(_x0, active(_x1))]] = 1 + 2x1 + 3x0 >= 1 + 2x1 + 3x0 = [[add(_x0, _x1)]] [[dbl(mark(_x0))]] = x0 >= x0 = [[dbl(_x0)]] [[dbl(active(_x0))]] = x0 >= x0 = [[dbl(_x0)]] [[first(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[first(_x0, _x1)]] [[first(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[first(_x0, _x1)]] [[first(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[first(_x0, _x1)]] [[first(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[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: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(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)) =#> 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_15, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_15, 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 : 3 * 1 : 0 * 2 : 1, 2, 3, 4, 5, 6, 7, 8, 9 * 3 : 1, 2, 3, 4, 5, 6, 7, 8, 9 * 4 : 1, 2, 3, 4, 5, 6, 7, 8, 9 * 5 : 1, 2, 3, 4, 5, 6, 7, 8, 9 * 6 : 1, 2, 3, 4, 5, 6, 7, 8, 9 * 7 : * 8 : 1, 2, 3, 4, 5, 6, 7, 8, 9 * 9 : 1, 2, 3, 4, 5, 6, 7, 8, 9 This graph has the following strongly connected components: P_16: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(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)) =#> mark#(X) mark#(dbl(X)) =#> mark#(X) 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_15, R_0, m, f) by (P_16, R_0, m, f). 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). The formative rules of (P_16, 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))) 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(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) 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) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_16, R_0, minimal, formative) by (P_16, R_1, minimal, formative). Thus, the original system is terminating if (P_16, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_16, 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)))) 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)) >? mark#(X) mark#(dbl(X)) >? mark#(X) 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(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) 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 = 0 active = \y0.y0 active# = \y0.2y0 add = \y0y1.y1 cons = \y0y1.y0 dbl = \y0.1 + y0 first = \y0y1.y0 + y1 mark = \y0.y0 mark# = \y0.2y0 nil = 0 recip = \y0.2y0 s = \y0.0 sqr = \y0.y0 terms = \y0.2y0 Using this interpretation, the requirements translate to: [[active#(terms(_x0))]] = 4x0 >= 4x0 = [[mark#(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[mark#(terms(_x0))]] = 4x0 >= 4x0 = [[active#(terms(mark(_x0)))]] [[mark#(terms(_x0))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(cons(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(recip(_x0))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(sqr(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(dbl(_x0))]] = 2 + 2x0 > 2x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = 2x0 + 2x1 >= 2x1 = [[mark#(_x1)]] [[active(terms(_x0))]] = 2x0 >= 2x0 = [[mark(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active(sqr(0))]] = 0 >= 0 = [[mark(0)]] [[active(sqr(s(_x0)))]] = 0 >= 0 = [[mark(s(add(sqr(_x0), dbl(_x0))))]] [[active(dbl(0))]] = 1 >= 0 = [[mark(0)]] [[active(dbl(s(_x0)))]] = 1 >= 0 = [[mark(s(s(dbl(_x0))))]] [[active(add(0, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = x1 >= 0 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = x0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = x1 >= 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))]] = 2x0 >= 2x0 = [[active(recip(mark(_x0)))]] [[mark(sqr(_x0))]] = x0 >= x0 = [[active(sqr(mark(_x0)))]] [[mark(s(_x0))]] = 0 >= 0 = [[active(s(_x0))]] [[mark(0)]] = 0 >= 0 = [[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))]] = x0 + x1 >= x0 + x1 = [[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))]] = 2x0 >= 2x0 = [[recip(_x0)]] [[recip(active(_x0))]] = 2x0 >= 2x0 = [[recip(_x0)]] [[sqr(mark(_x0))]] = x0 >= x0 = [[sqr(_x0)]] [[sqr(active(_x0))]] = x0 >= x0 = [[sqr(_x0)]] [[dbl(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[dbl(_x0)]] [[dbl(active(_x0))]] = 1 + x0 >= 1 + x0 = [[dbl(_x0)]] [[first(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[first(_x0, _x1)]] [[first(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[first(_x0, _x1)]] [[first(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[first(_x0, _x1)]] [[first(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[first(_x0, _x1)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_16, R_1, minimal, formative) by (P_17, R_1, minimal, formative), where P_17 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(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)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) Thus, the original system is terminating if (P_17, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_17, R_1, minimal, formative). The formative rules of (P_17, 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))) 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(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) 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.17], we may replace the dependency pair problem (P_17, R_1, minimal, formative) by (P_17, R_2, minimal, formative). Thus, the original system is terminating if (P_17, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_17, 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)))) 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)) >? mark#(X) 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(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) 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 = 0 active = \y0.y0 active# = \y0.y0 add = \y0y1.2y1 cons = \y0y1.y0 dbl = \y0.2 first = \y0y1.1 + y0 + y1 mark = \y0.y0 mark# = \y0.2y0 nil = 0 recip = \y0.y0 s = \y0.0 sqr = \y0.y0 terms = \y0.2y0 Using this interpretation, the requirements translate to: [[active#(terms(_x0))]] = 2x0 >= 2x0 = [[mark#(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[mark#(terms(_x0))]] = 4x0 >= 2x0 = [[active#(terms(mark(_x0)))]] [[mark#(terms(_x0))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(cons(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(recip(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(sqr(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = 2 + 2x0 + 2x1 > 2x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = 2 + 2x0 + 2x1 > 2x1 = [[mark#(_x1)]] [[active(terms(_x0))]] = 2x0 >= x0 = [[mark(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active(sqr(0))]] = 0 >= 0 = [[mark(0)]] [[active(sqr(s(_x0)))]] = 0 >= 0 = [[mark(s(add(sqr(_x0), dbl(_x0))))]] [[active(dbl(0))]] = 2 >= 0 = [[mark(0)]] [[active(dbl(s(_x0)))]] = 2 >= 0 = [[mark(s(s(dbl(_x0))))]] [[active(add(0, _x0))]] = 2x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = 2x1 >= 0 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = 1 + x0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = 1 + x1 >= 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))]] = x0 >= x0 = [[active(sqr(mark(_x0)))]] [[mark(s(_x0))]] = 0 >= 0 = [[active(s(_x0))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(add(_x0, _x1))]] = 2x1 >= 2x1 = [[active(add(mark(_x0), mark(_x1)))]] [[mark(dbl(_x0))]] = 2 >= 2 = [[active(dbl(mark(_x0)))]] [[mark(first(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[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))]] = x0 >= x0 = [[sqr(_x0)]] [[sqr(active(_x0))]] = x0 >= x0 = [[sqr(_x0)]] [[first(mark(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[first(_x0, _x1)]] [[first(_x0, mark(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[first(_x0, _x1)]] [[first(active(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[first(_x0, _x1)]] [[first(_x0, active(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[first(_x0, _x1)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_17, R_2, minimal, formative) by (P_18, R_2, minimal, formative), where P_18 consists of: active#(terms(X)) =#> mark#(cons(recip(sqr(X)), terms(s(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)) =#> mark#(X) Thus, the original system is terminating if (P_18, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_18, R_2, minimal, formative). The formative rules of (P_18, 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))) 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(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) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_18, R_2, minimal, formative) by (P_18, R_3, minimal, formative). Thus, the original system is terminating if (P_18, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_18, 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#(terms(X)) >? mark#(cons(recip(sqr(X)), terms(s(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)) >? 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))) 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(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) 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.2y0 add = \y0y1.y1 cons = \y0y1.y0 dbl = \y0.0 first = \y0y1.2y1 mark = \y0.y0 mark# = \y0.2y0 nil = 0 recip = \y0.y0 s = \y0.0 sqr = \y0.y0 terms = \y0.2 + 2y0 Using this interpretation, the requirements translate to: [[active#(terms(_x0))]] = 4 + 4x0 > 2x0 = [[mark#(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[mark#(terms(_x0))]] = 4 + 4x0 >= 4 + 4x0 = [[active#(terms(mark(_x0)))]] [[mark#(terms(_x0))]] = 4 + 4x0 > 2x0 = [[mark#(_x0)]] [[mark#(cons(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(recip(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(sqr(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[active(terms(_x0))]] = 2 + 2x0 >= x0 = [[mark(cons(recip(sqr(_x0)), terms(s(_x0))))]] [[active(sqr(0))]] = 0 >= 0 = [[mark(0)]] [[active(sqr(s(_x0)))]] = 0 >= 0 = [[mark(s(add(sqr(_x0), dbl(_x0))))]] [[active(dbl(0))]] = 0 >= 0 = [[mark(0)]] [[active(dbl(s(_x0)))]] = 0 >= 0 = [[mark(s(s(dbl(_x0))))]] [[active(add(0, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = x1 >= 0 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = 2x0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = 2x1 >= x1 = [[mark(cons(_x1, first(_x0, _x2)))]] [[mark(terms(_x0))]] = 2 + 2x0 >= 2 + 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))]] = x0 >= x0 = [[active(sqr(mark(_x0)))]] [[mark(s(_x0))]] = 0 >= 0 = [[active(s(_x0))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(add(_x0, _x1))]] = x1 >= x1 = [[active(add(mark(_x0), mark(_x1)))]] [[mark(dbl(_x0))]] = 0 >= 0 = [[active(dbl(mark(_x0)))]] [[mark(first(_x0, _x1))]] = 2x1 >= 2x1 = [[active(first(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[terms(mark(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[terms(_x0)]] [[terms(active(_x0))]] = 2 + 2x0 >= 2 + 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))]] = x0 >= x0 = [[sqr(_x0)]] [[sqr(active(_x0))]] = x0 >= x0 = [[sqr(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_18, R_3, minimal, formative) by (P_19, R_3, minimal, formative), where P_19 consists of: mark#(terms(X)) =#> active#(terms(mark(X))) mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> mark#(X) Thus, the original system is terminating if (P_19, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_19, 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 : * 1 : 0, 1, 2, 3 * 2 : 0, 1, 2, 3 * 3 : 0, 1, 2, 3 This graph has the following strongly connected components: P_20: mark#(cons(X, Y)) =#> mark#(X) mark#(recip(X)) =#> mark#(X) mark#(sqr(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_19, R_3, m, f) by (P_20, R_3, m, f). Thus, the original system is terminating if (P_20, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_20, R_3, 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#(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)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_20, R_3, minimal, f) by ({}, R_3, 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.