0.59/0.63 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 0 : [] --> c 0.62/0.65 1 : [] --> c 0.62/0.65 add : [] --> c -> a -> c 0.62/0.65 cons : [a * b] --> b 0.62/0.65 fold : [c -> a -> c * b * c] --> c 0.62/0.65 mul : [] --> c -> a -> c 0.62/0.65 nil : [] --> b 0.62/0.65 prod : [b] --> c 0.62/0.65 sum : [b] --> c 0.62/0.65 0.62/0.65 Rules: 0.62/0.65 0.62/0.65 fold(f, nil, x) => x 0.62/0.65 fold(f, cons(x, y), z) => fold(f, y, f z x) 0.62/0.65 sum(x) => fold(add, x, 0) 0.62/0.65 fold(mul, x, 1) => prod(x) 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 fold(F, nil, X) >? X 0.62/0.65 fold(F, cons(X, Y), Z) >? fold(F, Y, F Z X) 0.62/0.65 sum(X) >? fold(add, X, 0) 0.62/0.65 fold(mul, X, 1) >? prod(X) 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 [[add]] = _|_ 0.62/0.65 [[fold(x_1, x_2, x_3)]] = fold(x_2, x_1, x_3) 0.62/0.65 0.62/0.65 We choose Lex = {fold, prod} and Mul = {1, @_{o -> o -> o}, @_{o -> o}, cons, mul, nil, sum}, and the following precedence: 1 > cons > mul > nil > sum > fold = prod > @_{o -> o -> o} > @_{o -> o} 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 fold(F, nil, X) >= X 0.62/0.65 fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) 0.62/0.65 sum(X) >= fold(_|_, X, _|_) 0.62/0.65 fold(mul, X, 1) > prod(X) 0.62/0.65 0.62/0.65 With these choices, we have: 0.62/0.65 0.62/0.65 1] fold(F, nil, X) >= X because [2], by (Star) 0.62/0.65 2] fold*(F, nil, X) >= X because [3], by (Select) 0.62/0.65 3] X >= X by (Meta) 0.62/0.65 0.62/0.65 4] fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [5], by (Star) 0.62/0.65 5] fold*(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [6], [9], [11] and [13], by (Stat) 0.62/0.65 6] cons(X, Y) > Y because [7], by definition 0.62/0.65 7] cons*(X, Y) >= Y because [8], by (Select) 0.62/0.65 8] Y >= Y by (Meta) 0.62/0.65 9] fold*(F, cons(X, Y), Z) >= F because [10], by (Select) 0.62/0.65 10] F >= F by (Meta) 0.62/0.65 11] fold*(F, cons(X, Y), Z) >= Y because [12], by (Select) 0.62/0.65 12] cons(X, Y) >= Y because [7], by (Star) 0.62/0.65 13] fold*(F, cons(X, Y), Z) >= @_{o -> o}(@_{o -> o -> o}(F, Z), X) because fold > @_{o -> o}, [14] and [17], by (Copy) 0.62/0.65 14] fold*(F, cons(X, Y), Z) >= @_{o -> o -> o}(F, Z) because fold > @_{o -> o -> o}, [9] and [15], by (Copy) 0.62/0.65 15] fold*(F, cons(X, Y), Z) >= Z because [16], by (Select) 0.62/0.65 16] Z >= Z by (Meta) 0.62/0.65 17] fold*(F, cons(X, Y), Z) >= X because [18], by (Select) 0.62/0.65 18] cons(X, Y) >= X because [19], by (Star) 0.62/0.65 19] cons*(X, Y) >= X because [20], by (Select) 0.62/0.65 20] X >= X by (Meta) 0.62/0.65 0.62/0.65 21] sum(X) >= fold(_|_, X, _|_) because [22], by (Star) 0.62/0.65 22] sum*(X) >= fold(_|_, X, _|_) because sum > fold, [23], [24] and [26], by (Copy) 0.62/0.65 23] sum*(X) >= _|_ by (Bot) 0.62/0.65 24] sum*(X) >= X because [25], by (Select) 0.62/0.65 25] X >= X by (Meta) 0.62/0.65 26] sum*(X) >= _|_ by (Bot) 0.62/0.65 0.62/0.65 27] fold(mul, X, 1) > prod(X) because [28], by definition 0.62/0.65 28] fold*(mul, X, 1) >= prod(X) because fold = prod, [29] and [30], by (Stat) 0.62/0.65 29] X >= X by (Meta) 0.62/0.65 30] fold*(mul, X, 1) >= X because [29], 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 fold(mul, X, 1) => prod(X) 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 fold(F, nil, X) >? X 0.62/0.65 fold(F, cons(X, Y), Z) >? fold(F, Y, F Z X) 0.62/0.65 sum(X) >? fold(add, X, 0) 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 [[add]] = _|_ 0.62/0.65 [[fold(x_1, x_2, x_3)]] = fold(x_2, x_3, x_1) 0.62/0.65 0.62/0.65 We choose Lex = {fold} and Mul = {@_{o -> o -> o}, @_{o -> o}, cons, nil, sum}, and the following precedence: sum > cons > fold > nil > @_{o -> o} > @_{o -> o -> o} 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 fold(F, nil, X) > X 0.62/0.65 fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) 0.62/0.65 sum(X) >= fold(_|_, X, _|_) 0.62/0.65 0.62/0.65 With these choices, we have: 0.62/0.65 0.62/0.65 1] fold(F, nil, X) > X because [2], by definition 0.62/0.65 2] fold*(F, nil, X) >= X because [3], by (Select) 0.62/0.65 3] X >= X by (Meta) 0.62/0.65 0.62/0.65 4] fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [5], by (Star) 0.62/0.65 5] fold*(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [6], [9], [11] and [13], by (Stat) 0.62/0.65 6] cons(X, Y) > Y because [7], by definition 0.62/0.65 7] cons*(X, Y) >= Y because [8], by (Select) 0.62/0.65 8] Y >= Y by (Meta) 0.62/0.65 9] fold*(F, cons(X, Y), Z) >= F because [10], by (Select) 0.62/0.65 10] F >= F by (Meta) 0.62/0.65 11] fold*(F, cons(X, Y), Z) >= Y because [12], by (Select) 0.62/0.65 12] cons(X, Y) >= Y because [7], by (Star) 0.62/0.65 13] fold*(F, cons(X, Y), Z) >= @_{o -> o}(@_{o -> o -> o}(F, Z), X) because fold > @_{o -> o}, [14] and [17], by (Copy) 0.62/0.65 14] fold*(F, cons(X, Y), Z) >= @_{o -> o -> o}(F, Z) because fold > @_{o -> o -> o}, [9] and [15], by (Copy) 0.62/0.65 15] fold*(F, cons(X, Y), Z) >= Z because [16], by (Select) 0.62/0.65 16] Z >= Z by (Meta) 0.62/0.65 17] fold*(F, cons(X, Y), Z) >= X because [18], by (Select) 0.62/0.65 18] cons(X, Y) >= X because [19], by (Star) 0.62/0.65 19] cons*(X, Y) >= X because [20], by (Select) 0.62/0.65 20] X >= X by (Meta) 0.62/0.65 0.62/0.65 21] sum(X) >= fold(_|_, X, _|_) because [22], by (Star) 0.62/0.65 22] sum*(X) >= fold(_|_, X, _|_) because sum > fold, [23], [24] and [26], by (Copy) 0.62/0.65 23] sum*(X) >= _|_ by (Bot) 0.62/0.65 24] sum*(X) >= X because [25], by (Select) 0.62/0.65 25] X >= X by (Meta) 0.62/0.65 26] sum*(X) >= _|_ by (Bot) 0.62/0.65 0.62/0.65 We can thus remove the following rules: 0.62/0.65 0.62/0.65 fold(F, nil, X) => X 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 fold(F, cons(X, Y), Z) >? fold(F, Y, F Z X) 0.62/0.65 sum(X) >? fold(add, X, 0) 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 [[add]] = _|_ 0.62/0.65 0.62/0.65 We choose Lex = {fold} and Mul = {@_{o -> o -> o}, @_{o -> o}, cons, sum}, and the following precedence: cons > sum > fold > @_{o -> o} > @_{o -> o -> o} 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 fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) 0.62/0.65 sum(X) > fold(_|_, X, _|_) 0.62/0.65 0.62/0.65 With these choices, we have: 0.62/0.65 0.62/0.65 1] fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [2], by (Star) 0.62/0.65 2] fold*(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [3], [4], [7], [8] and [10], by (Stat) 0.62/0.65 3] F >= F by (Meta) 0.62/0.65 4] cons(X, Y) > Y because [5], by definition 0.62/0.65 5] cons*(X, Y) >= Y because [6], by (Select) 0.62/0.65 6] Y >= Y by (Meta) 0.62/0.65 7] fold*(F, cons(X, Y), Z) >= F because [3], by (Select) 0.62/0.65 8] fold*(F, cons(X, Y), Z) >= Y because [9], by (Select) 0.62/0.65 9] cons(X, Y) >= Y because [5], by (Star) 0.62/0.65 10] fold*(F, cons(X, Y), Z) >= @_{o -> o}(@_{o -> o -> o}(F, Z), X) because fold > @_{o -> o}, [11] and [14], by (Copy) 0.62/0.65 11] fold*(F, cons(X, Y), Z) >= @_{o -> o -> o}(F, Z) because fold > @_{o -> o -> o}, [7] and [12], by (Copy) 0.62/0.65 12] fold*(F, cons(X, Y), Z) >= Z because [13], by (Select) 0.62/0.65 13] Z >= Z by (Meta) 0.62/0.65 14] fold*(F, cons(X, Y), Z) >= X because [15], by (Select) 0.62/0.65 15] cons(X, Y) >= X because [16], by (Star) 0.62/0.65 16] cons*(X, Y) >= X because [17], by (Select) 0.62/0.65 17] X >= X by (Meta) 0.62/0.65 0.62/0.65 18] sum(X) > fold(_|_, X, _|_) because [19], by definition 0.62/0.65 19] sum*(X) >= fold(_|_, X, _|_) because sum > fold, [20], [21] and [23], by (Copy) 0.62/0.65 20] sum*(X) >= _|_ by (Bot) 0.62/0.65 21] sum*(X) >= X because [22], by (Select) 0.62/0.65 22] X >= X by (Meta) 0.62/0.65 23] sum*(X) >= _|_ by (Bot) 0.62/0.65 0.62/0.65 We can thus remove the following rules: 0.62/0.65 0.62/0.65 sum(X) => fold(add, X, 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 fold(F, cons(X, Y), Z) >? fold(F, Y, F Z X) 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 [[fold(x_1, x_2, x_3)]] = fold(x_2, x_3, x_1) 0.62/0.65 0.62/0.65 We choose Lex = {fold} and Mul = {@_{o -> o -> o}, @_{o -> o}, cons}, and the following precedence: fold > @_{o -> o} > @_{o -> o -> o} > cons 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 fold(F, cons(X, Y), Z) > fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) 0.62/0.65 0.62/0.65 With these choices, we have: 0.62/0.65 0.62/0.65 1] fold(F, cons(X, Y), Z) > fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [2], by definition 0.62/0.65 2] fold*(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [3], [6], [8] and [10], by (Stat) 0.62/0.65 3] cons(X, Y) > Y because [4], by definition 0.62/0.65 4] cons*(X, Y) >= Y because [5], by (Select) 0.62/0.65 5] Y >= Y by (Meta) 0.62/0.65 6] fold*(F, cons(X, Y), Z) >= F because [7], by (Select) 0.62/0.65 7] F >= F by (Meta) 0.62/0.65 8] fold*(F, cons(X, Y), Z) >= Y because [9], by (Select) 0.62/0.65 9] cons(X, Y) >= Y because [4], by (Star) 0.62/0.65 10] fold*(F, cons(X, Y), Z) >= @_{o -> o}(@_{o -> o -> o}(F, Z), X) because fold > @_{o -> o}, [11] and [14], by (Copy) 0.62/0.65 11] fold*(F, cons(X, Y), Z) >= @_{o -> o -> o}(F, Z) because fold > @_{o -> o -> o}, [6] and [12], by (Copy) 0.62/0.65 12] fold*(F, cons(X, Y), Z) >= Z because [13], by (Select) 0.62/0.65 13] Z >= Z by (Meta) 0.62/0.65 14] fold*(F, cons(X, Y), Z) >= X because [15], by (Select) 0.62/0.65 15] cons(X, Y) >= X because [16], by (Star) 0.62/0.65 16] cons*(X, Y) >= X because [17], by (Select) 0.62/0.65 17] X >= X by (Meta) 0.62/0.65 0.62/0.65 We can thus remove the following rules: 0.62/0.65 0.62/0.65 fold(F, cons(X, Y), Z) => fold(F, Y, F Z X) 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