1.06/1.12 YES 1.22/1.25 We consider the system theBenchmark. 1.22/1.25 1.22/1.25 Alphabet: 1.22/1.25 1.22/1.25 and : [a * a] --> a 1.22/1.25 cons : [c * d] --> d 1.22/1.25 false : [] --> b 1.22/1.25 filter : [c -> b * d] --> d 1.22/1.25 filter2 : [b * c -> b * c * d] --> d 1.22/1.25 map : [c -> c * d] --> d 1.22/1.25 nil : [] --> d 1.22/1.25 not : [a] --> a 1.22/1.25 or : [a * a] --> a 1.22/1.25 true : [] --> b 1.22/1.25 1.22/1.25 Rules: 1.22/1.25 1.22/1.25 not(not(x)) => x 1.22/1.25 not(or(x, y)) => and(not(x), not(y)) 1.22/1.25 not(and(x, y)) => or(not(x), not(y)) 1.22/1.25 and(x, or(y, z)) => or(and(x, y), and(x, z)) 1.22/1.25 and(or(x, y), z) => or(and(z, x), and(z, y)) 1.22/1.25 map(f, nil) => nil 1.22/1.25 map(f, cons(x, y)) => cons(f x, map(f, y)) 1.22/1.25 filter(f, nil) => nil 1.22/1.25 filter(f, cons(x, y)) => filter2(f x, f, x, y) 1.22/1.25 filter2(true, f, x, y) => cons(x, filter(f, y)) 1.22/1.25 filter2(false, f, x, y) => filter(f, y) 1.22/1.25 1.22/1.25 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 1.22/1.25 1.22/1.25 We use rule removal, following [Kop12, Theorem 2.23]. 1.22/1.25 1.22/1.25 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 1.22/1.25 1.22/1.25 not(not(X)) >? X 1.22/1.25 not(or(X, Y)) >? and(not(X), not(Y)) 1.22/1.25 not(and(X, Y)) >? or(not(X), not(Y)) 1.22/1.25 and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) 1.22/1.25 and(or(X, Y), Z) >? or(and(Z, X), and(Z, Y)) 1.22/1.25 map(F, nil) >? nil 1.22/1.25 map(F, cons(X, Y)) >? cons(F X, map(F, Y)) 1.22/1.25 filter(F, nil) >? nil 1.22/1.25 filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 1.22/1.25 filter2(true, F, X, Y) >? cons(X, filter(F, Y)) 1.22/1.25 filter2(false, F, X, Y) >? filter(F, Y) 1.22/1.25 1.22/1.25 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 1.22/1.25 1.22/1.25 Argument functions: 1.22/1.25 1.22/1.25 [[filter(x_1, x_2)]] = filter(x_2, x_1) 1.22/1.25 [[filter2(x_1, x_2, x_3, x_4)]] = filter2(x_4, x_2, x_1, x_3) 1.22/1.25 [[nil]] = _|_ 1.22/1.25 1.22/1.25 We choose Lex = {filter, filter2} and Mul = {@_{o -> o}, and, cons, false, map, not, or, true}, and the following precedence: false > filter = filter2 > not > and > or > map > @_{o -> o} > cons > true 1.22/1.25 1.22/1.25 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 1.22/1.25 1.22/1.25 not(not(X)) >= X 1.22/1.25 not(or(X, Y)) > and(not(X), not(Y)) 1.22/1.25 not(and(X, Y)) >= or(not(X), not(Y)) 1.22/1.25 and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) 1.22/1.25 and(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) 1.22/1.25 map(F, _|_) >= _|_ 1.22/1.25 map(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) 1.22/1.25 filter(F, _|_) >= _|_ 1.22/1.25 filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) 1.22/1.25 filter2(true, F, X, Y) >= cons(X, filter(F, Y)) 1.22/1.25 filter2(false, F, X, Y) >= filter(F, Y) 1.22/1.25 1.22/1.25 With these choices, we have: 1.22/1.25 1.22/1.25 1] not(not(X)) >= X because [2], by (Star) 1.22/1.25 2] not*(not(X)) >= X because [3], by (Select) 1.22/1.25 3] not(X) >= X because [4], by (Star) 1.22/1.25 4] not*(X) >= X because [5], by (Select) 1.22/1.25 5] X >= X by (Meta) 1.22/1.25 1.22/1.25 6] not(or(X, Y)) > and(not(X), not(Y)) because [7], by definition 1.22/1.25 7] not*(or(X, Y)) >= and(not(X), not(Y)) because not > and, [8] and [12], by (Copy) 1.22/1.25 8] not*(or(X, Y)) >= not(X) because not in Mul and [9], by (Stat) 1.22/1.25 9] or(X, Y) > X because [10], by definition 1.22/1.25 10] or*(X, Y) >= X because [11], by (Select) 1.22/1.25 11] X >= X by (Meta) 1.22/1.25 12] not*(or(X, Y)) >= not(Y) because not in Mul and [13], by (Stat) 1.22/1.25 13] or(X, Y) > Y because [14], by definition 1.22/1.25 14] or*(X, Y) >= Y because [15], by (Select) 1.22/1.25 15] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 16] not(and(X, Y)) >= or(not(X), not(Y)) because [17], by (Star) 1.22/1.25 17] not*(and(X, Y)) >= or(not(X), not(Y)) because not > or, [18] and [22], by (Copy) 1.22/1.25 18] not*(and(X, Y)) >= not(X) because not in Mul and [19], by (Stat) 1.22/1.25 19] and(X, Y) > X because [20], by definition 1.22/1.25 20] and*(X, Y) >= X because [21], by (Select) 1.22/1.25 21] X >= X by (Meta) 1.22/1.25 22] not*(and(X, Y)) >= not(Y) because not in Mul and [23], by (Stat) 1.22/1.25 23] and(X, Y) > Y because [24], by definition 1.22/1.25 24] and*(X, Y) >= Y because [25], by (Select) 1.22/1.25 25] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 26] and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because [27], by (Star) 1.22/1.25 27] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because and > or, [28] and [33], by (Copy) 1.22/1.25 28] and*(X, or(Y, Z)) >= and(X, Y) because and in Mul, [29] and [30], by (Stat) 1.22/1.25 29] X >= X by (Meta) 1.22/1.25 30] or(Y, Z) > Y because [31], by definition 1.22/1.25 31] or*(Y, Z) >= Y because [32], by (Select) 1.22/1.25 32] Y >= Y by (Meta) 1.22/1.25 33] and*(X, or(Y, Z)) >= and(X, Z) because and in Mul, [29] and [34], by (Stat) 1.22/1.25 34] or(Y, Z) > Z because [35], by definition 1.22/1.25 35] or*(Y, Z) >= Z because [36], by (Select) 1.22/1.25 36] Z >= Z by (Meta) 1.22/1.25 1.22/1.25 37] and(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because [38], by (Star) 1.22/1.25 38] and*(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because and > or, [39] and [44], by (Copy) 1.22/1.25 39] and*(or(X, Y), Z) >= and(Z, X) because and in Mul, [40] and [43], by (Stat) 1.22/1.25 40] or(X, Y) > X because [41], by definition 1.22/1.25 41] or*(X, Y) >= X because [42], by (Select) 1.22/1.25 42] X >= X by (Meta) 1.22/1.25 43] Z >= Z by (Meta) 1.22/1.25 44] and*(or(X, Y), Z) >= and(Z, Y) because and in Mul, [45] and [43], by (Stat) 1.22/1.25 45] or(X, Y) > Y because [46], by definition 1.22/1.25 46] or*(X, Y) >= Y because [47], by (Select) 1.22/1.25 47] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 48] map(F, _|_) >= _|_ by (Bot) 1.22/1.25 1.22/1.25 49] map(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) because [50], by (Star) 1.22/1.25 50] map*(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) because map > cons, [51] and [58], by (Copy) 1.22/1.25 51] map*(F, cons(X, Y)) >= @_{o -> o}(F, X) because map > @_{o -> o}, [52] and [54], by (Copy) 1.22/1.25 52] map*(F, cons(X, Y)) >= F because [53], by (Select) 1.22/1.25 53] F >= F by (Meta) 1.22/1.25 54] map*(F, cons(X, Y)) >= X because [55], by (Select) 1.22/1.25 55] cons(X, Y) >= X because [56], by (Star) 1.22/1.25 56] cons*(X, Y) >= X because [57], by (Select) 1.22/1.25 57] X >= X by (Meta) 1.22/1.25 58] map*(F, cons(X, Y)) >= map(F, Y) because map in Mul, [59] and [60], by (Stat) 1.22/1.25 59] F >= F by (Meta) 1.22/1.25 60] cons(X, Y) > Y because [61], by definition 1.22/1.25 61] cons*(X, Y) >= Y because [62], by (Select) 1.22/1.25 62] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 63] filter(F, _|_) >= _|_ by (Bot) 1.22/1.25 1.22/1.25 64] filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because [65], by (Star) 1.22/1.25 65] filter*(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because filter = filter2, [66], [69], [70], [72] and [76], by (Stat) 1.22/1.25 66] cons(X, Y) > Y because [67], by definition 1.22/1.25 67] cons*(X, Y) >= Y because [68], by (Select) 1.22/1.25 68] Y >= Y by (Meta) 1.22/1.25 69] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [70] and [72], by (Copy) 1.22/1.25 70] filter*(F, cons(X, Y)) >= F because [71], by (Select) 1.22/1.25 71] F >= F by (Meta) 1.22/1.25 72] filter*(F, cons(X, Y)) >= X because [73], by (Select) 1.22/1.25 73] cons(X, Y) >= X because [74], by (Star) 1.22/1.25 74] cons*(X, Y) >= X because [75], by (Select) 1.22/1.25 75] X >= X by (Meta) 1.22/1.25 76] filter*(F, cons(X, Y)) >= Y because [77], by (Select) 1.22/1.25 77] cons(X, Y) >= Y because [67], by (Star) 1.22/1.25 1.22/1.25 78] filter2(true, F, X, Y) >= cons(X, filter(F, Y)) because [79], by (Star) 1.22/1.25 79] filter2*(true, F, X, Y) >= cons(X, filter(F, Y)) because filter2 > cons, [80] and [82], by (Copy) 1.22/1.25 80] filter2*(true, F, X, Y) >= X because [81], by (Select) 1.22/1.25 81] X >= X by (Meta) 1.22/1.25 82] filter2*(true, F, X, Y) >= filter(F, Y) because filter2 = filter, [83], [84], [85] and [86], by (Stat) 1.22/1.25 83] F >= F by (Meta) 1.22/1.25 84] Y >= Y by (Meta) 1.22/1.25 85] filter2*(true, F, X, Y) >= F because [83], by (Select) 1.22/1.25 86] filter2*(true, F, X, Y) >= Y because [84], by (Select) 1.22/1.25 1.22/1.25 87] filter2(false, F, X, Y) >= filter(F, Y) because [88], by (Star) 1.22/1.25 88] filter2*(false, F, X, Y) >= filter(F, Y) because filter2 = filter, [89], [90], [91] and [92], by (Stat) 1.22/1.25 89] F >= F by (Meta) 1.22/1.25 90] Y >= Y by (Meta) 1.22/1.25 91] filter2*(false, F, X, Y) >= F because [89], by (Select) 1.22/1.25 92] filter2*(false, F, X, Y) >= Y because [90], by (Select) 1.22/1.25 1.22/1.25 We can thus remove the following rules: 1.22/1.25 1.22/1.25 not(or(X, Y)) => and(not(X), not(Y)) 1.22/1.25 1.22/1.25 We use rule removal, following [Kop12, Theorem 2.23]. 1.22/1.25 1.22/1.25 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 1.22/1.25 1.22/1.25 not(not(X)) >? X 1.22/1.25 not(and(X, Y)) >? or(not(X), not(Y)) 1.22/1.25 and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) 1.22/1.25 and(or(X, Y), Z) >? or(and(Z, X), and(Z, Y)) 1.22/1.25 map(F, nil) >? nil 1.22/1.25 map(F, cons(X, Y)) >? cons(F X, map(F, Y)) 1.22/1.25 filter(F, nil) >? nil 1.22/1.25 filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 1.22/1.25 filter2(true, F, X, Y) >? cons(X, filter(F, Y)) 1.22/1.25 filter2(false, F, X, Y) >? filter(F, Y) 1.22/1.25 1.22/1.25 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 1.22/1.25 1.22/1.25 Argument functions: 1.22/1.25 1.22/1.25 [[filter(x_1, x_2)]] = filter(x_2, x_1) 1.22/1.25 [[filter2(x_1, x_2, x_3, x_4)]] = filter2(x_4, x_2, x_1, x_3) 1.22/1.25 [[nil]] = _|_ 1.22/1.25 1.22/1.25 We choose Lex = {filter, filter2} and Mul = {@_{o -> o}, and, cons, false, map, not, or, true}, and the following precedence: and = not > or > map > filter = filter2 > cons > true > false > @_{o -> o} 1.22/1.25 1.22/1.25 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 1.22/1.25 1.22/1.25 not(not(X)) > X 1.22/1.25 not(and(X, Y)) >= or(not(X), not(Y)) 1.22/1.25 and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) 1.22/1.25 and(or(X, Y), Z) > or(and(Z, X), and(Z, Y)) 1.22/1.25 map(F, _|_) >= _|_ 1.22/1.25 map(F, cons(X, Y)) > cons(@_{o -> o}(F, X), map(F, Y)) 1.22/1.25 filter(F, _|_) >= _|_ 1.22/1.25 filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) 1.22/1.25 filter2(true, F, X, Y) > cons(X, filter(F, Y)) 1.22/1.25 filter2(false, F, X, Y) >= filter(F, Y) 1.22/1.25 1.22/1.25 With these choices, we have: 1.22/1.25 1.22/1.25 1] not(not(X)) > X because [2], by definition 1.22/1.25 2] not*(not(X)) >= X because [3], by (Select) 1.22/1.25 3] not(X) >= X because [4], by (Star) 1.22/1.25 4] not*(X) >= X because [5], by (Select) 1.22/1.25 5] X >= X by (Meta) 1.22/1.25 1.22/1.25 6] not(and(X, Y)) >= or(not(X), not(Y)) because [7], by (Star) 1.22/1.25 7] not*(and(X, Y)) >= or(not(X), not(Y)) because not > or, [8] and [12], by (Copy) 1.22/1.25 8] not*(and(X, Y)) >= not(X) because [9], by (Select) 1.22/1.25 9] and(X, Y) >= not(X) because [10], by (Star) 1.22/1.25 10] and*(X, Y) >= not(X) because and = not, and in Mul and [11], by (Stat) 1.22/1.25 11] X >= X by (Meta) 1.22/1.25 12] not*(and(X, Y)) >= not(Y) because [13], by (Select) 1.22/1.25 13] and(X, Y) >= not(Y) because [14], by (Star) 1.22/1.25 14] and*(X, Y) >= not(Y) because and = not, and in Mul and [15], by (Stat) 1.22/1.25 15] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 16] and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because [17], by (Star) 1.22/1.25 17] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because and > or, [18] and [23], by (Copy) 1.22/1.25 18] and*(X, or(Y, Z)) >= and(X, Y) because and in Mul, [19] and [20], by (Stat) 1.22/1.25 19] X >= X by (Meta) 1.22/1.25 20] or(Y, Z) > Y because [21], by definition 1.22/1.25 21] or*(Y, Z) >= Y because [22], by (Select) 1.22/1.25 22] Y >= Y by (Meta) 1.22/1.25 23] and*(X, or(Y, Z)) >= and(X, Z) because and in Mul, [19] and [24], by (Stat) 1.22/1.25 24] or(Y, Z) > Z because [25], by definition 1.22/1.25 25] or*(Y, Z) >= Z because [26], by (Select) 1.22/1.25 26] Z >= Z by (Meta) 1.22/1.25 1.22/1.25 27] and(or(X, Y), Z) > or(and(Z, X), and(Z, Y)) because [28], by definition 1.22/1.25 28] and*(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because and > or, [29] and [34], by (Copy) 1.22/1.25 29] and*(or(X, Y), Z) >= and(Z, X) because and in Mul, [30] and [33], by (Stat) 1.22/1.25 30] or(X, Y) > X because [31], by definition 1.22/1.25 31] or*(X, Y) >= X because [32], by (Select) 1.22/1.25 32] X >= X by (Meta) 1.22/1.25 33] Z >= Z by (Meta) 1.22/1.25 34] and*(or(X, Y), Z) >= and(Z, Y) because and in Mul, [35] and [33], by (Stat) 1.22/1.25 35] or(X, Y) > Y because [36], by definition 1.22/1.25 36] or*(X, Y) >= Y because [37], by (Select) 1.22/1.25 37] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 38] map(F, _|_) >= _|_ by (Bot) 1.22/1.25 1.22/1.25 39] map(F, cons(X, Y)) > cons(@_{o -> o}(F, X), map(F, Y)) because [40], by definition 1.22/1.25 40] map*(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) because map > cons, [41] and [48], by (Copy) 1.22/1.25 41] map*(F, cons(X, Y)) >= @_{o -> o}(F, X) because map > @_{o -> o}, [42] and [44], by (Copy) 1.22/1.25 42] map*(F, cons(X, Y)) >= F because [43], by (Select) 1.22/1.25 43] F >= F by (Meta) 1.22/1.25 44] map*(F, cons(X, Y)) >= X because [45], by (Select) 1.22/1.25 45] cons(X, Y) >= X because [46], by (Star) 1.22/1.25 46] cons*(X, Y) >= X because [47], by (Select) 1.22/1.25 47] X >= X by (Meta) 1.22/1.25 48] map*(F, cons(X, Y)) >= map(F, Y) because map in Mul, [49] and [50], by (Stat) 1.22/1.25 49] F >= F by (Meta) 1.22/1.25 50] cons(X, Y) > Y because [51], by definition 1.22/1.25 51] cons*(X, Y) >= Y because [52], by (Select) 1.22/1.25 52] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 53] filter(F, _|_) >= _|_ by (Bot) 1.22/1.25 1.22/1.25 54] filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because [55], by (Star) 1.22/1.25 55] filter*(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because filter = filter2, [56], [59], [60], [62] and [66], by (Stat) 1.22/1.25 56] cons(X, Y) > Y because [57], by definition 1.22/1.25 57] cons*(X, Y) >= Y because [58], by (Select) 1.22/1.25 58] Y >= Y by (Meta) 1.22/1.25 59] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [60] and [62], by (Copy) 1.22/1.25 60] filter*(F, cons(X, Y)) >= F because [61], by (Select) 1.22/1.25 61] F >= F by (Meta) 1.22/1.25 62] filter*(F, cons(X, Y)) >= X because [63], by (Select) 1.22/1.25 63] cons(X, Y) >= X because [64], by (Star) 1.22/1.25 64] cons*(X, Y) >= X because [65], by (Select) 1.22/1.25 65] X >= X by (Meta) 1.22/1.25 66] filter*(F, cons(X, Y)) >= Y because [67], by (Select) 1.22/1.25 67] cons(X, Y) >= Y because [57], by (Star) 1.22/1.25 1.22/1.25 68] filter2(true, F, X, Y) > cons(X, filter(F, Y)) because [69], by definition 1.22/1.25 69] filter2*(true, F, X, Y) >= cons(X, filter(F, Y)) because filter2 > cons, [70] and [72], by (Copy) 1.22/1.25 70] filter2*(true, F, X, Y) >= X because [71], by (Select) 1.22/1.25 71] X >= X by (Meta) 1.22/1.25 72] filter2*(true, F, X, Y) >= filter(F, Y) because filter2 = filter, [73], [74], [75] and [76], by (Stat) 1.22/1.25 73] F >= F by (Meta) 1.22/1.25 74] Y >= Y by (Meta) 1.22/1.25 75] filter2*(true, F, X, Y) >= F because [73], by (Select) 1.22/1.25 76] filter2*(true, F, X, Y) >= Y because [74], by (Select) 1.22/1.25 1.22/1.25 77] filter2(false, F, X, Y) >= filter(F, Y) because [78], by (Star) 1.22/1.25 78] filter2*(false, F, X, Y) >= filter(F, Y) because filter2 = filter, [79], [80], [81] and [82], by (Stat) 1.22/1.25 79] F >= F by (Meta) 1.22/1.25 80] Y >= Y by (Meta) 1.22/1.25 81] filter2*(false, F, X, Y) >= F because [79], by (Select) 1.22/1.25 82] filter2*(false, F, X, Y) >= Y because [80], by (Select) 1.22/1.25 1.22/1.25 We can thus remove the following rules: 1.22/1.25 1.22/1.25 not(not(X)) => X 1.22/1.25 and(or(X, Y), Z) => or(and(Z, X), and(Z, Y)) 1.22/1.25 map(F, cons(X, Y)) => cons(F X, map(F, Y)) 1.22/1.25 filter2(true, F, X, Y) => cons(X, filter(F, Y)) 1.22/1.25 1.22/1.25 We use rule removal, following [Kop12, Theorem 2.23]. 1.22/1.25 1.22/1.25 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 1.22/1.25 1.22/1.25 not(and(X, Y)) >? or(not(X), not(Y)) 1.22/1.25 and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) 1.22/1.25 map(F, nil) >? nil 1.22/1.25 filter(F, nil) >? nil 1.22/1.25 filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 1.22/1.25 filter2(false, F, X, Y) >? filter(F, Y) 1.22/1.25 1.22/1.25 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 1.22/1.25 1.22/1.25 Argument functions: 1.22/1.25 1.22/1.25 [[filter(x_1, x_2)]] = filter(x_2, x_1) 1.22/1.25 [[filter2(x_1, x_2, x_3, x_4)]] = filter2(x_4, x_2, x_3, x_1) 1.22/1.25 [[not(x_1)]] = x_1 1.22/1.25 1.22/1.25 We choose Lex = {filter, filter2} and Mul = {@_{o -> o}, and, cons, false, map, nil, or}, and the following precedence: filter = filter2 > nil > false > map > and > or > cons > @_{o -> o} 1.22/1.25 1.22/1.25 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 1.22/1.25 1.22/1.25 and(X, Y) >= or(X, Y) 1.22/1.25 and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) 1.22/1.25 map(F, nil) > nil 1.22/1.25 filter(F, nil) > nil 1.22/1.25 filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) 1.22/1.25 filter2(false, F, X, Y) > filter(F, Y) 1.22/1.25 1.22/1.25 With these choices, we have: 1.22/1.25 1.22/1.25 1] and(X, Y) >= or(X, Y) because [2], by (Star) 1.22/1.25 2] and*(X, Y) >= or(X, Y) because and > or, [3] and [5], by (Copy) 1.22/1.25 3] and*(X, Y) >= X because [4], by (Select) 1.22/1.25 4] X >= X by (Meta) 1.22/1.25 5] and*(X, Y) >= Y because [6], by (Select) 1.22/1.25 6] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 7] and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because [8], by (Star) 1.22/1.25 8] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because and > or, [9] and [14], by (Copy) 1.22/1.25 9] and*(X, or(Y, Z)) >= and(X, Y) because and in Mul, [10] and [11], by (Stat) 1.22/1.25 10] X >= X by (Meta) 1.22/1.25 11] or(Y, Z) > Y because [12], by definition 1.22/1.25 12] or*(Y, Z) >= Y because [13], by (Select) 1.22/1.25 13] Y >= Y by (Meta) 1.22/1.25 14] and*(X, or(Y, Z)) >= and(X, Z) because and in Mul, [10] and [15], by (Stat) 1.22/1.25 15] or(Y, Z) > Z because [16], by definition 1.22/1.25 16] or*(Y, Z) >= Z because [17], by (Select) 1.22/1.25 17] Z >= Z by (Meta) 1.22/1.25 1.22/1.25 18] map(F, nil) > nil because [19], by definition 1.22/1.25 19] map*(F, nil) >= nil because [20], by (Select) 1.22/1.25 20] nil >= nil by (Fun) 1.22/1.25 1.22/1.25 21] filter(F, nil) > nil because [22], by definition 1.22/1.25 22] filter*(F, nil) >= nil because filter > nil, by (Copy) 1.22/1.25 1.22/1.25 23] filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because [24], by (Star) 1.22/1.25 24] filter*(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because filter = filter2, [25], [28], [29], [31] and [35], by (Stat) 1.22/1.25 25] cons(X, Y) > Y because [26], by definition 1.22/1.25 26] cons*(X, Y) >= Y because [27], by (Select) 1.22/1.25 27] Y >= Y by (Meta) 1.22/1.25 28] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [29] and [31], by (Copy) 1.22/1.25 29] filter*(F, cons(X, Y)) >= F because [30], by (Select) 1.22/1.25 30] F >= F by (Meta) 1.22/1.25 31] filter*(F, cons(X, Y)) >= X because [32], by (Select) 1.22/1.25 32] cons(X, Y) >= X because [33], by (Star) 1.22/1.25 33] cons*(X, Y) >= X because [34], by (Select) 1.22/1.25 34] X >= X by (Meta) 1.22/1.25 35] filter*(F, cons(X, Y)) >= Y because [36], by (Select) 1.22/1.25 36] cons(X, Y) >= Y because [26], by (Star) 1.22/1.25 1.22/1.25 37] filter2(false, F, X, Y) > filter(F, Y) because [38], by definition 1.22/1.25 38] filter2*(false, F, X, Y) >= filter(F, Y) because filter2 = filter, [39], [40], [41] and [42], by (Stat) 1.22/1.25 39] F >= F by (Meta) 1.22/1.25 40] Y >= Y by (Meta) 1.22/1.25 41] filter2*(false, F, X, Y) >= F because [39], by (Select) 1.22/1.25 42] filter2*(false, F, X, Y) >= Y because [40], by (Select) 1.22/1.25 1.22/1.25 We can thus remove the following rules: 1.22/1.25 1.22/1.25 map(F, nil) => nil 1.22/1.25 filter(F, nil) => nil 1.22/1.25 filter2(false, F, X, Y) => filter(F, Y) 1.22/1.25 1.22/1.25 We use rule removal, following [Kop12, Theorem 2.23]. 1.22/1.25 1.22/1.25 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 1.22/1.25 1.22/1.25 not(and(X, Y)) >? or(not(X), not(Y)) 1.22/1.25 and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) 1.22/1.25 filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 1.22/1.25 1.22/1.25 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 1.22/1.25 1.22/1.25 We choose Lex = {} and Mul = {@_{o -> o}, and, cons, filter, filter2, not, or}, and the following precedence: and > not > or > filter > cons > filter2 > @_{o -> o} 1.22/1.25 1.22/1.25 With these choices, we have: 1.22/1.25 1.22/1.25 1] not(and(X, Y)) > or(not(X), not(Y)) because [2], by definition 1.22/1.25 2] not*(and(X, Y)) >= or(not(X), not(Y)) because not > or, [3] and [7], by (Copy) 1.22/1.25 3] not*(and(X, Y)) >= not(X) because not in Mul and [4], by (Stat) 1.22/1.25 4] and(X, Y) > X because [5], by definition 1.22/1.25 5] and*(X, Y) >= X because [6], by (Select) 1.22/1.25 6] X >= X by (Meta) 1.22/1.25 7] not*(and(X, Y)) >= not(Y) because [8], by (Select) 1.22/1.25 8] and(X, Y) >= not(Y) because [9], by (Star) 1.22/1.25 9] and*(X, Y) >= not(Y) because and > not and [10], by (Copy) 1.22/1.25 10] and*(X, Y) >= Y because [11], by (Select) 1.22/1.25 11] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 12] and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because [13], by (Star) 1.22/1.25 13] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because and > or, [14] and [19], by (Copy) 1.22/1.25 14] and*(X, or(Y, Z)) >= and(X, Y) because and in Mul, [15] and [16], by (Stat) 1.22/1.25 15] X >= X by (Meta) 1.22/1.25 16] or(Y, Z) > Y because [17], by definition 1.22/1.25 17] or*(Y, Z) >= Y because [18], by (Select) 1.22/1.25 18] Y >= Y by (Meta) 1.22/1.25 19] and*(X, or(Y, Z)) >= and(X, Z) because and in Mul, [15] and [20], by (Stat) 1.22/1.25 20] or(Y, Z) > Z because [21], by definition 1.22/1.25 21] or*(Y, Z) >= Z because [22], by (Select) 1.22/1.25 22] Z >= Z by (Meta) 1.22/1.25 1.22/1.25 23] filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because [24], by (Star) 1.22/1.25 24] filter*(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because filter > filter2, [25], [26], [28] and [32], by (Copy) 1.22/1.25 25] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [26] and [28], by (Copy) 1.22/1.25 26] filter*(F, cons(X, Y)) >= F because [27], by (Select) 1.22/1.25 27] F >= F by (Meta) 1.22/1.25 28] filter*(F, cons(X, Y)) >= X because [29], by (Select) 1.22/1.25 29] cons(X, Y) >= X because [30], by (Star) 1.22/1.25 30] cons*(X, Y) >= X because [31], by (Select) 1.22/1.25 31] X >= X by (Meta) 1.22/1.25 32] filter*(F, cons(X, Y)) >= Y because [33], by (Select) 1.22/1.25 33] cons(X, Y) >= Y because [34], by (Star) 1.22/1.25 34] cons*(X, Y) >= Y because [35], by (Select) 1.22/1.25 35] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 We can thus remove the following rules: 1.22/1.25 1.22/1.25 not(and(X, Y)) => or(not(X), not(Y)) 1.22/1.25 1.22/1.25 We use rule removal, following [Kop12, Theorem 2.23]. 1.22/1.25 1.22/1.25 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 1.22/1.25 1.22/1.25 and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) 1.22/1.25 filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 1.22/1.25 1.22/1.25 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 1.22/1.25 1.22/1.25 We choose Lex = {} and Mul = {@_{o -> o}, and, cons, filter, filter2, or}, and the following precedence: and > cons > filter > filter2 > @_{o -> o} > or 1.22/1.25 1.22/1.25 With these choices, we have: 1.22/1.25 1.22/1.25 1] and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because [2], by (Star) 1.22/1.25 2] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because and > or, [3] and [8], by (Copy) 1.22/1.25 3] and*(X, or(Y, Z)) >= and(X, Y) because and in Mul, [4] and [5], by (Stat) 1.22/1.25 4] X >= X by (Meta) 1.22/1.25 5] or(Y, Z) > Y because [6], by definition 1.22/1.25 6] or*(Y, Z) >= Y because [7], by (Select) 1.22/1.25 7] Y >= Y by (Meta) 1.22/1.25 8] and*(X, or(Y, Z)) >= and(X, Z) because and in Mul, [4] and [9], by (Stat) 1.22/1.25 9] or(Y, Z) > Z because [10], by definition 1.22/1.25 10] or*(Y, Z) >= Z because [11], by (Select) 1.22/1.25 11] Z >= Z by (Meta) 1.22/1.25 1.22/1.25 12] filter(F, cons(X, Y)) > filter2(@_{o -> o}(F, X), F, X, Y) because [13], by definition 1.22/1.25 13] filter*(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because filter > filter2, [14], [15], [17] and [21], by (Copy) 1.22/1.25 14] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [15] and [17], by (Copy) 1.22/1.25 15] filter*(F, cons(X, Y)) >= F because [16], by (Select) 1.22/1.25 16] F >= F by (Meta) 1.22/1.25 17] filter*(F, cons(X, Y)) >= X because [18], by (Select) 1.22/1.25 18] cons(X, Y) >= X because [19], by (Star) 1.22/1.25 19] cons*(X, Y) >= X because [20], by (Select) 1.22/1.25 20] X >= X by (Meta) 1.22/1.25 21] filter*(F, cons(X, Y)) >= Y because [22], by (Select) 1.22/1.25 22] cons(X, Y) >= Y because [23], by (Star) 1.22/1.25 23] cons*(X, Y) >= Y because [24], by (Select) 1.22/1.25 24] Y >= Y by (Meta) 1.22/1.25 1.22/1.25 We can thus remove the following rules: 1.22/1.25 1.22/1.25 filter(F, cons(X, Y)) => filter2(F X, F, X, Y) 1.22/1.25 1.22/1.25 We use rule removal, following [Kop12, Theorem 2.23]. 1.22/1.25 1.22/1.25 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 1.22/1.25 1.22/1.25 and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) 1.22/1.25 1.22/1.25 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 1.22/1.25 1.22/1.25 We choose Lex = {} and Mul = {and, or}, and the following precedence: and > or 1.22/1.25 1.22/1.25 With these choices, we have: 1.22/1.25 1.22/1.25 1] and(X, or(Y, Z)) > or(and(X, Y), and(X, Z)) because [2], by definition 1.22/1.25 2] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because and > or, [3] and [8], by (Copy) 1.22/1.25 3] and*(X, or(Y, Z)) >= and(X, Y) because and in Mul, [4] and [5], by (Stat) 1.22/1.25 4] X >= X by (Meta) 1.22/1.25 5] or(Y, Z) > Y because [6], by definition 1.22/1.25 6] or*(Y, Z) >= Y because [7], by (Select) 1.22/1.25 7] Y >= Y by (Meta) 1.22/1.25 8] and*(X, or(Y, Z)) >= and(X, Z) because and in Mul, [4] and [9], by (Stat) 1.22/1.25 9] or(Y, Z) > Z because [10], by definition 1.22/1.25 10] or*(Y, Z) >= Z because [11], by (Select) 1.22/1.25 11] Z >= Z by (Meta) 1.22/1.25 1.22/1.25 We can thus remove the following rules: 1.22/1.25 1.22/1.25 and(X, or(Y, Z)) => or(and(X, Y), and(X, Z)) 1.22/1.25 1.22/1.25 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. 1.22/1.25 1.22/1.25 1.22/1.25 +++ Citations +++ 1.22/1.25 1.22/1.25 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 1.22/1.25 EOF