/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. !plus : [o * o] --> o !times : [o * o] --> o 1 : [] --> o oplus : [o * o] --> o otimes : [o * o] --> o !times(X, !times(Y, Z)) => !times(otimes(X, Y), Z) !times(1, X) => X !times(!plus(X, Y), Z) => oplus(!times(X, Z), !times(Y, Z)) !times(X, oplus(Y, Z)) => oplus(!times(X, Y), !times(X, 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]): !times(X, !times(Y, Z)) >? !times(otimes(X, Y), Z) !times(1, X) >? X !times(!plus(X, Y), Z) >? oplus(!times(X, Z), !times(Y, Z)) !times(X, oplus(Y, Z)) >? oplus(!times(X, Y), !times(X, Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[!times(x_1, x_2)]] = !times(x_2, x_1) We choose Lex = {!times} and Mul = {!plus, 1, oplus, otimes}, and the following precedence: 1 > !plus > !times > oplus > otimes Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: !times(X, !times(Y, Z)) >= !times(otimes(X, Y), Z) !times(1, X) > X !times(!plus(X, Y), Z) >= oplus(!times, !times Y Z) !times(X, oplus(Y, Z)) >= oplus(!times, !times X Z) With these choices, we have: 1] !times(X, !times(Y, Z)) >= !times(otimes(X, Y), Z) because [2], by (Star) 2] !times*(X, !times(Y, Z)) >= !times(otimes(X, Y), Z) because [3], [6] and [13], by (Stat) 3] !times(Y, Z) > Z because [4], by definition 4] !times*(Y, Z) >= Z because [5], by (Select) 5] Z >= Z by (Meta) 6] !times*(X, !times(Y, Z)) >= otimes(X, Y) because !times > otimes, [7] and [9], by (Copy) 7] !times*(X, !times(Y, Z)) >= X because [8], by (Select) 8] X >= X by (Meta) 9] !times*(X, !times(Y, Z)) >= Y because [10], by (Select) 10] !times(Y, Z) >= Y because [11], by (Star) 11] !times*(Y, Z) >= Y because [12], by (Select) 12] Y >= Y by (Meta) 13] !times*(X, !times(Y, Z)) >= Z because [14], by (Select) 14] !times(Y, Z) >= Z because [4], by (Star) 15] !times(1, X) > X because [16], by definition 16] !times*(1, X) >= X because [12], by (Select) 17] !times(!plus(X, Y), Z) >= oplus(!times, !times Y Z) because [18], by (Star) 18] !times*(!plus(X, Y), Z) >= oplus(!times, !times Y Z) because !times > oplus, [19] and [26], by (Copy) 19] !times*(!plus(X, Y), Z) >= !times(X, Z) because [20], [22], [23] and [25], by (Stat) 20] !plus(X, Y) > X because [21], by definition 21] !plus*(X, Y) >= X because [8], by (Select) 22] Z >= Z by (Meta) 23] !times*(!plus(X, Y), Z) >= X because [24], by (Select) 24] !plus(X, Y) >= X because [21], by (Star) 25] !times*(!plus(X, Y), Z) >= Z because [22], by (Select) 26] !times*(!plus(X, Y), Z) >= !times(Y, Z) because [27], [22], [29] and [25], by (Stat) 27] !plus(X, Y) > Y because [28], by definition 28] !plus*(X, Y) >= Y because [12], by (Select) 29] !times*(!plus(X, Y), Z) >= Y because [30], by (Select) 30] !plus(X, Y) >= Y because [28], by (Star) 31] !times(X, oplus(Y, Z)) >= oplus(!times, !times X Z) because [32], by (Star) 32] !times*(X, oplus(Y, Z)) >= oplus(!times, !times X Z) because !times > oplus, [33] and [39], by (Copy) 33] !times*(X, oplus(Y, Z)) >= !times(X, Y) because [34], [36] and [37], by (Stat) 34] oplus(Y, Z) > Y because [35], by definition 35] oplus*(Y, Z) >= Y because [12], by (Select) 36] !times*(X, oplus(Y, Z)) >= X because [8], by (Select) 37] !times*(X, oplus(Y, Z)) >= Y because [38], by (Select) 38] oplus(Y, Z) >= Y because [35], by (Star) 39] !times*(X, oplus(Y, Z)) >= !times(X, Z) because [40], [36] and [42], by (Stat) 40] oplus(Y, Z) > Z because [41], by definition 41] oplus*(Y, Z) >= Z because [22], by (Select) 42] !times*(X, oplus(Y, Z)) >= Z because [43], by (Select) 43] oplus(Y, Z) >= Z because [41], by (Star) We can thus remove the following rules: !times(1, 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]): !times(X, !times(Y, Z)) >? !times(otimes(X, Y), Z) !times(!plus(X, Y), Z) >? oplus(!times(X, Z), !times(Y, Z)) !times(X, oplus(Y, Z)) >? oplus(!times(X, Y), !times(X, Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[!times(x_1, x_2)]] = !times(x_2, x_1) We choose Lex = {!times} and Mul = {!plus, oplus, otimes}, and the following precedence: !plus > !times > oplus > otimes Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: !times(X, !times(Y, Z)) >= !times(otimes(X, Y), Z) !times(!plus(X, Y), Z) >= oplus(!times, !times Y Z) !times(X, oplus(Y, Z)) > oplus(!times, !times X Z) With these choices, we have: 1] !times(X, !times(Y, Z)) >= !times(otimes(X, Y), Z) because [2], by (Star) 2] !times*(X, !times(Y, Z)) >= !times(otimes(X, Y), Z) because [3], [6] and [13], by (Stat) 3] !times(Y, Z) > Z because [4], by definition 4] !times*(Y, Z) >= Z because [5], by (Select) 5] Z >= Z by (Meta) 6] !times*(X, !times(Y, Z)) >= otimes(X, Y) because !times > otimes, [7] and [9], by (Copy) 7] !times*(X, !times(Y, Z)) >= X because [8], by (Select) 8] X >= X by (Meta) 9] !times*(X, !times(Y, Z)) >= Y because [10], by (Select) 10] !times(Y, Z) >= Y because [11], by (Star) 11] !times*(Y, Z) >= Y because [12], by (Select) 12] Y >= Y by (Meta) 13] !times*(X, !times(Y, Z)) >= Z because [14], by (Select) 14] !times(Y, Z) >= Z because [4], by (Star) 15] !times(!plus(X, Y), Z) >= oplus(!times, !times Y Z) because [16], by (Star) 16] !times*(!plus(X, Y), Z) >= oplus(!times, !times Y Z) because !times > oplus, [17] and [24], by (Copy) 17] !times*(!plus(X, Y), Z) >= !times(X, Z) because [18], [20], [21] and [23], by (Stat) 18] !plus(X, Y) > X because [19], by definition 19] !plus*(X, Y) >= X because [8], by (Select) 20] Z >= Z by (Meta) 21] !times*(!plus(X, Y), Z) >= X because [22], by (Select) 22] !plus(X, Y) >= X because [19], by (Star) 23] !times*(!plus(X, Y), Z) >= Z because [20], by (Select) 24] !times*(!plus(X, Y), Z) >= !times(Y, Z) because [25], [20], [27] and [23], by (Stat) 25] !plus(X, Y) > Y because [26], by definition 26] !plus*(X, Y) >= Y because [12], by (Select) 27] !times*(!plus(X, Y), Z) >= Y because [28], by (Select) 28] !plus(X, Y) >= Y because [26], by (Star) 29] !times(X, oplus(Y, Z)) > oplus(!times, !times X Z) because [30], by definition 30] !times*(X, oplus(Y, Z)) >= oplus(!times, !times X Z) because !times > oplus, [31] and [37], by (Copy) 31] !times*(X, oplus(Y, Z)) >= !times(X, Y) because [32], [34] and [35], by (Stat) 32] oplus(Y, Z) > Y because [33], by definition 33] oplus*(Y, Z) >= Y because [12], by (Select) 34] !times*(X, oplus(Y, Z)) >= X because [8], by (Select) 35] !times*(X, oplus(Y, Z)) >= Y because [36], by (Select) 36] oplus(Y, Z) >= Y because [33], by (Star) 37] !times*(X, oplus(Y, Z)) >= !times(X, Z) because [38], [34] and [40], by (Stat) 38] oplus(Y, Z) > Z because [39], by definition 39] oplus*(Y, Z) >= Z because [20], by (Select) 40] !times*(X, oplus(Y, Z)) >= Z because [41], by (Select) 41] oplus(Y, Z) >= Z because [39], by (Star) We can thus remove the following rules: !times(X, oplus(Y, Z)) => oplus(!times(X, Y), !times(X, 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]): !times(X, !times(Y, Z)) >? !times(otimes(X, Y), Z) !times(!plus(X, Y), Z) >? oplus(!times(X, Z), !times(Y, Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[!times(x_1, x_2)]] = !times(x_2, x_1) [[otimes(x_1, x_2)]] = otimes(x_2, x_1) We choose Lex = {!times, otimes} and Mul = {!plus, oplus}, and the following precedence: !plus > !times = otimes > oplus Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: !times(X, !times(Y, Z)) >= !times(otimes(X, Y), Z) !times(!plus(X, Y), Z) > oplus(!times, !times Y Z) With these choices, we have: 1] !times(X, !times(Y, Z)) >= !times(otimes(X, Y), Z) because [2], by (Star) 2] !times*(X, !times(Y, Z)) >= !times(otimes(X, Y), Z) because [3], [6] and [14], by (Stat) 3] !times(Y, Z) > Z because [4], by definition 4] !times*(Y, Z) >= Z because [5], by (Select) 5] Z >= Z by (Meta) 6] !times*(X, !times(Y, Z)) >= otimes(X, Y) because !times = otimes, [7], [10] and [12], by (Stat) 7] !times(Y, Z) > Y because [8], by definition 8] !times*(Y, Z) >= Y because [9], by (Select) 9] Y >= Y by (Meta) 10] !times*(X, !times(Y, Z)) >= X because [11], by (Select) 11] X >= X by (Meta) 12] !times*(X, !times(Y, Z)) >= Y because [13], by (Select) 13] !times(Y, Z) >= Y because [8], by (Star) 14] !times*(X, !times(Y, Z)) >= Z because [15], by (Select) 15] !times(Y, Z) >= Z because [4], by (Star) 16] !times(!plus(X, Y), Z) > oplus(!times, !times Y Z) because [17], by definition 17] !times*(!plus(X, Y), Z) >= oplus(!times, !times Y Z) because !times > oplus, [18] and [25], by (Copy) 18] !times*(!plus(X, Y), Z) >= !times(X, Z) because [19], [21], [22] and [24], by (Stat) 19] !plus(X, Y) > X because [20], by definition 20] !plus*(X, Y) >= X because [11], by (Select) 21] Z >= Z by (Meta) 22] !times*(!plus(X, Y), Z) >= X because [23], by (Select) 23] !plus(X, Y) >= X because [20], by (Star) 24] !times*(!plus(X, Y), Z) >= Z because [21], by (Select) 25] !times*(!plus(X, Y), Z) >= !times(Y, Z) because [26], [21], [28] and [24], by (Stat) 26] !plus(X, Y) > Y because [27], by definition 27] !plus*(X, Y) >= Y because [9], by (Select) 28] !times*(!plus(X, Y), Z) >= Y because [29], by (Select) 29] !plus(X, Y) >= Y because [27], by (Star) We can thus remove the following rules: !times(!plus(X, Y), Z) => oplus(!times(X, Z), !times(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]): !times(X, !times(Y, Z)) >? !times(otimes(X, Y), Z) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !times = \y0y1.3 + y0 + 2y1 otimes = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[!times(_x0, !times(_x1, _x2))]] = 9 + x0 + 2x1 + 4x2 > 3 + x0 + x1 + 2x2 = [[!times(otimes(_x0, _x1), _x2)]] We can thus remove the following rules: !times(X, !times(Y, Z)) => !times(otimes(X, Y), Z) 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.