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