/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. !minus : [o * o] --> o !plus : [o * o] --> o !times : [o * o] --> o 0 : [] --> o 1 : [] --> o 2 : [] --> o D : [o] --> o constant : [] --> o div : [o * o] --> o ln : [o] --> o minus : [o] --> o pow : [o * o] --> o t : [] --> o D(t) => 1 D(constant) => 0 D(!plus(X, Y)) => !plus(D(X), D(Y)) D(!times(X, Y)) => !plus(!times(Y, D(X)), !times(X, D(Y))) D(!minus(X, Y)) => !minus(D(X), D(Y)) D(minus(X)) => minus(D(X)) D(div(X, Y)) => !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, 2))) D(ln(X)) => div(D(X), X) D(pow(X, Y)) => !plus(!times(!times(Y, pow(X, !minus(Y, 1))), D(X)), !times(!times(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(t) >? 1 D(constant) >? 0 D(!plus(X, Y)) >? !plus(D(X), D(Y)) D(!times(X, Y)) >? !plus(!times(Y, D(X)), !times(X, D(Y))) D(!minus(X, Y)) >? !minus(D(X), D(Y)) D(minus(X)) >? minus(D(X)) D(div(X, Y)) >? !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, 2))) D(ln(X)) >? div(D(X), X) D(pow(X, Y)) >? !plus(!times(!times(Y, pow(X, !minus(Y, 1))), D(X)), !times(!times(pow(X, Y), ln(X)), D(Y))) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[1]] = _|_ [[2]] = _|_ We choose Lex = {} and Mul = {!minus, !plus, !times, D, constant, div, ln, minus, pow, t}, and the following precedence: D = ln = minus > !times > pow > constant > t > div > !minus > !plus Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: D(t) >= _|_ D(constant) >= _|_ D(!plus(X, Y)) >= !plus(D(X), D(Y)) D(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y))) D(!minus(X, Y)) > !minus(D(X), D(Y)) D(minus(X)) >= minus(D(X)) D(div(X, Y)) >= !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, _|_))) D(ln(X)) >= div(D(X), X) D(pow(X, Y)) > !plus(!times(!times(Y, pow(X, !minus(Y, _|_))), D(X)), !times(!times(pow(X, Y), ln(X)), D(Y))) With these choices, we have: 1] D(t) >= _|_ by (Bot) 2] D(constant) >= _|_ by (Bot) 3] D(!plus(X, Y)) >= !plus(D(X), D(Y)) because [4], by (Star) 4] D*(!plus(X, Y)) >= !plus(D(X), D(Y)) because D > !plus, [5] and [9], by (Copy) 5] D*(!plus(X, Y)) >= D(X) because D in Mul and [6], by (Stat) 6] !plus(X, Y) > X because [7], by definition 7] !plus*(X, Y) >= X because [8], by (Select) 8] X >= X by (Meta) 9] D*(!plus(X, Y)) >= D(Y) because D in Mul and [10], by (Stat) 10] !plus(X, Y) > Y because [11], by definition 11] !plus*(X, Y) >= Y because [12], by (Select) 12] Y >= Y by (Meta) 13] D(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y))) because [14], by (Star) 14] D*(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y))) because D > !plus, [15] and [22], by (Copy) 15] D*(!times(X, Y)) >= !times(Y, D(X)) because D > !times, [16] and [19], by (Copy) 16] D*(!times(X, Y)) >= Y because [17], by (Select) 17] !times(X, Y) >= Y because [18], by (Star) 18] !times*(X, Y) >= Y because [12], by (Select) 19] D*(!times(X, Y)) >= D(X) because D in Mul and [20], by (Stat) 20] !times(X, Y) > X because [21], by definition 21] !times*(X, Y) >= X because [8], by (Select) 22] D*(!times(X, Y)) >= !times(X, D(Y)) because D > !times, [23] and [25], by (Copy) 23] D*(!times(X, Y)) >= X because [24], by (Select) 24] !times(X, Y) >= X because [21], by (Star) 25] D*(!times(X, Y)) >= D(Y) because D in Mul and [26], by (Stat) 26] !times(X, Y) > Y because [27], by definition 27] !times*(X, Y) >= Y because [12], by (Select) 28] D(!minus(X, Y)) > !minus(D(X), D(Y)) because [29], by definition 29] D*(!minus(X, Y)) >= !minus(D(X), D(Y)) because D > !minus, [30] and [33], by (Copy) 30] D*(!minus(X, Y)) >= D(X) because D in Mul and [31], by (Stat) 31] !minus(X, Y) > X because [32], by definition 32] !minus*(X, Y) >= X because [8], by (Select) 33] D*(!minus(X, Y)) >= D(Y) because D in Mul and [34], by (Stat) 34] !minus(X, Y) > Y because [35], by definition 35] !minus*(X, Y) >= Y because [12], by (Select) 36] D(minus(X)) >= minus(D(X)) because D = minus, D in Mul and [37], by (Fun) 37] minus(X) >= D(X) because minus = D, minus in Mul and [38], by (Fun) 38] X >= X by (Meta) 39] D(div(X, Y)) >= !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, _|_))) because [40], by (Star) 40] D*(div(X, Y)) >= !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, _|_))) because D > !minus, [41] and [48], by (Copy) 41] D*(div(X, Y)) >= div(D(X), Y) because D > div, [42] and [45], by (Copy) 42] D*(div(X, Y)) >= D(X) because D in Mul and [43], by (Stat) 43] div(X, Y) > X because [44], by definition 44] div*(X, Y) >= X because [38], by (Select) 45] D*(div(X, Y)) >= Y because [46], by (Select) 46] div(X, Y) >= Y because [47], by (Star) 47] div*(X, Y) >= Y because [12], by (Select) 48] D*(div(X, Y)) >= div(!times(X, D(Y)), pow(Y, _|_)) because D > div, [49] and [55], by (Copy) 49] D*(div(X, Y)) >= !times(X, D(Y)) because D > !times, [50] and [52], by (Copy) 50] D*(div(X, Y)) >= X because [51], by (Select) 51] div(X, Y) >= X because [44], by (Star) 52] D*(div(X, Y)) >= D(Y) because D in Mul and [53], by (Stat) 53] div(X, Y) > Y because [54], by definition 54] div*(X, Y) >= Y because [12], by (Select) 55] D*(div(X, Y)) >= pow(Y, _|_) because D > pow, [45] and [56], by (Copy) 56] D*(div(X, Y)) >= _|_ by (Bot) 57] D(ln(X)) >= div(D(X), X) because [58], by (Star) 58] D*(ln(X)) >= div(D(X), X) because D > div, [59] and [61], by (Copy) 59] D*(ln(X)) >= D(X) because [60], by (Select) 60] ln(X) >= D(X) because ln = D, ln in Mul and [38], by (Fun) 61] D*(ln(X)) >= X because [62], by (Select) 62] ln(X) >= X because [63], by (Star) 63] ln*(X) >= X because [38], by (Select) 64] D(pow(X, Y)) > !plus(!times(!times(Y, pow(X, !minus(Y, _|_))), D(X)), !times(!times(pow(X, Y), ln(X)), D(Y))) because [65], by definition 65] D*(pow(X, Y)) >= !plus(!times(!times(Y, pow(X, !minus(Y, _|_))), D(X)), !times(!times(pow(X, Y), ln(X)), D(Y))) because D > !plus, [66] and [80], by (Copy) 66] D*(pow(X, Y)) >= !times(!times(Y, pow(X, !minus(Y, _|_))), D(X)) because D > !times, [67] and [77], by (Copy) 67] D*(pow(X, Y)) >= !times(Y, pow(X, !minus(Y, _|_))) because D > !times, [68] and [71], by (Copy) 68] D*(pow(X, Y)) >= Y because [69], by (Select) 69] pow(X, Y) >= Y because [70], by (Star) 70] pow*(X, Y) >= Y because [12], by (Select) 71] D*(pow(X, Y)) >= pow(X, !minus(Y, _|_)) because D > pow, [72] and [75], by (Copy) 72] D*(pow(X, Y)) >= X because [73], by (Select) 73] pow(X, Y) >= X because [74], by (Star) 74] pow*(X, Y) >= X because [38], by (Select) 75] D*(pow(X, Y)) >= !minus(Y, _|_) because D > !minus, [68] and [76], by (Copy) 76] D*(pow(X, Y)) >= _|_ by (Bot) 77] D*(pow(X, Y)) >= D(X) because D in Mul and [78], by (Stat) 78] pow(X, Y) > X because [79], by definition 79] pow*(X, Y) >= X because [38], by (Select) 80] D*(pow(X, Y)) >= !times(!times(pow(X, Y), ln(X)), D(Y)) because D > !times, [81] and [84], by (Copy) 81] D*(pow(X, Y)) >= !times(pow(X, Y), ln(X)) because D > !times, [82] and [83], by (Copy) 82] D*(pow(X, Y)) >= pow(X, Y) because D > pow, [72] and [68], by (Copy) 83] D*(pow(X, Y)) >= ln(X) because D = ln, D in Mul and [78], by (Stat) 84] D*(pow(X, Y)) >= D(Y) because D in Mul and [85], by (Stat) 85] pow(X, Y) > Y because [86], by definition 86] pow*(X, Y) >= Y because [12], by (Select) We can thus remove the following rules: D(!minus(X, Y)) => !minus(D(X), D(Y)) D(pow(X, Y)) => !plus(!times(!times(Y, pow(X, !minus(Y, 1))), D(X)), !times(!times(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(t) >? 1 D(constant) >? 0 D(!plus(X, Y)) >? !plus(D(X), D(Y)) D(!times(X, Y)) >? !plus(!times(Y, D(X)), !times(X, D(Y))) D(minus(X)) >? minus(D(X)) D(div(X, Y)) >? !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, 2))) D(ln(X)) >? div(D(X), X) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[1]] = _|_ [[2]] = _|_ [[minus(x_1)]] = x_1 We choose Lex = {} and Mul = {!minus, !plus, !times, D, constant, div, ln, pow, t}, and the following precedence: D = ln > pow > div > !minus > !plus > !times > t > constant Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: D(t) >= _|_ D(constant) >= _|_ D(!plus(X, Y)) > !plus(D(X), D(Y)) D(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y))) D(X) >= D(X) D(div(X, Y)) >= !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, _|_))) D(ln(X)) > div(D(X), X) With these choices, we have: 1] D(t) >= _|_ by (Bot) 2] D(constant) >= _|_ by (Bot) 3] D(!plus(X, Y)) > !plus(D(X), D(Y)) because [4], by definition 4] D*(!plus(X, Y)) >= !plus(D(X), D(Y)) because D > !plus, [5] and [9], by (Copy) 5] D*(!plus(X, Y)) >= D(X) because D in Mul and [6], by (Stat) 6] !plus(X, Y) > X because [7], by definition 7] !plus*(X, Y) >= X because [8], by (Select) 8] X >= X by (Meta) 9] D*(!plus(X, Y)) >= D(Y) because D in Mul and [10], by (Stat) 10] !plus(X, Y) > Y because [11], by definition 11] !plus*(X, Y) >= Y because [12], by (Select) 12] Y >= Y by (Meta) 13] D(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y))) because [14], by (Star) 14] D*(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y))) because D > !plus, [15] and [22], by (Copy) 15] D*(!times(X, Y)) >= !times(Y, D(X)) because D > !times, [16] and [19], by (Copy) 16] D*(!times(X, Y)) >= Y because [17], by (Select) 17] !times(X, Y) >= Y because [18], by (Star) 18] !times*(X, Y) >= Y because [12], by (Select) 19] D*(!times(X, Y)) >= D(X) because D in Mul and [20], by (Stat) 20] !times(X, Y) > X because [21], by definition 21] !times*(X, Y) >= X because [8], by (Select) 22] D*(!times(X, Y)) >= !times(X, D(Y)) because D > !times, [23] and [25], by (Copy) 23] D*(!times(X, Y)) >= X because [24], by (Select) 24] !times(X, Y) >= X because [21], by (Star) 25] D*(!times(X, Y)) >= D(Y) because D in Mul and [26], by (Stat) 26] !times(X, Y) > Y because [27], by definition 27] !times*(X, Y) >= Y because [12], by (Select) 28] D(X) >= D(X) because D in Mul and [29], by (Fun) 29] X >= X by (Meta) 30] D(div(X, Y)) >= !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, _|_))) because [31], by (Star) 31] D*(div(X, Y)) >= !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, _|_))) because D > !minus, [32] and [39], by (Copy) 32] D*(div(X, Y)) >= div(D(X), Y) because D > div, [33] and [36], by (Copy) 33] D*(div(X, Y)) >= D(X) because D in Mul and [34], by (Stat) 34] div(X, Y) > X because [35], by definition 35] div*(X, Y) >= X because [29], by (Select) 36] D*(div(X, Y)) >= Y because [37], by (Select) 37] div(X, Y) >= Y because [38], by (Star) 38] div*(X, Y) >= Y because [12], by (Select) 39] D*(div(X, Y)) >= div(!times(X, D(Y)), pow(Y, _|_)) because D > div, [40] and [46], by (Copy) 40] D*(div(X, Y)) >= !times(X, D(Y)) because D > !times, [41] and [43], by (Copy) 41] D*(div(X, Y)) >= X because [42], by (Select) 42] div(X, Y) >= X because [35], by (Star) 43] D*(div(X, Y)) >= D(Y) because D in Mul and [44], by (Stat) 44] div(X, Y) > Y because [45], by definition 45] div*(X, Y) >= Y because [12], by (Select) 46] D*(div(X, Y)) >= pow(Y, _|_) because D > pow, [36] and [47], by (Copy) 47] D*(div(X, Y)) >= _|_ by (Bot) 48] D(ln(X)) > div(D(X), X) because [49], by definition 49] D*(ln(X)) >= div(D(X), X) because D > div, [50] and [53], by (Copy) 50] D*(ln(X)) >= D(X) because [51], by (Select) 51] ln(X) >= D(X) because ln = D, ln in Mul and [52], by (Fun) 52] X >= X by (Meta) 53] D*(ln(X)) >= X because [54], by (Select) 54] ln(X) >= X because [55], by (Star) 55] ln*(X) >= X because [52], by (Select) We can thus remove the following rules: D(!plus(X, Y)) => !plus(D(X), D(Y)) 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]): D(t) >? 1 D(constant) >? 0 D(!times(X, Y)) >? !plus(!times(Y, D(X)), !times(X, D(Y))) D(minus(X)) >? minus(D(X)) D(div(X, Y)) >? !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, 2))) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[1]] = _|_ [[2]] = _|_ We choose Lex = {} and Mul = {!minus, !plus, !times, D, constant, div, minus, pow, t}, and the following precedence: D > constant > minus > pow > t > !plus > !minus > !times > div Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: D(t) >= _|_ D(constant) >= _|_ D(!times(X, Y)) > !plus(!times(Y, D(X)), !times(X, D(Y))) D(minus(X)) > minus(D(X)) D(div(X, Y)) > !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, _|_))) With these choices, we have: 1] D(t) >= _|_ by (Bot) 2] D(constant) >= _|_ by (Bot) 3] D(!times(X, Y)) > !plus(!times(Y, D(X)), !times(X, D(Y))) because [4], by definition 4] D*(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y))) because D > !plus, [5] and [14], by (Copy) 5] D*(!times(X, Y)) >= !times(Y, D(X)) because D > !times, [6] and [10], by (Copy) 6] D*(!times(X, Y)) >= Y because [7], by (Select) 7] !times(X, Y) >= Y because [8], by (Star) 8] !times*(X, Y) >= Y because [9], by (Select) 9] Y >= Y by (Meta) 10] D*(!times(X, Y)) >= D(X) because D in Mul and [11], by (Stat) 11] !times(X, Y) > X because [12], by definition 12] !times*(X, Y) >= X because [13], by (Select) 13] X >= X by (Meta) 14] D*(!times(X, Y)) >= !times(X, D(Y)) because D > !times, [15] and [17], by (Copy) 15] D*(!times(X, Y)) >= X because [16], by (Select) 16] !times(X, Y) >= X because [12], by (Star) 17] D*(!times(X, Y)) >= D(Y) because D in Mul and [18], by (Stat) 18] !times(X, Y) > Y because [19], by definition 19] !times*(X, Y) >= Y because [9], by (Select) 20] D(minus(X)) > minus(D(X)) because [21], by definition 21] D*(minus(X)) >= minus(D(X)) because D > minus and [22], by (Copy) 22] D*(minus(X)) >= D(X) because D in Mul and [23], by (Stat) 23] minus(X) > X because [24], by definition 24] minus*(X) >= X because [13], by (Select) 25] D(div(X, Y)) > !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, _|_))) because [26], by definition 26] D*(div(X, Y)) >= !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, _|_))) because D > !minus, [27] and [34], by (Copy) 27] D*(div(X, Y)) >= div(D(X), Y) because D > div, [28] and [31], by (Copy) 28] D*(div(X, Y)) >= D(X) because D in Mul and [29], by (Stat) 29] div(X, Y) > X because [30], by definition 30] div*(X, Y) >= X because [13], by (Select) 31] D*(div(X, Y)) >= Y because [32], by (Select) 32] div(X, Y) >= Y because [33], by (Star) 33] div*(X, Y) >= Y because [9], by (Select) 34] D*(div(X, Y)) >= div(!times(X, D(Y)), pow(Y, _|_)) because D > div, [35] and [41], by (Copy) 35] D*(div(X, Y)) >= !times(X, D(Y)) because D > !times, [36] and [38], by (Copy) 36] D*(div(X, Y)) >= X because [37], by (Select) 37] div(X, Y) >= X because [30], by (Star) 38] D*(div(X, Y)) >= D(Y) because D in Mul and [39], by (Stat) 39] div(X, Y) > Y because [40], by definition 40] div*(X, Y) >= Y because [9], by (Select) 41] D*(div(X, Y)) >= pow(Y, _|_) because D > pow, [31] and [42], by (Copy) 42] D*(div(X, Y)) >= _|_ by (Bot) We can thus remove the following rules: D(!times(X, Y)) => !plus(!times(Y, D(X)), !times(X, D(Y))) D(minus(X)) => minus(D(X)) D(div(X, Y)) => !minus(div(D(X), Y), div(!times(X, D(Y)), pow(Y, 2))) 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) >? 1 D(constant) >? 0 We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 1 = 0 D = \y0.3 + y0 constant = 3 t = 3 Using this interpretation, the requirements translate to: [[D(t)]] = 6 > 0 = [[1]] [[D(constant)]] = 6 > 0 = [[0]] We can thus remove the following rules: D(t) => 1 D(constant) => 0 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.