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