/export/starexec/sandbox/solver/bin/starexec_run_HigherOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. Alphabet: 0 : [] --> c 1 : [] --> c add : [] --> c -> a -> c cons : [a * b] --> b fold : [c -> a -> c * b * c] --> c mul : [] --> c -> a -> c nil : [] --> b prod : [b] --> c sum : [b] --> c Rules: fold(f, nil, x) => x fold(f, cons(x, y), z) => fold(f, y, f z x) sum(x) => fold(add, x, 0) fold(mul, x, 1) => prod(x) 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]): fold(F, nil, X) >? X fold(F, cons(X, Y), Z) >? fold(F, Y, F Z X) sum(X) >? fold(add, X, 0) fold(mul, X, 1) >? prod(X) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[add]] = _|_ [[fold(x_1, x_2, x_3)]] = fold(x_2, x_1, x_3) 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} Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: fold(F, nil, X) >= X fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) sum(X) >= fold(_|_, X, _|_) fold(mul, X, 1) > prod(X) With these choices, we have: 1] fold(F, nil, X) >= X because [2], by (Star) 2] fold*(F, nil, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [5], by (Star) 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) 6] cons(X, Y) > Y because [7], by definition 7] cons*(X, Y) >= Y because [8], by (Select) 8] Y >= Y by (Meta) 9] fold*(F, cons(X, Y), Z) >= F because [10], by (Select) 10] F >= F by (Meta) 11] fold*(F, cons(X, Y), Z) >= Y because [12], by (Select) 12] cons(X, Y) >= Y because [7], by (Star) 13] fold*(F, cons(X, Y), Z) >= @_{o -> o}(@_{o -> o -> o}(F, Z), X) because fold > @_{o -> o}, [14] and [17], by (Copy) 14] fold*(F, cons(X, Y), Z) >= @_{o -> o -> o}(F, Z) because fold > @_{o -> o -> o}, [9] and [15], by (Copy) 15] fold*(F, cons(X, Y), Z) >= Z because [16], by (Select) 16] Z >= Z by (Meta) 17] fold*(F, cons(X, Y), Z) >= X because [18], by (Select) 18] cons(X, Y) >= X because [19], by (Star) 19] cons*(X, Y) >= X because [20], by (Select) 20] X >= X by (Meta) 21] sum(X) >= fold(_|_, X, _|_) because [22], by (Star) 22] sum*(X) >= fold(_|_, X, _|_) because sum > fold, [23], [24] and [26], by (Copy) 23] sum*(X) >= _|_ by (Bot) 24] sum*(X) >= X because [25], by (Select) 25] X >= X by (Meta) 26] sum*(X) >= _|_ by (Bot) 27] fold(mul, X, 1) > prod(X) because [28], by definition 28] fold*(mul, X, 1) >= prod(X) because fold = prod, [29] and [30], by (Stat) 29] X >= X by (Meta) 30] fold*(mul, X, 1) >= X because [29], by (Select) We can thus remove the following rules: fold(mul, X, 1) => prod(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]): fold(F, nil, X) >? X fold(F, cons(X, Y), Z) >? fold(F, Y, F Z X) sum(X) >? fold(add, X, 0) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[add]] = _|_ [[fold(x_1, x_2, x_3)]] = fold(x_2, x_3, x_1) 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} Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: fold(F, nil, X) > X fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) sum(X) >= fold(_|_, X, _|_) With these choices, we have: 1] fold(F, nil, X) > X because [2], by definition 2] fold*(F, nil, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [5], by (Star) 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) 6] cons(X, Y) > Y because [7], by definition 7] cons*(X, Y) >= Y because [8], by (Select) 8] Y >= Y by (Meta) 9] fold*(F, cons(X, Y), Z) >= F because [10], by (Select) 10] F >= F by (Meta) 11] fold*(F, cons(X, Y), Z) >= Y because [12], by (Select) 12] cons(X, Y) >= Y because [7], by (Star) 13] fold*(F, cons(X, Y), Z) >= @_{o -> o}(@_{o -> o -> o}(F, Z), X) because fold > @_{o -> o}, [14] and [17], by (Copy) 14] fold*(F, cons(X, Y), Z) >= @_{o -> o -> o}(F, Z) because fold > @_{o -> o -> o}, [9] and [15], by (Copy) 15] fold*(F, cons(X, Y), Z) >= Z because [16], by (Select) 16] Z >= Z by (Meta) 17] fold*(F, cons(X, Y), Z) >= X because [18], by (Select) 18] cons(X, Y) >= X because [19], by (Star) 19] cons*(X, Y) >= X because [20], by (Select) 20] X >= X by (Meta) 21] sum(X) >= fold(_|_, X, _|_) because [22], by (Star) 22] sum*(X) >= fold(_|_, X, _|_) because sum > fold, [23], [24] and [26], by (Copy) 23] sum*(X) >= _|_ by (Bot) 24] sum*(X) >= X because [25], by (Select) 25] X >= X by (Meta) 26] sum*(X) >= _|_ by (Bot) We can thus remove the following rules: fold(F, nil, X) => 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]): fold(F, cons(X, Y), Z) >? fold(F, Y, F Z X) sum(X) >? fold(add, X, 0) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[add]] = _|_ 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} Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) sum(X) > fold(_|_, X, _|_) With these choices, we have: 1] fold(F, cons(X, Y), Z) >= fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [2], by (Star) 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) 3] F >= F by (Meta) 4] cons(X, Y) > Y because [5], by definition 5] cons*(X, Y) >= Y because [6], by (Select) 6] Y >= Y by (Meta) 7] fold*(F, cons(X, Y), Z) >= F because [3], by (Select) 8] fold*(F, cons(X, Y), Z) >= Y because [9], by (Select) 9] cons(X, Y) >= Y because [5], by (Star) 10] fold*(F, cons(X, Y), Z) >= @_{o -> o}(@_{o -> o -> o}(F, Z), X) because fold > @_{o -> o}, [11] and [14], by (Copy) 11] fold*(F, cons(X, Y), Z) >= @_{o -> o -> o}(F, Z) because fold > @_{o -> o -> o}, [7] and [12], by (Copy) 12] fold*(F, cons(X, Y), Z) >= Z because [13], by (Select) 13] Z >= Z by (Meta) 14] fold*(F, cons(X, Y), Z) >= X because [15], by (Select) 15] cons(X, Y) >= X because [16], by (Star) 16] cons*(X, Y) >= X because [17], by (Select) 17] X >= X by (Meta) 18] sum(X) > fold(_|_, X, _|_) because [19], by definition 19] sum*(X) >= fold(_|_, X, _|_) because sum > fold, [20], [21] and [23], by (Copy) 20] sum*(X) >= _|_ by (Bot) 21] sum*(X) >= X because [22], by (Select) 22] X >= X by (Meta) 23] sum*(X) >= _|_ by (Bot) We can thus remove the following rules: sum(X) => fold(add, X, 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]): fold(F, cons(X, Y), Z) >? fold(F, Y, F Z X) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[fold(x_1, x_2, x_3)]] = fold(x_2, x_3, x_1) We choose Lex = {fold} and Mul = {@_{o -> o -> o}, @_{o -> o}, cons}, and the following precedence: fold > @_{o -> o} > @_{o -> o -> o} > cons Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: fold(F, cons(X, Y), Z) > fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) With these choices, we have: 1] fold(F, cons(X, Y), Z) > fold(F, Y, @_{o -> o}(@_{o -> o -> o}(F, Z), X)) because [2], by definition 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) 3] cons(X, Y) > Y because [4], by definition 4] cons*(X, Y) >= Y because [5], by (Select) 5] Y >= Y by (Meta) 6] fold*(F, cons(X, Y), Z) >= F because [7], by (Select) 7] F >= F by (Meta) 8] fold*(F, cons(X, Y), Z) >= Y because [9], by (Select) 9] cons(X, Y) >= Y because [4], by (Star) 10] fold*(F, cons(X, Y), Z) >= @_{o -> o}(@_{o -> o -> o}(F, Z), X) because fold > @_{o -> o}, [11] and [14], by (Copy) 11] fold*(F, cons(X, Y), Z) >= @_{o -> o -> o}(F, Z) because fold > @_{o -> o -> o}, [6] and [12], by (Copy) 12] fold*(F, cons(X, Y), Z) >= Z because [13], by (Select) 13] Z >= Z by (Meta) 14] fold*(F, cons(X, Y), Z) >= X because [15], by (Select) 15] cons(X, Y) >= X because [16], by (Star) 16] cons*(X, Y) >= X because [17], by (Select) 17] X >= X by (Meta) We can thus remove the following rules: fold(F, cons(X, Y), Z) => fold(F, Y, F Z X) 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.