3.00/5.08	YES
3.20/5.22	We consider the system theBenchmark.
3.20/5.22	
3.20/5.22	  Alphabet:
3.20/5.22	
3.20/5.22	    0 : [] --> nat 
3.20/5.22	    ascending!6220sort : [list] --> list 
3.20/5.22	    cons : [nat * list] --> list 
3.20/5.22	    descending!6220sort : [list] --> list 
3.20/5.22	    insert : [nat * list * nat -> nat -> nat * nat -> nat -> nat] --> list 
3.20/5.22	    max : [nat * nat] --> nat 
3.20/5.22	    min : [nat * nat] --> nat 
3.20/5.22	    nil : [] --> list 
3.20/5.22	    s : [nat] --> nat 
3.20/5.22	    sort : [list * nat -> nat -> nat * nat -> nat -> nat] --> list 
3.20/5.22	
3.20/5.22	  Rules:
3.20/5.22	
3.20/5.22	    max(0, x) => x 
3.20/5.22	    max(x, 0) => x 
3.20/5.22	    max(s(x), s(y)) => s(max(x, y)) 
3.20/5.22	    min(0, x) => 0 
3.20/5.22	    min(x, 0) => 0 
3.20/5.22	    min(s(x), s(y)) => s(min(x, y)) 
3.20/5.22	    insert(x, nil, f, g) => cons(x, nil) 
3.20/5.22	    insert(x, cons(y, z), f, g) => cons(f x y, insert(g x y, z, f, g)) 
3.20/5.22	    sort(nil, f, g) => nil 
3.20/5.22	    sort(cons(x, y), f, g) => insert(x, sort(y, f, g), f, g) 
3.20/5.22	    ascending!6220sort(x) => sort(x, /\y./\z.min(y, z), /\u./\v.max(u, v)) 
3.20/5.22	    descending!6220sort(x) => sort(x, /\y./\z.max(y, z), /\u./\v.min(u, v)) 
3.20/5.22	
3.20/5.22	This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0).
3.20/5.22	
3.20/5.22	We use rule removal, following [Kop12, Theorem 2.23].
3.20/5.22	
3.20/5.22	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
3.20/5.22	
3.20/5.22	  max(0, X) >? X 
3.20/5.22	  max(X, 0) >? X 
3.20/5.22	  max(s(X), s(Y)) >? s(max(X, Y)) 
3.20/5.22	  min(0, X) >? 0 
3.20/5.22	  min(X, 0) >? 0 
3.20/5.22	  min(s(X), s(Y)) >? s(min(X, Y)) 
3.20/5.22	  insert(X, nil, F, G) >? cons(X, nil) 
3.20/5.22	  insert(X, cons(Y, Z), F, G) >? cons(F X Y, insert(G X Y, Z, F, G)) 
3.20/5.22	  sort(nil, F, G) >? nil 
3.20/5.22	  sort(cons(X, Y), F, G) >? insert(X, sort(Y, F, G), F, G) 
3.20/5.22	  ascending!6220sort(X) >? sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u)) 
3.20/5.22	  descending!6220sort(X) >? sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u)) 
3.20/5.22	
3.20/5.22	We use a recursive path ordering as defined in [Kop12, Chapter 5].
3.20/5.22	
3.20/5.22	Argument functions:
3.20/5.22	
3.20/5.22	  [[0]] = _|_ 
3.20/5.22	  [[insert(x_1, x_2, x_3, x_4)]] = insert(x_2, x_4, x_1, x_3) 
3.20/5.22	  [[nil]] = _|_ 
3.20/5.22	
3.20/5.22	We choose Lex = {insert} and Mul = {@_{o -> o -> o}, @_{o -> o}, ascending!6220sort, cons, descending!6220sort, max, min, s, sort}, and the following precedence: ascending!6220sort > descending!6220sort > max > min > s > sort > insert > @_{o -> o -> o} > @_{o -> o} > cons
3.20/5.22	
3.20/5.22	Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:
3.20/5.22	
3.20/5.22	  max(_|_, X) > X 
3.20/5.22	  max(X, _|_) >= X 
3.20/5.22	  max(s(X), s(Y)) >= s(max(X, Y)) 
3.20/5.22	  min(_|_, X) >= _|_ 
3.20/5.22	  min(X, _|_) >= _|_ 
3.20/5.22	  min(s(X), s(Y)) >= s(min(X, Y)) 
3.20/5.22	  insert(X, _|_, F, G) >= cons(X, _|_) 
3.20/5.22	  insert(X, cons(Y, Z), F, G) >= cons(@_{o -> o}(@_{o -> o -> o}(F, X), Y), insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G)) 
3.20/5.22	  sort(_|_, F, G) >= _|_ 
3.20/5.22	  sort(cons(X, Y), F, G) >= insert(X, sort(Y, F, G), F, G) 
3.20/5.22	  ascending!6220sort(X) >= sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u)) 
3.20/5.22	  descending!6220sort(X) >= sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u)) 
3.20/5.22	
3.20/5.22	With these choices, we have:
3.20/5.22	
3.20/5.22	  1] max(_|_, X) > X  because [2], by definition 
3.20/5.22	  2] max*(_|_, X) >= X  because [3], by (Select) 
3.20/5.22	  3] X >= X  by (Meta) 
3.20/5.22	
3.20/5.22	  4] max(X, _|_) >= X  because [5], by (Star) 
3.20/5.22	  5] max*(X, _|_) >= X  because [6], by (Select) 
3.20/5.22	  6] X >= X  by (Meta) 
3.20/5.22	
3.20/5.22	  7] max(s(X), s(Y)) >= s(max(X, Y))  because [8], by (Star) 
3.20/5.22	  8] max*(s(X), s(Y)) >= s(max(X, Y))  because max > s and [9], by (Copy) 
3.20/5.22	  9] max*(s(X), s(Y)) >= max(X, Y)  because max in Mul, [10] and [13], by (Stat) 
3.20/5.22	  10] s(X) >= X  because [11], by (Star) 
3.20/5.22	  11] s*(X) >= X  because [12], by (Select) 
3.20/5.22	  12] X >= X  by (Meta) 
3.20/5.22	  13] s(Y) > Y  because [14], by definition 
3.20/5.22	  14] s*(Y) >= Y  because [15], by (Select) 
3.20/5.22	  15] Y >= Y  by (Meta) 
3.20/5.22	
3.20/5.22	  16] min(_|_, X) >= _|_  by (Bot) 
3.20/5.22	
3.20/5.22	  17] min(X, _|_) >= _|_  by (Bot) 
3.20/5.22	
3.20/5.22	  18] min(s(X), s(Y)) >= s(min(X, Y))  because [19], by (Star) 
3.20/5.22	  19] min*(s(X), s(Y)) >= s(min(X, Y))  because min > s and [20], by (Copy) 
3.20/5.22	  20] min*(s(X), s(Y)) >= min(X, Y)  because min in Mul, [21] and [24], by (Stat) 
3.20/5.22	  21] s(X) >= X  because [22], by (Star) 
3.20/5.22	  22] s*(X) >= X  because [23], by (Select) 
3.20/5.22	  23] X >= X  by (Meta) 
3.20/5.22	  24] s(Y) > Y  because [25], by definition 
3.20/5.22	  25] s*(Y) >= Y  because [26], by (Select) 
3.20/5.22	  26] Y >= Y  by (Meta) 
3.20/5.22	
3.20/5.22	  27] insert(X, _|_, F, G) >= cons(X, _|_)  because [28], by (Star) 
3.20/5.22	  28] insert*(X, _|_, F, G) >= cons(X, _|_)  because insert > cons, [29] and [31], by (Copy) 
3.20/5.22	  29] insert*(X, _|_, F, G) >= X  because [30], by (Select) 
3.20/5.22	  30] X >= X  by (Meta) 
3.20/5.22	  31] insert*(X, _|_, F, G) >= _|_  by (Bot) 
3.20/5.22	
3.20/5.22	  32] insert(X, cons(Y, Z), F, G) >= cons(@_{o -> o}(@_{o -> o -> o}(F, X), Y), insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G))  because [33], by (Star) 
3.20/5.22	  33] insert*(X, cons(Y, Z), F, G) >= cons(@_{o -> o}(@_{o -> o -> o}(F, X), Y), insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G))  because insert > cons, [34] and [44], by (Copy) 
3.20/5.22	  34] insert*(X, cons(Y, Z), F, G) >= @_{o -> o}(@_{o -> o -> o}(F, X), Y)  because insert > @_{o -> o}, [35] and [40], by (Copy) 
3.20/5.22	  35] insert*(X, cons(Y, Z), F, G) >= @_{o -> o -> o}(F, X)  because insert > @_{o -> o -> o}, [36] and [38], by (Copy) 
3.20/5.22	  36] insert*(X, cons(Y, Z), F, G) >= F  because [37], by (Select) 
3.20/5.22	  37] F >= F  by (Meta) 
3.20/5.22	  38] insert*(X, cons(Y, Z), F, G) >= X  because [39], by (Select) 
3.20/5.23	  39] X >= X  by (Meta) 
3.20/5.23	  40] insert*(X, cons(Y, Z), F, G) >= Y  because [41], by (Select) 
3.20/5.23	  41] cons(Y, Z) >= Y  because [42], by (Star) 
3.20/5.23	  42] cons*(Y, Z) >= Y  because [43], by (Select) 
3.20/5.23	  43] Y >= Y  by (Meta) 
3.20/5.23	  44] insert*(X, cons(Y, Z), F, G) >= insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G)  because [45], [48], [52], [36] and [50], by (Stat) 
3.20/5.23	  45] cons(Y, Z) > Z  because [46], by definition 
3.20/5.23	  46] cons*(Y, Z) >= Z  because [47], by (Select) 
3.20/5.23	  47] Z >= Z  by (Meta) 
3.20/5.23	  48] insert*(X, cons(Y, Z), F, G) >= @_{o -> o}(@_{o -> o -> o}(G, X), Y)  because insert > @_{o -> o}, [49] and [40], by (Copy) 
3.20/5.23	  49] insert*(X, cons(Y, Z), F, G) >= @_{o -> o -> o}(G, X)  because insert > @_{o -> o -> o}, [50] and [38], by (Copy) 
3.20/5.23	  50] insert*(X, cons(Y, Z), F, G) >= G  because [51], by (Select) 
3.20/5.23	  51] G >= G  by (Meta) 
3.20/5.23	  52] insert*(X, cons(Y, Z), F, G) >= Z  because [53], by (Select) 
3.20/5.23	  53] cons(Y, Z) >= Z  because [46], by (Star) 
3.20/5.23	
3.20/5.23	  54] sort(_|_, F, G) >= _|_  by (Bot) 
3.20/5.23	
3.20/5.23	  55] sort(cons(X, Y), F, G) >= insert(X, sort(Y, F, G), F, G)  because [56], by (Star) 
3.20/5.23	  56] sort*(cons(X, Y), F, G) >= insert(X, sort(Y, F, G), F, G)  because sort > insert, [57], [61], [67] and [68], by (Copy) 
3.20/5.23	  57] sort*(cons(X, Y), F, G) >= X  because [58], by (Select) 
3.20/5.23	  58] cons(X, Y) >= X  because [59], by (Star) 
3.20/5.23	  59] cons*(X, Y) >= X  because [60], by (Select) 
3.20/5.23	  60] X >= X  by (Meta) 
3.20/5.23	  61] sort*(cons(X, Y), F, G) >= sort(Y, F, G)  because sort in Mul, [62], [65] and [66], by (Stat) 
3.20/5.23	  62] cons(X, Y) > Y  because [63], by definition 
3.20/5.23	  63] cons*(X, Y) >= Y  because [64], by (Select) 
3.20/5.23	  64] Y >= Y  by (Meta) 
3.20/5.23	  65] F >= F  by (Meta) 
3.20/5.23	  66] G >= G  by (Meta) 
3.20/5.23	  67] sort*(cons(X, Y), F, G) >= F  because [65], by (Select) 
3.20/5.23	  68] sort*(cons(X, Y), F, G) >= G  because [66], by (Select) 
3.20/5.23	
3.20/5.23	  69] ascending!6220sort(X) >= sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u))  because [70], by (Star) 
3.20/5.23	  70] ascending!6220sort*(X) >= sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u))  because ascending!6220sort > sort, [71], [73] and [80], by (Copy) 
3.20/5.23	  71] ascending!6220sort*(X) >= X  because [72], by (Select) 
3.20/5.23	  72] X >= X  by (Meta) 
3.20/5.23	  73] ascending!6220sort*(X) >= /\y./\z.min(y, z)  because [74], by (F-Abs) 
3.20/5.23	  74] ascending!6220sort*(X, x) >= /\z.min(x, z)  because [75], by (F-Abs) 
3.20/5.23	  75] ascending!6220sort*(X, x, y) >= min(x, y)  because ascending!6220sort > min, [76] and [78], by (Copy) 
3.20/5.23	  76] ascending!6220sort*(X, x, y) >= x  because [77], by (Select) 
3.20/5.23	  77] x >= x  by (Var) 
3.20/5.23	  78] ascending!6220sort*(X, x, y) >= y  because [79], by (Select) 
3.20/5.23	  79] y >= y  by (Var) 
3.20/5.23	  80] ascending!6220sort*(X) >= /\u./\v.max(u, v)  because [81], by (F-Abs) 
3.20/5.23	  81] ascending!6220sort*(X, z) >= /\v.max(z, v)  because [82], by (F-Abs) 
3.20/5.23	  82] ascending!6220sort*(X, z, u) >= max(z, u)  because ascending!6220sort > max, [83] and [85], by (Copy) 
3.20/5.23	  83] ascending!6220sort*(X, z, u) >= z  because [84], by (Select) 
3.20/5.23	  84] z >= z  by (Var) 
3.20/5.23	  85] ascending!6220sort*(X, z, u) >= u  because [86], by (Select) 
3.20/5.23	  86] u >= u  by (Var) 
3.20/5.23	
3.20/5.23	  87] descending!6220sort(X) >= sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u))  because [88], by (Star) 
3.20/5.23	  88] descending!6220sort*(X) >= sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u))  because descending!6220sort > sort, [89], [91] and [98], by (Copy) 
3.20/5.23	  89] descending!6220sort*(X) >= X  because [90], by (Select) 
3.20/5.23	  90] X >= X  by (Meta) 
3.20/5.23	  91] descending!6220sort*(X) >= /\y./\z.max(y, z)  because [92], by (F-Abs) 
3.20/5.23	  92] descending!6220sort*(X, x) >= /\z.max(x, z)  because [93], by (F-Abs) 
3.20/5.23	  93] descending!6220sort*(X, x, y) >= max(x, y)  because descending!6220sort > max, [94] and [96], by (Copy) 
3.20/5.23	  94] descending!6220sort*(X, x, y) >= x  because [95], by (Select) 
3.20/5.23	  95] x >= x  by (Var) 
3.20/5.23	  96] descending!6220sort*(X, x, y) >= y  because [97], by (Select) 
3.20/5.23	  97] y >= y  by (Var) 
3.20/5.23	  98] descending!6220sort*(X) >= /\u./\v.min(u, v)  because [99], by (F-Abs) 
3.20/5.23	  99] descending!6220sort*(X, z) >= /\v.min(z, v)  because [100], by (F-Abs) 
3.20/5.23	  100] descending!6220sort*(X, z, u) >= min(z, u)  because descending!6220sort > min, [101] and [103], by (Copy) 
3.20/5.23	  101] descending!6220sort*(X, z, u) >= z  because [102], by (Select) 
3.20/5.23	  102] z >= z  by (Var) 
3.20/5.23	  103] descending!6220sort*(X, z, u) >= u  because [104], by (Select) 
3.20/5.23	  104] u >= u  by (Var) 
3.20/5.23	
3.20/5.23	We can thus remove the following rules:
3.20/5.23	
3.20/5.23	  max(0, X) => X 
3.20/5.23	
3.20/5.23	We use rule removal, following [Kop12, Theorem 2.23].
3.20/5.23	
3.20/5.23	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
3.20/5.23	
3.20/5.23	  max(X, 0) >? X 
3.20/5.23	  max(s(X), s(Y)) >? s(max(X, Y)) 
3.20/5.23	  min(0, X) >? 0 
3.20/5.23	  min(X, 0) >? 0 
3.20/5.23	  min(s(X), s(Y)) >? s(min(X, Y)) 
3.20/5.23	  insert(X, nil, F, G) >? cons(X, nil) 
3.20/5.23	  insert(X, cons(Y, Z), F, G) >? cons(F X Y, insert(G X Y, Z, F, G)) 
3.20/5.23	  sort(nil, F, G) >? nil 
3.20/5.23	  sort(cons(X, Y), F, G) >? insert(X, sort(Y, F, G), F, G) 
3.20/5.23	  ascending!6220sort(X) >? sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u)) 
3.20/5.23	  descending!6220sort(X) >? sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u)) 
3.20/5.23	
3.20/5.23	We use a recursive path ordering as defined in [Kop12, Chapter 5].
3.20/5.23	
3.20/5.23	Argument functions:
3.20/5.23	
3.20/5.23	  [[0]] = _|_ 
3.20/5.23	  [[insert(x_1, x_2, x_3, x_4)]] = insert(x_2, x_4, x_3, x_1) 
3.20/5.23	  [[nil]] = _|_ 
3.20/5.23	
3.20/5.23	We choose Lex = {insert} and Mul = {@_{o -> o -> o}, @_{o -> o}, ascending!6220sort, cons, descending!6220sort, max, min, s, sort}, and the following precedence: ascending!6220sort > descending!6220sort > max > min > s > sort > insert > @_{o -> o -> o} > @_{o -> o} > cons
3.20/5.23	
3.20/5.23	Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:
3.20/5.23	
3.20/5.23	  max(X, _|_) > X 
3.20/5.23	  max(s(X), s(Y)) > s(max(X, Y)) 
3.20/5.23	  min(_|_, X) >= _|_ 
3.20/5.23	  min(X, _|_) >= _|_ 
3.20/5.23	  min(s(X), s(Y)) >= s(min(X, Y)) 
3.20/5.23	  insert(X, _|_, F, G) >= cons(X, _|_) 
3.20/5.23	  insert(X, cons(Y, Z), F, G) >= cons(@_{o -> o}(@_{o -> o -> o}(F, X), Y), insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G)) 
3.20/5.23	  sort(_|_, F, G) >= _|_ 
3.20/5.23	  sort(cons(X, Y), F, G) > insert(X, sort(Y, F, G), F, G) 
3.20/5.23	  ascending!6220sort(X) >= sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u)) 
3.20/5.23	  descending!6220sort(X) >= sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u)) 
3.20/5.23	
3.20/5.23	With these choices, we have:
3.20/5.23	
3.20/5.23	  1] max(X, _|_) > X  because [2], by definition 
3.20/5.23	  2] max*(X, _|_) >= X  because [3], by (Select) 
3.20/5.23	  3] X >= X  by (Meta) 
3.20/5.23	
3.20/5.23	  4] max(s(X), s(Y)) > s(max(X, Y))  because [5], by definition 
3.20/5.23	  5] max*(s(X), s(Y)) >= s(max(X, Y))  because max > s and [6], by (Copy) 
3.20/5.23	  6] max*(s(X), s(Y)) >= max(X, Y)  because max in Mul, [7] and [10], by (Stat) 
3.20/5.23	  7] s(X) >= X  because [8], by (Star) 
3.20/5.23	  8] s*(X) >= X  because [9], by (Select) 
3.20/5.23	  9] X >= X  by (Meta) 
3.20/5.23	  10] s(Y) > Y  because [11], by definition 
3.20/5.23	  11] s*(Y) >= Y  because [12], by (Select) 
3.20/5.23	  12] Y >= Y  by (Meta) 
3.20/5.23	
3.20/5.23	  13] min(_|_, X) >= _|_  by (Bot) 
3.20/5.23	
3.20/5.23	  14] min(X, _|_) >= _|_  by (Bot) 
3.20/5.23	
3.20/5.23	  15] min(s(X), s(Y)) >= s(min(X, Y))  because [16], by (Star) 
3.20/5.23	  16] min*(s(X), s(Y)) >= s(min(X, Y))  because min > s and [17], by (Copy) 
3.20/5.23	  17] min*(s(X), s(Y)) >= min(X, Y)  because min in Mul, [18] and [21], by (Stat) 
3.20/5.23	  18] s(X) >= X  because [19], by (Star) 
3.20/5.23	  19] s*(X) >= X  because [20], by (Select) 
3.20/5.23	  20] X >= X  by (Meta) 
3.20/5.23	  21] s(Y) > Y  because [22], by definition 
3.20/5.23	  22] s*(Y) >= Y  because [23], by (Select) 
3.20/5.23	  23] Y >= Y  by (Meta) 
3.20/5.23	
3.20/5.23	  24] insert(X, _|_, F, G) >= cons(X, _|_)  because [25], by (Star) 
3.20/5.23	  25] insert*(X, _|_, F, G) >= cons(X, _|_)  because insert > cons, [26] and [28], by (Copy) 
3.20/5.23	  26] insert*(X, _|_, F, G) >= X  because [27], by (Select) 
3.20/5.23	  27] X >= X  by (Meta) 
3.20/5.23	  28] insert*(X, _|_, F, G) >= _|_  by (Bot) 
3.20/5.23	
3.20/5.23	  29] insert(X, cons(Y, Z), F, G) >= cons(@_{o -> o}(@_{o -> o -> o}(F, X), Y), insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G))  because [30], by (Star) 
3.20/5.23	  30] insert*(X, cons(Y, Z), F, G) >= cons(@_{o -> o}(@_{o -> o -> o}(F, X), Y), insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G))  because insert > cons, [31] and [41], by (Copy) 
3.20/5.23	  31] insert*(X, cons(Y, Z), F, G) >= @_{o -> o}(@_{o -> o -> o}(F, X), Y)  because insert > @_{o -> o}, [32] and [37], by (Copy) 
3.20/5.23	  32] insert*(X, cons(Y, Z), F, G) >= @_{o -> o -> o}(F, X)  because insert > @_{o -> o -> o}, [33] and [35], by (Copy) 
3.20/5.23	  33] insert*(X, cons(Y, Z), F, G) >= F  because [34], by (Select) 
3.20/5.23	  34] F >= F  by (Meta) 
3.20/5.23	  35] insert*(X, cons(Y, Z), F, G) >= X  because [36], by (Select) 
3.20/5.23	  36] X >= X  by (Meta) 
3.20/5.23	  37] insert*(X, cons(Y, Z), F, G) >= Y  because [38], by (Select) 
3.20/5.23	  38] cons(Y, Z) >= Y  because [39], by (Star) 
3.20/5.23	  39] cons*(Y, Z) >= Y  because [40], by (Select) 
3.20/5.23	  40] Y >= Y  by (Meta) 
3.20/5.23	  41] insert*(X, cons(Y, Z), F, G) >= insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G)  because [42], [45], [49], [33] and [47], by (Stat) 
3.20/5.23	  42] cons(Y, Z) > Z  because [43], by definition 
3.20/5.23	  43] cons*(Y, Z) >= Z  because [44], by (Select) 
3.20/5.23	  44] Z >= Z  by (Meta) 
3.20/5.23	  45] insert*(X, cons(Y, Z), F, G) >= @_{o -> o}(@_{o -> o -> o}(G, X), Y)  because insert > @_{o -> o}, [46] and [37], by (Copy) 
3.20/5.23	  46] insert*(X, cons(Y, Z), F, G) >= @_{o -> o -> o}(G, X)  because insert > @_{o -> o -> o}, [47] and [35], by (Copy) 
3.20/5.23	  47] insert*(X, cons(Y, Z), F, G) >= G  because [48], by (Select) 
3.20/5.23	  48] G >= G  by (Meta) 
3.20/5.23	  49] insert*(X, cons(Y, Z), F, G) >= Z  because [50], by (Select) 
3.20/5.23	  50] cons(Y, Z) >= Z  because [43], by (Star) 
3.20/5.23	
3.20/5.23	  51] sort(_|_, F, G) >= _|_  by (Bot) 
3.20/5.23	
3.20/5.23	  52] sort(cons(X, Y), F, G) > insert(X, sort(Y, F, G), F, G)  because [53], by definition 
3.20/5.23	  53] sort*(cons(X, Y), F, G) >= insert(X, sort(Y, F, G), F, G)  because sort > insert, [54], [58], [64] and [65], by (Copy) 
3.20/5.23	  54] sort*(cons(X, Y), F, G) >= X  because [55], by (Select) 
3.20/5.23	  55] cons(X, Y) >= X  because [56], by (Star) 
3.20/5.23	  56] cons*(X, Y) >= X  because [57], by (Select) 
3.20/5.23	  57] X >= X  by (Meta) 
3.20/5.23	  58] sort*(cons(X, Y), F, G) >= sort(Y, F, G)  because sort in Mul, [59], [62] and [63], by (Stat) 
3.20/5.23	  59] cons(X, Y) > Y  because [60], by definition 
3.20/5.23	  60] cons*(X, Y) >= Y  because [61], by (Select) 
3.20/5.23	  61] Y >= Y  by (Meta) 
3.20/5.23	  62] F >= F  by (Meta) 
3.20/5.23	  63] G >= G  by (Meta) 
3.20/5.23	  64] sort*(cons(X, Y), F, G) >= F  because [62], by (Select) 
3.20/5.23	  65] sort*(cons(X, Y), F, G) >= G  because [63], by (Select) 
3.20/5.23	
3.20/5.23	  66] ascending!6220sort(X) >= sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u))  because [67], by (Star) 
3.20/5.23	  67] ascending!6220sort*(X) >= sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u))  because ascending!6220sort > sort, [68], [70] and [77], by (Copy) 
3.20/5.23	  68] ascending!6220sort*(X) >= X  because [69], by (Select) 
3.20/5.23	  69] X >= X  by (Meta) 
3.20/5.23	  70] ascending!6220sort*(X) >= /\y./\z.min(y, z)  because [71], by (F-Abs) 
3.20/5.23	  71] ascending!6220sort*(X, x) >= /\z.min(x, z)  because [72], by (F-Abs) 
3.20/5.23	  72] ascending!6220sort*(X, x, y) >= min(x, y)  because ascending!6220sort > min, [73] and [75], by (Copy) 
3.20/5.23	  73] ascending!6220sort*(X, x, y) >= x  because [74], by (Select) 
3.20/5.23	  74] x >= x  by (Var) 
3.20/5.23	  75] ascending!6220sort*(X, x, y) >= y  because [76], by (Select) 
3.20/5.23	  76] y >= y  by (Var) 
3.20/5.23	  77] ascending!6220sort*(X) >= /\u./\v.max(u, v)  because [78], by (F-Abs) 
3.20/5.23	  78] ascending!6220sort*(X, z) >= /\v.max(z, v)  because [79], by (F-Abs) 
3.20/5.23	  79] ascending!6220sort*(X, z, u) >= max(z, u)  because ascending!6220sort > max, [80] and [82], by (Copy) 
3.20/5.23	  80] ascending!6220sort*(X, z, u) >= z  because [81], by (Select) 
3.20/5.23	  81] z >= z  by (Var) 
3.20/5.23	  82] ascending!6220sort*(X, z, u) >= u  because [83], by (Select) 
3.20/5.23	  83] u >= u  by (Var) 
3.20/5.23	
3.20/5.23	  84] descending!6220sort(X) >= sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u))  because [85], by (Star) 
3.20/5.23	  85] descending!6220sort*(X) >= sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u))  because descending!6220sort > sort, [86], [88] and [95], by (Copy) 
3.20/5.23	  86] descending!6220sort*(X) >= X  because [87], by (Select) 
3.20/5.23	  87] X >= X  by (Meta) 
3.20/5.23	  88] descending!6220sort*(X) >= /\y./\z.max(y, z)  because [89], by (F-Abs) 
3.20/5.23	  89] descending!6220sort*(X, x) >= /\z.max(x, z)  because [90], by (F-Abs) 
3.20/5.23	  90] descending!6220sort*(X, x, y) >= max(x, y)  because descending!6220sort > max, [91] and [93], by (Copy) 
3.20/5.23	  91] descending!6220sort*(X, x, y) >= x  because [92], by (Select) 
3.20/5.23	  92] x >= x  by (Var) 
3.20/5.23	  93] descending!6220sort*(X, x, y) >= y  because [94], by (Select) 
3.20/5.23	  94] y >= y  by (Var) 
3.20/5.23	  95] descending!6220sort*(X) >= /\u./\v.min(u, v)  because [96], by (F-Abs) 
3.20/5.23	  96] descending!6220sort*(X, z) >= /\v.min(z, v)  because [97], by (F-Abs) 
3.20/5.23	  97] descending!6220sort*(X, z, u) >= min(z, u)  because descending!6220sort > min, [98] and [100], by (Copy) 
3.20/5.23	  98] descending!6220sort*(X, z, u) >= z  because [99], by (Select) 
3.20/5.23	  99] z >= z  by (Var) 
3.20/5.23	  100] descending!6220sort*(X, z, u) >= u  because [101], by (Select) 
3.20/5.23	  101] u >= u  by (Var) 
3.20/5.23	
3.20/5.23	We can thus remove the following rules:
3.20/5.23	
3.20/5.23	  max(X, 0) => X 
3.20/5.23	  max(s(X), s(Y)) => s(max(X, Y)) 
3.20/5.23	  sort(cons(X, Y), F, G) => insert(X, sort(Y, F, G), F, G) 
3.20/5.23	
3.20/5.23	We use rule removal, following [Kop12, Theorem 2.23].
3.20/5.23	
3.20/5.23	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
3.20/5.23	
3.20/5.23	  min(0, X) >? 0 
3.20/5.23	  min(X, 0) >? 0 
3.20/5.23	  min(s(X), s(Y)) >? s(min(X, Y)) 
3.20/5.23	  insert(X, nil, F, G) >? cons(X, nil) 
3.20/5.23	  insert(X, cons(Y, Z), F, G) >? cons(F X Y, insert(G X Y, Z, F, G)) 
3.20/5.23	  sort(nil, F, G) >? nil 
3.20/5.23	  ascending!6220sort(X) >? sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u)) 
3.20/5.23	  descending!6220sort(X) >? sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u)) 
3.20/5.23	
3.20/5.23	We use a recursive path ordering as defined in [Kop12, Chapter 5].
3.20/5.23	
3.20/5.23	Argument functions:
3.20/5.23	
3.20/5.23	  [[0]] = _|_ 
3.20/5.23	  [[insert(x_1, x_2, x_3, x_4)]] = insert(x_2, x_4, x_1, x_3) 
3.20/5.23	  [[nil]] = _|_ 
3.20/5.23	
3.20/5.23	We choose Lex = {insert} and Mul = {@_{o -> o -> o}, @_{o -> o}, ascending!6220sort, cons, descending!6220sort, max, min, s, sort}, and the following precedence: ascending!6220sort > descending!6220sort > insert > @_{o -> o -> o} > @_{o -> o} > cons > max > min > s > sort
3.20/5.23	
3.20/5.23	Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:
3.20/5.23	
3.20/5.23	  min(_|_, X) >= _|_ 
3.20/5.23	  min(X, _|_) >= _|_ 
3.20/5.23	  min(s(X), s(Y)) >= s(min(X, Y)) 
3.20/5.23	  insert(X, _|_, F, G) >= cons(X, _|_) 
3.20/5.23	  insert(X, cons(Y, Z), F, G) > cons(@_{o -> o}(@_{o -> o -> o}(F, X), Y), insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G)) 
3.20/5.23	  sort(_|_, F, G) >= _|_ 
3.20/5.23	  ascending!6220sort(X) >= sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u)) 
3.20/5.23	  descending!6220sort(X) >= sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u)) 
3.20/5.23	
3.20/5.23	With these choices, we have:
3.20/5.23	
3.20/5.23	  1] min(_|_, X) >= _|_  by (Bot) 
3.20/5.23	
3.20/5.23	  2] min(X, _|_) >= _|_  by (Bot) 
3.20/5.23	
3.20/5.23	  3] min(s(X), s(Y)) >= s(min(X, Y))  because [4], by (Star) 
3.20/5.23	  4] min*(s(X), s(Y)) >= s(min(X, Y))  because min > s and [5], by (Copy) 
3.20/5.23	  5] min*(s(X), s(Y)) >= min(X, Y)  because min in Mul, [6] and [9], by (Stat) 
3.20/5.23	  6] s(X) >= X  because [7], by (Star) 
3.20/5.23	  7] s*(X) >= X  because [8], by (Select) 
3.20/5.23	  8] X >= X  by (Meta) 
3.20/5.23	  9] s(Y) > Y  because [10], by definition 
3.20/5.23	  10] s*(Y) >= Y  because [11], by (Select) 
3.20/5.23	  11] Y >= Y  by (Meta) 
3.20/5.23	
3.20/5.23	  12] insert(X, _|_, F, G) >= cons(X, _|_)  because [13], by (Star) 
3.20/5.23	  13] insert*(X, _|_, F, G) >= cons(X, _|_)  because insert > cons, [14] and [16], by (Copy) 
3.20/5.23	  14] insert*(X, _|_, F, G) >= X  because [15], by (Select) 
3.20/5.23	  15] X >= X  by (Meta) 
3.20/5.23	  16] insert*(X, _|_, F, G) >= _|_  by (Bot) 
3.20/5.23	
3.20/5.23	  17] insert(X, cons(Y, Z), F, G) > cons(@_{o -> o}(@_{o -> o -> o}(F, X), Y), insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G))  because [18], by definition 
3.20/5.23	  18] insert*(X, cons(Y, Z), F, G) >= cons(@_{o -> o}(@_{o -> o -> o}(F, X), Y), insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G))  because insert > cons, [19] and [29], by (Copy) 
3.20/5.23	  19] insert*(X, cons(Y, Z), F, G) >= @_{o -> o}(@_{o -> o -> o}(F, X), Y)  because insert > @_{o -> o}, [20] and [25], by (Copy) 
3.20/5.23	  20] insert*(X, cons(Y, Z), F, G) >= @_{o -> o -> o}(F, X)  because insert > @_{o -> o -> o}, [21] and [23], by (Copy) 
3.20/5.23	  21] insert*(X, cons(Y, Z), F, G) >= F  because [22], by (Select) 
3.20/5.23	  22] F >= F  by (Meta) 
3.20/5.23	  23] insert*(X, cons(Y, Z), F, G) >= X  because [24], by (Select) 
3.20/5.23	  24] X >= X  by (Meta) 
3.20/5.23	  25] insert*(X, cons(Y, Z), F, G) >= Y  because [26], by (Select) 
3.20/5.23	  26] cons(Y, Z) >= Y  because [27], by (Star) 
3.20/5.23	  27] cons*(Y, Z) >= Y  because [28], by (Select) 
3.20/5.23	  28] Y >= Y  by (Meta) 
3.20/5.23	  29] insert*(X, cons(Y, Z), F, G) >= insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G)  because [30], [33], [37], [21] and [35], by (Stat) 
3.20/5.23	  30] cons(Y, Z) > Z  because [31], by definition 
3.20/5.23	  31] cons*(Y, Z) >= Z  because [32], by (Select) 
3.20/5.23	  32] Z >= Z  by (Meta) 
3.20/5.23	  33] insert*(X, cons(Y, Z), F, G) >= @_{o -> o}(@_{o -> o -> o}(G, X), Y)  because insert > @_{o -> o}, [34] and [25], by (Copy) 
3.20/5.23	  34] insert*(X, cons(Y, Z), F, G) >= @_{o -> o -> o}(G, X)  because insert > @_{o -> o -> o}, [35] and [23], by (Copy) 
3.20/5.23	  35] insert*(X, cons(Y, Z), F, G) >= G  because [36], by (Select) 
3.20/5.23	  36] G >= G  by (Meta) 
3.20/5.23	  37] insert*(X, cons(Y, Z), F, G) >= Z  because [38], by (Select) 
3.20/5.23	  38] cons(Y, Z) >= Z  because [31], by (Star) 
3.20/5.23	
3.20/5.23	  39] sort(_|_, F, G) >= _|_  by (Bot) 
3.20/5.23	
3.20/5.23	  40] ascending!6220sort(X) >= sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u))  because [41], by (Star) 
3.20/5.23	  41] ascending!6220sort*(X) >= sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u))  because ascending!6220sort > sort, [42], [44] and [51], by (Copy) 
3.20/5.23	  42] ascending!6220sort*(X) >= X  because [43], by (Select) 
3.20/5.23	  43] X >= X  by (Meta) 
3.20/5.23	  44] ascending!6220sort*(X) >= /\y./\z.min(y, z)  because [45], by (F-Abs) 
3.20/5.23	  45] ascending!6220sort*(X, x) >= /\z.min(x, z)  because [46], by (F-Abs) 
3.20/5.23	  46] ascending!6220sort*(X, x, y) >= min(x, y)  because ascending!6220sort > min, [47] and [49], by (Copy) 
3.20/5.23	  47] ascending!6220sort*(X, x, y) >= x  because [48], by (Select) 
3.20/5.23	  48] x >= x  by (Var) 
3.20/5.23	  49] ascending!6220sort*(X, x, y) >= y  because [50], by (Select) 
3.20/5.23	  50] y >= y  by (Var) 
3.20/5.23	  51] ascending!6220sort*(X) >= /\u./\v.max(u, v)  because [52], by (F-Abs) 
3.20/5.23	  52] ascending!6220sort*(X, z) >= /\v.max(z, v)  because [53], by (F-Abs) 
3.20/5.23	  53] ascending!6220sort*(X, z, u) >= max(z, u)  because ascending!6220sort > max, [54] and [56], by (Copy) 
3.20/5.23	  54] ascending!6220sort*(X, z, u) >= z  because [55], by (Select) 
3.20/5.23	  55] z >= z  by (Var) 
3.20/5.23	  56] ascending!6220sort*(X, z, u) >= u  because [57], by (Select) 
3.20/5.23	  57] u >= u  by (Var) 
3.20/5.23	
3.20/5.23	  58] descending!6220sort(X) >= sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u))  because [59], by (Star) 
3.20/5.23	  59] descending!6220sort*(X) >= sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u))  because descending!6220sort > sort, [60], [62] and [69], by (Copy) 
3.20/5.23	  60] descending!6220sort*(X) >= X  because [61], by (Select) 
3.20/5.23	  61] X >= X  by (Meta) 
3.20/5.23	  62] descending!6220sort*(X) >= /\y./\z.max(y, z)  because [63], by (F-Abs) 
3.20/5.23	  63] descending!6220sort*(X, x) >= /\z.max(x, z)  because [64], by (F-Abs) 
3.20/5.23	  64] descending!6220sort*(X, x, y) >= max(x, y)  because descending!6220sort > max, [65] and [67], by (Copy) 
3.20/5.23	  65] descending!6220sort*(X, x, y) >= x  because [66], by (Select) 
3.20/5.23	  66] x >= x  by (Var) 
3.20/5.23	  67] descending!6220sort*(X, x, y) >= y  because [68], by (Select) 
3.20/5.23	  68] y >= y  by (Var) 
3.20/5.23	  69] descending!6220sort*(X) >= /\u./\v.min(u, v)  because [70], by (F-Abs) 
3.20/5.23	  70] descending!6220sort*(X, z) >= /\v.min(z, v)  because [71], by (F-Abs) 
3.20/5.23	  71] descending!6220sort*(X, z, u) >= min(z, u)  because descending!6220sort > min, [72] and [74], by (Copy) 
3.20/5.23	  72] descending!6220sort*(X, z, u) >= z  because [73], by (Select) 
3.20/5.23	  73] z >= z  by (Var) 
3.20/5.23	  74] descending!6220sort*(X, z, u) >= u  because [75], by (Select) 
3.20/5.23	  75] u >= u  by (Var) 
3.20/5.23	
3.20/5.23	We can thus remove the following rules:
3.20/5.23	
3.20/5.23	  insert(X, cons(Y, Z), F, G) => cons(F X Y, insert(G X Y, Z, F, G)) 
3.20/5.23	
3.20/5.23	We use rule removal, following [Kop12, Theorem 2.23].
3.20/5.23	
3.20/5.23	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
3.20/5.23	
3.20/5.23	  min(0, X) >? 0 
3.20/5.23	  min(X, 0) >? 0 
3.20/5.23	  min(s(X), s(Y)) >? s(min(X, Y)) 
3.20/5.23	  insert(X, nil, F, G) >? cons(X, nil) 
3.20/5.23	  sort(nil, F, G) >? nil 
3.20/5.23	  ascending!6220sort(X) >? sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u)) 
3.20/5.23	  descending!6220sort(X) >? sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u)) 
3.20/5.23	
3.20/5.23	We orient these requirements with a polynomial interpretation in the natural numbers.
3.20/5.23	
3.20/5.23	The following interpretation satisfies the requirements:
3.20/5.23	
3.20/5.23	  0 = 1 
3.20/5.23	  ascending!6220sort = \y0.3 + 3y0 
3.20/5.23	  cons = \y0y1.y0 + y1 
3.20/5.23	  descending!6220sort = \y0.3 + 3y0 
3.20/5.23	  insert = \y0y1G2G3.3 + 3y0 + 3y1 + G3(0,0) + 2G2(0,0) 
3.20/5.23	  max = \y0y1.y0 + y1 
3.20/5.23	  min = \y0y1.2y0 + 2y1 
3.20/5.23	  nil = 0 
3.20/5.23	  s = \y0.2 + y0 
3.20/5.23	  sort = \y0G1G2.2 + 2y0 + G2(0,0) + 2G1(0,0) 
3.20/5.23	
3.20/5.23	Using this interpretation, the requirements translate to:
3.20/5.23	
3.20/5.23	  [[min(0, _x0)]] = 2 + 2x0 > 1 = [[0]] 
3.20/5.23	  [[min(_x0, 0)]] = 2 + 2x0 > 1 = [[0]] 
3.20/5.23	  [[min(s(_x0), s(_x1))]] = 8 + 2x0 + 2x1 > 2 + 2x0 + 2x1 = [[s(min(_x0, _x1))]] 
3.20/5.23	  [[insert(_x0, nil, _F1, _F2)]] = 3 + 3x0 + F2(0,0) + 2F1(0,0) > x0 = [[cons(_x0, nil)]] 
3.20/5.23	  [[sort(nil, _F0, _F1)]] = 2 + F1(0,0) + 2F0(0,0) > 0 = [[nil]] 
3.20/5.23	  [[ascending!6220sort(_x0)]] = 3 + 3x0 > 2 + 2x0 = [[sort(_x0, /\x./\y.min(x, y), /\z./\u.max(z, u))]] 
3.20/5.23	  [[descending!6220sort(_x0)]] = 3 + 3x0 > 2 + 2x0 = [[sort(_x0, /\x./\y.max(x, y), /\z./\u.min(z, u))]] 
3.20/5.23	
3.20/5.23	We can thus remove the following rules:
3.20/5.23	
3.20/5.23	  min(0, X) => 0 
3.20/5.23	  min(X, 0) => 0 
3.20/5.23	  min(s(X), s(Y)) => s(min(X, Y)) 
3.20/5.23	  insert(X, nil, F, G) => cons(X, nil) 
3.20/5.23	  sort(nil, F, G) => nil 
3.20/5.23	  ascending!6220sort(X) => sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u)) 
3.20/5.23	  descending!6220sort(X) => sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u)) 
3.20/5.23	
3.20/5.23	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.
3.20/5.23	
3.20/5.23	
3.20/5.23	+++ Citations +++
3.20/5.23	
3.20/5.23	[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.
3.20/5.23	EOF