9.27/9.32 YES 9.27/9.33 We consider the system theBenchmark. 9.27/9.33 9.27/9.33 Alphabet: 9.27/9.33 9.27/9.33 0 : [] --> nat 9.27/9.33 rec : [nat * a * nat -> a -> a] --> a 9.27/9.33 s : [nat] --> nat 9.27/9.33 xap : [nat -> a -> a * nat] --> a -> a 9.27/9.33 yap : [a -> a * a] --> a 9.27/9.33 9.27/9.33 Rules: 9.27/9.33 9.27/9.33 rec(0, x, /\y./\z.yap(xap(f, y), z)) => x 9.27/9.33 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))) 9.27/9.33 xap(f, x) => f x 9.27/9.33 yap(f, x) => f x 9.27/9.33 9.27/9.33 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 9.27/9.33 9.27/9.33 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: 9.27/9.33 9.27/9.33 Alphabet: 9.27/9.33 9.27/9.33 0 : [] --> nat 9.27/9.33 rec : [nat * a * nat -> a -> a] --> a 9.27/9.33 s : [nat] --> nat 9.27/9.33 yap : [a -> a * a] --> a 9.27/9.33 9.27/9.33 Rules: 9.27/9.33 9.27/9.33 rec(0, X, /\x./\y.yap(F(x), y)) => X 9.27/9.33 rec(s(X), Y, /\x./\y.yap(F(x), y)) => yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 9.27/9.33 yap(F, X) => F X 9.27/9.33 9.27/9.33 We use rule removal, following [Kop12, Theorem 2.23]. 9.27/9.33 9.27/9.33 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 9.27/9.33 9.27/9.33 rec(0, X, /\x./\y.yap(F(x), y)) >? X 9.27/9.33 rec(s(X), Y, /\x./\y.yap(F(x), y)) >? yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 9.27/9.33 yap(F, X) >? F X 9.27/9.33 9.27/9.33 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 9.27/9.33 9.27/9.33 We choose Lex = {} and Mul = {0, @_{o -> o}, rec, s, yap}, and the following precedence: 0 > rec > s > yap > @_{o -> o} 9.27/9.33 9.27/9.33 With these choices, we have: 9.27/9.33 9.27/9.33 1] rec(0, X, /\x./\y.yap(F(x), y)) > X because [2], by definition 9.27/9.33 2] rec*(0, X, /\x./\y.yap(F(x), y)) >= X because [3], by (Select) 9.27/9.33 3] X >= X by (Meta) 9.27/9.33 9.27/9.33 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) 9.27/9.33 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) 9.27/9.33 6] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= F(X) because [7], by (Select) 9.27/9.33 7] /\x.yap(F(rec*(s(X), Y, /\y./\z.yap(F(y), z))), x) >= F(X) because [8], by (Eta)[Kop13:2] 9.27/9.33 8] F(rec*(s(X), Y, /\x./\y.yap(F(x), y))) >= F(X) because [9], by (Meta) 9.27/9.33 9] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= X because [10], by (Select) 9.27/9.33 10] s(X) >= X because [11], by (Star) 9.27/9.33 11] s*(X) >= X because [12], by (Select) 9.27/9.33 12] X >= X by (Meta) 9.27/9.33 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) 9.27/9.33 14] s(X) > X because [15], by definition 9.27/9.33 15] s*(X) >= X because [12], by (Select) 9.27/9.33 16] Y >= Y by (Meta) 9.27/9.33 17] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [18], by (Abs) 9.27/9.33 18] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [19], by (Abs) 9.27/9.33 19] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [20] and [22], by (Fun) 9.27/9.33 20] F(y) >= F(y) because [21], by (Meta) 9.27/9.33 21] y >= y by (Var) 9.27/9.33 22] x >= x by (Var) 9.27/9.33 9.27/9.33 23] yap(F, X) >= @_{o -> o}(F, X) because [24], by (Star) 9.27/9.33 24] yap*(F, X) >= @_{o -> o}(F, X) because yap > @_{o -> o}, [25] and [27], by (Copy) 9.27/9.33 25] yap*(F, X) >= F because [26], by (Select) 9.27/9.33 26] F >= F by (Meta) 9.27/9.33 27] yap*(F, X) >= X because [28], by (Select) 9.27/9.33 28] X >= X by (Meta) 9.27/9.33 9.27/9.33 We can thus remove the following rules: 9.27/9.33 9.27/9.33 rec(0, X, /\x./\y.yap(F(x), y)) => X 9.27/9.33 9.27/9.33 We use rule removal, following [Kop12, Theorem 2.23]. 9.27/9.33 9.27/9.33 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 9.27/9.33 9.27/9.33 rec(s(X), Y, /\x./\y.yap(F(x), y)) >? yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 9.27/9.33 yap(F, X) >? F X 9.27/9.33 9.27/9.33 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 9.27/9.33 9.27/9.33 We choose Lex = {} and Mul = {@_{o -> o}, rec, s, yap}, and the following precedence: rec > s > yap > @_{o -> o} 9.27/9.33 9.27/9.33 With these choices, we have: 9.27/9.33 9.27/9.33 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 (Star) 9.27/9.33 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) 9.27/9.33 3] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= F(X) because [4], by (Select) 9.27/9.33 4] /\x.yap(F(rec*(s(X), Y, /\y./\z.yap(F(y), z))), x) >= F(X) because [5], by (Eta)[Kop13:2] 9.27/9.33 5] F(rec*(s(X), Y, /\x./\y.yap(F(x), y))) >= F(X) because [6], by (Meta) 9.27/9.33 6] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= X because [7], by (Select) 9.27/9.33 7] s(X) >= X because [8], by (Star) 9.27/9.33 8] s*(X) >= X because [9], by (Select) 9.27/9.33 9] X >= X by (Meta) 9.27/9.33 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) 9.27/9.33 11] s(X) > X because [12], by definition 9.27/9.33 12] s*(X) >= X because [9], by (Select) 9.27/9.33 13] Y >= Y by (Meta) 9.27/9.33 14] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [15], by (Abs) 9.27/9.33 15] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [16], by (Abs) 9.27/9.33 16] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [17] and [19], by (Fun) 9.27/9.33 17] F(y) >= F(y) because [18], by (Meta) 9.27/9.33 18] y >= y by (Var) 9.27/9.33 19] x >= x by (Var) 9.27/9.33 9.27/9.33 20] yap(F, X) > @_{o -> o}(F, X) because [21], by definition 9.27/9.33 21] yap*(F, X) >= @_{o -> o}(F, X) because yap > @_{o -> o}, [22] and [24], by (Copy) 9.27/9.33 22] yap*(F, X) >= F because [23], by (Select) 9.27/9.33 23] F >= F by (Meta) 9.27/9.33 24] yap*(F, X) >= X because [25], by (Select) 9.27/9.33 25] X >= X by (Meta) 9.27/9.33 9.27/9.33 We can thus remove the following rules: 9.27/9.33 9.27/9.33 yap(F, X) => F X 9.27/9.33 9.27/9.33 We use rule removal, following [Kop12, Theorem 2.23]. 9.27/9.33 9.27/9.33 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 9.27/9.33 9.27/9.33 rec(s(X), Y, /\x./\y.yap(F(x), y)) >? yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 9.27/9.33 9.27/9.33 We orient these requirements with a polynomial interpretation in the natural numbers. 9.27/9.33 9.27/9.33 The following interpretation satisfies the requirements: 9.27/9.33 9.27/9.33 rec = \y0y1G2.1 + y0 + y1 + 2G2(y0,y1) + y0y0G2(y0,y0) 9.27/9.33 s = \y0.3 + 3y0 9.27/9.33 yap = \G0y1.y1 + 2G0(0) 9.27/9.33 9.27/9.33 Using this interpretation, the requirements translate to: 9.27/9.33 9.27/9.33 [[rec(s(_x0), _x1, /\x./\y.yap(_F2(x), y))]] = 4 + 3*3*3 + 3x0 + 3x1 + 3*33x0 + 33x0*3 + 33x03x0 + 3x0*3*3 + 3x0*33x0 + 3x03x0*3 + 3x03x03x0 + 4F2(3 + 3x0,0) + 3*32F2(3 + 3x0,0) + 33x02F2(3 + 3x0,0) + 3x0*32F2(3 + 3x0,0) + 3x03x02F2(3 + 3x0,0) > 1 + x0 + 3x1 + x0x0x0 + 2x0x0F2(x0,0) + 6F2(x0,0) = [[yap(_F2(_x0), rec(_x0, _x1, /\x./\y.yap(_F2(x), y)))]] 9.27/9.33 9.27/9.33 We can thus remove the following rules: 9.27/9.33 9.27/9.33 rec(s(X), Y, /\x./\y.yap(F(x), y)) => yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 9.27/9.33 9.27/9.33 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. 9.27/9.33 9.27/9.33 9.27/9.33 +++ Citations +++ 9.27/9.33 9.27/9.33 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 9.27/9.33 [Kop13:2] C. Kop. StarHorpo with an Eta-Rule. Unpublished manuscript, http://cl-informatik.uibk.ac.at/users/kop/etahorpo.pdf, 2013. 9.27/9.34 EOF