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