/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 and : [o * o] --> o cons : [o * o] --> o false : [] --> o first : [o * o] --> o from : [o] --> o if : [o * o * o] --> o mark : [o] --> o nil : [] --> o s : [o] --> o true : [] --> o active(and(true, X)) => mark(X) active(and(false, X)) => mark(false) active(if(true, X, Y)) => mark(X) active(if(false, X, Y)) => mark(Y) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(from(X)) => mark(cons(X, from(s(X)))) mark(and(X, Y)) => active(and(mark(X), Y)) mark(true) => active(true) mark(false) => active(false) mark(if(X, Y, Z)) => active(if(mark(X), Y, Z)) mark(add(X, Y)) => active(add(mark(X), Y)) mark(0) => active(0) mark(s(X)) => active(s(X)) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(cons(X, Y)) => active(cons(X, Y)) mark(from(X)) => active(from(X)) and(mark(X), Y) => and(X, Y) and(X, mark(Y)) => and(X, Y) and(active(X), Y) => and(X, Y) and(X, active(Y)) => and(X, Y) if(mark(X), Y, Z) => if(X, Y, Z) if(X, mark(Y), Z) => if(X, Y, Z) if(X, Y, mark(Z)) => if(X, Y, Z) if(active(X), Y, Z) => if(X, Y, Z) if(X, active(Y), Z) => if(X, Y, Z) if(X, Y, active(Z)) => if(X, Y, Z) 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) s(mark(X)) => s(X) s(active(X)) => s(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) 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) from(mark(X)) => from(X) from(active(X)) => from(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#(and(true, X)) =#> mark#(X) 1] active#(and(false, X)) =#> mark#(false) 2] active#(if(true, X, Y)) =#> mark#(X) 3] active#(if(false, X, Y)) =#> mark#(Y) 4] active#(add(0, X)) =#> mark#(X) 5] active#(add(s(X), Y)) =#> mark#(s(add(X, Y))) 6] active#(add(s(X), Y)) =#> s#(add(X, Y)) 7] active#(add(s(X), Y)) =#> add#(X, Y) 8] active#(first(0, X)) =#> mark#(nil) 9] active#(first(s(X), cons(Y, Z))) =#> mark#(cons(Y, first(X, Z))) 10] active#(first(s(X), cons(Y, Z))) =#> cons#(Y, first(X, Z)) 11] active#(first(s(X), cons(Y, Z))) =#> first#(X, Z) 12] active#(from(X)) =#> mark#(cons(X, from(s(X)))) 13] active#(from(X)) =#> cons#(X, from(s(X))) 14] active#(from(X)) =#> from#(s(X)) 15] active#(from(X)) =#> s#(X) 16] mark#(and(X, Y)) =#> active#(and(mark(X), Y)) 17] mark#(and(X, Y)) =#> and#(mark(X), Y) 18] mark#(and(X, Y)) =#> mark#(X) 19] mark#(true) =#> active#(true) 20] mark#(false) =#> active#(false) 21] mark#(if(X, Y, Z)) =#> active#(if(mark(X), Y, Z)) 22] mark#(if(X, Y, Z)) =#> if#(mark(X), Y, Z) 23] mark#(if(X, Y, Z)) =#> mark#(X) 24] mark#(add(X, Y)) =#> active#(add(mark(X), Y)) 25] mark#(add(X, Y)) =#> add#(mark(X), Y) 26] mark#(add(X, Y)) =#> mark#(X) 27] mark#(0) =#> active#(0) 28] mark#(s(X)) =#> active#(s(X)) 29] mark#(s(X)) =#> s#(X) 30] mark#(first(X, Y)) =#> active#(first(mark(X), mark(Y))) 31] mark#(first(X, Y)) =#> first#(mark(X), mark(Y)) 32] mark#(first(X, Y)) =#> mark#(X) 33] mark#(first(X, Y)) =#> mark#(Y) 34] mark#(nil) =#> active#(nil) 35] mark#(cons(X, Y)) =#> active#(cons(X, Y)) 36] mark#(cons(X, Y)) =#> cons#(X, Y) 37] mark#(from(X)) =#> active#(from(X)) 38] mark#(from(X)) =#> from#(X) 39] and#(mark(X), Y) =#> and#(X, Y) 40] and#(X, mark(Y)) =#> and#(X, Y) 41] and#(active(X), Y) =#> and#(X, Y) 42] and#(X, active(Y)) =#> and#(X, Y) 43] if#(mark(X), Y, Z) =#> if#(X, Y, Z) 44] if#(X, mark(Y), Z) =#> if#(X, Y, Z) 45] if#(X, Y, mark(Z)) =#> if#(X, Y, Z) 46] if#(active(X), Y, Z) =#> if#(X, Y, Z) 47] if#(X, active(Y), Z) =#> if#(X, Y, Z) 48] if#(X, Y, active(Z)) =#> if#(X, Y, Z) 49] add#(mark(X), Y) =#> add#(X, Y) 50] add#(X, mark(Y)) =#> add#(X, Y) 51] add#(active(X), Y) =#> add#(X, Y) 52] add#(X, active(Y)) =#> add#(X, Y) 53] s#(mark(X)) =#> s#(X) 54] s#(active(X)) =#> s#(X) 55] first#(mark(X), Y) =#> first#(X, Y) 56] first#(X, mark(Y)) =#> first#(X, Y) 57] first#(active(X), Y) =#> first#(X, Y) 58] first#(X, active(Y)) =#> first#(X, Y) 59] cons#(mark(X), Y) =#> cons#(X, Y) 60] cons#(X, mark(Y)) =#> cons#(X, Y) 61] cons#(active(X), Y) =#> cons#(X, Y) 62] cons#(X, active(Y)) =#> cons#(X, Y) 63] from#(mark(X)) =#> from#(X) 64] from#(active(X)) =#> from#(X) Rules R_0: active(and(true, X)) => mark(X) active(and(false, X)) => mark(false) active(if(true, X, Y)) => mark(X) active(if(false, X, Y)) => mark(Y) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(from(X)) => mark(cons(X, from(s(X)))) mark(and(X, Y)) => active(and(mark(X), Y)) mark(true) => active(true) mark(false) => active(false) mark(if(X, Y, Z)) => active(if(mark(X), Y, Z)) mark(add(X, Y)) => active(add(mark(X), Y)) mark(0) => active(0) mark(s(X)) => active(s(X)) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(cons(X, Y)) => active(cons(X, Y)) mark(from(X)) => active(from(X)) and(mark(X), Y) => and(X, Y) and(X, mark(Y)) => and(X, Y) and(active(X), Y) => and(X, Y) and(X, active(Y)) => and(X, Y) if(mark(X), Y, Z) => if(X, Y, Z) if(X, mark(Y), Z) => if(X, Y, Z) if(X, Y, mark(Z)) => if(X, Y, Z) if(active(X), Y, Z) => if(X, Y, Z) if(X, active(Y), Z) => if(X, Y, Z) if(X, Y, active(Z)) => if(X, Y, Z) 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) s(mark(X)) => s(X) s(active(X)) => s(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) 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) from(mark(X)) => from(X) from(active(X)) => from(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 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 * 1 : 20 * 2 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 * 3 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 * 4 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 * 5 : 28, 29 * 6 : * 7 : 49, 50, 51, 52 * 8 : 34 * 9 : 35, 36 * 10 : 59, 61 * 11 : 55, 56, 57, 58 * 12 : 35, 36 * 13 : 59, 61 * 14 : * 15 : 53, 54 * 16 : 0, 1 * 17 : 39, 40, 41, 42 * 18 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 * 19 : * 20 : * 21 : 2, 3 * 22 : 43, 44, 45, 46, 47, 48 * 23 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 * 24 : 4, 5, 6, 7 * 25 : 49, 50, 51, 52 * 26 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 * 27 : * 28 : * 29 : 53, 54 * 30 : 8, 9, 10, 11 * 31 : 55, 56, 57, 58 * 32 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 * 33 : 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 * 34 : * 35 : * 36 : 59, 60, 61, 62 * 37 : 12, 13, 14, 15 * 38 : 63, 64 * 39 : 39, 40, 41, 42 * 40 : 39, 40, 41, 42 * 41 : 39, 40, 41, 42 * 42 : 39, 40, 41, 42 * 43 : 43, 44, 45, 46, 47, 48 * 44 : 43, 44, 45, 46, 47, 48 * 45 : 43, 44, 45, 46, 47, 48 * 46 : 43, 44, 45, 46, 47, 48 * 47 : 43, 44, 45, 46, 47, 48 * 48 : 43, 44, 45, 46, 47, 48 * 49 : 49, 50, 51, 52 * 50 : 49, 50, 51, 52 * 51 : 49, 50, 51, 52 * 52 : 49, 50, 51, 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, 61, 62 * 60 : 59, 60, 61, 62 * 61 : 59, 60, 61, 62 * 62 : 59, 60, 61, 62 * 63 : 63, 64 * 64 : 63, 64 This graph has the following strongly connected components: P_1: active#(and(true, X)) =#> mark#(X) active#(if(true, X, Y)) =#> mark#(X) active#(if(false, X, Y)) =#> mark#(Y) active#(add(0, X)) =#> mark#(X) mark#(and(X, Y)) =#> active#(and(mark(X), Y)) mark#(and(X, Y)) =#> mark#(X) mark#(if(X, Y, Z)) =#> active#(if(mark(X), Y, Z)) mark#(if(X, Y, Z)) =#> mark#(X) mark#(add(X, Y)) =#> active#(add(mark(X), Y)) mark#(add(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(X) mark#(first(X, Y)) =#> mark#(Y) P_2: and#(mark(X), Y) =#> and#(X, Y) and#(X, mark(Y)) =#> and#(X, Y) and#(active(X), Y) =#> and#(X, Y) and#(X, active(Y)) =#> and#(X, Y) P_3: if#(mark(X), Y, Z) =#> if#(X, Y, Z) if#(X, mark(Y), Z) =#> if#(X, Y, Z) if#(X, Y, mark(Z)) =#> if#(X, Y, Z) if#(active(X), Y, Z) =#> if#(X, Y, Z) if#(X, active(Y), Z) =#> if#(X, Y, Z) if#(X, Y, active(Z)) =#> if#(X, Y, Z) P_4: 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_5: s#(mark(X)) =#> s#(X) s#(active(X)) =#> s#(X) P_6: first#(mark(X), Y) =#> first#(X, Y) first#(X, mark(Y)) =#> first#(X, Y) first#(active(X), Y) =#> first#(X, Y) first#(X, active(Y)) =#> first#(X, Y) P_7: 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_8: from#(mark(X)) =#> from#(X) from#(active(X)) =#> from#(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(from#) = 1 Thus, we can orient the dependency pairs as follows: nu(from#(mark(X))) = mark(X) |> X = nu(from#(X)) nu(from#(active(X))) = active(X) |> X = nu(from#(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(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_7, R_0, minimal, f) by (P_9, R_0, minimal, f), where P_9 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), (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(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_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(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_6, 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) 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) 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(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_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(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_4, 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) 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) 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(if#) = 1 Thus, we can orient the dependency pairs as follows: nu(if#(mark(X), Y, Z)) = mark(X) |> X = nu(if#(X, Y, Z)) nu(if#(X, mark(Y), Z)) = X = X = nu(if#(X, Y, Z)) nu(if#(X, Y, mark(Z))) = X = X = nu(if#(X, Y, Z)) nu(if#(active(X), Y, Z)) = active(X) |> X = nu(if#(X, Y, Z)) nu(if#(X, active(Y), Z)) = X = X = nu(if#(X, Y, Z)) nu(if#(X, Y, active(Z))) = X = X = nu(if#(X, Y, Z)) 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: if#(X, mark(Y), Z) =#> if#(X, Y, Z) if#(X, Y, mark(Z)) =#> if#(X, Y, Z) if#(X, active(Y), Z) =#> if#(X, Y, Z) if#(X, Y, active(Z)) =#> if#(X, Y, Z) 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(if#) = 2 Thus, we can orient the dependency pairs as follows: nu(if#(X, mark(Y), Z)) = mark(Y) |> Y = nu(if#(X, Y, Z)) nu(if#(X, Y, mark(Z))) = Y = Y = nu(if#(X, Y, Z)) nu(if#(X, active(Y), Z)) = active(Y) |> Y = nu(if#(X, Y, Z)) nu(if#(X, Y, active(Z))) = Y = Y = nu(if#(X, Y, Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_12, R_0, minimal, f) by (P_13, R_0, minimal, f), where P_13 contains: if#(X, Y, mark(Z)) =#> if#(X, Y, Z) if#(X, Y, active(Z)) =#> if#(X, Y, Z) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative) and (P_13, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_13, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(if#) = 3 Thus, we can orient the dependency pairs as follows: nu(if#(X, Y, mark(Z))) = mark(Z) |> Z = nu(if#(X, Y, Z)) nu(if#(X, Y, active(Z))) = active(Z) |> Z = nu(if#(X, Y, Z)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_13, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(and#) = 1 Thus, we can orient the dependency pairs as follows: nu(and#(mark(X), Y)) = mark(X) |> X = nu(and#(X, Y)) nu(and#(X, mark(Y))) = X = X = nu(and#(X, Y)) nu(and#(active(X), Y)) = active(X) |> X = nu(and#(X, Y)) nu(and#(X, active(Y))) = X = X = nu(and#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_2, R_0, minimal, f) by (P_14, R_0, minimal, f), where P_14 contains: and#(X, mark(Y)) =#> and#(X, Y) and#(X, active(Y)) =#> and#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_14, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_14, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(and#) = 2 Thus, we can orient the dependency pairs as follows: nu(and#(X, mark(Y))) = mark(Y) |> Y = nu(and#(X, Y)) nu(and#(X, active(Y))) = active(Y) |> Y = nu(and#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_14, 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(and(true, X)) => mark(X) active(and(false, X)) => mark(false) active(if(true, X, Y)) => mark(X) active(if(false, X, Y)) => mark(Y) active(add(0, X)) => mark(X) active(add(s(X), Y)) => mark(s(add(X, Y))) active(first(0, X)) => mark(nil) active(first(s(X), cons(Y, Z))) => mark(cons(Y, first(X, Z))) active(from(X)) => mark(cons(X, from(s(X)))) mark(and(X, Y)) => active(and(mark(X), Y)) mark(true) => active(true) mark(false) => active(false) mark(if(X, Y, Z)) => active(if(mark(X), Y, Z)) mark(add(X, Y)) => active(add(mark(X), Y)) mark(0) => active(0) mark(s(X)) => active(s(X)) mark(first(X, Y)) => active(first(mark(X), mark(Y))) mark(nil) => active(nil) mark(cons(X, Y)) => active(cons(X, Y)) mark(from(X)) => active(from(X)) and(mark(X), Y) => and(X, Y) and(X, mark(Y)) => and(X, Y) and(active(X), Y) => and(X, Y) and(X, active(Y)) => and(X, Y) if(mark(X), Y, Z) => if(X, Y, Z) if(X, mark(Y), Z) => if(X, Y, Z) if(X, Y, mark(Z)) => if(X, Y, Z) if(active(X), Y, Z) => if(X, Y, Z) if(X, active(Y), Z) => if(X, Y, Z) if(X, Y, active(Z)) => if(X, Y, Z) 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) 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_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 [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(and(true, X)) >? mark#(X) active#(if(true, X, Y)) >? mark#(X) active#(if(false, X, Y)) >? mark#(Y) active#(add(0, X)) >? mark#(X) mark#(and(X, Y)) >? active#(and(mark(X), Y)) mark#(and(X, Y)) >? mark#(X) mark#(if(X, Y, Z)) >? active#(if(mark(X), Y, Z)) mark#(if(X, Y, Z)) >? mark#(X) mark#(add(X, Y)) >? active#(add(mark(X), Y)) mark#(add(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(X) mark#(first(X, Y)) >? mark#(Y) active(and(true, X)) >= mark(X) active(and(false, X)) >= mark(false) active(if(true, X, Y)) >= mark(X) active(if(false, X, Y)) >= mark(Y) active(add(0, X)) >= mark(X) active(add(s(X), Y)) >= mark(s(add(X, Y))) active(first(0, X)) >= mark(nil) active(first(s(X), cons(Y, Z))) >= mark(cons(Y, first(X, Z))) active(from(X)) >= mark(cons(X, from(s(X)))) mark(and(X, Y)) >= active(and(mark(X), Y)) mark(true) >= active(true) mark(false) >= active(false) mark(if(X, Y, Z)) >= active(if(mark(X), Y, Z)) mark(add(X, Y)) >= active(add(mark(X), Y)) mark(0) >= active(0) mark(s(X)) >= active(s(X)) mark(first(X, Y)) >= active(first(mark(X), mark(Y))) mark(nil) >= active(nil) mark(cons(X, Y)) >= active(cons(X, Y)) mark(from(X)) >= active(from(X)) and(mark(X), Y) >= and(X, Y) and(X, mark(Y)) >= and(X, Y) and(active(X), Y) >= and(X, Y) and(X, active(Y)) >= and(X, Y) if(mark(X), Y, Z) >= if(X, Y, Z) if(X, mark(Y), Z) >= if(X, Y, Z) if(X, Y, mark(Z)) >= if(X, Y, Z) if(active(X), Y, Z) >= if(X, Y, Z) if(X, active(Y), Z) >= if(X, Y, Z) if(X, Y, active(Z)) >= if(X, Y, Z) 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) 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.1 + y0 + y1 and = \y0y1.2 + y1 + 2y0 cons = \y0y1.0 false = 0 first = \y0y1.y0 + 2y1 from = \y0.0 if = \y0y1y2.1 + y1 + y2 + 2y0 mark = \y0.y0 mark# = \y0.1 + y0 nil = 0 s = \y0.0 true = 0 Using this interpretation, the requirements translate to: [[active#(and(true, _x0))]] = 2 + x0 > 1 + x0 = [[mark#(_x0)]] [[active#(if(true, _x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 = [[mark#(_x0)]] [[active#(if(false, _x0, _x1))]] = 1 + x0 + x1 >= 1 + x1 = [[mark#(_x1)]] [[active#(add(0, _x0))]] = 1 + x0 >= 1 + x0 = [[mark#(_x0)]] [[mark#(and(_x0, _x1))]] = 3 + x1 + 2x0 > 2 + x1 + 2x0 = [[active#(and(mark(_x0), _x1))]] [[mark#(and(_x0, _x1))]] = 3 + x1 + 2x0 > 1 + x0 = [[mark#(_x0)]] [[mark#(if(_x0, _x1, _x2))]] = 2 + x1 + x2 + 2x0 > 1 + x1 + x2 + 2x0 = [[active#(if(mark(_x0), _x1, _x2))]] [[mark#(if(_x0, _x1, _x2))]] = 2 + x1 + x2 + 2x0 > 1 + x0 = [[mark#(_x0)]] [[mark#(add(_x0, _x1))]] = 2 + x0 + x1 > 1 + x0 + x1 = [[active#(add(mark(_x0), _x1))]] [[mark#(add(_x0, _x1))]] = 2 + x0 + x1 > 1 + x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 = [[mark#(_x0)]] [[mark#(first(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x1 = [[mark#(_x1)]] [[active(and(true, _x0))]] = 2 + x0 >= x0 = [[mark(_x0)]] [[active(and(false, _x0))]] = 2 + x0 >= 0 = [[mark(false)]] [[active(if(true, _x0, _x1))]] = 1 + x0 + x1 >= x0 = [[mark(_x0)]] [[active(if(false, _x0, _x1))]] = 1 + x0 + x1 >= x1 = [[mark(_x1)]] [[active(add(0, _x0))]] = 1 + x0 >= x0 = [[mark(_x0)]] [[active(add(s(_x0), _x1))]] = 1 + x1 >= 0 = [[mark(s(add(_x0, _x1)))]] [[active(first(0, _x0))]] = 2x0 >= 0 = [[mark(nil)]] [[active(first(s(_x0), cons(_x1, _x2)))]] = 0 >= 0 = [[mark(cons(_x1, first(_x0, _x2)))]] [[active(from(_x0))]] = 0 >= 0 = [[mark(cons(_x0, from(s(_x0))))]] [[mark(and(_x0, _x1))]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[active(and(mark(_x0), _x1))]] [[mark(true)]] = 0 >= 0 = [[active(true)]] [[mark(false)]] = 0 >= 0 = [[active(false)]] [[mark(if(_x0, _x1, _x2))]] = 1 + x1 + x2 + 2x0 >= 1 + x1 + x2 + 2x0 = [[active(if(mark(_x0), _x1, _x2))]] [[mark(add(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[active(add(mark(_x0), _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(s(_x0))]] = 0 >= 0 = [[active(s(_x0))]] [[mark(first(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(first(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(cons(_x0, _x1))]] = 0 >= 0 = [[active(cons(_x0, _x1))]] [[mark(from(_x0))]] = 0 >= 0 = [[active(from(_x0))]] [[and(mark(_x0), _x1)]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[and(_x0, _x1)]] [[if(mark(_x0), _x1, _x2)]] = 1 + x1 + x2 + 2x0 >= 1 + x1 + x2 + 2x0 = [[if(_x0, _x1, _x2)]] [[if(_x0, mark(_x1), _x2)]] = 1 + x1 + x2 + 2x0 >= 1 + x1 + x2 + 2x0 = [[if(_x0, _x1, _x2)]] [[if(_x0, _x1, mark(_x2))]] = 1 + x1 + x2 + 2x0 >= 1 + x1 + x2 + 2x0 = [[if(_x0, _x1, _x2)]] [[if(active(_x0), _x1, _x2)]] = 1 + x1 + x2 + 2x0 >= 1 + x1 + x2 + 2x0 = [[if(_x0, _x1, _x2)]] [[if(_x0, active(_x1), _x2)]] = 1 + x1 + x2 + 2x0 >= 1 + x1 + x2 + 2x0 = [[if(_x0, _x1, _x2)]] [[if(_x0, _x1, active(_x2))]] = 1 + x1 + x2 + 2x0 >= 1 + x1 + x2 + 2x0 = [[if(_x0, _x1, _x2)]] [[add(mark(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[add(_x0, _x1)]] [[add(_x0, mark(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[add(_x0, _x1)]] [[add(active(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[add(_x0, _x1)]] [[add(_x0, active(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[add(_x0, _x1)]] [[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_1, minimal, formative) by (P_15, R_1, minimal, formative), where P_15 consists of: active#(if(true, X, Y)) =#> mark#(X) active#(if(false, X, Y)) =#> mark#(Y) active#(add(0, 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_1, minimal, formative) is finite. We consider the dependency pair problem (P_15, 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 : 3, 4 * 1 : 3, 4 * 2 : 3, 4 * 3 : 3, 4 * 4 : 3, 4 This graph has the following strongly connected components: P_16: 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_1, m, f) by (P_16, R_1, m, f). 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 apply the subterm criterion with the following projection function: nu(mark#) = 1 Thus, we can orient the dependency pairs as follows: 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_16, R_1, minimal, f) by ({}, R_1, 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.