/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. !plus : [o * o] --> o !times : [o * o] --> o 0 : [] --> o i : [o] --> o !plus(X, 0) => X !plus(X, i(X)) => 0 !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) !times(X, !plus(Y, Z)) => !plus(!times(X, Y), !times(X, Z)) !times(!plus(X, Y), Z) => !plus(!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]): !plus(X, 0) >? X !plus(X, i(X)) >? 0 !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) !times(X, !plus(Y, Z)) >? !plus(!times(X, Y), !times(X, Z)) !times(!plus(X, Y), Z) >? !plus(!times(X, Z), !times(Y, Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ We choose Lex = {!plus} and Mul = {!times, i}, and the following precedence: i > !times > !plus Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: !plus(X, _|_) >= X !plus(X, i(X)) > _|_ !plus(!plus(X, Y), Z) > !plus(X, !plus(Y, Z)) !times(X, !plus(Y, Z)) >= !plus(!times(X, Y), !times(X, Z)) !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) With these choices, we have: 1] !plus(X, _|_) >= X because [2], by (Star) 2] !plus*(X, _|_) >= X because [3], by (Select) 3] X >= X by (Meta) 4] !plus(X, i(X)) > _|_ because [5], by definition 5] !plus*(X, i(X)) >= _|_ by (Bot) 6] !plus(!plus(X, Y), Z) > !plus(X, !plus(Y, Z)) because [7], by definition 7] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [8], [10] and [12], by (Stat) 8] !plus(X, Y) > X because [9], by definition 9] !plus*(X, Y) >= X because [3], by (Select) 10] !plus*(!plus(X, Y), Z) >= X because [11], by (Select) 11] !plus(X, Y) >= X because [9], by (Star) 12] !plus*(!plus(X, Y), Z) >= !plus(Y, Z) because [13], [16] and [18], by (Stat) 13] !plus(X, Y) > Y because [14], by definition 14] !plus*(X, Y) >= Y because [15], by (Select) 15] Y >= Y by (Meta) 16] !plus*(!plus(X, Y), Z) >= Y because [17], by (Select) 17] !plus(X, Y) >= Y because [14], by (Star) 18] !plus*(!plus(X, Y), Z) >= Z because [19], by (Select) 19] Z >= Z by (Meta) 20] !times(X, !plus(Y, Z)) >= !plus(!times(X, Y), !times(X, Z)) because [21], by (Star) 21] !times*(X, !plus(Y, Z)) >= !plus(!times(X, Y), !times(X, Z)) because !times > !plus, [22] and [26], by (Copy) 22] !times*(X, !plus(Y, Z)) >= !times(X, Y) because !times in Mul, [23] and [24], by (Stat) 23] X >= X by (Meta) 24] !plus(Y, Z) > Y because [25], by definition 25] !plus*(Y, Z) >= Y because [15], by (Select) 26] !times*(X, !plus(Y, Z)) >= !times(X, Z) because !times in Mul, [23] and [27], by (Stat) 27] !plus(Y, Z) > Z because [28], by definition 28] !plus*(Y, Z) >= Z because [19], by (Select) 29] !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) because [30], by (Star) 30] !times*(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) because !times > !plus, [31] and [33], by (Copy) 31] !times*(!plus(X, Y), Z) >= !times(X, Z) because !times in Mul, [8] and [32], by (Stat) 32] Z >= Z by (Meta) 33] !times*(!plus(X, Y), Z) >= !times(Y, Z) because !times in Mul, [13] and [32], by (Stat) We can thus remove the following rules: !plus(X, i(X)) => 0 !plus(!plus(X, Y), Z) => !plus(X, !plus(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]): !plus(X, 0) >? X !times(X, !plus(Y, Z)) >? !plus(!times(X, Y), !times(X, Z)) !times(!plus(X, Y), Z) >? !plus(!times(X, Z), !times(Y, Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {} and Mul = {!plus, !times, 0}, and the following precedence: !times > 0 > !plus With these choices, we have: 1] !plus(X, 0) >= X because [2], by (Star) 2] !plus*(X, 0) >= X because [3], by (Select) 3] X >= X by (Meta) 4] !times(X, !plus(Y, Z)) > !plus(!times(X, Y), !times(X, Z)) because [5], by definition 5] !times*(X, !plus(Y, Z)) >= !plus(!times(X, Y), !times(X, Z)) because !times > !plus, [6] and [11], by (Copy) 6] !times*(X, !plus(Y, Z)) >= !times(X, Y) because !times in Mul, [7] and [8], by (Stat) 7] X >= X by (Meta) 8] !plus(Y, Z) > Y because [9], by definition 9] !plus*(Y, Z) >= Y because [10], by (Select) 10] Y >= Y by (Meta) 11] !times*(X, !plus(Y, Z)) >= !times(X, Z) because !times in Mul, [7] and [12], by (Stat) 12] !plus(Y, Z) > Z because [13], by definition 13] !plus*(Y, Z) >= Z because [14], by (Select) 14] Z >= Z by (Meta) 15] !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) because [16], by (Star) 16] !times*(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) because !times > !plus, [17] and [21], by (Copy) 17] !times*(!plus(X, Y), Z) >= !times(X, Z) because !times in Mul, [18] and [20], by (Stat) 18] !plus(X, Y) > X because [19], by definition 19] !plus*(X, Y) >= X because [7], by (Select) 20] Z >= Z by (Meta) 21] !times*(!plus(X, Y), Z) >= !times(Y, Z) because !times in Mul, [22] and [20], by (Stat) 22] !plus(X, Y) > Y because [23], by definition 23] !plus*(X, Y) >= Y because [10], by (Select) We can thus remove the following rules: !times(X, !plus(Y, Z)) => !plus(!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]): !plus(X, 0) >? X !times(!plus(X, Y), Z) >? !plus(!times(X, Z), !times(Y, Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {} and Mul = {!plus, !times, 0}, and the following precedence: !times > !plus > 0 With these choices, we have: 1] !plus(X, 0) > X because [2], by definition 2] !plus*(X, 0) >= X because [3], by (Select) 3] X >= X by (Meta) 4] !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) because [5], by (Star) 5] !times*(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) because !times > !plus, [6] and [10], by (Copy) 6] !times*(!plus(X, Y), Z) >= !times(X, Z) because !times in Mul, [7] and [9], by (Stat) 7] !plus(X, Y) > X because [8], by definition 8] !plus*(X, Y) >= X because [3], by (Select) 9] Z >= Z by (Meta) 10] !times*(!plus(X, Y), Z) >= !times(Y, Z) because !times in Mul, [11] and [9], by (Stat) 11] !plus(X, Y) > Y because [12], by definition 12] !plus*(X, Y) >= Y because [13], by (Select) 13] Y >= Y by (Meta) We can thus remove the following rules: !plus(X, 0) => 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(!plus(X, Y), Z) >? !plus(!times(X, Z), !times(Y, Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {} and Mul = {!plus, !times}, and the following precedence: !times > !plus With these choices, we have: 1] !times(!plus(X, Y), Z) > !plus(!times(X, Z), !times(Y, Z)) because [2], by definition 2] !times*(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) because !times > !plus, [3] and [8], by (Copy) 3] !times*(!plus(X, Y), Z) >= !times(X, Z) because !times in Mul, [4] and [7], by (Stat) 4] !plus(X, Y) > X because [5], by definition 5] !plus*(X, Y) >= X because [6], by (Select) 6] X >= X by (Meta) 7] Z >= Z by (Meta) 8] !times*(!plus(X, Y), Z) >= !times(Y, Z) because !times in Mul, [9] and [7], by (Stat) 9] !plus(X, Y) > Y because [10], by definition 10] !plus*(X, Y) >= Y because [11], by (Select) 11] Y >= Y by (Meta) We can thus remove the following rules: !times(!plus(X, Y), Z) => !plus(!times(X, Z), !times(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.