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