/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 double : [o] --> o minus : [o * o] --> o plus : [o * o] --> o s : [o] --> o minus(X, 0) => X minus(s(X), s(Y)) => minus(X, Y) double(0) => 0 double(s(X)) => s(s(double(X))) plus(0, X) => X plus(s(X), Y) => s(plus(X, Y)) plus(s(X), Y) => plus(X, s(Y)) plus(s(X), Y) => s(plus(minus(X, Y), double(Y))) plus(s(plus(X, Y)), Z) => s(plus(plus(X, Y), Z)) 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] minus#(s(X), s(Y)) =#> minus#(X, Y) 1] double#(s(X)) =#> double#(X) 2] plus#(s(X), Y) =#> plus#(X, Y) 3] plus#(s(X), Y) =#> plus#(X, s(Y)) 4] plus#(s(X), Y) =#> plus#(minus(X, Y), double(Y)) 5] plus#(s(X), Y) =#> minus#(X, Y) 6] plus#(s(X), Y) =#> double#(Y) 7] plus#(s(plus(X, Y)), Z) =#> plus#(plus(X, Y), Z) 8] plus#(s(plus(X, Y)), Z) =#> plus#(X, Y) Rules R_0: minus(X, 0) => X minus(s(X), s(Y)) => minus(X, Y) double(0) => 0 double(s(X)) => s(s(double(X))) plus(0, X) => X plus(s(X), Y) => s(plus(X, Y)) plus(s(X), Y) => plus(X, s(Y)) plus(s(X), Y) => s(plus(minus(X, Y), double(Y))) plus(s(plus(X, Y)), Z) => s(plus(plus(X, Y), Z)) 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 : 0 * 1 : 1 * 2 : 2, 3, 4, 5, 6, 7, 8 * 3 : 2, 3, 4, 5, 6, 7, 8 * 4 : 2, 3, 4, 5, 6, 7, 8 * 5 : 0 * 6 : 1 * 7 : 2, 3, 4, 5, 6, 7, 8 * 8 : 2, 3, 4, 5, 6, 7, 8 This graph has the following strongly connected components: P_1: minus#(s(X), s(Y)) =#> minus#(X, Y) P_2: double#(s(X)) =#> double#(X) P_3: plus#(s(X), Y) =#> plus#(X, Y) plus#(s(X), Y) =#> plus#(X, s(Y)) plus#(s(X), Y) =#> plus#(minus(X, Y), double(Y)) plus#(s(plus(X, Y)), Z) =#> plus#(plus(X, Y), Z) plus#(s(plus(X, Y)), Z) =#> plus#(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) and (P_3, 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) and (P_3, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_3, 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: plus#(s(X), Y) >? plus#(X, Y) plus#(s(X), Y) >? plus#(X, s(Y)) plus#(s(X), Y) >? plus#(minus(X, Y), double(Y)) plus#(s(plus(X, Y)), Z) >? plus#(plus(X, Y), Z) plus#(s(plus(X, Y)), Z) >? plus#(X, Y) minus(X, 0) >= X minus(s(X), s(Y)) >= minus(X, Y) double(0) >= 0 double(s(X)) >= s(s(double(X))) plus(0, X) >= X plus(s(X), Y) >= s(plus(X, Y)) plus(s(X), Y) >= plus(X, s(Y)) plus(s(X), Y) >= s(plus(minus(X, Y), double(Y))) plus(s(plus(X, Y)), Z) >= s(plus(plus(X, Y), Z)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 double = \y0.0 minus = \y0y1.y0 plus = \y0y1.1 + y0 + y1 plus# = \y0y1.2y0 s = \y0.y0 Using this interpretation, the requirements translate to: [[plus#(s(_x0), _x1)]] = 2x0 >= 2x0 = [[plus#(_x0, _x1)]] [[plus#(s(_x0), _x1)]] = 2x0 >= 2x0 = [[plus#(_x0, s(_x1))]] [[plus#(s(_x0), _x1)]] = 2x0 >= 2x0 = [[plus#(minus(_x0, _x1), double(_x1))]] [[plus#(s(plus(_x0, _x1)), _x2)]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[plus#(plus(_x0, _x1), _x2)]] [[plus#(s(plus(_x0, _x1)), _x2)]] = 2 + 2x0 + 2x1 > 2x0 = [[plus#(_x0, _x1)]] [[minus(_x0, 0)]] = x0 >= x0 = [[_x0]] [[minus(s(_x0), s(_x1))]] = x0 >= x0 = [[minus(_x0, _x1)]] [[double(0)]] = 0 >= 0 = [[0]] [[double(s(_x0))]] = 0 >= 0 = [[s(s(double(_x0)))]] [[plus(0, _x0)]] = 1 + x0 >= x0 = [[_x0]] [[plus(s(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[s(plus(_x0, _x1))]] [[plus(s(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[plus(_x0, s(_x1))]] [[plus(s(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 = [[s(plus(minus(_x0, _x1), double(_x1)))]] [[plus(s(plus(_x0, _x1)), _x2)]] = 2 + x0 + x1 + x2 >= 2 + x0 + x1 + x2 = [[s(plus(plus(_x0, _x1), _x2))]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_3, R_0, minimal, formative) by (P_4, R_0, minimal, formative), where P_4 consists of: plus#(s(X), Y) =#> plus#(X, Y) plus#(s(X), Y) =#> plus#(X, s(Y)) plus#(s(X), Y) =#> plus#(minus(X, Y), double(Y)) plus#(s(plus(X, Y)), Z) =#> plus#(plus(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_4, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_4, 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: plus#(s(X), Y) >? plus#(X, Y) plus#(s(X), Y) >? plus#(X, s(Y)) plus#(s(X), Y) >? plus#(minus(X, Y), double(Y)) plus#(s(plus(X, Y)), Z) >? plus#(plus(X, Y), Z) minus(X, 0) >= X minus(s(X), s(Y)) >= minus(X, Y) double(0) >= 0 double(s(X)) >= s(s(double(X))) plus(0, X) >= X plus(s(X), Y) >= s(plus(X, Y)) plus(s(X), Y) >= plus(X, s(Y)) plus(s(X), Y) >= s(plus(minus(X, Y), double(Y))) plus(s(plus(X, Y)), Z) >= s(plus(plus(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: [[0]] = _|_ [[minus(x_1, x_2)]] = minus(x_1) [[plus#(x_1, x_2)]] = plus#(x_1) We choose Lex = {minus, plus} and Mul = {double, plus#, s}, and the following precedence: plus > double > s > plus# > minus Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: plus#(s(X)) >= plus#(X) plus#(s(X)) >= plus#(X) plus#(s(X)) >= plus#(minus(X, Y)) plus#(s(plus(X, Y))) > plus#(plus(X, Y)) minus(X, _|_) >= X minus(s(X), s(Y)) >= minus(X, Y) double(_|_) >= _|_ double(s(X)) >= s(s(double(X))) plus(_|_, X) >= X plus(s(X), Y) >= s(plus(X, Y)) plus(s(X), Y) >= plus(X, s(Y)) plus(s(X), Y) >= s(plus(minus(X, Y), double(Y))) plus(s(plus(X, Y)), Z) >= s(plus(plus(X, Y), Z)) With these choices, we have: 1] plus#(s(X)) >= plus#(X) because plus# in Mul and [2], by (Fun) 2] s(X) >= X because [3], by (Star) 3] s*(X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] plus#(s(X)) >= plus#(X) because plus# in Mul and [2], by (Fun) 6] plus#(s(X)) >= plus#(minus(X, Y)) because plus# in Mul and [7], by (Fun) 7] s(X) >= minus(X, Y) because [8], by (Star) 8] s*(X) >= minus(X, Y) because s > minus and [9], by (Copy) 9] s*(X) >= X because [4], by (Select) 10] plus#(s(plus(X, Y))) > plus#(plus(X, Y)) because [11], by definition 11] plus#*(s(plus(X, Y))) >= plus#(plus(X, Y)) because [12], by (Select) 12] s(plus(X, Y)) >= plus#(plus(X, Y)) because [13], by (Star) 13] s*(plus(X, Y)) >= plus#(plus(X, Y)) because s > plus# and [14], by (Copy) 14] s*(plus(X, Y)) >= plus(X, Y) because [15], by (Select) 15] plus(X, Y) >= plus(X, Y) because [16] and [17], by (Fun) 16] X >= X by (Meta) 17] Y >= Y by (Meta) 18] minus(X, _|_) >= X because [19], by (Star) 19] minus*(X, _|_) >= X because [16], by (Select) 20] minus(s(X), s(Y)) >= minus(X, Y) because [2], by (Fun) 21] double(_|_) >= _|_ by (Bot) 22] double(s(X)) >= s(s(double(X))) because [23], by (Star) 23] double*(s(X)) >= s(s(double(X))) because double > s and [24], by (Copy) 24] double*(s(X)) >= s(double(X)) because double > s and [25], by (Copy) 25] double*(s(X)) >= double(X) because double in Mul and [26], by (Stat) 26] s(X) > X because [9], by definition 27] plus(_|_, X) >= X because [28], by (Star) 28] plus*(_|_, X) >= X because [17], by (Select) 29] plus(s(X), Y) >= s(plus(X, Y)) because [30], by (Star) 30] plus*(s(X), Y) >= s(plus(X, Y)) because plus > s and [31], by (Copy) 31] plus*(s(X), Y) >= plus(X, Y) because [26], [32] and [33], by (Stat) 32] plus*(s(X), Y) >= X because [2], by (Select) 33] plus*(s(X), Y) >= Y because [17], by (Select) 34] plus(s(X), Y) >= plus(X, s(Y)) because [35], by (Star) 35] plus*(s(X), Y) >= plus(X, s(Y)) because [26], [32] and [36], by (Stat) 36] plus*(s(X), Y) >= s(Y) because plus > s and [33], by (Copy) 37] plus(s(X), Y) >= s(plus(minus(X, Y), double(Y))) because [38], by (Star) 38] plus*(s(X), Y) >= s(plus(minus(X, Y), double(Y))) because plus > s and [39], by (Copy) 39] plus*(s(X), Y) >= plus(minus(X, Y), double(Y)) because [40], [42] and [43], by (Stat) 40] s(X) > minus(X, Y) because [41], by definition 41] s*(X) >= minus(X, Y) because s > minus and [9], by (Copy) 42] plus*(s(X), Y) >= minus(X, Y) because plus > minus and [32], by (Copy) 43] plus*(s(X), Y) >= double(Y) because plus > double and [33], by (Copy) 44] plus(s(plus(X, Y)), Z) >= s(plus(plus(X, Y), Z)) because [45], by (Star) 45] plus*(s(plus(X, Y)), Z) >= s(plus(plus(X, Y), Z)) because plus > s and [46], by (Copy) 46] plus*(s(plus(X, Y)), Z) >= plus(plus(X, Y), Z) because [47], [48] and [50], by (Stat) 47] s(plus(X, Y)) > plus(X, Y) because [14], by definition 48] plus*(s(plus(X, Y)), Z) >= plus(X, Y) because [49], by (Select) 49] s(plus(X, Y)) >= plus(X, Y) because [14], by (Star) 50] plus*(s(plus(X, Y)), Z) >= Z because [51], by (Select) 51] 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_4, R_0, minimal, formative) by (P_5, R_0, minimal, formative), where P_5 consists of: plus#(s(X), Y) =#> plus#(X, Y) plus#(s(X), Y) =#> plus#(X, s(Y)) plus#(s(X), Y) =#> plus#(minus(X, Y), double(Y)) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, 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 will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_5, R_0) are: minus(X, 0) => X minus(s(X), s(Y)) => minus(X, Y) double(0) => 0 double(s(X)) => s(s(double(X))) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: plus#(s(X), Y) >? plus#(X, Y) plus#(s(X), Y) >? plus#(X, s(Y)) plus#(s(X), Y) >? plus#(minus(X, Y), double(Y)) minus(X, 0) >= X minus(s(X), s(Y)) >= minus(X, Y) double(0) >= 0 double(s(X)) >= s(s(double(X))) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: plus#(x_1,x_2) = plus#(x_1) This leaves the following ordering requirements: plus#(s(X), Y) >= plus#(X, Y) plus#(s(X), Y) >= plus#(X, s(Y)) plus#(s(X), Y) > plus#(minus(X, Y), double(Y)) minus(X, 0) >= X minus(s(X), s(Y)) >= minus(X, Y) The following interpretation satisfies the requirements: 0 = 0 double = \y0.0 minus = \y0y1.y0 plus# = \y0y1.2y0 s = \y0.2 + 2y0 Using this interpretation, the requirements translate to: [[plus#(s(_x0), _x1)]] = 4 + 4x0 > 2x0 = [[plus#(_x0, _x1)]] [[plus#(s(_x0), _x1)]] = 4 + 4x0 > 2x0 = [[plus#(_x0, s(_x1))]] [[plus#(s(_x0), _x1)]] = 4 + 4x0 > 2x0 = [[plus#(minus(_x0, _x1), double(_x1))]] [[minus(_x0, 0)]] = x0 >= x0 = [[_x0]] [[minus(s(_x0), s(_x1))]] = 2 + 2x0 >= x0 = [[minus(_x0, _x1)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_5, R_0) by ({}, R_0). 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(double#) = 1 Thus, we can orient the dependency pairs as follows: nu(double#(s(X))) = s(X) |> X = nu(double#(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(minus#) = 1 Thus, we can orient the dependency pairs as follows: nu(minus#(s(X), s(Y))) = s(X) |> X = nu(minus#(X, Y)) 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.