7.15/7.26 YES 7.15/7.27 We consider the system theBenchmark. 7.15/7.27 7.15/7.27 Alphabet: 7.15/7.27 7.15/7.27 cons : [a * b] --> b 7.15/7.27 foldr : [a -> b -> b * b * b] --> b 7.15/7.27 nil : [] --> b 7.15/7.27 xap : [a -> b -> b * a] --> b -> b 7.15/7.27 yap : [b -> b * b] --> b 7.15/7.27 7.15/7.27 Rules: 7.15/7.27 7.15/7.27 foldr(/\x./\y.yap(xap(f, x), y), z, nil) => z 7.15/7.27 foldr(/\x./\y.yap(xap(f, x), y), z, cons(u, v)) => yap(xap(f, u), foldr(/\w./\x'.yap(xap(f, w), x'), z, v)) 7.15/7.27 xap(f, x) => f x 7.15/7.27 yap(f, x) => f x 7.15/7.27 7.15/7.27 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 7.15/7.27 7.15/7.27 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: 7.15/7.27 7.15/7.27 Alphabet: 7.15/7.27 7.15/7.27 cons : [a * b] --> b 7.15/7.27 foldr : [a -> b -> b * b * b] --> b 7.15/7.27 nil : [] --> b 7.15/7.27 yap : [b -> b * b] --> b 7.15/7.27 7.15/7.27 Rules: 7.15/7.27 7.15/7.27 foldr(/\x./\y.yap(F(x), y), X, nil) => X 7.15/7.27 foldr(/\x./\y.yap(F(x), y), X, cons(Y, Z)) => yap(F(Y), foldr(/\z./\u.yap(F(z), u), X, Z)) 7.15/7.27 yap(F, X) => F X 7.15/7.27 7.15/7.27 We use rule removal, following [Kop12, Theorem 2.23]. 7.15/7.27 7.15/7.27 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 7.15/7.27 7.15/7.27 foldr(/\x./\y.yap(F(x), y), X, nil) >? X 7.15/7.27 foldr(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >? yap(F(Y), foldr(/\z./\u.yap(F(z), u), X, Z)) 7.15/7.27 yap(F, X) >? F X 7.15/7.27 7.15/7.27 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 7.15/7.27 7.15/7.27 We choose Lex = {} and Mul = {@_{o -> o}, cons, foldr, nil, yap}, and the following precedence: foldr > nil > yap > @_{o -> o} > cons 7.15/7.27 7.15/7.27 With these choices, we have: 7.15/7.27 7.15/7.27 1] foldr(/\x./\y.yap(F(x), y), X, nil) > X because [2], by definition 7.15/7.27 2] foldr*(/\x./\y.yap(F(x), y), X, nil) >= X because [3], by (Select) 7.15/7.27 3] X >= X by (Meta) 7.15/7.27 7.15/7.27 4] foldr(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= yap(F(Y), foldr(/\x./\y.yap(F(x), y), X, Z)) because [5], by (Star) 7.15/7.27 5] foldr*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= yap(F(Y), foldr(/\x./\y.yap(F(x), y), X, Z)) because foldr > yap, [6] and [13], by (Copy) 7.15/7.27 6] foldr*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= F(Y) because [7], by (Select) 7.15/7.27 7] /\x.yap(F(foldr*(/\y./\z.yap(F(y), z), X, cons(Y, Z))), x) >= F(Y) because [8], by (Eta)[Kop13:2] 7.15/7.27 8] F(foldr*(/\x./\y.yap(F(x), y), X, cons(Y, Z))) >= F(Y) because [9], by (Meta) 7.15/7.27 9] foldr*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= Y because [10], by (Select) 7.15/7.27 10] cons(Y, Z) >= Y because [11], by (Star) 7.15/7.27 11] cons*(Y, Z) >= Y because [12], by (Select) 7.15/7.27 12] Y >= Y by (Meta) 7.15/7.27 13] foldr*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= foldr(/\x./\y.yap(F(x), y), X, Z) because foldr in Mul, [14], [20] and [21], by (Stat) 7.15/7.27 14] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [15], by (Abs) 7.15/7.27 15] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [16], by (Abs) 7.15/7.27 16] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [17] and [19], by (Fun) 7.15/7.27 17] F(y) >= F(y) because [18], by (Meta) 7.15/7.27 18] y >= y by (Var) 7.15/7.27 19] x >= x by (Var) 7.15/7.27 20] X >= X by (Meta) 7.15/7.27 21] cons(Y, Z) > Z because [22], by definition 7.15/7.27 22] cons*(Y, Z) >= Z because [23], by (Select) 7.15/7.27 23] Z >= Z by (Meta) 7.15/7.27 7.15/7.27 24] yap(F, X) > @_{o -> o}(F, X) because [25], by definition 7.15/7.27 25] yap*(F, X) >= @_{o -> o}(F, X) because yap > @_{o -> o}, [26] and [28], by (Copy) 7.15/7.27 26] yap*(F, X) >= F because [27], by (Select) 7.15/7.27 27] F >= F by (Meta) 7.15/7.27 28] yap*(F, X) >= X because [29], by (Select) 7.15/7.27 29] X >= X by (Meta) 7.15/7.27 7.15/7.27 We can thus remove the following rules: 7.15/7.27 7.15/7.27 foldr(/\x./\y.yap(F(x), y), X, nil) => X 7.15/7.27 yap(F, X) => F X 7.15/7.27 7.15/7.27 We use rule removal, following [Kop12, Theorem 2.23]. 7.15/7.27 7.15/7.27 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 7.15/7.27 7.15/7.27 foldr(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >? yap(F(Y), foldr(/\z./\u.yap(F(z), u), X, Z)) 7.15/7.27 7.15/7.27 We orient these requirements with a polynomial interpretation in the natural numbers. 7.15/7.27 7.15/7.27 The following interpretation satisfies the requirements: 7.15/7.27 7.15/7.27 cons = \y0y1.3 + y0 + 3y1 7.15/7.27 foldr = \G0y1y2.y1 + 3y2 + G0(y2,y1) + 3y2y2G0(y2,y2) + y1y2G0(y1,y2) 7.15/7.27 yap = \G0y1.2y1 + G0(0) 7.15/7.27 7.15/7.27 Using this interpretation, the requirements translate to: 7.15/7.27 7.15/7.27 [[foldr(/\x./\y.yap(_F0(x), y), _x1, cons(_x2, _x3))]] = 171 + 2x1x2x2 + 6x2x2x2 + 12x1x2 + 12x1x2x3 + 18x1x3x3 + 21x1 + 36x1x3 + 54x2x2 + 54x2x2x3 + 162x2x3x3 + 162x3x3x3 + 165x2 + 324x2x3 + 486x3x3 + 495x3 + 3x1x3F0(x1,0) + 3x1F0(x1,0) + 3x2x2F0(3 + x2 + 3x3,0) + 18x2x3F0(3 + x2 + 3x3,0) + 18x2F0(3 + x2 + 3x3,0) + 27x3x3F0(3 + x2 + 3x3,0) + 28F0(3 + x2 + 3x3,0) + 54x3F0(3 + x2 + 3x3,0) + x1x2F0(x1,0) > 4x1x3x3 + 6x1 + 6x3 + 12x3x3x3 + F0(x2,0) + 2x1x3F0(x1,0) + 2F0(x3,0) + 6x3x3F0(x3,0) = [[yap(_F0(_x2), foldr(/\x./\y.yap(_F0(x), y), _x1, _x3))]] 7.15/7.27 7.15/7.27 We can thus remove the following rules: 7.15/7.27 7.15/7.27 foldr(/\x./\y.yap(F(x), y), X, cons(Y, Z)) => yap(F(Y), foldr(/\z./\u.yap(F(z), u), X, Z)) 7.15/7.27 7.15/7.27 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. 7.15/7.27 7.15/7.27 7.15/7.27 +++ Citations +++ 7.15/7.27 7.15/7.27 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 7.15/7.27 [Kop13:2] C. Kop. StarHorpo with an Eta-Rule. Unpublished manuscript, http://cl-informatik.uibk.ac.at/users/kop/etahorpo.pdf, 2013. 7.15/7.28 EOF