0.24/1.31 YES 0.24/1.34 We consider the system theBenchmark. 0.24/1.34 0.24/1.34 Alphabet: 0.24/1.34 0.24/1.34 mult : [N * N] --> N 0.24/1.34 plus : [N * N] --> N 0.24/1.34 s : [N] --> N 0.24/1.34 z : [] --> N 0.24/1.34 0.24/1.34 Rules: 0.24/1.34 0.24/1.34 plus(z, x) => x 0.24/1.34 plus(s(x), y) => plus(x, s(y)) 0.24/1.34 plus(plus(x, y), u) => plus(x, plus(y, u)) 0.24/1.34 mult(z, x) => z 0.24/1.34 mult(s(x), y) => plus(mult(x, y), y) 0.24/1.34 mult(plus(x, y), u) => plus(mult(x, u), mult(y, u)) 0.24/1.34 0.24/1.34 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 0.24/1.34 0.24/1.34 We use rule removal, following [Kop12, Theorem 2.23]. 0.24/1.34 0.24/1.34 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.24/1.34 0.24/1.34 plus(z, X) >? X 0.24/1.34 plus(s(X), Y) >? plus(X, s(Y)) 0.24/1.34 plus(plus(X, Y), Z) >? plus(X, plus(Y, Z)) 0.24/1.34 mult(z, X) >? z 0.24/1.34 mult(s(X), Y) >? plus(mult(X, Y), Y) 0.24/1.34 mult(plus(X, Y), Z) >? plus(mult(X, Z), mult(Y, Z)) 0.24/1.34 0.24/1.34 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.24/1.34 0.24/1.34 Argument functions: 0.24/1.34 0.24/1.34 [[z]] = _|_ 0.24/1.34 0.24/1.34 We choose Lex = {plus} and Mul = {mult, s}, and the following precedence: mult > plus > s 0.24/1.34 0.24/1.34 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.24/1.34 0.24/1.34 plus(_|_, X) >= X 0.24/1.34 plus(s(X), Y) >= plus(X, s(Y)) 0.24/1.34 plus(plus(X, Y), Z) > plus(X, plus(Y, Z)) 0.24/1.34 mult(_|_, X) >= _|_ 0.24/1.34 mult(s(X), Y) >= plus(mult(X, Y), Y) 0.24/1.34 mult(plus(X, Y), Z) > plus(mult(X, Z), mult(Y, Z)) 0.24/1.34 0.24/1.34 With these choices, we have: 0.24/1.34 0.24/1.34 1] plus(_|_, X) >= X because [2], by (Star) 0.24/1.34 2] plus*(_|_, X) >= X because [3], by (Select) 0.24/1.34 3] X >= X by (Meta) 0.24/1.34 0.24/1.34 4] plus(s(X), Y) >= plus(X, s(Y)) because [5], by (Star) 0.24/1.34 5] plus*(s(X), Y) >= plus(X, s(Y)) because [6], [9] and [11], by (Stat) 0.24/1.34 6] s(X) > X because [7], by definition 0.24/1.34 7] s*(X) >= X because [8], by (Select) 0.24/1.34 8] X >= X by (Meta) 0.24/1.34 9] plus*(s(X), Y) >= X because [10], by (Select) 0.24/1.34 10] s(X) >= X because [7], by (Star) 0.24/1.34 11] plus*(s(X), Y) >= s(Y) because plus > s and [12], by (Copy) 0.24/1.34 12] plus*(s(X), Y) >= Y because [13], by (Select) 0.24/1.34 13] Y >= Y by (Meta) 0.24/1.34 0.24/1.34 14] plus(plus(X, Y), Z) > plus(X, plus(Y, Z)) because [15], by definition 0.24/1.34 15] plus*(plus(X, Y), Z) >= plus(X, plus(Y, Z)) because [16], [19] and [21], by (Stat) 0.24/1.34 16] plus(X, Y) > X because [17], by definition 0.24/1.34 17] plus*(X, Y) >= X because [18], by (Select) 0.24/1.34 18] X >= X by (Meta) 0.24/1.34 19] plus*(plus(X, Y), Z) >= X because [20], by (Select) 0.24/1.34 20] plus(X, Y) >= X because [17], by (Star) 0.24/1.34 21] plus*(plus(X, Y), Z) >= plus(Y, Z) because [22], [25] and [27], by (Stat) 0.24/1.34 22] plus(X, Y) > Y because [23], by definition 0.24/1.34 23] plus*(X, Y) >= Y because [24], by (Select) 0.24/1.34 24] Y >= Y by (Meta) 0.24/1.34 25] plus*(plus(X, Y), Z) >= Y because [26], by (Select) 0.24/1.34 26] plus(X, Y) >= Y because [23], by (Star) 0.24/1.34 27] plus*(plus(X, Y), Z) >= Z because [28], by (Select) 0.24/1.34 28] Z >= Z by (Meta) 0.24/1.34 0.24/1.34 29] mult(_|_, X) >= _|_ by (Bot) 0.24/1.34 0.24/1.34 30] mult(s(X), Y) >= plus(mult(X, Y), Y) because [31], by (Star) 0.24/1.34 31] mult*(s(X), Y) >= plus(mult(X, Y), Y) because mult > plus, [32] and [37], by (Copy) 0.24/1.34 32] mult*(s(X), Y) >= mult(X, Y) because mult in Mul, [33] and [36], by (Stat) 0.24/1.34 33] s(X) > X because [34], by definition 0.24/1.34 34] s*(X) >= X because [35], by (Select) 0.24/1.34 35] X >= X by (Meta) 0.24/1.34 36] Y >= Y by (Meta) 0.24/1.34 37] mult*(s(X), Y) >= Y because [36], by (Select) 0.24/1.34 0.24/1.34 38] mult(plus(X, Y), Z) > plus(mult(X, Z), mult(Y, Z)) because [39], by definition 0.24/1.34 39] mult*(plus(X, Y), Z) >= plus(mult(X, Z), mult(Y, Z)) because mult > plus, [40] and [45], by (Copy) 0.24/1.34 40] mult*(plus(X, Y), Z) >= mult(X, Z) because mult in Mul, [41] and [44], by (Stat) 0.24/1.34 41] plus(X, Y) > X because [42], by definition 0.24/1.34 42] plus*(X, Y) >= X because [43], by (Select) 0.24/1.34 43] X >= X by (Meta) 0.24/1.34 44] Z >= Z by (Meta) 0.24/1.34 45] mult*(plus(X, Y), Z) >= mult(Y, Z) because mult in Mul, [46] and [44], by (Stat) 0.24/1.34 46] plus(X, Y) > Y because [47], by definition 0.24/1.34 47] plus*(X, Y) >= Y because [48], by (Select) 0.24/1.34 48] Y >= Y by (Meta) 0.24/1.34 0.24/1.34 We can thus remove the following rules: 0.24/1.34 0.24/1.34 plus(plus(X, Y), Z) => plus(X, plus(Y, Z)) 0.24/1.34 mult(plus(X, Y), Z) => plus(mult(X, Z), mult(Y, Z)) 0.24/1.34 0.24/1.34 We use rule removal, following [Kop12, Theorem 2.23]. 0.24/1.34 0.24/1.34 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.24/1.34 0.24/1.34 plus(z, X) >? X 0.24/1.34 plus(s(X), Y) >? plus(X, s(Y)) 0.24/1.34 mult(z, X) >? z 0.24/1.34 mult(s(X), Y) >? plus(mult(X, Y), Y) 0.24/1.34 0.24/1.34 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.24/1.34 0.24/1.34 Argument functions: 0.24/1.34 0.24/1.34 [[z]] = _|_ 0.24/1.34 0.24/1.34 We choose Lex = {mult, plus} and Mul = {s}, and the following precedence: mult > plus > s 0.24/1.34 0.24/1.34 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.24/1.34 0.24/1.34 plus(_|_, X) > X 0.24/1.34 plus(s(X), Y) >= plus(X, s(Y)) 0.24/1.34 mult(_|_, X) >= _|_ 0.24/1.34 mult(s(X), Y) >= plus(mult(X, Y), Y) 0.24/1.34 0.24/1.34 With these choices, we have: 0.24/1.34 0.24/1.34 1] plus(_|_, X) > X because [2], by definition 0.24/1.34 2] plus*(_|_, X) >= X because [3], by (Select) 0.24/1.34 3] X >= X by (Meta) 0.24/1.34 0.24/1.34 4] plus(s(X), Y) >= plus(X, s(Y)) because [5], by (Star) 0.24/1.34 5] plus*(s(X), Y) >= plus(X, s(Y)) because [6], [9] and [11], by (Stat) 0.24/1.34 6] s(X) > X because [7], by definition 0.24/1.34 7] s*(X) >= X because [8], by (Select) 0.24/1.34 8] X >= X by (Meta) 0.24/1.34 9] plus*(s(X), Y) >= X because [10], by (Select) 0.24/1.34 10] s(X) >= X because [7], by (Star) 0.24/1.34 11] plus*(s(X), Y) >= s(Y) because plus > s and [12], by (Copy) 0.24/1.34 12] plus*(s(X), Y) >= Y because [13], by (Select) 0.24/1.34 13] Y >= Y by (Meta) 0.24/1.34 0.24/1.34 14] mult(_|_, X) >= _|_ by (Bot) 0.24/1.34 0.24/1.34 15] mult(s(X), Y) >= plus(mult(X, Y), Y) because [16], by (Star) 0.24/1.34 16] mult*(s(X), Y) >= plus(mult(X, Y), Y) because mult > plus, [17] and [23], by (Copy) 0.24/1.34 17] mult*(s(X), Y) >= mult(X, Y) because [18], [21] and [23], by (Stat) 0.24/1.34 18] s(X) > X because [19], by definition 0.24/1.34 19] s*(X) >= X because [20], by (Select) 0.24/1.34 20] X >= X by (Meta) 0.24/1.34 21] mult*(s(X), Y) >= X because [22], by (Select) 0.24/1.34 22] s(X) >= X because [19], by (Star) 0.24/1.34 23] mult*(s(X), Y) >= Y because [24], by (Select) 0.24/1.34 24] Y >= Y by (Meta) 0.24/1.34 0.24/1.34 We can thus remove the following rules: 0.24/1.34 0.24/1.34 plus(z, X) => X 0.24/1.34 0.24/1.34 We use rule removal, following [Kop12, Theorem 2.23]. 0.24/1.34 0.24/1.34 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.24/1.34 0.24/1.34 plus(s(X), Y) >? plus(X, s(Y)) 0.24/1.34 mult(z, X) >? z 0.24/1.34 mult(s(X), Y) >? plus(mult(X, Y), Y) 0.24/1.34 0.24/1.34 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.24/1.34 0.24/1.34 Argument functions: 0.24/1.34 0.24/1.34 [[z]] = _|_ 0.24/1.34 0.24/1.34 We choose Lex = {plus} and Mul = {mult, s}, and the following precedence: mult > plus > s 0.24/1.34 0.24/1.34 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.24/1.34 0.24/1.34 plus(s(X), Y) >= plus(X, s(Y)) 0.24/1.34 mult(_|_, X) > _|_ 0.24/1.34 mult(s(X), Y) >= plus(mult(X, Y), Y) 0.24/1.34 0.24/1.34 With these choices, we have: 0.24/1.34 0.24/1.34 1] plus(s(X), Y) >= plus(X, s(Y)) because [2], by (Star) 0.24/1.34 2] plus*(s(X), Y) >= plus(X, s(Y)) because [3], [6] and [8], by (Stat) 0.24/1.34 3] s(X) > X because [4], by definition 0.24/1.34 4] s*(X) >= X because [5], by (Select) 0.24/1.34 5] X >= X by (Meta) 0.24/1.34 6] plus*(s(X), Y) >= X because [7], by (Select) 0.24/1.34 7] s(X) >= X because [4], by (Star) 0.24/1.34 8] plus*(s(X), Y) >= s(Y) because plus > s and [9], by (Copy) 0.24/1.34 9] plus*(s(X), Y) >= Y because [10], by (Select) 0.24/1.34 10] Y >= Y by (Meta) 0.24/1.34 0.24/1.34 11] mult(_|_, X) > _|_ because [12], by definition 0.24/1.34 12] mult*(_|_, X) >= _|_ by (Bot) 0.24/1.34 0.24/1.34 13] mult(s(X), Y) >= plus(mult(X, Y), Y) because [14], by (Star) 0.24/1.34 14] mult*(s(X), Y) >= plus(mult(X, Y), Y) because mult > plus, [15] and [20], by (Copy) 0.24/1.34 15] mult*(s(X), Y) >= mult(X, Y) because mult in Mul, [16] and [19], by (Stat) 0.24/1.34 16] s(X) > X because [17], by definition 0.24/1.34 17] s*(X) >= X because [18], by (Select) 0.24/1.34 18] X >= X by (Meta) 0.24/1.34 19] Y >= Y by (Meta) 0.24/1.34 20] mult*(s(X), Y) >= Y because [19], by (Select) 0.24/1.34 0.24/1.34 We can thus remove the following rules: 0.24/1.34 0.24/1.34 mult(z, X) => z 0.24/1.34 0.24/1.34 We use rule removal, following [Kop12, Theorem 2.23]. 0.24/1.34 0.24/1.34 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.24/1.34 0.24/1.34 plus(s(X), Y) >? plus(X, s(Y)) 0.24/1.34 mult(s(X), Y) >? plus(mult(X, Y), Y) 0.24/1.34 0.24/1.34 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.24/1.34 0.24/1.34 We choose Lex = {plus} and Mul = {mult, s}, and the following precedence: mult > plus > s 0.24/1.34 0.24/1.34 With these choices, we have: 0.24/1.34 0.24/1.34 1] plus(s(X), Y) >= plus(X, s(Y)) because [2], by (Star) 0.24/1.34 2] plus*(s(X), Y) >= plus(X, s(Y)) because [3], [6] and [8], by (Stat) 0.24/1.34 3] s(X) > X because [4], by definition 0.24/1.34 4] s*(X) >= X because [5], by (Select) 0.24/1.34 5] X >= X by (Meta) 0.24/1.34 6] plus*(s(X), Y) >= X because [7], by (Select) 0.24/1.34 7] s(X) >= X because [4], by (Star) 0.24/1.34 8] plus*(s(X), Y) >= s(Y) because plus > s and [9], by (Copy) 0.24/1.34 9] plus*(s(X), Y) >= Y because [10], by (Select) 0.24/1.34 10] Y >= Y by (Meta) 0.24/1.34 0.24/1.34 11] mult(s(X), Y) > plus(mult(X, Y), Y) because [12], by definition 0.24/1.34 12] mult*(s(X), Y) >= plus(mult(X, Y), Y) because mult > plus, [13] and [18], by (Copy) 0.24/1.34 13] mult*(s(X), Y) >= mult(X, Y) because mult in Mul, [14] and [17], by (Stat) 0.24/1.34 14] s(X) > X because [15], by definition 0.24/1.34 15] s*(X) >= X because [16], by (Select) 0.24/1.34 16] X >= X by (Meta) 0.24/1.34 17] Y >= Y by (Meta) 0.24/1.34 18] mult*(s(X), Y) >= Y because [17], by (Select) 0.24/1.34 0.24/1.34 We can thus remove the following rules: 0.24/1.34 0.24/1.34 mult(s(X), Y) => plus(mult(X, Y), Y) 0.24/1.34 0.24/1.34 We use rule removal, following [Kop12, Theorem 2.23]. 0.24/1.34 0.24/1.34 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.24/1.34 0.24/1.34 plus(s(X), Y) >? plus(X, s(Y)) 0.24/1.34 0.24/1.34 We orient these requirements with a polynomial interpretation in the natural numbers. 0.24/1.34 0.24/1.34 The following interpretation satisfies the requirements: 0.24/1.34 0.24/1.34 plus = \y0y1.y1 + 2y0 0.24/1.34 s = \y0.2 + y0 0.24/1.34 0.24/1.34 Using this interpretation, the requirements translate to: 0.24/1.34 0.24/1.34 [[plus(s(_x0), _x1)]] = 4 + x1 + 2x0 > 2 + x1 + 2x0 = [[plus(_x0, s(_x1))]] 0.24/1.34 0.24/1.34 We can thus remove the following rules: 0.24/1.34 0.24/1.34 plus(s(X), Y) => plus(X, s(Y)) 0.24/1.34 0.24/1.34 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. 0.24/1.34 0.24/1.34 0.24/1.34 +++ Citations +++ 0.24/1.34 0.24/1.34 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 0.24/1.34 EOF