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