/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o active : [o] --> o cons : [o * o] --> o eq : [o * o] --> o false : [] --> o inf : [o] --> o length : [o] --> o mark : [o] --> o nil : [] --> o s : [o] --> o take : [o * o] --> o true : [] --> o active(eq(0, 0)) => mark(true) active(eq(s(X), s(Y))) => mark(eq(X, Y)) active(eq(X, Y)) => mark(false) active(inf(X)) => mark(cons(X, inf(s(X)))) active(take(0, X)) => mark(nil) active(take(s(X), cons(Y, Z))) => mark(cons(Y, take(X, Z))) active(length(nil)) => mark(0) active(length(cons(X, Y))) => mark(s(length(Y))) mark(eq(X, Y)) => active(eq(X, Y)) mark(0) => active(0) mark(true) => active(true) mark(s(X)) => active(s(X)) mark(false) => active(false) mark(inf(X)) => active(inf(mark(X))) mark(cons(X, Y)) => active(cons(X, Y)) mark(take(X, Y)) => active(take(mark(X), mark(Y))) mark(nil) => active(nil) mark(length(X)) => active(length(mark(X))) eq(mark(X), Y) => eq(X, Y) eq(X, mark(Y)) => eq(X, Y) eq(active(X), Y) => eq(X, Y) eq(X, active(Y)) => eq(X, Y) s(mark(X)) => s(X) s(active(X)) => s(X) inf(mark(X)) => inf(X) inf(active(X)) => inf(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) take(mark(X), Y) => take(X, Y) take(X, mark(Y)) => take(X, Y) take(active(X), Y) => take(X, Y) take(X, active(Y)) => take(X, Y) length(mark(X)) => length(X) length(active(X)) => length(X) We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] active#(eq(0, 0)) =#> mark#(true) 1] active#(eq(s(X), s(Y))) =#> mark#(eq(X, Y)) 2] active#(eq(s(X), s(Y))) =#> eq#(X, Y) 3] active#(eq(X, Y)) =#> mark#(false) 4] active#(inf(X)) =#> mark#(cons(X, inf(s(X)))) 5] active#(inf(X)) =#> cons#(X, inf(s(X))) 6] active#(inf(X)) =#> inf#(s(X)) 7] active#(inf(X)) =#> s#(X) 8] active#(take(0, X)) =#> mark#(nil) 9] active#(take(s(X), cons(Y, Z))) =#> mark#(cons(Y, take(X, Z))) 10] active#(take(s(X), cons(Y, Z))) =#> cons#(Y, take(X, Z)) 11] active#(take(s(X), cons(Y, Z))) =#> take#(X, Z) 12] active#(length(nil)) =#> mark#(0) 13] active#(length(cons(X, Y))) =#> mark#(s(length(Y))) 14] active#(length(cons(X, Y))) =#> s#(length(Y)) 15] active#(length(cons(X, Y))) =#> length#(Y) 16] mark#(eq(X, Y)) =#> active#(eq(X, Y)) 17] mark#(eq(X, Y)) =#> eq#(X, Y) 18] mark#(0) =#> active#(0) 19] mark#(true) =#> active#(true) 20] mark#(s(X)) =#> active#(s(X)) 21] mark#(s(X)) =#> s#(X) 22] mark#(false) =#> active#(false) 23] mark#(inf(X)) =#> active#(inf(mark(X))) 24] mark#(inf(X)) =#> inf#(mark(X)) 25] mark#(inf(X)) =#> mark#(X) 26] mark#(cons(X, Y)) =#> active#(cons(X, Y)) 27] mark#(cons(X, Y)) =#> cons#(X, Y) 28] mark#(take(X, Y)) =#> active#(take(mark(X), mark(Y))) 29] mark#(take(X, Y)) =#> take#(mark(X), mark(Y)) 30] mark#(take(X, Y)) =#> mark#(X) 31] mark#(take(X, Y)) =#> mark#(Y) 32] mark#(nil) =#> active#(nil) 33] mark#(length(X)) =#> active#(length(mark(X))) 34] mark#(length(X)) =#> length#(mark(X)) 35] mark#(length(X)) =#> mark#(X) 36] eq#(mark(X), Y) =#> eq#(X, Y) 37] eq#(X, mark(Y)) =#> eq#(X, Y) 38] eq#(active(X), Y) =#> eq#(X, Y) 39] eq#(X, active(Y)) =#> eq#(X, Y) 40] s#(mark(X)) =#> s#(X) 41] s#(active(X)) =#> s#(X) 42] inf#(mark(X)) =#> inf#(X) 43] inf#(active(X)) =#> inf#(X) 44] cons#(mark(X), Y) =#> cons#(X, Y) 45] cons#(X, mark(Y)) =#> cons#(X, Y) 46] cons#(active(X), Y) =#> cons#(X, Y) 47] cons#(X, active(Y)) =#> cons#(X, Y) 48] take#(mark(X), Y) =#> take#(X, Y) 49] take#(X, mark(Y)) =#> take#(X, Y) 50] take#(active(X), Y) =#> take#(X, Y) 51] take#(X, active(Y)) =#> take#(X, Y) 52] length#(mark(X)) =#> length#(X) 53] length#(active(X)) =#> length#(X) Rules R_0: active(eq(0, 0)) => mark(true) active(eq(s(X), s(Y))) => mark(eq(X, Y)) active(eq(X, Y)) => mark(false) active(inf(X)) => mark(cons(X, inf(s(X)))) active(take(0, X)) => mark(nil) active(take(s(X), cons(Y, Z))) => mark(cons(Y, take(X, Z))) active(length(nil)) => mark(0) active(length(cons(X, Y))) => mark(s(length(Y))) mark(eq(X, Y)) => active(eq(X, Y)) mark(0) => active(0) mark(true) => active(true) mark(s(X)) => active(s(X)) mark(false) => active(false) mark(inf(X)) => active(inf(mark(X))) mark(cons(X, Y)) => active(cons(X, Y)) mark(take(X, Y)) => active(take(mark(X), mark(Y))) mark(nil) => active(nil) mark(length(X)) => active(length(mark(X))) eq(mark(X), Y) => eq(X, Y) eq(X, mark(Y)) => eq(X, Y) eq(active(X), Y) => eq(X, Y) eq(X, active(Y)) => eq(X, Y) s(mark(X)) => s(X) s(active(X)) => s(X) inf(mark(X)) => inf(X) inf(active(X)) => inf(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) take(mark(X), Y) => take(X, Y) take(X, mark(Y)) => take(X, Y) take(active(X), Y) => take(X, Y) take(X, active(Y)) => take(X, Y) length(mark(X)) => length(X) length(active(X)) => length(X) Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 19 * 1 : 16, 17 * 2 : 36, 37, 38, 39 * 3 : 22 * 4 : 26, 27 * 5 : 44, 46 * 6 : * 7 : 40, 41 * 8 : 32 * 9 : 26, 27 * 10 : 44, 46 * 11 : 48, 49, 50, 51 * 12 : 18 * 13 : 20, 21 * 14 : * 15 : 52, 53 * 16 : 0, 1, 2, 3 * 17 : 36, 37, 38, 39 * 18 : * 19 : * 20 : * 21 : 40, 41 * 22 : * 23 : 4, 5, 6, 7 * 24 : 42, 43 * 25 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35 * 26 : * 27 : 44, 45, 46, 47 * 28 : 8, 9, 10, 11 * 29 : 48, 49, 50, 51 * 30 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35 * 31 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35 * 32 : * 33 : 12, 13, 14, 15 * 34 : 52, 53 * 35 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35 * 36 : 36, 37, 38, 39 * 37 : 36, 37, 38, 39 * 38 : 36, 37, 38, 39 * 39 : 36, 37, 38, 39 * 40 : 40, 41 * 41 : 40, 41 * 42 : 42, 43 * 43 : 42, 43 * 44 : 44, 45, 46, 47 * 45 : 44, 45, 46, 47 * 46 : 44, 45, 46, 47 * 47 : 44, 45, 46, 47 * 48 : 48, 49, 50, 51 * 49 : 48, 49, 50, 51 * 50 : 48, 49, 50, 51 * 51 : 48, 49, 50, 51 * 52 : 52, 53 * 53 : 52, 53 This graph has the following strongly connected components: P_1: active#(eq(s(X), s(Y))) =#> mark#(eq(X, Y)) mark#(eq(X, Y)) =#> active#(eq(X, Y)) P_2: mark#(inf(X)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(length(X)) =#> mark#(X) P_3: eq#(mark(X), Y) =#> eq#(X, Y) eq#(X, mark(Y)) =#> eq#(X, Y) eq#(active(X), Y) =#> eq#(X, Y) eq#(X, active(Y)) =#> eq#(X, Y) P_4: s#(mark(X)) =#> s#(X) s#(active(X)) =#> s#(X) P_5: inf#(mark(X)) =#> inf#(X) inf#(active(X)) =#> inf#(X) P_6: 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_7: take#(mark(X), Y) =#> take#(X, Y) take#(X, mark(Y)) =#> take#(X, Y) take#(active(X), Y) =#> take#(X, Y) take#(X, active(Y)) =#> take#(X, Y) P_8: length#(mark(X)) =#> length#(X) length#(active(X)) =#> length#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f), (P_2, R_0, m, f), (P_3, R_0, m, f), (P_4, R_0, m, f), (P_5, R_0, m, f), (P_6, R_0, m, f), (P_7, R_0, m, f) and (P_8, 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) 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(length#) = 1 Thus, we can orient the dependency pairs as follows: nu(length#(mark(X))) = mark(X) |> X = nu(length#(X)) nu(length#(active(X))) = active(X) |> X = nu(length#(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(take#) = 1 Thus, we can orient the dependency pairs as follows: nu(take#(mark(X), Y)) = mark(X) |> X = nu(take#(X, Y)) nu(take#(X, mark(Y))) = X = X = nu(take#(X, Y)) nu(take#(active(X), Y)) = active(X) |> X = nu(take#(X, Y)) nu(take#(X, active(Y))) = X = X = nu(take#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_7, R_0, minimal, f) by (P_9, R_0, minimal, f), where P_9 contains: take#(X, mark(Y)) =#> take#(X, Y) take#(X, active(Y)) =#> take#(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_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(take#) = 2 Thus, we can orient the dependency pairs as follows: nu(take#(X, mark(Y))) = mark(Y) |> Y = nu(take#(X, Y)) nu(take#(X, active(Y))) = active(Y) |> Y = nu(take#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_9, 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(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_6, R_0, minimal, f) by (P_10, R_0, minimal, f), where P_10 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), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, 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(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_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) 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(inf#) = 1 Thus, we can orient the dependency pairs as follows: nu(inf#(mark(X))) = mark(X) |> X = nu(inf#(X)) nu(inf#(active(X))) = active(X) |> X = nu(inf#(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(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_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(eq#) = 1 Thus, we can orient the dependency pairs as follows: nu(eq#(mark(X), Y)) = mark(X) |> X = nu(eq#(X, Y)) nu(eq#(X, mark(Y))) = X = X = nu(eq#(X, Y)) nu(eq#(active(X), Y)) = active(X) |> X = nu(eq#(X, Y)) nu(eq#(X, active(Y))) = X = X = nu(eq#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_3, R_0, minimal, f) by (P_11, R_0, minimal, f), where P_11 contains: eq#(X, mark(Y)) =#> eq#(X, Y) eq#(X, active(Y)) =#> eq#(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_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(eq#) = 2 Thus, we can orient the dependency pairs as follows: nu(eq#(X, mark(Y))) = mark(Y) |> Y = nu(eq#(X, Y)) nu(eq#(X, active(Y))) = active(Y) |> Y = nu(eq#(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) 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(mark#) = 1 Thus, we can orient the dependency pairs as follows: nu(mark#(inf(X))) = inf(X) |> X = nu(mark#(X)) nu(mark#(take(X, Y))) = take(X, Y) |> X = nu(mark#(X)) nu(mark#(take(X, Y))) = take(X, Y) |> Y = nu(mark#(Y)) nu(mark#(length(X))) = length(X) |> X = nu(mark#(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). The formative rules of (P_1, R_0) are R_1 ::= active(eq(0, 0)) => mark(true) active(eq(s(X), s(Y))) => mark(eq(X, Y)) active(eq(X, Y)) => mark(false) active(inf(X)) => mark(cons(X, inf(s(X)))) active(take(0, X)) => mark(nil) active(take(s(X), cons(Y, Z))) => mark(cons(Y, take(X, Z))) active(length(nil)) => mark(0) active(length(cons(X, Y))) => mark(s(length(Y))) mark(eq(X, Y)) => active(eq(X, Y)) mark(0) => active(0) mark(true) => active(true) mark(s(X)) => active(s(X)) mark(false) => active(false) mark(inf(X)) => active(inf(mark(X))) mark(cons(X, Y)) => active(cons(X, Y)) mark(take(X, Y)) => active(take(mark(X), mark(Y))) mark(nil) => active(nil) mark(length(X)) => active(length(mark(X))) eq(mark(X), Y) => eq(X, Y) eq(X, mark(Y)) => eq(X, Y) eq(active(X), Y) => eq(X, Y) eq(X, active(Y)) => eq(X, Y) s(mark(X)) => s(X) s(active(X)) => s(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_1, R_1, minimal, formative). Thus, the original system is terminating if (P_1, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_1, minimal, formative). We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_1, R_1) are: eq(mark(X), Y) => eq(X, Y) eq(X, mark(Y)) => eq(X, Y) eq(active(X), Y) => eq(X, Y) eq(X, active(Y)) => eq(X, Y) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(eq(s(X), s(Y))) >? mark#(eq(X, Y)) mark#(eq(X, Y)) >? active#(eq(X, Y)) eq(mark(X), Y) >= eq(X, Y) eq(X, mark(Y)) >= eq(X, Y) eq(active(X), Y) >= eq(X, Y) eq(X, active(Y)) >= eq(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: active = \y0.y0 active# = \y0.y0 eq = \y0y1.3y1 mark = \y0.2y0 mark# = \y0.3y0 s = \y0.3 + 3y0 Using this interpretation, the requirements translate to: [[active#(eq(s(_x0), s(_x1)))]] = 9 + 9x1 > 9x1 = [[mark#(eq(_x0, _x1))]] [[mark#(eq(_x0, _x1))]] = 9x1 >= 3x1 = [[active#(eq(_x0, _x1))]] [[eq(mark(_x0), _x1)]] = 3x1 >= 3x1 = [[eq(_x0, _x1)]] [[eq(_x0, mark(_x1))]] = 6x1 >= 3x1 = [[eq(_x0, _x1)]] [[eq(active(_x0), _x1)]] = 3x1 >= 3x1 = [[eq(_x0, _x1)]] [[eq(_x0, active(_x1))]] = 3x1 >= 3x1 = [[eq(_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_1, minimal, formative) by (P_12, R_1, minimal, formative), where P_12 consists of: mark#(eq(X, Y)) =#> active#(eq(X, Y)) Thus, the original system is terminating if (P_12, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_12, R_1, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : This graph has no strongly connected components. By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem. As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. [KusIsoSakBla09] K. Kusakari, Y. Isogai, M. Sakai, and F. Blanqui. Static Dependency Pair Method Based On Strong Computability for Higher-Order Rewrite Systems. In volume 92(10) of IEICE Transactions on Information and Systems. 2007--2015, 2009.