0.00/0.12 YES 0.00/0.13 We consider the system theBenchmark. 0.00/0.13 0.00/0.13 Alphabet: 0.00/0.13 0.00/0.13 0 : [] --> nat 0.00/0.13 cons : [] --> nat -> list -> list 0.00/0.13 foldr : [] --> (nat -> nat -> nat) -> nat -> list -> nat 0.00/0.13 length : [] --> list -> nat 0.00/0.13 nil : [] --> list 0.00/0.13 s : [] --> nat -> nat 0.00/0.13 0.00/0.13 Rules: 0.00/0.13 0.00/0.13 foldr (/\x./\y.f x y) z nil => z 0.00/0.13 foldr (/\x./\y.f x y) z (cons u v) => f u (foldr (/\w./\x'.f w x') z v) 0.00/0.13 length x => foldr (/\y./\z.s z) 0 x 0.00/0.13 0.00/0.13 Using the transformations described in [Kop11], this system can be brought in a form without leading free variables in the left-hand side, and where the left-hand side of a variable is always a functional term or application headed by a functional term. 0.00/0.13 0.00/0.13 We now transform the resulting AFS into an AFSM by replacing all free variables by meta-variables (with arity 0). This leads to the following AFSM: 0.00/0.13 0.00/0.13 Alphabet: 0.00/0.13 0.00/0.13 0 : [] --> nat 0.00/0.13 cons : [nat * list] --> list 0.00/0.13 foldr : [nat -> nat -> nat * nat * list] --> nat 0.00/0.13 length : [list] --> nat 0.00/0.13 nil : [] --> list 0.00/0.13 s : [nat] --> nat 0.00/0.14 ~AP1 : [nat -> nat -> nat * nat] --> nat -> nat 0.00/0.14 0.00/0.14 Rules: 0.00/0.14 0.00/0.14 foldr(/\x./\y.~AP1(F, x) y, X, nil) => X 0.00/0.14 foldr(/\x./\y.~AP1(F, x) y, X, cons(Y, Z)) => ~AP1(F, Y) foldr(/\z./\u.~AP1(F, z) u, X, Z) 0.00/0.14 length(X) => foldr(/\x./\y.s(y), 0, X) 0.00/0.14 ~AP1(F, X) => F X 0.00/0.14 0.00/0.14 Symbol ~AP1 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: 0.00/0.14 0.00/0.14 Alphabet: 0.00/0.14 0.00/0.14 0 : [] --> nat 0.00/0.14 cons : [nat * list] --> list 0.00/0.14 foldr : [nat -> nat -> nat * nat * list] --> nat 0.00/0.14 length : [list] --> nat 0.00/0.14 nil : [] --> list 0.00/0.14 s : [nat] --> nat 0.00/0.14 0.00/0.14 Rules: 0.00/0.14 0.00/0.14 foldr(/\x./\y.X(x, y), Y, nil) => Y 0.00/0.14 foldr(/\x./\y.X(x, y), Y, cons(Z, U)) => X(Z, foldr(/\z./\u.X(z, u), Y, U)) 0.00/0.14 length(X) => foldr(/\x./\y.s(y), 0, X) 0.00/0.14 0.00/0.14 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.14 0.00/0.14 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.14 0.00/0.14 foldr(/\x./\y.X(x, y), Y, nil) >? Y 0.00/0.14 foldr(/\x./\y.X(x, y), Y, cons(Z, U)) >? X(Z, foldr(/\z./\u.X(z, u), Y, U)) 0.00/0.14 length(X) >? foldr(/\x./\y.s(y), 0, X) 0.00/0.14 0.00/0.14 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.00/0.14 0.00/0.14 Argument functions: 0.00/0.14 0.00/0.14 [[0]] = _|_ 0.00/0.14 [[s(x_1)]] = x_1 0.00/0.14 0.00/0.14 We choose Lex = {} and Mul = {cons, foldr, length, nil}, and the following precedence: cons > length > foldr > nil 0.00/0.14 0.00/0.14 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.00/0.14 0.00/0.14 foldr(/\x./\y.X(x, y), Y, nil) >= Y 0.00/0.14 foldr(/\x./\y.X(x, y), Y, cons(Z, U)) > X(Z, foldr(/\x./\y.X(x, y), Y, U)) 0.00/0.14 length(X) >= foldr(/\x./\y.y, _|_, X) 0.00/0.14 0.00/0.14 With these choices, we have: 0.00/0.14 0.00/0.14 1] foldr(/\x./\y.X(x, y), Y, nil) >= Y because [2], by (Star) 0.00/0.14 2] foldr*(/\x./\y.X(x, y), Y, nil) >= Y because [3], by (Select) 0.00/0.14 3] Y >= Y by (Meta) 0.00/0.14 0.00/0.14 4] foldr(/\x./\y.X(x, y), Y, cons(Z, U)) > X(Z, foldr(/\x./\y.X(x, y), Y, U)) because [5], by definition 0.00/0.14 5] foldr*(/\x./\y.X(x, y), Y, cons(Z, U)) >= X(Z, foldr(/\x./\y.X(x, y), Y, U)) because [6], by (Select) 0.00/0.14 6] X(foldr*(/\x./\y.X(x, y), Y, cons(Z, U)), foldr*(/\z./\u.X(z, u), Y, cons(Z, U))) >= X(Z, foldr(/\x./\y.X(x, y), Y, U)) because [7] and [11], by (Meta) 0.00/0.14 7] foldr*(/\x./\y.X(x, y), Y, cons(Z, U)) >= Z because [8], by (Select) 0.00/0.14 8] cons(Z, U) >= Z because [9], by (Star) 0.00/0.14 9] cons*(Z, U) >= Z because [10], by (Select) 0.00/0.14 10] Z >= Z by (Meta) 0.00/0.14 11] foldr*(/\x./\y.X(x, y), Y, cons(Z, U)) >= foldr(/\x./\y.X(x, y), Y, U) because foldr in Mul, [12], [17] and [18], by (Stat) 0.00/0.14 12] /\x./\z.X(x, z) >= /\x./\z.X(x, z) because [13], by (Abs) 0.00/0.14 13] /\z.X(y, z) >= /\z.X(y, z) because [14], by (Abs) 0.00/0.14 14] X(y, x) >= X(y, x) because [15] and [16], by (Meta) 0.00/0.14 15] y >= y by (Var) 0.00/0.14 16] x >= x by (Var) 0.00/0.14 17] Y >= Y by (Meta) 0.00/0.14 18] cons(Z, U) > U because [19], by definition 0.00/0.14 19] cons*(Z, U) >= U because [20], by (Select) 0.00/0.14 20] U >= U by (Meta) 0.00/0.14 0.00/0.14 21] length(X) >= foldr(/\x./\y.y, _|_, X) because [22], by (Star) 0.00/0.14 22] length*(X) >= foldr(/\x./\y.y, _|_, X) because length > foldr, [23], [27] and [28], by (Copy) 0.00/0.14 23] length*(X) >= /\y./\z.z because [24], by (F-Abs) 0.00/0.14 24] length*(X, x) >= /\z.z because [25], by (F-Abs) 0.00/0.14 25] length*(X, x, y) >= y because [26], by (Select) 0.00/0.14 26] y >= y by (Var) 0.00/0.14 27] length*(X) >= _|_ by (Bot) 0.00/0.14 28] length*(X) >= X because [29], by (Select) 0.00/0.14 29] X >= X by (Meta) 0.00/0.14 0.00/0.14 We can thus remove the following rules: 0.00/0.14 0.00/0.14 foldr(/\x./\y.X(x, y), Y, cons(Z, U)) => X(Z, foldr(/\z./\u.X(z, u), Y, U)) 0.00/0.14 0.00/0.14 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.14 0.00/0.14 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.14 0.00/0.14 foldr(/\x./\y.X(x, y), Y, nil) >? Y 0.00/0.14 length(X) >? foldr(/\x./\y.s(y), 0, X) 0.00/0.14 0.00/0.14 We orient these requirements with a polynomial interpretation in the natural numbers. 0.00/0.14 0.00/0.14 The following interpretation satisfies the requirements: 0.00/0.14 0.00/0.14 0 = 0 0.00/0.14 foldr = \G0y1y2.y1 + y2 + G0(0,0) 0.00/0.14 length = \y0.3 + 3y0 0.00/0.14 nil = 3 0.00/0.14 s = \y0.y0 0.00/0.14 0.00/0.14 Using this interpretation, the requirements translate to: 0.00/0.14 0.00/0.14 [[foldr(/\x./\y._x0(x, y), _x1, nil)]] = 3 + x1 + F0(0,0) > x1 = [[_x1]] 0.00/0.14 [[length(_x0)]] = 3 + 3x0 > x0 = [[foldr(/\x./\y.s(y), 0, _x0)]] 0.00/0.14 0.00/0.14 We can thus remove the following rules: 0.00/0.14 0.00/0.14 foldr(/\x./\y.X(x, y), Y, nil) => Y 0.00/0.14 length(X) => foldr(/\x./\y.s(y), 0, X) 0.00/0.14 0.00/0.14 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.14 0.00/0.14 0.00/0.14 +++ Citations +++ 0.00/0.14 0.00/0.14 [Kop11] C. Kop. Simplifying Algebraic Functional Systems. In Proceedings of CAI 2011, volume 6742 of LNCS. 201--215, Springer, 2011. 0.00/0.14 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 0.00/0.14 EOF