11.52/11.61 YES 11.61/11.64 We consider the system theBenchmark. 11.61/11.64 11.61/11.64 Alphabet: 11.61/11.64 11.61/11.64 0 : [] --> nat 11.61/11.64 plus : [nat * nat] --> nat 11.61/11.64 rec : [nat * nat * nat -> nat -> nat] --> nat 11.61/11.64 s : [nat] --> nat 11.61/11.64 succ : [] --> nat -> nat -> nat 11.61/11.64 xap : [nat -> nat -> nat * nat] --> nat -> nat 11.61/11.64 yap : [nat -> nat * nat] --> nat 11.61/11.64 11.61/11.64 Rules: 11.61/11.64 11.61/11.64 rec(0, x, /\y./\z.yap(xap(f, y), z)) => x 11.61/11.64 rec(s(x), y, /\z./\u.yap(xap(f, z), u)) => yap(xap(f, x), rec(x, y, /\v./\w.yap(xap(f, v), w))) 11.61/11.64 succ x y => s(y) 11.61/11.64 plus(x, y) => rec(x, y, succ) 11.61/11.64 xap(f, x) => f x 11.61/11.64 yap(f, x) => f x 11.61/11.64 11.61/11.64 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 11.61/11.64 11.61/11.64 Symbol xap is an encoding for application that is only used in innocuous ways. We can simplify the program (without losing non-termination) by removing it. This gives: 11.61/11.64 11.61/11.64 Alphabet: 11.61/11.64 11.61/11.64 0 : [] --> nat 11.61/11.64 plus : [nat * nat] --> nat 11.61/11.64 rec : [nat * nat * nat -> nat -> nat] --> nat 11.61/11.64 s : [nat] --> nat 11.61/11.64 succ : [] --> nat -> nat -> nat 11.61/11.64 yap : [nat -> nat * nat] --> nat 11.61/11.64 11.61/11.64 Rules: 11.61/11.64 11.61/11.64 rec(0, X, /\x./\y.yap(F(x), y)) => X 11.61/11.64 rec(s(X), Y, /\x./\y.yap(F(x), y)) => yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 11.61/11.64 succ X Y => s(Y) 11.61/11.64 plus(X, Y) => rec(X, Y, succ) 11.61/11.64 yap(F, X) => F X 11.61/11.64 11.61/11.64 We use rule removal, following [Kop12, Theorem 2.23]. 11.61/11.64 11.61/11.64 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 11.61/11.64 11.61/11.64 rec(0, X, /\x./\y.yap(F(x), y)) >? X 11.61/11.64 rec(s(X), Y, /\x./\y.yap(F(x), y)) >? yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 11.61/11.64 succ X Y >? s(Y) 11.61/11.64 plus(X, Y) >? rec(X, Y, succ) 11.61/11.64 yap(F, X) >? F X 11.61/11.64 11.61/11.64 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 11.61/11.64 11.61/11.64 Argument functions: 11.61/11.64 11.61/11.64 [[succ]] = _|_ 11.61/11.64 11.61/11.64 We choose Lex = {} and Mul = {0, @_{o -> o -> o}, @_{o -> o}, plus, rec, s, yap}, and the following precedence: 0 > @_{o -> o -> o} > s > plus > rec > yap > @_{o -> o} 11.61/11.64 11.61/11.64 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 11.61/11.64 11.61/11.64 rec(0, X, /\x./\y.yap(F(x), y)) >= X 11.61/11.64 rec(s(X), Y, /\x./\y.yap(F(x), y)) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) 11.61/11.64 @_{o -> o}(@_{o -> o -> o}(_|_, X), Y) >= s(Y) 11.61/11.64 plus(X, Y) > rec(X, Y, _|_) 11.61/11.64 yap(F, X) >= @_{o -> o}(F, X) 11.61/11.64 11.61/11.64 With these choices, we have: 11.61/11.64 11.61/11.64 1] rec(0, X, /\x./\y.yap(F(x), y)) >= X because [2], by (Star) 11.61/11.64 2] rec*(0, X, /\x./\y.yap(F(x), y)) >= X because [3], by (Select) 11.61/11.64 3] X >= X by (Meta) 11.61/11.64 11.61/11.64 4] rec(s(X), Y, /\x./\y.yap(F(x), y)) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) because [5], by (Star) 11.61/11.64 5] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) because [6], by (Select) 11.61/11.64 6] yap(F(rec*(s(X), Y, /\x./\y.yap(F(x), y))), rec*(s(X), Y, /\z./\u.yap(F(z), u))) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) because yap in Mul, [7] and [12], by (Fun) 11.61/11.64 7] F(rec*(s(X), Y, /\x./\y.yap(F(x), y))) >= F(X) because [8], by (Meta) 11.61/11.64 8] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= X because [9], by (Select) 11.61/11.64 9] s(X) >= X because [10], by (Star) 11.61/11.64 10] s*(X) >= X because [11], by (Select) 11.61/11.64 11] X >= X by (Meta) 11.61/11.64 12] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= rec(X, Y, /\x./\y.yap(F(x), y)) because rec in Mul, [13], [15] and [16], by (Stat) 11.61/11.64 13] s(X) > X because [14], by definition 11.61/11.64 14] s*(X) >= X because [11], by (Select) 11.61/11.64 15] Y >= Y by (Meta) 11.61/11.64 16] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [17], by (Abs) 11.61/11.64 17] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [18], by (Abs) 11.61/11.64 18] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [19] and [21], by (Fun) 11.61/11.64 19] F(y) >= F(y) because [20], by (Meta) 11.61/11.64 20] y >= y by (Var) 11.61/11.64 21] x >= x by (Var) 11.61/11.64 11.61/11.64 22] @_{o -> o}(@_{o -> o -> o}(_|_, X), Y) >= s(Y) because [23], by (Star) 11.61/11.64 23] @_{o -> o}*(@_{o -> o -> o}(_|_, X), Y) >= s(Y) because [24], by (Select) 11.61/11.64 24] @_{o -> o -> o}(_|_, X) @_{o -> o}*(@_{o -> o -> o}(_|_, X), Y) >= s(Y) because [25] 11.61/11.64 25] @_{o -> o -> o}*(_|_, X, @_{o -> o}*(@_{o -> o -> o}(_|_, X), Y)) >= s(Y) because @_{o -> o -> o} > s and [26], by (Copy) 11.61/11.64 26] @_{o -> o -> o}*(_|_, X, @_{o -> o}*(@_{o -> o -> o}(_|_, X), Y)) >= Y because [27], by (Select) 11.61/11.64 27] @_{o -> o}*(@_{o -> o -> o}(_|_, X), Y) >= Y because [28], by (Select) 11.61/11.64 28] Y >= Y by (Meta) 11.61/11.64 11.61/11.64 29] plus(X, Y) > rec(X, Y, _|_) because [30], by definition 11.61/11.64 30] plus*(X, Y) >= rec(X, Y, _|_) because plus > rec, [31], [33] and [35], by (Copy) 11.61/11.64 31] plus*(X, Y) >= X because [32], by (Select) 11.61/11.64 32] X >= X by (Meta) 11.61/11.64 33] plus*(X, Y) >= Y because [34], by (Select) 11.61/11.64 34] Y >= Y by (Meta) 11.61/11.64 35] plus*(X, Y) >= _|_ by (Bot) 11.61/11.64 11.61/11.64 36] yap(F, X) >= @_{o -> o}(F, X) because [37], by (Star) 11.61/11.64 37] yap*(F, X) >= @_{o -> o}(F, X) because yap > @_{o -> o}, [38] and [40], by (Copy) 11.61/11.64 38] yap*(F, X) >= F because [39], by (Select) 11.61/11.64 39] F >= F by (Meta) 11.61/11.64 40] yap*(F, X) >= X because [41], by (Select) 11.61/11.64 41] X >= X by (Meta) 11.61/11.64 11.61/11.64 We can thus remove the following rules: 11.61/11.64 11.61/11.64 plus(X, Y) => rec(X, Y, succ) 11.61/11.64 11.61/11.64 We use rule removal, following [Kop12, Theorem 2.23]. 11.61/11.64 11.61/11.64 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 11.61/11.64 11.61/11.64 rec(0, X, /\x./\y.yap(F(x), y)) >? X 11.61/11.64 rec(s(X), Y, /\x./\y.yap(F(x), y)) >? yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 11.61/11.64 succ(X, Y) >? s(Y) 11.61/11.64 yap(F, X) >? F X 11.61/11.64 11.61/11.64 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 11.61/11.64 11.61/11.64 We choose Lex = {} and Mul = {0, @_{o -> o}, rec, s, succ, yap}, and the following precedence: 0 > rec > succ > s > @_{o -> o} = yap 11.61/11.64 11.61/11.64 With these choices, we have: 11.61/11.64 11.61/11.64 1] rec(0, X, /\x./\y.yap(F(x), y)) > X because [2], by definition 11.61/11.64 2] rec*(0, X, /\x./\y.yap(F(x), y)) >= X because [3], by (Select) 11.61/11.64 3] X >= X by (Meta) 11.61/11.64 11.61/11.64 4] rec(s(X), Y, /\x./\y.yap(F(x), y)) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) because [5], by (Star) 11.61/11.64 5] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) because rec > yap, [6] and [13], by (Copy) 11.61/11.64 6] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= F(X) because [7], by (Select) 11.61/11.64 7] /\x.yap(F(rec*(s(X), Y, /\y./\z.yap(F(y), z))), x) >= F(X) because [8], by (Eta)[Kop13:2] 11.61/11.64 8] F(rec*(s(X), Y, /\x./\y.yap(F(x), y))) >= F(X) because [9], by (Meta) 11.61/11.64 9] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= X because [10], by (Select) 11.61/11.64 10] s(X) >= X because [11], by (Star) 11.61/11.64 11] s*(X) >= X because [12], by (Select) 11.61/11.64 12] X >= X by (Meta) 11.61/11.64 13] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= rec(X, Y, /\x./\y.yap(F(x), y)) because rec in Mul, [14], [16] and [17], by (Stat) 11.61/11.64 14] s(X) > X because [15], by definition 11.61/11.64 15] s*(X) >= X because [12], by (Select) 11.61/11.64 16] Y >= Y by (Meta) 11.61/11.64 17] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [18], by (Abs) 11.61/11.64 18] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [19], by (Abs) 11.61/11.64 19] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [20] and [22], by (Fun) 11.61/11.64 20] F(y) >= F(y) because [21], by (Meta) 11.61/11.64 21] y >= y by (Var) 11.61/11.64 22] x >= x by (Var) 11.61/11.64 11.61/11.64 23] succ(X, Y) >= s(Y) because [24], by (Star) 11.61/11.64 24] succ*(X, Y) >= s(Y) because succ > s and [25], by (Copy) 11.61/11.64 25] succ*(X, Y) >= Y because [26], by (Select) 11.61/11.64 26] Y >= Y by (Meta) 11.61/11.64 11.61/11.64 27] yap(F, X) >= @_{o -> o}(F, X) because yap = @_{o -> o}, yap in Mul, [28] and [29], by (Fun) 11.61/11.64 28] F >= F by (Meta) 11.61/11.64 29] X >= X by (Meta) 11.61/11.64 11.61/11.64 We can thus remove the following rules: 11.61/11.64 11.61/11.64 rec(0, X, /\x./\y.yap(F(x), y)) => X 11.61/11.64 11.61/11.64 We use rule removal, following [Kop12, Theorem 2.23]. 11.61/11.64 11.61/11.64 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 11.61/11.64 11.61/11.64 rec(s(X), Y, /\x./\y.yap(F(x), y)) >? yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 11.61/11.64 succ(X, Y) >? s(Y) 11.61/11.64 yap(F, X) >? F X 11.61/11.64 11.61/11.64 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 11.61/11.64 11.61/11.64 We choose Lex = {} and Mul = {@_{o -> o}, rec, s, succ, yap}, and the following precedence: succ > s > rec > @_{o -> o} = yap 11.61/11.64 11.61/11.64 With these choices, we have: 11.61/11.64 11.61/11.64 1] rec(s(X), Y, /\x./\y.yap(F(x), y)) > yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) because [2], by definition 11.61/11.64 2] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) because rec > yap, [3] and [10], by (Copy) 11.61/11.64 3] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= F(X) because [4], by (Select) 11.61/11.64 4] /\x.yap(F(rec*(s(X), Y, /\y./\z.yap(F(y), z))), x) >= F(X) because [5], by (Eta)[Kop13:2] 11.61/11.64 5] F(rec*(s(X), Y, /\x./\y.yap(F(x), y))) >= F(X) because [6], by (Meta) 11.61/11.64 6] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= X because [7], by (Select) 11.61/11.64 7] s(X) >= X because [8], by (Star) 11.61/11.64 8] s*(X) >= X because [9], by (Select) 11.61/11.64 9] X >= X by (Meta) 11.61/11.64 10] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= rec(X, Y, /\x./\y.yap(F(x), y)) because rec in Mul, [11], [13] and [14], by (Stat) 11.61/11.64 11] s(X) > X because [12], by definition 11.61/11.64 12] s*(X) >= X because [9], by (Select) 11.61/11.64 13] Y >= Y by (Meta) 11.61/11.64 14] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [15], by (Abs) 11.61/11.64 15] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [16], by (Abs) 11.61/11.64 16] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [17] and [19], by (Fun) 11.61/11.64 17] F(y) >= F(y) because [18], by (Meta) 11.61/11.64 18] y >= y by (Var) 11.61/11.64 19] x >= x by (Var) 11.61/11.64 11.61/11.64 20] succ(X, Y) >= s(Y) because [21], by (Star) 11.61/11.64 21] succ*(X, Y) >= s(Y) because succ > s and [22], by (Copy) 11.61/11.64 22] succ*(X, Y) >= Y because [23], by (Select) 11.61/11.64 23] Y >= Y by (Meta) 11.61/11.64 11.61/11.64 24] yap(F, X) >= @_{o -> o}(F, X) because yap = @_{o -> o}, yap in Mul, [25] and [26], by (Fun) 11.61/11.64 25] F >= F by (Meta) 11.61/11.64 26] X >= X by (Meta) 11.61/11.64 11.61/11.64 We can thus remove the following rules: 11.61/11.64 11.61/11.64 rec(s(X), Y, /\x./\y.yap(F(x), y)) => yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 11.61/11.64 11.61/11.64 We use rule removal, following [Kop12, Theorem 2.23]. 11.61/11.64 11.61/11.64 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 11.61/11.64 11.61/11.64 succ(X, Y) >? s(Y) 11.61/11.64 yap(F, X) >? F X 11.61/11.64 11.61/11.64 We orient these requirements with a polynomial interpretation in the natural numbers. 11.61/11.64 11.61/11.64 The following interpretation satisfies the requirements: 11.61/11.64 11.61/11.64 s = \y0.y0 11.61/11.64 succ = \y0y1.3 + y0 + 3y1 11.61/11.64 yap = \G0y1.3 + y1 + G0(y1) 11.61/11.64 11.61/11.64 Using this interpretation, the requirements translate to: 11.61/11.64 11.61/11.64 [[succ(_x0, _x1)]] = 3 + x0 + 3x1 > x1 = [[s(_x1)]] 11.61/11.64 [[yap(_F0, _x1)]] = 3 + x1 + F0(x1) > x1 + F0(x1) = [[_F0 _x1]] 11.61/11.64 11.61/11.64 We can thus remove the following rules: 11.61/11.64 11.61/11.64 succ(X, Y) => s(Y) 11.61/11.64 yap(F, X) => F X 11.61/11.64 11.61/11.64 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. 11.61/11.64 11.61/11.64 11.61/11.64 +++ Citations +++ 11.61/11.64 11.61/11.64 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 11.61/11.64 [Kop13:2] C. Kop. StarHorpo with an Eta-Rule. Unpublished manuscript, http://cl-informatik.uibk.ac.at/users/kop/etahorpo.pdf, 2013. 11.61/11.65 EOF