0.81/0.84	YES
0.81/0.86	We consider the system theBenchmark.
0.81/0.86	
0.81/0.86	  Alphabet:
0.81/0.86	
0.81/0.86	    app : [list * list] --> list 
0.81/0.86	    cons : [nat * list] --> list 
0.81/0.86	    foldl : [list -> nat -> list * list * list] --> list 
0.81/0.86	    iconsc : [] --> list -> nat -> list 
0.81/0.86	    nil : [] --> list 
0.81/0.86	    reverse : [list] --> list 
0.81/0.86	    reverse1 : [list] --> list 
0.81/0.86	
0.81/0.86	  Rules:
0.81/0.86	
0.81/0.86	    app(nil, x) => x 
0.81/0.86	    app(cons(x, y), z) => cons(x, app(y, z)) 
0.81/0.86	    foldl(f, x, nil) => x 
0.81/0.86	    foldl(f, x, cons(y, z)) => foldl(f, f x y, z) 
0.81/0.86	    iconsc => /\x./\y.cons(y, x) 
0.81/0.86	    reverse(x) => foldl(iconsc, nil, x) 
0.81/0.86	    reverse1(x) => foldl(/\y./\z.app(cons(z, nil), y), nil, x) 
0.81/0.86	
0.81/0.86	This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0).
0.81/0.86	
0.81/0.86	We use rule removal, following [Kop12, Theorem 2.23].
0.81/0.86	
0.81/0.86	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
0.81/0.86	
0.81/0.86	  app(nil, X) >? X 
0.81/0.86	  app(cons(X, Y), Z) >? cons(X, app(Y, Z)) 
0.81/0.86	  foldl(F, X, nil) >? X 
0.81/0.86	  foldl(F, X, cons(Y, Z)) >? foldl(F, F X Y, Z) 
0.81/0.86	  iconsc >? /\x./\y.cons(y, x) 
0.81/0.86	  reverse(X) >? foldl(iconsc, nil, X) 
0.81/0.86	  reverse1(X) >? foldl(/\x./\y.app(cons(y, nil), x), nil, X) 
0.81/0.86	
0.81/0.86	We use a recursive path ordering as defined in [Kop12, Chapter 5].
0.81/0.86	
0.81/0.86	Argument functions:
0.81/0.86	
0.81/0.86	  [[foldl(x_1, x_2, x_3)]] = foldl(x_3, x_1, x_2) 
0.81/0.86	  [[nil]] = _|_ 
0.81/0.86	
0.81/0.86	We choose Lex = {foldl} and Mul = {@_{o -> o -> o}, @_{o -> o}, app, cons, iconsc, reverse, reverse1}, and the following precedence: reverse > iconsc > reverse1 > app > cons > foldl > @_{o -> o} > @_{o -> o -> o}
0.81/0.86	
0.81/0.86	Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:
0.81/0.86	
0.81/0.86	  app(_|_, X) >= X 
0.81/0.86	  app(cons(X, Y), Z) > cons(X, app(Y, Z)) 
0.81/0.86	  foldl(F, X, _|_) >= X 
0.81/0.86	  foldl(F, X, cons(Y, Z)) >= foldl(F, @_{o -> o}(@_{o -> o -> o}(F, X), Y), Z) 
0.81/0.86	  iconsc > /\x./\y.cons(y, x) 
0.81/0.86	  reverse(X) >= foldl(iconsc, _|_, X) 
0.81/0.86	  reverse1(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X) 
0.81/0.86	
0.81/0.86	With these choices, we have:
0.81/0.86	
0.81/0.86	  1] app(_|_, X) >= X  because [2], by (Star) 
0.81/0.86	  2] app*(_|_, X) >= X  because [3], by (Select) 
0.81/0.86	  3] X >= X  by (Meta) 
0.81/0.86	
0.81/0.86	  4] app(cons(X, Y), Z) > cons(X, app(Y, Z))  because [5], by definition 
0.81/0.86	  5] app*(cons(X, Y), Z) >= cons(X, app(Y, Z))  because app > cons, [6] and [10], by (Copy) 
0.81/0.86	  6] app*(cons(X, Y), Z) >= X  because [7], by (Select) 
0.81/0.86	  7] cons(X, Y) >= X  because [8], by (Star) 
0.81/0.86	  8] cons*(X, Y) >= X  because [9], by (Select) 
0.81/0.86	  9] X >= X  by (Meta) 
0.81/0.86	  10] app*(cons(X, Y), Z) >= app(Y, Z)  because app in Mul, [11] and [14], by (Stat) 
0.81/0.86	  11] cons(X, Y) > Y  because [12], by definition 
0.81/0.86	  12] cons*(X, Y) >= Y  because [13], by (Select) 
0.81/0.86	  13] Y >= Y  by (Meta) 
0.81/0.86	  14] Z >= Z  by (Meta) 
0.81/0.86	
0.81/0.86	  15] foldl(F, X, _|_) >= X  because [16], by (Star) 
0.81/0.86	  16] foldl*(F, X, _|_) >= X  because [17], by (Select) 
0.81/0.86	  17] X >= X  by (Meta) 
0.81/0.86	
0.81/0.86	  18] foldl(F, X, cons(Y, Z)) >= foldl(F, @_{o -> o}(@_{o -> o -> o}(F, X), Y), Z)  because [19], by (Star) 
0.81/0.86	  19] foldl*(F, X, cons(Y, Z)) >= foldl(F, @_{o -> o}(@_{o -> o -> o}(F, X), Y), Z)  because [20], [23], [25] and [33], by (Stat) 
0.81/0.86	  20] cons(Y, Z) > Z  because [21], by definition 
0.81/0.86	  21] cons*(Y, Z) >= Z  because [22], by (Select) 
0.81/0.86	  22] Z >= Z  by (Meta) 
0.81/0.86	  23] foldl*(F, X, cons(Y, Z)) >= F  because [24], by (Select) 
0.81/0.86	  24] F >= F  by (Meta) 
0.81/0.86	  25] foldl*(F, X, cons(Y, Z)) >= @_{o -> o}(@_{o -> o -> o}(F, X), Y)  because foldl > @_{o -> o}, [26] and [29], by (Copy) 
0.81/0.86	  26] foldl*(F, X, cons(Y, Z)) >= @_{o -> o -> o}(F, X)  because foldl > @_{o -> o -> o}, [23] and [27], by (Copy) 
0.81/0.86	  27] foldl*(F, X, cons(Y, Z)) >= X  because [28], by (Select) 
0.81/0.86	  28] X >= X  by (Meta) 
0.81/0.86	  29] foldl*(F, X, cons(Y, Z)) >= Y  because [30], by (Select) 
0.81/0.86	  30] cons(Y, Z) >= Y  because [31], by (Star) 
0.81/0.86	  31] cons*(Y, Z) >= Y  because [32], by (Select) 
0.81/0.86	  32] Y >= Y  by (Meta) 
0.81/0.86	  33] foldl*(F, X, cons(Y, Z)) >= Z  because [34], by (Select) 
0.81/0.86	  34] cons(Y, Z) >= Z  because [21], by (Star) 
0.81/0.86	
0.81/0.86	  35] iconsc > /\x./\y.cons(y, x)  because [36], by definition 
0.81/0.86	  36] iconsc* >= /\y./\z.cons(z, y)  because [37], by (F-Abs) 
0.81/0.86	  37] iconsc*(x) >= /\z.cons(z, x)  because [38], by (F-Abs) 
0.81/0.86	  38] iconsc*(x, y) >= cons(y, x)  because iconsc > cons, [39] and [41], by (Copy) 
0.81/0.87	  39] iconsc*(x, y) >= y  because [40], by (Select) 
0.81/0.87	  40] y >= y  by (Var) 
0.81/0.87	  41] iconsc*(x, y) >= x  because [42], by (Select) 
0.81/0.87	  42] x >= x  by (Var) 
0.81/0.87	
0.81/0.87	  43] reverse(X) >= foldl(iconsc, _|_, X)  because [44], by (Star) 
0.81/0.87	  44] reverse*(X) >= foldl(iconsc, _|_, X)  because reverse > foldl, [45], [46] and [47], by (Copy) 
0.81/0.87	  45] reverse*(X) >= iconsc  because reverse > iconsc, by (Copy) 
0.81/0.87	  46] reverse*(X) >= _|_  by (Bot) 
0.81/0.87	  47] reverse*(X) >= X  because [48], by (Select) 
0.81/0.87	  48] X >= X  by (Meta) 
0.81/0.87	
0.81/0.87	  49] reverse1(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X)  because [50], by (Star) 
0.81/0.87	  50] reverse1*(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X)  because reverse1 > foldl, [51], [60] and [61], by (Copy) 
0.81/0.87	  51] reverse1*(X) >= /\y./\z.app(cons(z, _|_), y)  because [52], by (F-Abs) 
0.81/0.87	  52] reverse1*(X, x) >= /\z.app(cons(z, _|_), x)  because [53], by (F-Abs) 
0.81/0.87	  53] reverse1*(X, x, y) >= app(cons(y, _|_), x)  because reverse1 > app, [54] and [58], by (Copy) 
0.81/0.87	  54] reverse1*(X, x, y) >= cons(y, _|_)  because reverse1 > cons, [55] and [57], by (Copy) 
0.81/0.87	  55] reverse1*(X, x, y) >= y  because [56], by (Select) 
0.81/0.87	  56] y >= y  by (Var) 
0.81/0.87	  57] reverse1*(X, x, y) >= _|_  by (Bot) 
0.81/0.87	  58] reverse1*(X, x, y) >= x  because [59], by (Select) 
0.81/0.87	  59] x >= x  by (Var) 
0.81/0.87	  60] reverse1*(X) >= _|_  by (Bot) 
0.81/0.87	  61] reverse1*(X) >= X  because [62], by (Select) 
0.81/0.87	  62] X >= X  by (Meta) 
0.81/0.87	
0.81/0.87	We can thus remove the following rules:
0.81/0.87	
0.81/0.87	  app(cons(X, Y), Z) => cons(X, app(Y, Z)) 
0.81/0.87	  iconsc => /\x./\y.cons(y, x) 
0.81/0.87	
0.81/0.87	We use rule removal, following [Kop12, Theorem 2.23].
0.81/0.87	
0.81/0.87	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
0.81/0.87	
0.81/0.87	  app(nil, X) >? X 
0.81/0.87	  foldl(F, X, nil) >? X 
0.81/0.87	  foldl(F, X, cons(Y, Z)) >? foldl(F, F X Y, Z) 
0.81/0.87	  reverse(X) >? foldl(iconsc, nil, X) 
0.81/0.87	  reverse1(X) >? foldl(/\x./\y.app(cons(y, nil), x), nil, X) 
0.81/0.87	
0.81/0.87	We use a recursive path ordering as defined in [Kop12, Chapter 5].
0.81/0.87	
0.81/0.87	Argument functions:
0.81/0.87	
0.81/0.87	  [[foldl(x_1, x_2, x_3)]] = foldl(x_1, x_3, x_2) 
0.81/0.87	  [[iconsc]] = _|_ 
0.81/0.87	  [[nil]] = _|_ 
0.81/0.87	
0.81/0.87	We choose Lex = {foldl} and Mul = {@_{o -> o -> o}, @_{o -> o}, app, cons, reverse, reverse1}, and the following precedence: reverse > reverse1 > app > cons > foldl > @_{o -> o -> o} > @_{o -> o}
0.81/0.87	
0.81/0.87	Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:
0.81/0.87	
0.81/0.87	  app(_|_, X) >= X 
0.81/0.87	  foldl(F, X, _|_) > X 
0.81/0.87	  foldl(F, X, cons(Y, Z)) > foldl(F, @_{o -> o}(@_{o -> o -> o}(F, X), Y), Z) 
0.81/0.87	  reverse(X) >= foldl(_|_, _|_, X) 
0.81/0.87	  reverse1(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X) 
0.81/0.87	
0.81/0.87	With these choices, we have:
0.81/0.87	
0.81/0.87	  1] app(_|_, X) >= X  because [2], by (Star) 
0.81/0.87	  2] app*(_|_, X) >= X  because [3], by (Select) 
0.81/0.87	  3] X >= X  by (Meta) 
0.81/0.87	
0.81/0.87	  4] foldl(F, X, _|_) > X  because [5], by definition 
0.81/0.87	  5] foldl*(F, X, _|_) >= X  because [6], by (Select) 
0.81/0.87	  6] X >= X  by (Meta) 
0.81/0.87	
0.81/0.87	  7] foldl(F, X, cons(Y, Z)) > foldl(F, @_{o -> o}(@_{o -> o -> o}(F, X), Y), Z)  because [8], by definition 
0.81/0.87	  8] foldl*(F, X, cons(Y, Z)) >= foldl(F, @_{o -> o}(@_{o -> o -> o}(F, X), Y), Z)  because [9], [10], [13], [14] and [22], by (Stat) 
0.81/0.87	  9] F >= F  by (Meta) 
0.81/0.87	  10] cons(Y, Z) > Z  because [11], by definition 
0.81/0.87	  11] cons*(Y, Z) >= Z  because [12], by (Select) 
0.81/0.87	  12] Z >= Z  by (Meta) 
0.81/0.87	  13] foldl*(F, X, cons(Y, Z)) >= F  because [9], by (Select) 
0.81/0.87	  14] foldl*(F, X, cons(Y, Z)) >= @_{o -> o}(@_{o -> o -> o}(F, X), Y)  because foldl > @_{o -> o}, [15] and [18], by (Copy) 
0.81/0.87	  15] foldl*(F, X, cons(Y, Z)) >= @_{o -> o -> o}(F, X)  because foldl > @_{o -> o -> o}, [13] and [16], by (Copy) 
0.81/0.87	  16] foldl*(F, X, cons(Y, Z)) >= X  because [17], by (Select) 
0.81/0.87	  17] X >= X  by (Meta) 
0.81/0.87	  18] foldl*(F, X, cons(Y, Z)) >= Y  because [19], by (Select) 
0.81/0.87	  19] cons(Y, Z) >= Y  because [20], by (Star) 
0.81/0.87	  20] cons*(Y, Z) >= Y  because [21], by (Select) 
0.81/0.87	  21] Y >= Y  by (Meta) 
0.81/0.87	  22] foldl*(F, X, cons(Y, Z)) >= Z  because [23], by (Select) 
0.81/0.87	  23] cons(Y, Z) >= Z  because [11], by (Star) 
0.81/0.87	
0.81/0.87	  24] reverse(X) >= foldl(_|_, _|_, X)  because [25], by (Star) 
0.81/0.87	  25] reverse*(X) >= foldl(_|_, _|_, X)  because reverse > foldl, [26], [27] and [28], by (Copy) 
0.81/0.87	  26] reverse*(X) >= _|_  by (Bot) 
0.81/0.87	  27] reverse*(X) >= _|_  by (Bot) 
0.81/0.87	  28] reverse*(X) >= X  because [29], by (Select) 
0.81/0.87	  29] X >= X  by (Meta) 
0.81/0.87	
0.81/0.87	  30] reverse1(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X)  because [31], by (Star) 
0.81/0.87	  31] reverse1*(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X)  because reverse1 > foldl, [32], [41] and [42], by (Copy) 
0.81/0.87	  32] reverse1*(X) >= /\y./\z.app(cons(z, _|_), y)  because [33], by (F-Abs) 
0.81/0.87	  33] reverse1*(X, x) >= /\z.app(cons(z, _|_), x)  because [34], by (F-Abs) 
0.81/0.87	  34] reverse1*(X, x, y) >= app(cons(y, _|_), x)  because reverse1 > app, [35] and [39], by (Copy) 
0.81/0.87	  35] reverse1*(X, x, y) >= cons(y, _|_)  because reverse1 > cons, [36] and [38], by (Copy) 
0.81/0.87	  36] reverse1*(X, x, y) >= y  because [37], by (Select) 
0.81/0.87	  37] y >= y  by (Var) 
0.81/0.87	  38] reverse1*(X, x, y) >= _|_  by (Bot) 
0.81/0.87	  39] reverse1*(X, x, y) >= x  because [40], by (Select) 
0.81/0.87	  40] x >= x  by (Var) 
0.81/0.87	  41] reverse1*(X) >= _|_  by (Bot) 
0.81/0.87	  42] reverse1*(X) >= X  because [43], by (Select) 
0.81/0.87	  43] X >= X  by (Meta) 
0.81/0.87	
0.81/0.87	We can thus remove the following rules:
0.81/0.87	
0.81/0.87	  foldl(F, X, nil) => X 
0.81/0.87	  foldl(F, X, cons(Y, Z)) => foldl(F, F X Y, Z) 
0.81/0.87	
0.81/0.87	We use rule removal, following [Kop12, Theorem 2.23].
0.81/0.87	
0.81/0.87	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
0.81/0.87	
0.81/0.87	  app(nil, X) >? X 
0.81/0.87	  reverse(X) >? foldl(iconsc, nil, X) 
0.81/0.87	  reverse1(X) >? foldl(/\x./\y.app(cons(y, nil), x), nil, X) 
0.81/0.87	
0.81/0.87	We orient these requirements with a polynomial interpretation in the natural numbers.
0.81/0.87	
0.81/0.87	The following interpretation satisfies the requirements:
0.81/0.87	
0.81/0.87	  app = \y0y1.y0 + y1 
0.81/0.87	  cons = \y0y1.y0 + y1 
0.81/0.87	  foldl = \G0y1y2.y1 + y2 + G0(0,0) 
0.81/0.87	  iconsc = \y0y1.0 
0.81/0.87	  nil = 0 
0.81/0.87	  reverse = \y0.3 + 3y0 
0.81/0.87	  reverse1 = \y0.3 + 3y0 
0.81/0.87	
0.81/0.87	Using this interpretation, the requirements translate to:
0.81/0.87	
0.81/0.87	  [[app(nil, _x0)]] = x0 >= x0 = [[_x0]] 
0.81/0.87	  [[reverse(_x0)]] = 3 + 3x0 > x0 = [[foldl(iconsc, nil, _x0)]] 
0.81/0.87	  [[reverse1(_x0)]] = 3 + 3x0 > x0 = [[foldl(/\x./\y.app(cons(y, nil), x), nil, _x0)]] 
0.81/0.87	
0.81/0.87	We can thus remove the following rules:
0.81/0.87	
0.81/0.87	  reverse(X) => foldl(iconsc, nil, X) 
0.81/0.87	  reverse1(X) => foldl(/\x./\y.app(cons(y, nil), x), nil, X) 
0.81/0.87	
0.81/0.87	We use rule removal, following [Kop12, Theorem 2.23].
0.81/0.87	
0.81/0.87	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
0.81/0.87	
0.81/0.87	  app(nil, X) >? X 
0.81/0.87	
0.81/0.87	We orient these requirements with a polynomial interpretation in the natural numbers.
0.81/0.87	
0.81/0.87	The following interpretation satisfies the requirements:
0.81/0.87	
0.81/0.87	  app = \y0y1.3 + y0 + y1 
0.81/0.87	  nil = 3 
0.81/0.87	
0.81/0.87	Using this interpretation, the requirements translate to:
0.81/0.87	
0.81/0.87	  [[app(nil, _x0)]] = 6 + x0 > x0 = [[_x0]] 
0.81/0.87	
0.81/0.87	We can thus remove the following rules:
0.81/0.87	
0.81/0.87	  app(nil, X) => X 
0.81/0.87	
0.81/0.87	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.81/0.87	
0.81/0.87	
0.81/0.87	+++ Citations +++
0.81/0.87	
0.81/0.87	[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.
0.81/0.87	EOF