0.00/0.18 YES 0.00/0.19 We consider the system theBenchmark. 0.00/0.19 0.00/0.19 Alphabet: 0.00/0.19 0.00/0.19 comp : [c -> c * c -> c] --> c -> c 0.00/0.19 cons : [a * b] --> b 0.00/0.19 map : [a -> a * b] --> b 0.00/0.19 nil : [] --> b 0.00/0.19 twice : [c -> c] --> c -> c 0.00/0.19 0.00/0.19 Rules: 0.00/0.19 0.00/0.19 map(f, nil) => nil 0.00/0.19 map(f, cons(x, y)) => cons(f x, map(f, y)) 0.00/0.19 comp(f, g) x => f (g x) 0.00/0.19 twice(f) => comp(f, f) 0.00/0.19 0.00/0.19 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 0.00/0.19 0.00/0.19 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.19 0.00/0.19 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.19 0.00/0.19 map(F, nil) >? nil 0.00/0.19 map(F, cons(X, Y)) >? cons(F X, map(F, Y)) 0.00/0.19 comp(F, G) X >? F (G X) 0.00/0.19 twice(F) >? comp(F, F) 0.00/0.19 0.00/0.19 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.00/0.19 0.00/0.19 Argument functions: 0.00/0.19 0.00/0.19 [[nil]] = _|_ 0.00/0.19 0.00/0.19 We choose Lex = {} and Mul = {@_{o -> o}, comp, cons, map, twice}, and the following precedence: map > cons > twice > comp > @_{o -> o} 0.00/0.19 0.00/0.19 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.00/0.19 0.00/0.19 map(F, _|_) >= _|_ 0.00/0.19 map(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) 0.00/0.19 @_{o -> o}(comp(F, G), X) > @_{o -> o}(F, @_{o -> o}(G, X)) 0.00/0.19 twice(F) >= comp(F, F) 0.00/0.19 0.00/0.19 With these choices, we have: 0.00/0.19 0.00/0.19 1] map(F, _|_) >= _|_ by (Bot) 0.00/0.19 0.00/0.19 2] map(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) because [3], by (Star) 0.00/0.19 3] map*(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) because map > cons, [4] and [11], by (Copy) 0.00/0.19 4] map*(F, cons(X, Y)) >= @_{o -> o}(F, X) because map > @_{o -> o}, [5] and [7], by (Copy) 0.00/0.19 5] map*(F, cons(X, Y)) >= F because [6], by (Select) 0.00/0.19 6] F >= F by (Meta) 0.00/0.19 7] map*(F, cons(X, Y)) >= X because [8], by (Select) 0.00/0.19 8] cons(X, Y) >= X because [9], by (Star) 0.00/0.19 9] cons*(X, Y) >= X because [10], by (Select) 0.00/0.19 10] X >= X by (Meta) 0.00/0.19 11] map*(F, cons(X, Y)) >= map(F, Y) because map in Mul, [12] and [13], by (Stat) 0.00/0.19 12] F >= F by (Meta) 0.00/0.19 13] cons(X, Y) > Y because [14], by definition 0.00/0.19 14] cons*(X, Y) >= Y because [15], by (Select) 0.00/0.19 15] Y >= Y by (Meta) 0.00/0.19 0.00/0.19 16] @_{o -> o}(comp(F, G), X) > @_{o -> o}(F, @_{o -> o}(G, X)) because [17], by definition 0.00/0.19 17] @_{o -> o}*(comp(F, G), X) >= @_{o -> o}(F, @_{o -> o}(G, X)) because [18], by (Select) 0.00/0.19 18] comp(F, G) @_{o -> o}*(comp(F, G), X) >= @_{o -> o}(F, @_{o -> o}(G, X)) because [19] 0.00/0.19 19] comp*(F, G, @_{o -> o}*(comp(F, G), X)) >= @_{o -> o}(F, @_{o -> o}(G, X)) because comp > @_{o -> o}, [20] and [22], by (Copy) 0.00/0.19 20] comp*(F, G, @_{o -> o}*(comp(F, G), X)) >= F because [21], by (Select) 0.00/0.19 21] F >= F by (Meta) 0.00/0.19 22] comp*(F, G, @_{o -> o}*(comp(F, G), X)) >= @_{o -> o}(G, X) because comp > @_{o -> o}, [23] and [25], by (Copy) 0.00/0.19 23] comp*(F, G, @_{o -> o}*(comp(F, G), X)) >= G because [24], by (Select) 0.00/0.19 24] G >= G by (Meta) 0.00/0.19 25] comp*(F, G, @_{o -> o}*(comp(F, G), X)) >= X because [26], by (Select) 0.00/0.19 26] @_{o -> o}*(comp(F, G), X) >= X because [27], by (Select) 0.00/0.19 27] X >= X by (Meta) 0.00/0.19 0.00/0.19 28] twice(F) >= comp(F, F) because [29], by (Star) 0.00/0.19 29] twice*(F) >= comp(F, F) because twice > comp, [30] and [30], by (Copy) 0.00/0.19 30] twice*(F) >= F because [31], by (Select) 0.00/0.19 31] F >= F by (Meta) 0.00/0.19 0.00/0.19 We can thus remove the following rules: 0.00/0.19 0.00/0.19 comp(F, G) X => F (G X) 0.00/0.19 0.00/0.19 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.19 0.00/0.19 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.19 0.00/0.19 map(F, nil) >? nil 0.00/0.19 map(F, cons(X, Y)) >? cons(F X, map(F, Y)) 0.00/0.19 twice(F) >? comp(F, F) 0.00/0.19 0.00/0.19 We orient these requirements with a polynomial interpretation in the natural numbers. 0.00/0.19 0.00/0.19 The following interpretation satisfies the requirements: 0.00/0.19 0.00/0.19 comp = \G0G1y2.G0(0) + G1(0) 0.00/0.19 cons = \y0y1.3 + y0 + y1 0.00/0.19 map = \G0y1.3 + 3y1 + G0(0) + 3y1G0(y1) 0.00/0.19 nil = 0 0.00/0.19 twice = \G0y1.3 + 3y1 + 2G0(0) + 3G0(y1) 0.00/0.19 0.00/0.19 Using this interpretation, the requirements translate to: 0.00/0.19 0.00/0.19 [[map(_F0, nil)]] = 3 + F0(0) > 0 = [[nil]] 0.00/0.19 [[map(_F0, cons(_x1, _x2))]] = 12 + 3x1 + 3x2 + F0(0) + 3x1F0(3 + x1 + x2) + 3x2F0(3 + x1 + x2) + 9F0(3 + x1 + x2) > 6 + x1 + 3x2 + F0(0) + F0(x1) + 3x2F0(x2) = [[cons(_F0 _x1, map(_F0, _x2))]] 0.00/0.19 [[twice(_F0)]] = \y0.3 + 3y0 + 2F0(0) + 3F0(y0) > \y0.2F0(0) = [[comp(_F0, _F0)]] 0.00/0.19 0.00/0.19 We can thus remove the following rules: 0.00/0.19 0.00/0.19 map(F, nil) => nil 0.00/0.19 map(F, cons(X, Y)) => cons(F X, map(F, Y)) 0.00/0.19 twice(F) => comp(F, F) 0.00/0.19 0.00/0.19 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.19 0.00/0.19 0.00/0.19 +++ Citations +++ 0.00/0.19 0.00/0.19 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 0.00/0.19 EOF