0.00/0.41 YES 0.00/0.44 We consider the system theBenchmark. 0.00/0.44 0.00/0.44 Alphabet: 0.00/0.44 0.00/0.44 compose : [a -> a * a -> a] --> a -> a 0.00/0.44 cons : [a * a] --> a 0.00/0.44 hd : [] --> a -> a 0.00/0.44 init : [] --> a -> a 0.00/0.44 last : [] --> a -> a 0.00/0.44 nil : [] --> a 0.00/0.44 reverse : [] --> a -> a 0.00/0.44 reverse2 : [a * a] --> a 0.00/0.44 tl : [] --> a -> a 0.00/0.44 0.00/0.44 Rules: 0.00/0.44 0.00/0.44 compose(f, g) x => g (f x) 0.00/0.44 reverse x => reverse2(x, nil) 0.00/0.44 reverse2(nil, x) => x 0.00/0.44 reverse2(cons(x, y), z) => reverse2(y, cons(x, z)) 0.00/0.44 hd cons(x, y) => x 0.00/0.44 tl cons(x, y) => y 0.00/0.44 last => compose(hd, reverse) 0.00/0.44 init => compose(reverse, compose(tl, reverse)) 0.00/0.44 0.00/0.44 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 0.00/0.44 0.00/0.44 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.44 0.00/0.44 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.44 0.00/0.44 compose(F, G) X >? G (F X) 0.00/0.44 reverse X >? reverse2(X, nil) 0.00/0.44 reverse2(nil, X) >? X 0.00/0.44 reverse2(cons(X, Y), Z) >? reverse2(Y, cons(X, Z)) 0.00/0.44 hd cons(X, Y) >? X 0.00/0.44 tl cons(X, Y) >? Y 0.00/0.44 last >? compose(hd, reverse) 0.00/0.44 init >? compose(reverse, compose(tl, reverse)) 0.00/0.44 0.00/0.44 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.00/0.44 0.00/0.44 Argument functions: 0.00/0.44 0.00/0.44 [[hd]] = _|_ 0.00/0.44 [[nil]] = _|_ 0.00/0.44 [[reverse]] = _|_ 0.00/0.44 [[tl]] = _|_ 0.00/0.44 0.00/0.44 We choose Lex = {reverse2} and Mul = {@_{o -> o}, compose, cons, init, last}, and the following precedence: init > last > compose > @_{o -> o} > reverse2 > cons 0.00/0.44 0.00/0.44 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.00/0.44 0.00/0.44 @_{o -> o}(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) 0.00/0.44 @_{o -> o}(_|_, X) >= reverse2(X, _|_) 0.00/0.44 reverse2(_|_, X) > X 0.00/0.44 reverse2(cons(X, Y), Z) >= reverse2(Y, cons(X, Z)) 0.00/0.44 @_{o -> o}(_|_, cons(X, Y)) > X 0.00/0.44 @_{o -> o}(_|_, cons(X, Y)) > Y 0.00/0.44 last >= compose(_|_, _|_) 0.00/0.44 init > compose(_|_, compose(_|_, _|_)) 0.00/0.44 0.00/0.44 With these choices, we have: 0.00/0.44 0.00/0.44 1] @_{o -> o}(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) because [2], by (Star) 0.00/0.44 2] @_{o -> o}*(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) because [3], by (Select) 0.00/0.44 3] compose(F, G) @_{o -> o}*(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) because [4] 0.00/0.44 4] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= @_{o -> o}(G, @_{o -> o}(F, X)) because compose > @_{o -> o}, [5] and [7], by (Copy) 0.00/0.44 5] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= G because [6], by (Select) 0.00/0.44 6] G >= G by (Meta) 0.00/0.44 7] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= @_{o -> o}(F, X) because compose > @_{o -> o}, [8] and [10], by (Copy) 0.00/0.44 8] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= F because [9], by (Select) 0.00/0.44 9] F >= F by (Meta) 0.00/0.44 10] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= X because [11], by (Select) 0.00/0.44 11] @_{o -> o}*(compose(F, G), X) >= X because [12], by (Select) 0.00/0.44 12] X >= X by (Meta) 0.00/0.44 0.00/0.44 13] @_{o -> o}(_|_, X) >= reverse2(X, _|_) because [14], by (Star) 0.00/0.44 14] @_{o -> o}*(_|_, X) >= reverse2(X, _|_) because @_{o -> o} > reverse2, [15] and [17], by (Copy) 0.00/0.44 15] @_{o -> o}*(_|_, X) >= X because [16], by (Select) 0.00/0.44 16] X >= X by (Meta) 0.00/0.44 17] @_{o -> o}*(_|_, X) >= _|_ by (Bot) 0.00/0.44 0.00/0.44 18] reverse2(_|_, X) > X because [19], by definition 0.00/0.44 19] reverse2*(_|_, X) >= X because [20], by (Select) 0.00/0.44 20] X >= X by (Meta) 0.00/0.44 0.00/0.44 21] reverse2(cons(X, Y), Z) >= reverse2(Y, cons(X, Z)) because [22], by (Star) 0.00/0.44 22] reverse2*(cons(X, Y), Z) >= reverse2(Y, cons(X, Z)) because [23], [26] and [28], by (Stat) 0.00/0.44 23] cons(X, Y) > Y because [24], by definition 0.00/0.44 24] cons*(X, Y) >= Y because [25], by (Select) 0.00/0.44 25] Y >= Y by (Meta) 0.00/0.44 26] reverse2*(cons(X, Y), Z) >= Y because [27], by (Select) 0.00/0.44 27] cons(X, Y) >= Y because [24], by (Star) 0.00/0.44 28] reverse2*(cons(X, Y), Z) >= cons(X, Z) because reverse2 > cons, [29] and [33], by (Copy) 0.00/0.44 29] reverse2*(cons(X, Y), Z) >= X because [30], by (Select) 0.00/0.44 30] cons(X, Y) >= X because [31], by (Star) 0.00/0.44 31] cons*(X, Y) >= X because [32], by (Select) 0.00/0.44 32] X >= X by (Meta) 0.00/0.44 33] reverse2*(cons(X, Y), Z) >= Z because [34], by (Select) 0.00/0.44 34] Z >= Z by (Meta) 0.00/0.44 0.00/0.44 35] @_{o -> o}(_|_, cons(X, Y)) > X because [36], by definition 0.00/0.44 36] @_{o -> o}*(_|_, cons(X, Y)) >= X because [37], by (Select) 0.00/0.44 37] cons(X, Y) >= X because [38], by (Star) 0.00/0.44 38] cons*(X, Y) >= X because [39], by (Select) 0.00/0.44 39] X >= X by (Meta) 0.00/0.44 0.00/0.44 40] @_{o -> o}(_|_, cons(X, Y)) > Y because [41], by definition 0.00/0.44 41] @_{o -> o}*(_|_, cons(X, Y)) >= Y because [42], by (Select) 0.00/0.44 42] cons(X, Y) >= Y because [43], by (Star) 0.00/0.44 43] cons*(X, Y) >= Y because [44], by (Select) 0.00/0.44 44] Y >= Y by (Meta) 0.00/0.44 0.00/0.44 45] last >= compose(_|_, _|_) because [46], by (Star) 0.00/0.44 46] last* >= compose(_|_, _|_) because last > compose, [47] and [48], by (Copy) 0.00/0.44 47] last* >= _|_ by (Bot) 0.00/0.44 48] last* >= _|_ by (Bot) 0.00/0.44 0.00/0.44 49] init > compose(_|_, compose(_|_, _|_)) because [50], by definition 0.00/0.44 50] init* >= compose(_|_, compose(_|_, _|_)) because init > compose, [51] and [52], by (Copy) 0.00/0.44 51] init* >= _|_ by (Bot) 0.00/0.44 52] init* >= compose(_|_, _|_) because init > compose, [53] and [51], by (Copy) 0.00/0.44 53] init* >= _|_ by (Bot) 0.00/0.44 0.00/0.44 We can thus remove the following rules: 0.00/0.44 0.00/0.44 reverse2(nil, X) => X 0.00/0.44 hd cons(X, Y) => X 0.00/0.44 tl cons(X, Y) => Y 0.00/0.44 init => compose(reverse, compose(tl, reverse)) 0.00/0.44 0.00/0.44 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.44 0.00/0.44 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.44 0.00/0.44 compose(F, G) X >? G (F X) 0.00/0.44 reverse X >? reverse2(X, nil) 0.00/0.44 reverse2(cons(X, Y), Z) >? reverse2(Y, cons(X, Z)) 0.00/0.44 last >? compose(hd, reverse) 0.00/0.44 0.00/0.44 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.00/0.44 0.00/0.44 Argument functions: 0.00/0.44 0.00/0.44 [[hd]] = _|_ 0.00/0.44 [[nil]] = _|_ 0.00/0.44 [[reverse]] = _|_ 0.00/0.44 0.00/0.44 We choose Lex = {reverse2} and Mul = {@_{o -> o}, compose, cons, last}, and the following precedence: last > compose > @_{o -> o} > reverse2 > cons 0.00/0.44 0.00/0.44 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.00/0.44 0.00/0.44 @_{o -> o}(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) 0.00/0.44 @_{o -> o}(_|_, X) > reverse2(X, _|_) 0.00/0.44 reverse2(cons(X, Y), Z) > reverse2(Y, cons(X, Z)) 0.00/0.44 last >= compose(_|_, _|_) 0.00/0.44 0.00/0.44 With these choices, we have: 0.00/0.44 0.00/0.44 1] @_{o -> o}(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) because [2], by (Star) 0.00/0.44 2] @_{o -> o}*(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) because [3], by (Select) 0.00/0.44 3] compose(F, G) @_{o -> o}*(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) because [4] 0.00/0.44 4] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= @_{o -> o}(G, @_{o -> o}(F, X)) because compose > @_{o -> o}, [5] and [7], by (Copy) 0.00/0.44 5] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= G because [6], by (Select) 0.00/0.44 6] G >= G by (Meta) 0.00/0.44 7] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= @_{o -> o}(F, X) because compose > @_{o -> o}, [8] and [10], by (Copy) 0.00/0.44 8] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= F because [9], by (Select) 0.00/0.44 9] F >= F by (Meta) 0.00/0.44 10] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= X because [11], by (Select) 0.00/0.44 11] @_{o -> o}*(compose(F, G), X) >= X because [12], by (Select) 0.00/0.44 12] X >= X by (Meta) 0.00/0.44 0.00/0.44 13] @_{o -> o}(_|_, X) > reverse2(X, _|_) because [14], by definition 0.00/0.44 14] @_{o -> o}*(_|_, X) >= reverse2(X, _|_) because @_{o -> o} > reverse2, [15] and [17], by (Copy) 0.00/0.44 15] @_{o -> o}*(_|_, X) >= X because [16], by (Select) 0.00/0.44 16] X >= X by (Meta) 0.00/0.44 17] @_{o -> o}*(_|_, X) >= _|_ by (Bot) 0.00/0.44 0.00/0.44 18] reverse2(cons(X, Y), Z) > reverse2(Y, cons(X, Z)) because [19], by definition 0.00/0.44 19] reverse2*(cons(X, Y), Z) >= reverse2(Y, cons(X, Z)) because [20], [23] and [25], by (Stat) 0.00/0.44 20] cons(X, Y) > Y because [21], by definition 0.00/0.44 21] cons*(X, Y) >= Y because [22], by (Select) 0.00/0.44 22] Y >= Y by (Meta) 0.00/0.44 23] reverse2*(cons(X, Y), Z) >= Y because [24], by (Select) 0.00/0.44 24] cons(X, Y) >= Y because [21], by (Star) 0.00/0.44 25] reverse2*(cons(X, Y), Z) >= cons(X, Z) because reverse2 > cons, [26] and [30], by (Copy) 0.00/0.44 26] reverse2*(cons(X, Y), Z) >= X because [27], by (Select) 0.00/0.44 27] cons(X, Y) >= X because [28], by (Star) 0.00/0.44 28] cons*(X, Y) >= X because [29], by (Select) 0.00/0.44 29] X >= X by (Meta) 0.00/0.44 30] reverse2*(cons(X, Y), Z) >= Z because [31], by (Select) 0.00/0.44 31] Z >= Z by (Meta) 0.00/0.44 0.00/0.44 32] last >= compose(_|_, _|_) because [33], by (Star) 0.00/0.44 33] last* >= compose(_|_, _|_) because last > compose, [34] and [35], by (Copy) 0.00/0.44 34] last* >= _|_ by (Bot) 0.00/0.44 35] last* >= _|_ by (Bot) 0.00/0.44 0.00/0.44 We can thus remove the following rules: 0.00/0.44 0.00/0.44 reverse X => reverse2(X, nil) 0.00/0.44 reverse2(cons(X, Y), Z) => reverse2(Y, cons(X, Z)) 0.00/0.44 0.00/0.44 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.44 0.00/0.44 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.44 0.00/0.44 compose(F, G) X >? G (F X) 0.00/0.44 last >? compose(hd, reverse) 0.00/0.44 0.00/0.44 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.00/0.44 0.00/0.44 Argument functions: 0.00/0.44 0.00/0.44 [[hd]] = _|_ 0.00/0.44 [[reverse]] = _|_ 0.00/0.44 0.00/0.44 We choose Lex = {} and Mul = {@_{o -> o}, compose, last}, and the following precedence: last > compose > @_{o -> o} 0.00/0.44 0.00/0.44 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.00/0.44 0.00/0.44 @_{o -> o}(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) 0.00/0.44 last > compose(_|_, _|_) 0.00/0.44 0.00/0.44 With these choices, we have: 0.00/0.44 0.00/0.44 1] @_{o -> o}(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) because [2], by (Star) 0.00/0.44 2] @_{o -> o}*(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) because [3], by (Select) 0.00/0.44 3] compose(F, G) @_{o -> o}*(compose(F, G), X) >= @_{o -> o}(G, @_{o -> o}(F, X)) because [4] 0.00/0.44 4] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= @_{o -> o}(G, @_{o -> o}(F, X)) because compose > @_{o -> o}, [5] and [7], by (Copy) 0.00/0.44 5] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= G because [6], by (Select) 0.00/0.44 6] G >= G by (Meta) 0.00/0.44 7] compose*(F, G, @_{o -> o}*(compose(F, G), X)) >= @_{o -> o}(F, X) because [8], by (Select) 0.00/0.44 8] @_{o -> o}*(compose(F, G), X) >= @_{o -> o}(F, X) because @_{o -> o} in Mul, [9] and [12], by (Stat) 0.00/0.44 9] compose(F, G) > F because [10], by definition 0.00/0.44 10] compose*(F, G) >= F because [11], by (Select) 0.00/0.44 11] F >= F by (Meta) 0.00/0.44 12] X >= X by (Meta) 0.00/0.44 0.00/0.44 13] last > compose(_|_, _|_) because [14], by definition 0.00/0.44 14] last* >= compose(_|_, _|_) because last > compose, [15] and [16], by (Copy) 0.00/0.44 15] last* >= _|_ by (Bot) 0.00/0.44 16] last* >= _|_ by (Bot) 0.00/0.44 0.00/0.44 We can thus remove the following rules: 0.00/0.44 0.00/0.44 last => compose(hd, reverse) 0.00/0.44 0.00/0.44 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.44 0.00/0.44 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.44 0.00/0.44 compose(F, G, X) >? G (F X) 0.00/0.44 0.00/0.44 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.00/0.44 0.00/0.44 We choose Lex = {} and Mul = {@_{o -> o}, compose}, and the following precedence: compose > @_{o -> o} 0.00/0.44 0.00/0.44 With these choices, we have: 0.00/0.44 0.00/0.44 1] compose(F, G, X) > @_{o -> o}(G, @_{o -> o}(F, X)) because [2], by definition 0.00/0.44 2] compose*(F, G, X) >= @_{o -> o}(G, @_{o -> o}(F, X)) because compose > @_{o -> o}, [3] and [5], by (Copy) 0.00/0.44 3] compose*(F, G, X) >= G because [4], by (Select) 0.00/0.44 4] G >= G by (Meta) 0.00/0.44 5] compose*(F, G, X) >= @_{o -> o}(F, X) because compose > @_{o -> o}, [6] and [8], by (Copy) 0.00/0.44 6] compose*(F, G, X) >= F because [7], by (Select) 0.00/0.44 7] F >= F by (Meta) 0.00/0.44 8] compose*(F, G, X) >= X because [9], by (Select) 0.00/0.44 9] X >= X by (Meta) 0.00/0.44 0.00/0.44 We can thus remove the following rules: 0.00/0.44 0.00/0.44 compose(F, G, X) => G (F X) 0.00/0.44 0.00/0.44 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.00/0.44 0.00/0.44 0.00/0.44 +++ Citations +++ 0.00/0.44 0.00/0.44 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 0.00/0.44 EOF