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