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