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