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