/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 div : [o * o] --> o false : [] --> o geq : [o * o] --> o if : [o * o * o] --> o mark : [o] --> o minus : [o * o] --> o ok : [o] --> o proper : [o] --> o s : [o] --> o top : [o] --> o true : [] --> o active(minus(0, X)) => mark(0) active(minus(s(X), s(Y))) => mark(minus(X, Y)) active(geq(X, 0)) => mark(true) active(geq(0, s(X))) => mark(false) active(geq(s(X), s(Y))) => mark(geq(X, Y)) active(div(0, s(X))) => mark(0) active(div(s(X), s(Y))) => mark(if(geq(X, Y), s(div(minus(X, Y), s(Y))), 0)) active(if(true, X, Y)) => mark(X) active(if(false, X, Y)) => mark(Y) active(s(X)) => s(active(X)) active(div(X, Y)) => div(active(X), Y) active(if(X, Y, Z)) => if(active(X), Y, Z) s(mark(X)) => mark(s(X)) div(mark(X), Y) => mark(div(X, Y)) if(mark(X), Y, Z) => mark(if(X, Y, Z)) proper(minus(X, Y)) => minus(proper(X), proper(Y)) proper(0) => ok(0) proper(s(X)) => s(proper(X)) proper(geq(X, Y)) => geq(proper(X), proper(Y)) proper(true) => ok(true) proper(false) => ok(false) proper(div(X, Y)) => div(proper(X), proper(Y)) proper(if(X, Y, Z)) => if(proper(X), proper(Y), proper(Z)) minus(ok(X), ok(Y)) => ok(minus(X, Y)) s(ok(X)) => ok(s(X)) geq(ok(X), ok(Y)) => ok(geq(X, Y)) div(ok(X), ok(Y)) => ok(div(X, Y)) if(ok(X), ok(Y), ok(Z)) => ok(if(X, Y, Z)) top(mark(X)) => top(proper(X)) top(ok(X)) => top(active(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#(minus(s(X), s(Y))) =#> minus#(X, Y) 1] active#(geq(s(X), s(Y))) =#> geq#(X, Y) 2] active#(div(s(X), s(Y))) =#> if#(geq(X, Y), s(div(minus(X, Y), s(Y))), 0) 3] active#(div(s(X), s(Y))) =#> geq#(X, Y) 4] active#(div(s(X), s(Y))) =#> s#(div(minus(X, Y), s(Y))) 5] active#(div(s(X), s(Y))) =#> div#(minus(X, Y), s(Y)) 6] active#(div(s(X), s(Y))) =#> minus#(X, Y) 7] active#(div(s(X), s(Y))) =#> s#(Y) 8] active#(s(X)) =#> s#(active(X)) 9] active#(s(X)) =#> active#(X) 10] active#(div(X, Y)) =#> div#(active(X), Y) 11] active#(div(X, Y)) =#> active#(X) 12] active#(if(X, Y, Z)) =#> if#(active(X), Y, Z) 13] active#(if(X, Y, Z)) =#> active#(X) 14] s#(mark(X)) =#> s#(X) 15] div#(mark(X), Y) =#> div#(X, Y) 16] if#(mark(X), Y, Z) =#> if#(X, Y, Z) 17] proper#(minus(X, Y)) =#> minus#(proper(X), proper(Y)) 18] proper#(minus(X, Y)) =#> proper#(X) 19] proper#(minus(X, Y)) =#> proper#(Y) 20] proper#(s(X)) =#> s#(proper(X)) 21] proper#(s(X)) =#> proper#(X) 22] proper#(geq(X, Y)) =#> geq#(proper(X), proper(Y)) 23] proper#(geq(X, Y)) =#> proper#(X) 24] proper#(geq(X, Y)) =#> proper#(Y) 25] proper#(div(X, Y)) =#> div#(proper(X), proper(Y)) 26] proper#(div(X, Y)) =#> proper#(X) 27] proper#(div(X, Y)) =#> proper#(Y) 28] proper#(if(X, Y, Z)) =#> if#(proper(X), proper(Y), proper(Z)) 29] proper#(if(X, Y, Z)) =#> proper#(X) 30] proper#(if(X, Y, Z)) =#> proper#(Y) 31] proper#(if(X, Y, Z)) =#> proper#(Z) 32] minus#(ok(X), ok(Y)) =#> minus#(X, Y) 33] s#(ok(X)) =#> s#(X) 34] geq#(ok(X), ok(Y)) =#> geq#(X, Y) 35] div#(ok(X), ok(Y)) =#> div#(X, Y) 36] if#(ok(X), ok(Y), ok(Z)) =#> if#(X, Y, Z) 37] top#(mark(X)) =#> top#(proper(X)) 38] top#(mark(X)) =#> proper#(X) 39] top#(ok(X)) =#> top#(active(X)) 40] top#(ok(X)) =#> active#(X) Rules R_0: active(minus(0, X)) => mark(0) active(minus(s(X), s(Y))) => mark(minus(X, Y)) active(geq(X, 0)) => mark(true) active(geq(0, s(X))) => mark(false) active(geq(s(X), s(Y))) => mark(geq(X, Y)) active(div(0, s(X))) => mark(0) active(div(s(X), s(Y))) => mark(if(geq(X, Y), s(div(minus(X, Y), s(Y))), 0)) active(if(true, X, Y)) => mark(X) active(if(false, X, Y)) => mark(Y) active(s(X)) => s(active(X)) active(div(X, Y)) => div(active(X), Y) active(if(X, Y, Z)) => if(active(X), Y, Z) s(mark(X)) => mark(s(X)) div(mark(X), Y) => mark(div(X, Y)) if(mark(X), Y, Z) => mark(if(X, Y, Z)) proper(minus(X, Y)) => minus(proper(X), proper(Y)) proper(0) => ok(0) proper(s(X)) => s(proper(X)) proper(geq(X, Y)) => geq(proper(X), proper(Y)) proper(true) => ok(true) proper(false) => ok(false) proper(div(X, Y)) => div(proper(X), proper(Y)) proper(if(X, Y, Z)) => if(proper(X), proper(Y), proper(Z)) minus(ok(X), ok(Y)) => ok(minus(X, Y)) s(ok(X)) => ok(s(X)) geq(ok(X), ok(Y)) => ok(geq(X, Y)) div(ok(X), ok(Y)) => ok(div(X, Y)) if(ok(X), ok(Y), ok(Z)) => ok(if(X, Y, Z)) top(mark(X)) => top(proper(X)) top(ok(X)) => top(active(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 : 32 * 1 : 34 * 2 : * 3 : 34 * 4 : 14, 33 * 5 : 35 * 6 : 32 * 7 : 14, 33 * 8 : 14, 33 * 9 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 10 : 15, 35 * 11 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 12 : 16, 36 * 13 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 14 : 14, 33 * 15 : 15, 35 * 16 : 16, 36 * 17 : 32 * 18 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 19 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 20 : 14, 33 * 21 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 22 : 34 * 23 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 24 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 25 : 15, 35 * 26 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 27 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 28 : 16, 36 * 29 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 30 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 31 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 32 : 32 * 33 : 14, 33 * 34 : 34 * 35 : 15, 35 * 36 : 16, 36 * 37 : 37, 38, 39, 40 * 38 : 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 * 39 : 37, 38, 39, 40 * 40 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 This graph has the following strongly connected components: P_1: active#(s(X)) =#> active#(X) active#(div(X, Y)) =#> active#(X) active#(if(X, Y, Z)) =#> active#(X) P_2: s#(mark(X)) =#> s#(X) s#(ok(X)) =#> s#(X) P_3: div#(mark(X), Y) =#> div#(X, Y) div#(ok(X), ok(Y)) =#> div#(X, Y) P_4: if#(mark(X), Y, Z) =#> if#(X, Y, Z) if#(ok(X), ok(Y), ok(Z)) =#> if#(X, Y, Z) P_5: proper#(minus(X, Y)) =#> proper#(X) proper#(minus(X, Y)) =#> proper#(Y) proper#(s(X)) =#> proper#(X) proper#(geq(X, Y)) =#> proper#(X) proper#(geq(X, Y)) =#> proper#(Y) proper#(div(X, Y)) =#> proper#(X) proper#(div(X, Y)) =#> proper#(Y) proper#(if(X, Y, Z)) =#> proper#(X) proper#(if(X, Y, Z)) =#> proper#(Y) proper#(if(X, Y, Z)) =#> proper#(Z) P_6: minus#(ok(X), ok(Y)) =#> minus#(X, Y) P_7: geq#(ok(X), ok(Y)) =#> geq#(X, Y) P_8: top#(mark(X)) =#> top#(proper(X)) top#(ok(X)) =#> top#(active(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). The formative rules of (P_8, R_0) are R_1 ::= active(minus(0, X)) => mark(0) active(minus(s(X), s(Y))) => mark(minus(X, Y)) active(geq(X, 0)) => mark(true) active(geq(0, s(X))) => mark(false) active(geq(s(X), s(Y))) => mark(geq(X, Y)) active(div(0, s(X))) => mark(0) active(div(s(X), s(Y))) => mark(if(geq(X, Y), s(div(minus(X, Y), s(Y))), 0)) active(if(true, X, Y)) => mark(X) active(if(false, X, Y)) => mark(Y) active(s(X)) => s(active(X)) active(div(X, Y)) => div(active(X), Y) active(if(X, Y, Z)) => if(active(X), Y, Z) s(mark(X)) => mark(s(X)) div(mark(X), Y) => mark(div(X, Y)) if(mark(X), Y, Z) => mark(if(X, Y, Z)) proper(minus(X, Y)) => minus(proper(X), proper(Y)) proper(0) => ok(0) proper(s(X)) => s(proper(X)) proper(geq(X, Y)) => geq(proper(X), proper(Y)) proper(true) => ok(true) proper(false) => ok(false) proper(div(X, Y)) => div(proper(X), proper(Y)) proper(if(X, Y, Z)) => if(proper(X), proper(Y), proper(Z)) minus(ok(X), ok(Y)) => ok(minus(X, Y)) s(ok(X)) => ok(s(X)) geq(ok(X), ok(Y)) => ok(geq(X, Y)) div(ok(X), ok(Y)) => ok(div(X, Y)) if(ok(X), ok(Y), ok(Z)) => ok(if(X, Y, Z)) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_8, R_0, minimal, formative) by (P_8, R_1, minimal, formative). 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_1, minimal, formative) is finite. We consider the dependency pair problem (P_8, 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: top#(mark(X)) >? top#(proper(X)) top#(ok(X)) >? top#(active(X)) active(minus(0, X)) >= mark(0) active(minus(s(X), s(Y))) >= mark(minus(X, Y)) active(geq(X, 0)) >= mark(true) active(geq(0, s(X))) >= mark(false) active(geq(s(X), s(Y))) >= mark(geq(X, Y)) active(div(0, s(X))) >= mark(0) active(div(s(X), s(Y))) >= mark(if(geq(X, Y), s(div(minus(X, Y), s(Y))), 0)) active(if(true, X, Y)) >= mark(X) active(if(false, X, Y)) >= mark(Y) active(s(X)) >= s(active(X)) active(div(X, Y)) >= div(active(X), Y) active(if(X, Y, Z)) >= if(active(X), Y, Z) s(mark(X)) >= mark(s(X)) div(mark(X), Y) >= mark(div(X, Y)) if(mark(X), Y, Z) >= mark(if(X, Y, Z)) proper(minus(X, Y)) >= minus(proper(X), proper(Y)) proper(0) >= ok(0) proper(s(X)) >= s(proper(X)) proper(geq(X, Y)) >= geq(proper(X), proper(Y)) proper(true) >= ok(true) proper(false) >= ok(false) proper(div(X, Y)) >= div(proper(X), proper(Y)) proper(if(X, Y, Z)) >= if(proper(X), proper(Y), proper(Z)) minus(ok(X), ok(Y)) >= ok(minus(X, Y)) s(ok(X)) >= ok(s(X)) geq(ok(X), ok(Y)) >= ok(geq(X, Y)) div(ok(X), ok(Y)) >= ok(div(X, Y)) if(ok(X), ok(Y), ok(Z)) >= ok(if(X, Y, Z)) Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.) We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[active(x_1)]] = x_1 [[false]] = _|_ [[geq(x_1, x_2)]] = geq(x_1) [[minus(x_1, x_2)]] = minus(x_1) [[ok(x_1)]] = x_1 [[proper(x_1)]] = x_1 [[true]] = _|_ We choose Lex = {} and Mul = {0, div, geq, if, mark, minus, s, top#}, and the following precedence: div > if > s > 0 > geq = mark = minus = top# Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: top#(mark(X)) > top#(X) top#(X) >= top#(X) minus(0) >= mark(0) minus(s(X)) >= mark(minus(X)) geq(X) >= mark(_|_) geq(0) >= mark(_|_) geq(s(X)) >= mark(geq(X)) div(0, s(X)) >= mark(0) div(s(X), s(Y)) >= mark(if(geq(X), s(div(minus(X), s(Y))), 0)) if(_|_, X, Y) >= mark(X) if(_|_, X, Y) >= mark(Y) s(X) >= s(X) div(X, Y) >= div(X, Y) if(X, Y, Z) >= if(X, Y, Z) s(mark(X)) >= mark(s(X)) div(mark(X), Y) >= mark(div(X, Y)) if(mark(X), Y, Z) >= mark(if(X, Y, Z)) minus(X) >= minus(X) 0 >= 0 s(X) >= s(X) geq(X) >= geq(X) _|_ >= _|_ _|_ >= _|_ div(X, Y) >= div(X, Y) if(X, Y, Z) >= if(X, Y, Z) minus(X) >= minus(X) s(X) >= s(X) geq(X) >= geq(X) div(X, Y) >= div(X, Y) if(X, Y, Z) >= if(X, Y, Z) With these choices, we have: 1] top#(mark(X)) > top#(X) because [2], by definition 2] top#*(mark(X)) >= top#(X) because [3], by (Select) 3] mark(X) >= top#(X) because mark = top#, mark in Mul and [4], by (Fun) 4] X >= X by (Meta) 5] top#(X) >= top#(X) because top# in Mul and [6], by (Fun) 6] X >= X by (Meta) 7] minus(0) >= mark(0) because minus = mark, minus in Mul and [8], by (Fun) 8] 0 >= 0 by (Fun) 9] minus(s(X)) >= mark(minus(X)) because minus = mark, minus in Mul and [10], by (Fun) 10] s(X) >= minus(X) because [11], by (Star) 11] s*(X) >= minus(X) because s > minus and [12], by (Copy) 12] s*(X) >= X because [6], by (Select) 13] geq(X) >= mark(_|_) because geq = mark, geq in Mul and [14], by (Fun) 14] X >= _|_ by (Bot) 15] geq(0) >= mark(_|_) because [16], by (Star) 16] geq*(0) >= mark(_|_) because [17], by (Select) 17] 0 >= mark(_|_) because [18], by (Star) 18] 0* >= mark(_|_) because 0 > mark and [19], by (Copy) 19] 0* >= _|_ by (Bot) 20] geq(s(X)) >= mark(geq(X)) because geq = mark, geq in Mul and [21], by (Fun) 21] s(X) >= geq(X) because [22], by (Star) 22] s*(X) >= geq(X) because s > geq and [12], by (Copy) 23] div(0, s(X)) >= mark(0) because [24], by (Star) 24] div*(0, s(X)) >= mark(0) because div > mark and [25], by (Copy) 25] div*(0, s(X)) >= 0 because div > 0, by (Copy) 26] div(s(X), s(Y)) >= mark(if(geq(X), s(div(minus(X), s(Y))), 0)) because [27], by (Star) 27] div*(s(X), s(Y)) >= mark(if(geq(X), s(div(minus(X), s(Y))), 0)) because div > mark and [28], by (Copy) 28] div*(s(X), s(Y)) >= if(geq(X), s(div(minus(X), s(Y))), 0) because div > if, [29], [30] and [36], by (Copy) 29] div*(s(X), s(Y)) >= geq(X) because [21], by (Select) 30] div*(s(X), s(Y)) >= s(div(minus(X), s(Y))) because div > s and [31], by (Copy) 31] div*(s(X), s(Y)) >= div(minus(X), s(Y)) because div in Mul, [32] and [34], by (Stat) 32] s(X) > minus(X) because [33], by definition 33] s*(X) >= minus(X) because s > minus and [12], by (Copy) 34] s(Y) >= s(Y) because s in Mul and [35], by (Fun) 35] Y >= Y by (Meta) 36] div*(s(X), s(Y)) >= 0 because [37], by (Select) 37] s(X) >= 0 because [38], by (Star) 38] s*(X) >= 0 because s > 0, by (Copy) 39] if(_|_, X, Y) >= mark(X) because [40], by (Star) 40] if*(_|_, X, Y) >= mark(X) because if > mark and [41], by (Copy) 41] if*(_|_, X, Y) >= X because [6], by (Select) 42] if(_|_, X, Y) >= mark(Y) because [43], by (Star) 43] if*(_|_, X, Y) >= mark(Y) because if > mark and [44], by (Copy) 44] if*(_|_, X, Y) >= Y because [35], by (Select) 45] s(X) >= s(X) because s in Mul and [46], by (Fun) 46] X >= X by (Meta) 47] div(X, Y) >= div(X, Y) because div in Mul, [48] and [49], by (Fun) 48] X >= X by (Meta) 49] Y >= Y by (Meta) 50] if(X, Y, Z) >= if(X, Y, Z) because if in Mul, [48], [49] and [51], by (Fun) 51] Z >= Z by (Meta) 52] s(mark(X)) >= mark(s(X)) because [53], by (Star) 53] s*(mark(X)) >= mark(s(X)) because s > mark and [54], by (Copy) 54] s*(mark(X)) >= s(X) because s in Mul and [55], by (Stat) 55] mark(X) > X because [56], by definition 56] mark*(X) >= X because [46], by (Select) 57] div(mark(X), Y) >= mark(div(X, Y)) because [58], by (Star) 58] div*(mark(X), Y) >= mark(div(X, Y)) because div > mark and [59], by (Copy) 59] div*(mark(X), Y) >= div(X, Y) because div in Mul, [60] and [49], by (Stat) 60] mark(X) > X because [61], by definition 61] mark*(X) >= X because [48], by (Select) 62] if(mark(X), Y, Z) >= mark(if(X, Y, Z)) because [63], by (Star) 63] if*(mark(X), Y, Z) >= mark(if(X, Y, Z)) because if > mark and [64], by (Copy) 64] if*(mark(X), Y, Z) >= if(X, Y, Z) because if in Mul, [60], [49] and [51], by (Stat) 65] minus(X) >= minus(X) because minus in Mul and [66], by (Fun) 66] X >= X by (Meta) 67] 0 >= 0 by (Fun) 68] s(X) >= s(X) because s in Mul and [4], by (Fun) 69] geq(X) >= geq(X) because geq in Mul and [66], by (Fun) 70] _|_ >= _|_ by (Bot) 71] _|_ >= _|_ by (Bot) 72] div(X, Y) >= div(X, Y) because div in Mul, [66] and [73], by (Fun) 73] Y >= Y by (Meta) 74] if(X, Y, Z) >= if(X, Y, Z) because if in Mul, [66], [73] and [75], by (Fun) 75] Z >= Z by (Meta) 76] minus(X) >= minus(X) because minus in Mul and [77], by (Fun) 77] X >= X by (Meta) 78] s(X) >= s(X) because s in Mul and [6], by (Fun) 79] geq(X) >= geq(X) because geq in Mul and [77], by (Fun) 80] div(X, Y) >= div(X, Y) because div in Mul, [77] and [81], by (Fun) 81] Y >= Y by (Meta) 82] if(X, Y, Z) >= if(X, Y, Z) because if in Mul, [77], [81] and [83], by (Fun) 83] Z >= Z by (Meta) By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_8, R_1, minimal, formative) by (P_9, R_1, minimal, formative), where P_9 consists of: top#(ok(X)) =#> top#(active(X)) 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_9, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_9, R_1, minimal, formative). The formative rules of (P_9, R_1) are R_2 ::= active(s(X)) => s(active(X)) active(div(X, Y)) => div(active(X), Y) active(if(X, Y, Z)) => if(active(X), Y, Z) proper(minus(X, Y)) => minus(proper(X), proper(Y)) proper(0) => ok(0) proper(s(X)) => s(proper(X)) proper(geq(X, Y)) => geq(proper(X), proper(Y)) proper(true) => ok(true) proper(false) => ok(false) proper(div(X, Y)) => div(proper(X), proper(Y)) proper(if(X, Y, Z)) => if(proper(X), proper(Y), proper(Z)) minus(ok(X), ok(Y)) => ok(minus(X, Y)) s(ok(X)) => ok(s(X)) geq(ok(X), ok(Y)) => ok(geq(X, Y)) div(ok(X), ok(Y)) => ok(div(X, Y)) if(ok(X), ok(Y), ok(Z)) => ok(if(X, Y, Z)) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_9, R_1, minimal, formative) by (P_9, R_2, minimal, formative). 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_9, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_9, R_2, minimal, formative). We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_9, R_2) are: active(s(X)) => s(active(X)) active(div(X, Y)) => div(active(X), Y) active(if(X, Y, Z)) => if(active(X), Y, Z) s(ok(X)) => ok(s(X)) div(ok(X), ok(Y)) => ok(div(X, Y)) if(ok(X), ok(Y), ok(Z)) => ok(if(X, Y, Z)) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: top#(ok(X)) >? top#(active(X)) active(s(X)) >= s(active(X)) active(div(X, Y)) >= div(active(X), Y) active(if(X, Y, Z)) >= if(active(X), Y, Z) s(ok(X)) >= ok(s(X)) div(ok(X), ok(Y)) >= ok(div(X, Y)) if(ok(X), ok(Y), ok(Z)) >= ok(if(X, Y, Z)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: active = \y0.1 div = \y0y1.y0 if = \y0y1y2.y0 ok = \y0.3 s = \y0.y0 top# = \y0.3y0 Using this interpretation, the requirements translate to: [[top#(ok(_x0))]] = 9 > 3 = [[top#(active(_x0))]] [[active(s(_x0))]] = 1 >= 1 = [[s(active(_x0))]] [[active(div(_x0, _x1))]] = 1 >= 1 = [[div(active(_x0), _x1)]] [[active(if(_x0, _x1, _x2))]] = 1 >= 1 = [[if(active(_x0), _x1, _x2)]] [[s(ok(_x0))]] = 3 >= 3 = [[ok(s(_x0))]] [[div(ok(_x0), ok(_x1))]] = 3 >= 3 = [[ok(div(_x0, _x1))]] [[if(ok(_x0), ok(_x1), ok(_x2))]] = 3 >= 3 = [[ok(if(_x0, _x1, _x2))]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_9, R_2) by ({}, R_2). 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(geq#) = 1 Thus, we can orient the dependency pairs as follows: nu(geq#(ok(X), ok(Y))) = ok(X) |> X = nu(geq#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_7, 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(minus#) = 1 Thus, we can orient the dependency pairs as follows: nu(minus#(ok(X), ok(Y))) = ok(X) |> X = nu(minus#(X, Y)) 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(proper#) = 1 Thus, we can orient the dependency pairs as follows: nu(proper#(minus(X, Y))) = minus(X, Y) |> X = nu(proper#(X)) nu(proper#(minus(X, Y))) = minus(X, Y) |> Y = nu(proper#(Y)) nu(proper#(s(X))) = s(X) |> X = nu(proper#(X)) nu(proper#(geq(X, Y))) = geq(X, Y) |> X = nu(proper#(X)) nu(proper#(geq(X, Y))) = geq(X, Y) |> Y = nu(proper#(Y)) nu(proper#(div(X, Y))) = div(X, Y) |> X = nu(proper#(X)) nu(proper#(div(X, Y))) = div(X, Y) |> Y = nu(proper#(Y)) nu(proper#(if(X, Y, Z))) = if(X, Y, Z) |> X = nu(proper#(X)) nu(proper#(if(X, Y, Z))) = if(X, Y, Z) |> Y = nu(proper#(Y)) nu(proper#(if(X, Y, Z))) = if(X, Y, Z) |> Z = nu(proper#(Z)) 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(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#(ok(X), ok(Y), ok(Z))) = ok(X) |> X = nu(if#(X, Y, Z)) 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(div#) = 1 Thus, we can orient the dependency pairs as follows: nu(div#(mark(X), Y)) = mark(X) |> X = nu(div#(X, Y)) nu(div#(ok(X), ok(Y))) = ok(X) |> X = nu(div#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_3, 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(s#) = 1 Thus, we can orient the dependency pairs as follows: nu(s#(mark(X))) = mark(X) |> X = nu(s#(X)) nu(s#(ok(X))) = ok(X) |> X = nu(s#(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 apply the subterm criterion with the following projection function: nu(active#) = 1 Thus, we can orient the dependency pairs as follows: nu(active#(s(X))) = s(X) |> X = nu(active#(X)) nu(active#(div(X, Y))) = div(X, Y) |> X = nu(active#(X)) nu(active#(if(X, Y, Z))) = if(X, Y, Z) |> X = nu(active#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_1, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. [KusIsoSakBla09] K. Kusakari, Y. Isogai, M. Sakai, and F. Blanqui. Static Dependency Pair Method Based On Strong Computability for Higher-Order Rewrite Systems. In volume 92(10) of IEICE Transactions on Information and Systems. 2007--2015, 2009.