/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 : [a * c] --> c false : [] --> b filter : [a -> b] --> c -> c filtersub : [b * a -> b * c] --> c neq : [a] --> a -> b nil : [] --> c nonzero : [] --> c -> c s : [a] --> a true : [] --> b Rules: neq(0) 0 => false neq(0) s(x) => true neq(s(x)) 0 => true neq(s(x)) s(y) => neq(x) y filter(f) nil => nil filter(f) cons(x, y) => filtersub(f x, f, cons(x, y)) filtersub(true, f, cons(x, y)) => cons(x, filter(f) y) filtersub(false, f, cons(x, y)) => filter(f) y nonzero => filter(neq(0)) 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]): neq(0) 0 >? false neq(0) s(X) >? true neq(s(X)) 0 >? true neq(s(X)) s(Y) >? neq(X) Y filter(F) nil >? nil filter(F) cons(X, Y) >? filtersub(F X, F, cons(X, Y)) filtersub(true, F, cons(X, Y)) >? cons(X, filter(F) Y) filtersub(false, F, cons(X, Y)) >? filter(F) Y nonzero >? filter(neq(0)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[@_{o -> o}(x_1, x_2)]] = @_{o -> o}(x_2, x_1) [[false]] = _|_ [[filtersub(x_1, x_2, x_3)]] = filtersub(x_3, x_2, x_1) [[nil]] = _|_ [[true]] = _|_ We choose Lex = {@_{o -> o}, filtersub} and Mul = {cons, filter, neq, nonzero, s}, and the following precedence: nonzero > neq > @_{o -> o} = filtersub > cons > filter > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: @_{o -> o}(neq(_|_), _|_) >= _|_ @_{o -> o}(neq(_|_), s(X)) >= _|_ @_{o -> o}(neq(s(X)), _|_) >= _|_ @_{o -> o}(neq(s(X)), s(Y)) > @_{o -> o}(neq(X), Y) @_{o -> o}(filter(F), _|_) >= _|_ @_{o -> o}(filter(F), cons(X, Y)) >= filtersub(@_{o -> o}(F, X), F, cons(X, Y)) filtersub(_|_, F, cons(X, Y)) > cons(X, @_{o -> o}(filter(F), Y)) filtersub(_|_, F, cons(X, Y)) >= @_{o -> o}(filter(F), Y) nonzero > filter(neq(_|_)) With these choices, we have: 1] @_{o -> o}(neq(_|_), _|_) >= _|_ by (Bot) 2] @_{o -> o}(neq(_|_), s(X)) >= _|_ by (Bot) 3] @_{o -> o}(neq(s(X)), _|_) >= _|_ by (Bot) 4] @_{o -> o}(neq(s(X)), s(Y)) > @_{o -> o}(neq(X), Y) because [5], by definition 5] @_{o -> o}*(neq(s(X)), s(Y)) >= @_{o -> o}(neq(X), Y) because [6], by (Select) 6] neq(s(X)) @_{o -> o}*(neq(s(X)), s(Y)) >= @_{o -> o}(neq(X), Y) because [7] 7] neq*(s(X), @_{o -> o}*(neq(s(X)), s(Y))) >= @_{o -> o}(neq(X), Y) because neq > @_{o -> o}, [8] and [12], by (Copy) 8] neq*(s(X), @_{o -> o}*(neq(s(X)), s(Y))) >= neq(X) because neq in Mul and [9], by (Stat) 9] s(X) > X because [10], by definition 10] s*(X) >= X because [11], by (Select) 11] X >= X by (Meta) 12] neq*(s(X), @_{o -> o}*(neq(s(X)), s(Y))) >= Y because [13], by (Select) 13] @_{o -> o}*(neq(s(X)), s(Y)) >= Y because [14], by (Select) 14] s(Y) >= Y because [15], by (Star) 15] s*(Y) >= Y because [16], by (Select) 16] Y >= Y by (Meta) 17] @_{o -> o}(filter(F), _|_) >= _|_ by (Bot) 18] @_{o -> o}(filter(F), cons(X, Y)) >= filtersub(@_{o -> o}(F, X), F, cons(X, Y)) because [19], by (Star) 19] @_{o -> o}*(filter(F), cons(X, Y)) >= filtersub(@_{o -> o}(F, X), F, cons(X, Y)) because @_{o -> o} = filtersub, [20], [23], [26], [32] and [35], by (Stat) 20] filter(F) > F because [21], by definition 21] filter*(F) >= F because [22], by (Select) 22] F >= F by (Meta) 23] cons(X, Y) >= cons(X, Y) because cons in Mul, [24] and [25], by (Fun) 24] X >= X by (Meta) 25] Y >= Y by (Meta) 26] @_{o -> o}*(filter(F), cons(X, Y)) >= @_{o -> o}(F, X) because [27], by (Select) 27] filter(F) @_{o -> o}*(filter(F), cons(X, Y)) >= @_{o -> o}(F, X) because [28] 28] filter*(F, @_{o -> o}*(filter(F), cons(X, Y))) >= @_{o -> o}(F, X) because [29], by (Select) 29] @_{o -> o}*(filter(F), cons(X, Y)) >= @_{o -> o}(F, X) because [20], [30], [32] and [34], by (Stat) 30] cons(X, Y) >= X because [31], by (Star) 31] cons*(X, Y) >= X because [24], by (Select) 32] @_{o -> o}*(filter(F), cons(X, Y)) >= F because [33], by (Select) 33] filter(F) >= F because [21], by (Star) 34] @_{o -> o}*(filter(F), cons(X, Y)) >= X because [30], by (Select) 35] @_{o -> o}*(filter(F), cons(X, Y)) >= cons(X, Y) because [23], by (Select) 36] filtersub(_|_, F, cons(X, Y)) > cons(X, @_{o -> o}(filter(F), Y)) because [37], by definition 37] filtersub*(_|_, F, cons(X, Y)) >= cons(X, @_{o -> o}(filter(F), Y)) because filtersub > cons, [38] and [42], by (Copy) 38] filtersub*(_|_, F, cons(X, Y)) >= X because [39], by (Select) 39] cons(X, Y) >= X because [40], by (Star) 40] cons*(X, Y) >= X because [41], by (Select) 41] X >= X by (Meta) 42] filtersub*(_|_, F, cons(X, Y)) >= @_{o -> o}(filter(F), Y) because filtersub = @_{o -> o}, [43], [46] and [49], by (Stat) 43] cons(X, Y) > Y because [44], by definition 44] cons*(X, Y) >= Y because [45], by (Select) 45] Y >= Y by (Meta) 46] filtersub*(_|_, F, cons(X, Y)) >= filter(F) because filtersub > filter and [47], by (Copy) 47] filtersub*(_|_, F, cons(X, Y)) >= F because [48], by (Select) 48] F >= F by (Meta) 49] filtersub*(_|_, F, cons(X, Y)) >= Y because [50], by (Select) 50] cons(X, Y) >= Y because [44], by (Star) 51] filtersub(_|_, F, cons(X, Y)) >= @_{o -> o}(filter(F), Y) because [52], by (Star) 52] filtersub*(_|_, F, cons(X, Y)) >= @_{o -> o}(filter(F), Y) because filtersub = @_{o -> o}, [53], [56] and [59], by (Stat) 53] cons(X, Y) > Y because [54], by definition 54] cons*(X, Y) >= Y because [55], by (Select) 55] Y >= Y by (Meta) 56] filtersub*(_|_, F, cons(X, Y)) >= filter(F) because filtersub > filter and [57], by (Copy) 57] filtersub*(_|_, F, cons(X, Y)) >= F because [58], by (Select) 58] F >= F by (Meta) 59] filtersub*(_|_, F, cons(X, Y)) >= Y because [60], by (Select) 60] cons(X, Y) >= Y because [54], by (Star) 61] nonzero > filter(neq(_|_)) because [62], by definition 62] nonzero* >= filter(neq(_|_)) because nonzero > filter and [63], by (Copy) 63] nonzero* >= neq(_|_) because nonzero > neq and [64], by (Copy) 64] nonzero* >= _|_ by (Bot) We can thus remove the following rules: neq(s(X)) s(Y) => neq(X) Y filtersub(true, F, cons(X, Y)) => cons(X, filter(F) Y) nonzero => filter(neq(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]): neq(0, 0) >? false neq(0, s(X)) >? true neq(s(X), 0) >? true filter(F, nil) >? nil filter(F, cons(X, Y)) >? filtersub(F X, F, cons(X, Y)) filtersub(false, F, cons(X, Y)) >? filter(F, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 3 cons = \y0y1.2 + y0 + 2y1 false = 1 filter = \G0y1.2y1 + G0(0) + 2y1G0(y1) + 2G0(y1) filtersub = \y0G1y2.y0 + y2 + G1(0) + y2G1(y2) neq = \y0y1.3 + 3y0 + 3y1 nil = 1 s = \y0.3 + y0 true = 0 Using this interpretation, the requirements translate to: [[neq(0, 0)]] = 21 > 1 = [[false]] [[neq(0, s(_x0))]] = 21 + 3x0 > 0 = [[true]] [[neq(s(_x0), 0)]] = 21 + 3x0 > 0 = [[true]] [[filter(_F0, nil)]] = 2 + F0(0) + 4F0(1) > 1 = [[nil]] [[filter(_F0, cons(_x1, _x2))]] = 4 + 2x1 + 4x2 + F0(0) + 2x1F0(2 + x1 + 2x2) + 4x2F0(2 + x1 + 2x2) + 6F0(2 + x1 + 2x2) > 2 + 2x1 + 2x2 + F0(0) + F0(x1) + 2x2F0(2 + x1 + 2x2) + 2F0(2 + x1 + 2x2) + x1F0(2 + x1 + 2x2) = [[filtersub(_F0 _x1, _F0, cons(_x1, _x2))]] [[filtersub(false, _F0, cons(_x1, _x2))]] = 3 + x1 + 2x2 + F0(0) + 2x2F0(2 + x1 + 2x2) + 2F0(2 + x1 + 2x2) + x1F0(2 + x1 + 2x2) > 2x2 + F0(0) + 2x2F0(x2) + 2F0(x2) = [[filter(_F0, _x2)]] We can thus remove the following rules: neq(0, 0) => false neq(0, s(X)) => true neq(s(X), 0) => true filter(F, nil) => nil filter(F, cons(X, Y)) => filtersub(F X, F, cons(X, Y)) filtersub(false, F, cons(X, Y)) => filter(F, 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.