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