/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. 1 : [] --> o 2 : [] --> o D : [o] --> o b : [o * o] --> o c : [o * o] --> o constant : [] --> o div : [o * o] --> o h : [] --> o ln : [o] --> o m : [o * o] --> o opp : [o] --> o pow : [o * o] --> o s : [o] --> o t : [] --> o D(t) => s(h) D(constant) => h D(b(X, Y)) => b(D(X), D(Y)) D(c(X, Y)) => b(c(Y, D(X)), c(X, D(Y))) D(m(X, Y)) => m(D(X), D(Y)) D(opp(X)) => opp(D(X)) D(div(X, Y)) => m(div(D(X), Y), div(c(X, D(Y)), pow(Y, 2))) D(ln(X)) => div(D(X), X) D(pow(X, Y)) => b(c(c(Y, pow(X, m(Y, 1))), D(X)), c(c(pow(X, Y), ln(X)), D(Y))) b(h, X) => X b(X, h) => X b(s(X), s(Y)) => s(s(b(X, Y))) b(b(X, Y), Z) => b(X, b(Y, Z)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): D(t) >? s(h) D(constant) >? h D(b(X, Y)) >? b(D(X), D(Y)) D(c(X, Y)) >? b(c(Y, D(X)), c(X, D(Y))) D(m(X, Y)) >? m(D(X), D(Y)) D(opp(X)) >? opp(D(X)) D(div(X, Y)) >? m(div(D(X), Y), div(c(X, D(Y)), pow(Y, 2))) D(ln(X)) >? div(D(X), X) D(pow(X, Y)) >? b(c(c(Y, pow(X, m(Y, 1))), D(X)), c(c(pow(X, Y), ln(X)), D(Y))) b(h, X) >? X b(X, h) >? X b(s(X), s(Y)) >? s(s(b(X, Y))) b(b(X, Y), Z) >? b(X, b(Y, Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[1]] = _|_ [[2]] = _|_ [[h]] = _|_ We choose Lex = {b} and Mul = {D, c, constant, div, ln, m, opp, pow, s, t}, and the following precedence: D = ln = opp = pow > b > c > constant > div > m > t > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: D(t) > s(_|_) D(constant) >= _|_ D(b(X, Y)) > b(D(X), D(Y)) D(c(X, Y)) > b(c(Y, D(X)), c(X, D(Y))) D(m(X, Y)) >= m(D(X), D(Y)) D(opp(X)) >= opp(D(X)) D(div(X, Y)) > m(div(D(X), Y), div(c(X, D(Y)), pow(Y, _|_))) D(ln(X)) >= div(D(X), X) D(pow(X, Y)) >= b(c(c(Y, pow(X, m(Y, _|_))), D(X)), c(c(pow(X, Y), ln(X)), D(Y))) b(_|_, X) >= X b(X, _|_) >= X b(s(X), s(Y)) >= s(s(b(X, Y))) b(b(X, Y), Z) > b(X, b(Y, Z)) With these choices, we have: 1] D(t) > s(_|_) because [2], by definition 2] D*(t) >= s(_|_) because [3], by (Select) 3] t >= s(_|_) because [4], by (Star) 4] t* >= s(_|_) because t > s and [5], by (Copy) 5] t* >= _|_ by (Bot) 6] D(constant) >= _|_ by (Bot) 7] D(b(X, Y)) > b(D(X), D(Y)) because [8], by definition 8] D*(b(X, Y)) >= b(D(X), D(Y)) because D > b, [9] and [13], by (Copy) 9] D*(b(X, Y)) >= D(X) because D in Mul and [10], by (Stat) 10] b(X, Y) > X because [11], by definition 11] b*(X, Y) >= X because [12], by (Select) 12] X >= X by (Meta) 13] D*(b(X, Y)) >= D(Y) because D in Mul and [14], by (Stat) 14] b(X, Y) > Y because [15], by definition 15] b*(X, Y) >= Y because [16], by (Select) 16] Y >= Y by (Meta) 17] D(c(X, Y)) > b(c(Y, D(X)), c(X, D(Y))) because [18], by definition 18] D*(c(X, Y)) >= b(c(Y, D(X)), c(X, D(Y))) because D > b, [19] and [26], by (Copy) 19] D*(c(X, Y)) >= c(Y, D(X)) because D > c, [20] and [23], by (Copy) 20] D*(c(X, Y)) >= Y because [21], by (Select) 21] c(X, Y) >= Y because [22], by (Star) 22] c*(X, Y) >= Y because [16], by (Select) 23] D*(c(X, Y)) >= D(X) because D in Mul and [24], by (Stat) 24] c(X, Y) > X because [25], by definition 25] c*(X, Y) >= X because [12], by (Select) 26] D*(c(X, Y)) >= c(X, D(Y)) because D > c, [27] and [29], by (Copy) 27] D*(c(X, Y)) >= X because [28], by (Select) 28] c(X, Y) >= X because [25], by (Star) 29] D*(c(X, Y)) >= D(Y) because D in Mul and [30], by (Stat) 30] c(X, Y) > Y because [31], by definition 31] c*(X, Y) >= Y because [16], by (Select) 32] D(m(X, Y)) >= m(D(X), D(Y)) because [33], by (Star) 33] D*(m(X, Y)) >= m(D(X), D(Y)) because D > m, [34] and [37], by (Copy) 34] D*(m(X, Y)) >= D(X) because D in Mul and [35], by (Stat) 35] m(X, Y) > X because [36], by definition 36] m*(X, Y) >= X because [12], by (Select) 37] D*(m(X, Y)) >= D(Y) because D in Mul and [38], by (Stat) 38] m(X, Y) > Y because [39], by definition 39] m*(X, Y) >= Y because [16], by (Select) 40] D(opp(X)) >= opp(D(X)) because D = opp, D in Mul and [41], by (Fun) 41] opp(X) >= D(X) because opp = D, opp in Mul and [42], by (Fun) 42] X >= X by (Meta) 43] D(div(X, Y)) > m(div(D(X), Y), div(c(X, D(Y)), pow(Y, _|_))) because [44], by definition 44] D*(div(X, Y)) >= m(div(D(X), Y), div(c(X, D(Y)), pow(Y, _|_))) because D > m, [45] and [52], by (Copy) 45] D*(div(X, Y)) >= div(D(X), Y) because D > div, [46] and [49], by (Copy) 46] D*(div(X, Y)) >= D(X) because D in Mul and [47], by (Stat) 47] div(X, Y) > X because [48], by definition 48] div*(X, Y) >= X because [42], by (Select) 49] D*(div(X, Y)) >= Y because [50], by (Select) 50] div(X, Y) >= Y because [51], by (Star) 51] div*(X, Y) >= Y because [16], by (Select) 52] D*(div(X, Y)) >= div(c(X, D(Y)), pow(Y, _|_)) because D > div, [53] and [59], by (Copy) 53] D*(div(X, Y)) >= c(X, D(Y)) because D > c, [54] and [56], by (Copy) 54] D*(div(X, Y)) >= X because [55], by (Select) 55] div(X, Y) >= X because [48], by (Star) 56] D*(div(X, Y)) >= D(Y) because D in Mul and [57], by (Stat) 57] div(X, Y) > Y because [58], by definition 58] div*(X, Y) >= Y because [16], by (Select) 59] D*(div(X, Y)) >= pow(Y, _|_) because D = pow, D in Mul, [57] and [60], by (Stat) 60] div(X, Y) > _|_ because [61], by definition 61] div*(X, Y) >= _|_ by (Bot) 62] D(ln(X)) >= div(D(X), X) because [63], by (Star) 63] D*(ln(X)) >= div(D(X), X) because D > div, [64] and [66], by (Copy) 64] D*(ln(X)) >= D(X) because [65], by (Select) 65] ln(X) >= D(X) because ln = D, ln in Mul and [42], by (Fun) 66] D*(ln(X)) >= X because [67], by (Select) 67] ln(X) >= X because [68], by (Star) 68] ln*(X) >= X because [42], by (Select) 69] D(pow(X, Y)) >= b(c(c(Y, pow(X, m(Y, _|_))), D(X)), c(c(pow(X, Y), ln(X)), D(Y))) because [70], by (Star) 70] D*(pow(X, Y)) >= b(c(c(Y, pow(X, m(Y, _|_))), D(X)), c(c(pow(X, Y), ln(X)), D(Y))) because D > b, [71] and [84], by (Copy) 71] D*(pow(X, Y)) >= c(c(Y, pow(X, m(Y, _|_))), D(X)) because D > c, [72] and [83], by (Copy) 72] D*(pow(X, Y)) >= c(Y, pow(X, m(Y, _|_))) because D > c, [73] and [76], by (Copy) 73] D*(pow(X, Y)) >= Y because [74], by (Select) 74] pow(X, Y) >= Y because [75], by (Star) 75] pow*(X, Y) >= Y because [16], by (Select) 76] D*(pow(X, Y)) >= pow(X, m(Y, _|_)) because D = pow, D in Mul, [77] and [79], by (Stat) 77] pow(X, Y) > X because [78], by definition 78] pow*(X, Y) >= X because [42], by (Select) 79] pow(X, Y) > m(Y, _|_) because [80], by definition 80] pow*(X, Y) >= m(Y, _|_) because pow > m, [81] and [82], by (Copy) 81] pow*(X, Y) >= Y because [16], by (Select) 82] pow*(X, Y) >= _|_ by (Bot) 83] D*(pow(X, Y)) >= D(X) because D in Mul and [77], by (Stat) 84] D*(pow(X, Y)) >= c(c(pow(X, Y), ln(X)), D(Y)) because D > c, [85] and [89], by (Copy) 85] D*(pow(X, Y)) >= c(pow(X, Y), ln(X)) because D > c, [86] and [88], by (Copy) 86] D*(pow(X, Y)) >= pow(X, Y) because D = pow, D in Mul, [77] and [87], by (Stat) 87] pow(X, Y) > Y because [81], by definition 88] D*(pow(X, Y)) >= ln(X) because D = ln, D in Mul and [77], by (Stat) 89] D*(pow(X, Y)) >= D(Y) because D in Mul and [87], by (Stat) 90] b(_|_, X) >= X because [91], by (Star) 91] b*(_|_, X) >= X because [42], by (Select) 92] b(X, _|_) >= X because [93], by (Star) 93] b*(X, _|_) >= X because [42], by (Select) 94] b(s(X), s(Y)) >= s(s(b(X, Y))) because [95], by (Star) 95] b*(s(X), s(Y)) >= s(s(b(X, Y))) because b > s and [96], by (Copy) 96] b*(s(X), s(Y)) >= s(b(X, Y)) because b > s and [97], by (Copy) 97] b*(s(X), s(Y)) >= b(X, Y) because [98], [100] and [102], by (Stat) 98] s(X) > X because [99], by definition 99] s*(X) >= X because [42], by (Select) 100] b*(s(X), s(Y)) >= X because [101], by (Select) 101] s(X) >= X because [99], by (Star) 102] b*(s(X), s(Y)) >= Y because [103], by (Select) 103] s(Y) >= Y because [104], by (Star) 104] s*(Y) >= Y because [16], by (Select) 105] b(b(X, Y), Z) > b(X, b(Y, Z)) because [106], by definition 106] b*(b(X, Y), Z) >= b(X, b(Y, Z)) because [10], [107] and [109], by (Stat) 107] b*(b(X, Y), Z) >= X because [108], by (Select) 108] b(X, Y) >= X because [11], by (Star) 109] b*(b(X, Y), Z) >= b(Y, Z) because [14], [110] and [112], by (Stat) 110] b*(b(X, Y), Z) >= Y because [111], by (Select) 111] b(X, Y) >= Y because [15], by (Star) 112] b*(b(X, Y), Z) >= Z because [113], by (Select) 113] Z >= Z by (Meta) We can thus remove the following rules: D(t) => s(h) D(b(X, Y)) => b(D(X), D(Y)) D(c(X, Y)) => b(c(Y, D(X)), c(X, D(Y))) D(div(X, Y)) => m(div(D(X), Y), div(c(X, D(Y)), pow(Y, 2))) b(b(X, Y), Z) => b(X, b(Y, Z)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): D(constant) >? h D(m(X, Y)) >? m(D(X), D(Y)) D(opp(X)) >? opp(D(X)) D(ln(X)) >? div(D(X), X) D(pow(X, Y)) >? b(c(c(Y, pow(X, m(Y, 1))), D(X)), c(c(pow(X, Y), ln(X)), D(Y))) b(h, X) >? X b(X, h) >? X b(s(X), s(Y)) >? s(s(b(X, Y))) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[1]] = _|_ [[opp(x_1)]] = x_1 We choose Lex = {} and Mul = {D, b, c, constant, div, h, ln, m, pow, s}, and the following precedence: D > h > constant > ln > m > pow > c > div > b > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: D(constant) >= h D(m(X, Y)) >= m(D(X), D(Y)) D(X) >= D(X) D(ln(X)) >= div(D(X), X) D(pow(X, Y)) > b(c(c(Y, pow(X, m(Y, _|_))), D(X)), c(c(pow(X, Y), ln(X)), D(Y))) b(h, X) >= X b(X, h) >= X b(s(X), s(Y)) >= s(s(b(X, Y))) With these choices, we have: 1] D(constant) >= h because [2], by (Star) 2] D*(constant) >= h because D > h, by (Copy) 3] D(m(X, Y)) >= m(D(X), D(Y)) because [4], by (Star) 4] D*(m(X, Y)) >= m(D(X), D(Y)) because D > m, [5] and [9], by (Copy) 5] D*(m(X, Y)) >= D(X) because D in Mul and [6], by (Stat) 6] m(X, Y) > X because [7], by definition 7] m*(X, Y) >= X because [8], by (Select) 8] X >= X by (Meta) 9] D*(m(X, Y)) >= D(Y) because D in Mul and [10], by (Stat) 10] m(X, Y) > Y because [11], by definition 11] m*(X, Y) >= Y because [12], by (Select) 12] Y >= Y by (Meta) 13] D(X) >= D(X) because D in Mul and [14], by (Fun) 14] X >= X by (Meta) 15] D(ln(X)) >= div(D(X), X) because [16], by (Star) 16] D*(ln(X)) >= div(D(X), X) because D > div, [17] and [20], by (Copy) 17] D*(ln(X)) >= D(X) because D in Mul and [18], by (Stat) 18] ln(X) > X because [19], by definition 19] ln*(X) >= X because [14], by (Select) 20] D*(ln(X)) >= X because [21], by (Select) 21] ln(X) >= X because [19], by (Star) 22] D(pow(X, Y)) > b(c(c(Y, pow(X, m(Y, _|_))), D(X)), c(c(pow(X, Y), ln(X)), D(Y))) because [23], by definition 23] D*(pow(X, Y)) >= b(c(c(Y, pow(X, m(Y, _|_))), D(X)), c(c(pow(X, Y), ln(X)), D(Y))) because D > b, [24] and [38], by (Copy) 24] D*(pow(X, Y)) >= c(c(Y, pow(X, m(Y, _|_))), D(X)) because D > c, [25] and [35], by (Copy) 25] D*(pow(X, Y)) >= c(Y, pow(X, m(Y, _|_))) because D > c, [26] and [29], by (Copy) 26] D*(pow(X, Y)) >= Y because [27], by (Select) 27] pow(X, Y) >= Y because [28], by (Star) 28] pow*(X, Y) >= Y because [12], by (Select) 29] D*(pow(X, Y)) >= pow(X, m(Y, _|_)) because D > pow, [30] and [33], by (Copy) 30] D*(pow(X, Y)) >= X because [31], by (Select) 31] pow(X, Y) >= X because [32], by (Star) 32] pow*(X, Y) >= X because [14], by (Select) 33] D*(pow(X, Y)) >= m(Y, _|_) because D > m, [26] and [34], by (Copy) 34] D*(pow(X, Y)) >= _|_ by (Bot) 35] D*(pow(X, Y)) >= D(X) because D in Mul and [36], by (Stat) 36] pow(X, Y) > X because [37], by definition 37] pow*(X, Y) >= X because [14], by (Select) 38] D*(pow(X, Y)) >= c(c(pow(X, Y), ln(X)), D(Y)) because D > c, [39] and [42], by (Copy) 39] D*(pow(X, Y)) >= c(pow(X, Y), ln(X)) because D > c, [40] and [41], by (Copy) 40] D*(pow(X, Y)) >= pow(X, Y) because D > pow, [30] and [26], by (Copy) 41] D*(pow(X, Y)) >= ln(X) because D > ln and [30], by (Copy) 42] D*(pow(X, Y)) >= D(Y) because D in Mul and [43], by (Stat) 43] pow(X, Y) > Y because [44], by definition 44] pow*(X, Y) >= Y because [12], by (Select) 45] b(h, X) >= X because [46], by (Star) 46] b*(h, X) >= X because [14], by (Select) 47] b(X, h) >= X because [48], by (Star) 48] b*(X, h) >= X because [14], by (Select) 49] b(s(X), s(Y)) >= s(s(b(X, Y))) because [50], by (Star) 50] b*(s(X), s(Y)) >= s(s(b(X, Y))) because b > s and [51], by (Copy) 51] b*(s(X), s(Y)) >= s(b(X, Y)) because b > s and [52], by (Copy) 52] b*(s(X), s(Y)) >= b(X, Y) because b in Mul, [53] and [55], by (Stat) 53] s(X) >= X because [54], by (Star) 54] s*(X) >= X because [14], by (Select) 55] s(Y) > Y because [56], by definition 56] s*(Y) >= Y because [12], by (Select) We can thus remove the following rules: D(pow(X, Y)) => b(c(c(Y, pow(X, m(Y, 1))), D(X)), c(c(pow(X, Y), ln(X)), D(Y))) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): D(constant) >? h D(m(X, Y)) >? m(D(X), D(Y)) D(opp(X)) >? opp(D(X)) D(ln(X)) >? div(D(X), X) b(h, X) >? X b(X, h) >? X b(s(X), s(Y)) >? s(s(b(X, Y))) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: D = \y0.2y0 b = \y0y1.y0 + 2y1 constant = 3 div = \y0y1.y0 + y1 h = 0 ln = \y0.3 + 3y0 m = \y0y1.2 + y0 + y1 opp = \y0.1 + y0 s = \y0.y0 Using this interpretation, the requirements translate to: [[D(constant)]] = 6 > 0 = [[h]] [[D(m(_x0, _x1))]] = 4 + 2x0 + 2x1 > 2 + 2x0 + 2x1 = [[m(D(_x0), D(_x1))]] [[D(opp(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[opp(D(_x0))]] [[D(ln(_x0))]] = 6 + 6x0 > 3x0 = [[div(D(_x0), _x0)]] [[b(h, _x0)]] = 2x0 >= x0 = [[_x0]] [[b(_x0, h)]] = x0 >= x0 = [[_x0]] [[b(s(_x0), s(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[s(s(b(_x0, _x1)))]] We can thus remove the following rules: D(constant) => h D(m(X, Y)) => m(D(X), D(Y)) D(opp(X)) => opp(D(X)) D(ln(X)) => div(D(X), X) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): b(h, X) >? X b(X, h) >? X b(s(X), s(Y)) >? s(s(b(X, Y))) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: b = \y0y1.y0 + y1 h = 3 s = \y0.y0 Using this interpretation, the requirements translate to: [[b(h, _x0)]] = 3 + x0 > x0 = [[_x0]] [[b(_x0, h)]] = 3 + x0 > x0 = [[_x0]] [[b(s(_x0), s(_x1))]] = x0 + x1 >= x0 + x1 = [[s(s(b(_x0, _x1)))]] We can thus remove the following rules: b(h, X) => X b(X, h) => X We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): b(s(X), s(Y)) >? s(s(b(X, Y))) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: b = \y0y1.1 + 2y0 + 2y1 s = \y0.1 + y0 Using this interpretation, the requirements translate to: [[b(s(_x0), s(_x1))]] = 5 + 2x0 + 2x1 > 3 + 2x0 + 2x1 = [[s(s(b(_x0, _x1)))]] We can thus remove the following rules: b(s(X), s(Y)) => s(s(b(X, Y))) All rules were succesfully removed. Thus, termination of the original system has been reduced to termination of the beta-rule, which is well-known to hold. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012.