0.63/0.67 YES 0.70/0.72 We consider the system theBenchmark. 0.70/0.72 0.70/0.72 Alphabet: 0.70/0.72 0.70/0.72 !faccolon : [a * a] --> a 0.70/0.72 C : [] --> a 0.70/0.72 cons : [c * d] --> d 0.70/0.72 false : [] --> b 0.70/0.72 filter : [c -> b * d] --> d 0.70/0.72 filter2 : [b * c -> b * c * d] --> d 0.70/0.72 map : [c -> c * d] --> d 0.70/0.72 nil : [] --> d 0.70/0.72 true : [] --> b 0.70/0.72 0.70/0.72 Rules: 0.70/0.72 0.70/0.72 !faccolon(!faccolon(!faccolon(!faccolon(C, x), y), z), u) => !faccolon(!faccolon(x, z), !faccolon(!faccolon(!faccolon(x, y), z), u)) 0.70/0.72 map(f, nil) => nil 0.70/0.72 map(f, cons(x, y)) => cons(f x, map(f, y)) 0.70/0.72 filter(f, nil) => nil 0.70/0.72 filter(f, cons(x, y)) => filter2(f x, f, x, y) 0.70/0.72 filter2(true, f, x, y) => cons(x, filter(f, y)) 0.70/0.72 filter2(false, f, x, y) => filter(f, y) 0.70/0.72 0.70/0.72 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 0.70/0.72 0.70/0.72 We use rule removal, following [Kop12, Theorem 2.23]. 0.70/0.72 0.70/0.72 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.70/0.72 0.70/0.72 !faccolon(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >? !faccolon(!faccolon(X, Z), !faccolon(!faccolon(!faccolon(X, Y), Z), U)) 0.70/0.72 map(F, nil) >? nil 0.70/0.72 map(F, cons(X, Y)) >? cons(F X, map(F, Y)) 0.70/0.72 filter(F, nil) >? nil 0.70/0.72 filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 0.70/0.72 filter2(true, F, X, Y) >? cons(X, filter(F, Y)) 0.70/0.72 filter2(false, F, X, Y) >? filter(F, Y) 0.70/0.72 0.70/0.72 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.70/0.72 0.70/0.72 Argument functions: 0.70/0.72 0.70/0.72 [[filter2(x_1, x_2, x_3, x_4)]] = filter2(x_2, x_4, x_1, x_3) 0.70/0.72 [[nil]] = _|_ 0.70/0.72 0.70/0.72 We choose Lex = {!faccolon, @_{o -> o}, filter, filter2} and Mul = {C, cons, false, map, true}, and the following precedence: map > C > !faccolon > false > @_{o -> o} = filter = filter2 > true > cons 0.70/0.72 0.70/0.72 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.70/0.72 0.70/0.72 !faccolon(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= !faccolon(!faccolon(X, Z), !faccolon(!faccolon(!faccolon(X, Y), Z), U)) 0.70/0.72 map(F, _|_) >= _|_ 0.70/0.72 map(F, cons(X, Y)) > cons(@_{o -> o}(F, X), map(F, Y)) 0.70/0.72 filter(F, _|_) >= _|_ 0.70/0.72 filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) 0.70/0.72 filter2(true, F, X, Y) >= cons(X, filter(F, Y)) 0.70/0.72 filter2(false, F, X, Y) >= filter(F, Y) 0.70/0.72 0.70/0.72 With these choices, we have: 0.70/0.72 0.70/0.72 1] !faccolon(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= !faccolon(!faccolon(X, Z), !faccolon(!faccolon(!faccolon(X, Y), Z), U)) because [2], by (Star) 0.70/0.72 2] !faccolon*(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= !faccolon(!faccolon(X, Z), !faccolon(!faccolon(!faccolon(X, Y), Z), U)) because [3], [14] and [18], by (Stat) 0.70/0.72 3] !faccolon(!faccolon(!faccolon(C, X), Y), Z) > !faccolon(X, Z) because [4], by definition 0.70/0.72 4] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= !faccolon(X, Z) because [5], [10] and [12], by (Stat) 0.70/0.72 5] !faccolon(!faccolon(C, X), Y) > X because [6], by definition 0.70/0.72 6] !faccolon*(!faccolon(C, X), Y) >= X because [7], by (Select) 0.70/0.72 7] !faccolon(C, X) >= X because [8], by (Star) 0.70/0.72 8] !faccolon*(C, X) >= X because [9], by (Select) 0.70/0.72 9] X >= X by (Meta) 0.70/0.72 10] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= X because [11], by (Select) 0.70/0.72 11] !faccolon(!faccolon(C, X), Y) >= X because [6], by (Star) 0.70/0.72 12] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= Z because [13], by (Select) 0.70/0.72 13] Z >= Z by (Meta) 0.70/0.72 14] !faccolon*(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= !faccolon(X, Z) because [15], by (Select) 0.70/0.72 15] !faccolon(!faccolon(!faccolon(C, X), Y), Z) >= !faccolon(X, Z) because [16] and [17], by (Fun) 0.70/0.72 16] !faccolon(!faccolon(C, X), Y) >= X because [6], by (Star) 0.70/0.72 17] Z >= Z by (Meta) 0.70/0.72 18] !faccolon*(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= !faccolon(!faccolon(!faccolon(X, Y), Z), U) because [19], [31] and [34], by (Stat) 0.70/0.72 19] !faccolon(!faccolon(!faccolon(C, X), Y), Z) > !faccolon(!faccolon(X, Y), Z) because [20], by definition 0.70/0.72 20] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= !faccolon(!faccolon(X, Y), Z) because [21], [27] and [12], by (Stat) 0.70/0.72 21] !faccolon(!faccolon(C, X), Y) > !faccolon(X, Y) because [22], by definition 0.70/0.72 22] !faccolon*(!faccolon(C, X), Y) >= !faccolon(X, Y) because [23], [6] and [25], by (Stat) 0.70/0.72 23] !faccolon(C, X) > X because [24], by definition 0.70/0.72 24] !faccolon*(C, X) >= X because [9], by (Select) 0.70/0.72 25] !faccolon*(!faccolon(C, X), Y) >= Y because [26], by (Select) 0.70/0.72 26] Y >= Y by (Meta) 0.70/0.72 27] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= !faccolon(X, Y) because [28], by (Select) 0.70/0.72 28] !faccolon(!faccolon(C, X), Y) >= !faccolon(X, Y) because [29] and [30], by (Fun) 0.70/0.72 29] !faccolon(C, X) >= X because [24], by (Star) 0.70/0.72 30] Y >= Y by (Meta) 0.70/0.72 31] !faccolon*(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= !faccolon(!faccolon(X, Y), Z) because [32], by (Select) 0.70/0.72 32] !faccolon(!faccolon(!faccolon(C, X), Y), Z) >= !faccolon(!faccolon(X, Y), Z) because [33] and [17], by (Fun) 0.70/0.72 33] !faccolon(!faccolon(C, X), Y) >= !faccolon(X, Y) because [29] and [30], by (Fun) 0.70/0.72 34] !faccolon*(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= U because [35], by (Select) 0.70/0.72 35] U >= U by (Meta) 0.70/0.72 0.70/0.72 36] map(F, _|_) >= _|_ by (Bot) 0.70/0.72 0.70/0.72 37] map(F, cons(X, Y)) > cons(@_{o -> o}(F, X), map(F, Y)) because [38], by definition 0.70/0.72 38] map*(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) because map > cons, [39] and [46], by (Copy) 0.70/0.72 39] map*(F, cons(X, Y)) >= @_{o -> o}(F, X) because map > @_{o -> o}, [40] and [42], by (Copy) 0.70/0.72 40] map*(F, cons(X, Y)) >= F because [41], by (Select) 0.70/0.72 41] F >= F by (Meta) 0.70/0.72 42] map*(F, cons(X, Y)) >= X because [43], by (Select) 0.70/0.72 43] cons(X, Y) >= X because [44], by (Star) 0.70/0.72 44] cons*(X, Y) >= X because [45], by (Select) 0.70/0.72 45] X >= X by (Meta) 0.70/0.72 46] map*(F, cons(X, Y)) >= map(F, Y) because map in Mul, [47] and [48], by (Stat) 0.70/0.72 47] F >= F by (Meta) 0.70/0.72 48] cons(X, Y) > Y because [49], by definition 0.70/0.72 49] cons*(X, Y) >= Y because [50], by (Select) 0.70/0.72 50] Y >= Y by (Meta) 0.70/0.72 0.70/0.72 51] filter(F, _|_) >= _|_ by (Bot) 0.70/0.72 0.70/0.72 52] filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because [53], by (Star) 0.70/0.72 53] filter*(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because filter = filter2, [54], [55], [58], [62], [63] and [65], by (Stat) 0.70/0.72 54] F >= F by (Meta) 0.70/0.72 55] cons(X, Y) > Y because [56], by definition 0.70/0.72 56] cons*(X, Y) >= Y because [57], by (Select) 0.70/0.72 57] Y >= Y by (Meta) 0.70/0.72 58] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter = @_{o -> o}, [54], [59], [62] and [63], by (Stat) 0.70/0.72 59] cons(X, Y) > X because [60], by definition 0.70/0.72 60] cons*(X, Y) >= X because [61], by (Select) 0.70/0.72 61] X >= X by (Meta) 0.70/0.72 62] filter*(F, cons(X, Y)) >= F because [54], by (Select) 0.70/0.72 63] filter*(F, cons(X, Y)) >= X because [64], by (Select) 0.70/0.72 64] cons(X, Y) >= X because [60], by (Star) 0.70/0.72 65] filter*(F, cons(X, Y)) >= Y because [66], by (Select) 0.70/0.72 66] cons(X, Y) >= Y because [56], by (Star) 0.70/0.72 0.70/0.72 67] filter2(true, F, X, Y) >= cons(X, filter(F, Y)) because [68], by (Star) 0.70/0.72 68] filter2*(true, F, X, Y) >= cons(X, filter(F, Y)) because filter2 > cons, [69] and [71], by (Copy) 0.70/0.72 69] filter2*(true, F, X, Y) >= X because [70], by (Select) 0.70/0.72 70] X >= X by (Meta) 0.70/0.72 71] filter2*(true, F, X, Y) >= filter(F, Y) because filter2 = filter, [72], [73], [74] and [75], by (Stat) 0.70/0.72 72] F >= F by (Meta) 0.70/0.72 73] Y >= Y by (Meta) 0.70/0.72 74] filter2*(true, F, X, Y) >= F because [72], by (Select) 0.70/0.72 75] filter2*(true, F, X, Y) >= Y because [73], by (Select) 0.70/0.72 0.70/0.72 76] filter2(false, F, X, Y) >= filter(F, Y) because [77], by (Star) 0.70/0.72 77] filter2*(false, F, X, Y) >= filter(F, Y) because filter2 = filter, [78], [79], [80] and [81], by (Stat) 0.70/0.72 78] F >= F by (Meta) 0.70/0.72 79] Y >= Y by (Meta) 0.70/0.72 80] filter2*(false, F, X, Y) >= F because [78], by (Select) 0.70/0.72 81] filter2*(false, F, X, Y) >= Y because [79], by (Select) 0.70/0.72 0.70/0.72 We can thus remove the following rules: 0.70/0.72 0.70/0.72 map(F, cons(X, Y)) => cons(F X, map(F, Y)) 0.70/0.72 0.70/0.72 We use rule removal, following [Kop12, Theorem 2.23]. 0.70/0.72 0.70/0.72 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.70/0.72 0.70/0.72 !faccolon(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >? !faccolon(!faccolon(X, Z), !faccolon(!faccolon(!faccolon(X, Y), Z), U)) 0.70/0.72 map(F, nil) >? nil 0.70/0.72 filter(F, nil) >? nil 0.70/0.72 filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 0.70/0.72 filter2(true, F, X, Y) >? cons(X, filter(F, Y)) 0.70/0.72 filter2(false, F, X, Y) >? filter(F, Y) 0.70/0.72 0.70/0.72 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.70/0.72 0.70/0.72 Argument functions: 0.70/0.72 0.70/0.72 [[filter(x_1, x_2)]] = filter(x_2, x_1) 0.70/0.72 [[filter2(x_1, x_2, x_3, x_4)]] = filter2(x_4, x_2, x_1, x_3) 0.70/0.72 [[nil]] = _|_ 0.70/0.72 0.70/0.72 We choose Lex = {!faccolon, filter, filter2} and Mul = {@_{o -> o}, C, cons, false, map, true}, and the following precedence: !faccolon > true > map > false > filter = filter2 > @_{o -> o} > C > cons 0.70/0.72 0.70/0.72 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.70/0.72 0.70/0.72 !faccolon(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) > !faccolon(!faccolon(X, Z), !faccolon(!faccolon(!faccolon(X, Y), Z), U)) 0.70/0.72 map(F, _|_) >= _|_ 0.70/0.72 filter(F, _|_) > _|_ 0.70/0.72 filter(F, cons(X, Y)) > filter2(@_{o -> o}(F, X), F, X, Y) 0.70/0.72 filter2(true, F, X, Y) > cons(X, filter(F, Y)) 0.70/0.72 filter2(false, F, X, Y) >= filter(F, Y) 0.70/0.72 0.70/0.72 With these choices, we have: 0.70/0.72 0.70/0.72 1] !faccolon(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) > !faccolon(!faccolon(X, Z), !faccolon(!faccolon(!faccolon(X, Y), Z), U)) because [2], by definition 0.70/0.72 2] !faccolon*(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= !faccolon(!faccolon(X, Z), !faccolon(!faccolon(!faccolon(X, Y), Z), U)) because [3], [14] and [18], by (Stat) 0.70/0.72 3] !faccolon(!faccolon(!faccolon(C, X), Y), Z) > !faccolon(X, Z) because [4], by definition 0.70/0.72 4] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= !faccolon(X, Z) because [5], [10] and [12], by (Stat) 0.70/0.72 5] !faccolon(!faccolon(C, X), Y) > X because [6], by definition 0.70/0.72 6] !faccolon*(!faccolon(C, X), Y) >= X because [7], by (Select) 0.70/0.72 7] !faccolon(C, X) >= X because [8], by (Star) 0.70/0.72 8] !faccolon*(C, X) >= X because [9], by (Select) 0.70/0.72 9] X >= X by (Meta) 0.70/0.72 10] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= X because [11], by (Select) 0.70/0.72 11] !faccolon(!faccolon(C, X), Y) >= X because [6], by (Star) 0.70/0.72 12] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= Z because [13], by (Select) 0.70/0.72 13] Z >= Z by (Meta) 0.70/0.72 14] !faccolon*(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= !faccolon(X, Z) because [15], by (Select) 0.70/0.72 15] !faccolon(!faccolon(!faccolon(C, X), Y), Z) >= !faccolon(X, Z) because [16] and [17], by (Fun) 0.70/0.72 16] !faccolon(!faccolon(C, X), Y) >= X because [6], by (Star) 0.70/0.72 17] Z >= Z by (Meta) 0.70/0.72 18] !faccolon*(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= !faccolon(!faccolon(!faccolon(X, Y), Z), U) because [19], [30] and [35], by (Stat) 0.70/0.72 19] !faccolon(!faccolon(!faccolon(C, X), Y), Z) > !faccolon(!faccolon(X, Y), Z) because [20], by definition 0.70/0.72 20] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= !faccolon(!faccolon(X, Y), Z) because [21], [27] and [12], by (Stat) 0.70/0.72 21] !faccolon(!faccolon(C, X), Y) > !faccolon(X, Y) because [22], by definition 0.70/0.72 22] !faccolon*(!faccolon(C, X), Y) >= !faccolon(X, Y) because [23], [6] and [25], by (Stat) 0.70/0.72 23] !faccolon(C, X) > X because [24], by definition 0.70/0.72 24] !faccolon*(C, X) >= X because [9], by (Select) 0.70/0.72 25] !faccolon*(!faccolon(C, X), Y) >= Y because [26], by (Select) 0.70/0.72 26] Y >= Y by (Meta) 0.70/0.72 27] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= !faccolon(X, Y) because [5], [10] and [28], by (Stat) 0.70/0.72 28] !faccolon*(!faccolon(!faccolon(C, X), Y), Z) >= Y because [29], by (Select) 0.70/0.72 29] !faccolon(!faccolon(C, X), Y) >= Y because [25], by (Star) 0.70/0.72 30] !faccolon*(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= !faccolon(!faccolon(X, Y), Z) because [31], by (Select) 0.70/0.72 31] !faccolon(!faccolon(!faccolon(C, X), Y), Z) >= !faccolon(!faccolon(X, Y), Z) because [32] and [17], by (Fun) 0.70/0.72 32] !faccolon(!faccolon(C, X), Y) >= !faccolon(X, Y) because [33] and [34], by (Fun) 0.70/0.72 33] !faccolon(C, X) >= X because [24], by (Star) 0.70/0.72 34] Y >= Y by (Meta) 0.70/0.72 35] !faccolon*(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) >= U because [36], by (Select) 0.70/0.72 36] U >= U by (Meta) 0.70/0.72 0.70/0.72 37] map(F, _|_) >= _|_ by (Bot) 0.70/0.72 0.70/0.72 38] filter(F, _|_) > _|_ because [39], by definition 0.70/0.72 39] filter*(F, _|_) >= _|_ by (Bot) 0.70/0.72 0.70/0.72 40] filter(F, cons(X, Y)) > filter2(@_{o -> o}(F, X), F, X, Y) because [41], by definition 0.70/0.72 41] filter*(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because filter = filter2, [42], [45], [46], [48] and [52], by (Stat) 0.70/0.72 42] cons(X, Y) > Y because [43], by definition 0.70/0.72 43] cons*(X, Y) >= Y because [44], by (Select) 0.70/0.72 44] Y >= Y by (Meta) 0.70/0.72 45] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [46] and [48], by (Copy) 0.70/0.72 46] filter*(F, cons(X, Y)) >= F because [47], by (Select) 0.70/0.72 47] F >= F by (Meta) 0.70/0.72 48] filter*(F, cons(X, Y)) >= X because [49], by (Select) 0.70/0.72 49] cons(X, Y) >= X because [50], by (Star) 0.70/0.72 50] cons*(X, Y) >= X because [51], by (Select) 0.70/0.72 51] X >= X by (Meta) 0.70/0.72 52] filter*(F, cons(X, Y)) >= Y because [53], by (Select) 0.70/0.72 53] cons(X, Y) >= Y because [43], by (Star) 0.70/0.72 0.70/0.72 54] filter2(true, F, X, Y) > cons(X, filter(F, Y)) because [55], by definition 0.70/0.72 55] filter2*(true, F, X, Y) >= cons(X, filter(F, Y)) because filter2 > cons, [56] and [58], by (Copy) 0.70/0.72 56] filter2*(true, F, X, Y) >= X because [57], by (Select) 0.70/0.72 57] X >= X by (Meta) 0.70/0.72 58] filter2*(true, F, X, Y) >= filter(F, Y) because filter2 = filter, [59], [60], [61] and [62], by (Stat) 0.70/0.72 59] F >= F by (Meta) 0.70/0.72 60] Y >= Y by (Meta) 0.70/0.72 61] filter2*(true, F, X, Y) >= F because [59], by (Select) 0.70/0.72 62] filter2*(true, F, X, Y) >= Y because [60], by (Select) 0.70/0.72 0.70/0.72 63] filter2(false, F, X, Y) >= filter(F, Y) because [64], by (Star) 0.70/0.72 64] filter2*(false, F, X, Y) >= filter(F, Y) because filter2 = filter, [65], [66], [67] and [68], by (Stat) 0.70/0.72 65] F >= F by (Meta) 0.70/0.72 66] Y >= Y by (Meta) 0.70/0.72 67] filter2*(false, F, X, Y) >= F because [65], by (Select) 0.70/0.72 68] filter2*(false, F, X, Y) >= Y because [66], by (Select) 0.70/0.72 0.70/0.72 We can thus remove the following rules: 0.70/0.72 0.70/0.72 !faccolon(!faccolon(!faccolon(!faccolon(C, X), Y), Z), U) => !faccolon(!faccolon(X, Z), !faccolon(!faccolon(!faccolon(X, Y), Z), U)) 0.70/0.72 filter(F, nil) => nil 0.70/0.72 filter(F, cons(X, Y)) => filter2(F X, F, X, Y) 0.70/0.72 filter2(true, F, X, Y) => cons(X, filter(F, Y)) 0.70/0.72 0.70/0.72 We use rule removal, following [Kop12, Theorem 2.23]. 0.70/0.72 0.70/0.72 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.70/0.72 0.70/0.72 map(F, nil) >? nil 0.70/0.72 filter2(false, F, X, Y) >? filter(F, Y) 0.70/0.72 0.70/0.72 We orient these requirements with a polynomial interpretation in the natural numbers. 0.70/0.72 0.70/0.72 The following interpretation satisfies the requirements: 0.70/0.72 0.70/0.72 false = 3 0.70/0.72 filter = \G0y1.y1 + G0(0) 0.70/0.72 filter2 = \y0G1y2y3.3 + y2 + 3y0 + 3y3 + 2G1(0) + 2G1(y0) + 2G1(y2) + 2G1(y3) + 3y0G1(y0) 0.70/0.72 map = \G0y1.3 + 3y1 + 2G0(0) 0.70/0.72 nil = 0 0.70/0.72 0.70/0.72 Using this interpretation, the requirements translate to: 0.70/0.72 0.70/0.72 [[map(_F0, nil)]] = 3 + 2F0(0) > 0 = [[nil]] 0.70/0.72 [[filter2(false, _F0, _x1, _x2)]] = 12 + x1 + 3x2 + 2F0(0) + 2F0(x1) + 2F0(x2) + 11F0(3) > x2 + F0(0) = [[filter(_F0, _x2)]] 0.70/0.72 0.70/0.72 We can thus remove the following rules: 0.70/0.72 0.70/0.72 map(F, nil) => nil 0.70/0.72 filter2(false, F, X, Y) => filter(F, Y) 0.70/0.72 0.70/0.72 All rules were succesfully removed. Thus, termination of the original system has been reduced to termination of the beta-rule, which is well-known to hold. 0.70/0.72 0.70/0.72 0.70/0.72 +++ Citations +++ 0.70/0.72 0.70/0.72 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 0.70/0.72 EOF