0.70/1.70 YES 0.70/1.73 We consider the system theBenchmark. 0.70/1.73 0.70/1.73 Alphabet: 0.70/1.73 0.70/1.73 0 : [] --> nat 0.70/1.73 cons : [nat * list] --> list 0.70/1.73 map : [nat -> nat * list] --> list 0.70/1.73 nil : [] --> list 0.70/1.73 op : [nat -> nat * nat -> nat] --> nat -> nat 0.70/1.73 pow : [nat -> nat * nat] --> nat -> nat 0.70/1.73 s : [nat] --> nat 0.70/1.73 0.70/1.73 Rules: 0.70/1.73 0.70/1.73 map(f, nil) => nil 0.70/1.73 map(f, cons(x, y)) => cons(f x, map(f, y)) 0.70/1.73 pow(f, 0) => /\x.x 0.70/1.73 pow(f, s(x)) => op(f, pow(f, x)) 0.70/1.73 op(f, g) x => f (g x) 0.70/1.73 /\x.f x => f 0.70/1.73 0.70/1.73 Using the transformations described in [Kop11], this system can be brought in a form without leading free variables in the left-hand side, and where the left-hand side of a variable is always a functional term or application headed by a functional term. 0.70/1.73 0.70/1.73 We now transform the resulting AFS into an AFSM by replacing all free variables by meta-variables (with arity 0). This leads to the following AFSM: 0.70/1.73 0.70/1.73 Alphabet: 0.70/1.73 0.70/1.73 0 : [] --> nat 0.70/1.73 cons : [nat * list] --> list 0.70/1.73 map : [nat -> nat * list] --> list 0.70/1.73 nil : [] --> list 0.70/1.73 op : [nat -> nat * nat -> nat] --> nat -> nat 0.70/1.73 pow : [nat -> nat * nat] --> nat -> nat 0.70/1.73 s : [nat] --> nat 0.70/1.73 ~AP1 : [nat -> nat * nat] --> nat 0.70/1.73 ~L1 : [nat -> nat] --> nat -> nat 0.70/1.73 0.70/1.73 Rules: 0.70/1.73 0.70/1.73 map(F, nil) => nil 0.70/1.73 map(F, cons(X, Y)) => cons(~AP1(F, X), map(F, Y)) 0.70/1.73 pow(F, 0) => ~L1(/\x.x) 0.70/1.73 pow(F, s(X)) => op(F, pow(F, X)) 0.70/1.73 op(F, G) X => ~AP1(F, ~AP1(G, X)) 0.70/1.73 ~L1(/\x.~AP1(F, x)) => F 0.70/1.73 ~L1(/\x.op(F, G) x) => op(F, G) 0.70/1.73 ~AP1(F, X) => F X 0.70/1.73 ~L1(F) => F 0.70/1.73 0.70/1.73 We use rule removal, following [Kop12, Theorem 2.23]. 0.70/1.73 0.70/1.73 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.70/1.73 0.70/1.73 map(F, nil) >? nil 0.70/1.73 map(F, cons(X, Y)) >? cons(~AP1(F, X), map(F, Y)) 0.70/1.73 pow(F, 0) >? ~L1(/\x.x) 0.70/1.73 pow(F, s(X)) >? op(F, pow(F, X)) 0.70/1.73 op(F, G) X >? ~AP1(F, ~AP1(G, X)) 0.70/1.73 ~L1(/\x.~AP1(F, x)) >? F 0.70/1.73 ~L1(/\x.op(F, G) x) >? op(F, G) 0.70/1.73 ~AP1(F, X) >? F X 0.70/1.73 ~L1(F) >? F 0.70/1.73 0.70/1.73 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.70/1.73 0.70/1.73 Argument functions: 0.70/1.73 0.70/1.73 [[nil]] = _|_ 0.70/1.73 0.70/1.73 We choose Lex = {} and Mul = {0, @_{o -> o}, cons, map, op, pow, s, ~AP1, ~L1}, and the following precedence: 0 > pow > s > ~L1 > op > map = ~AP1 > @_{o -> o} > cons 0.70/1.74 0.70/1.74 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.70/1.74 0.70/1.74 map(F, _|_) >= _|_ 0.70/1.74 map(F, cons(X, Y)) > cons(~AP1(F, X), map(F, Y)) 0.70/1.74 pow(F, 0) > ~L1(/\x.x) 0.70/1.74 pow(F, s(X)) >= op(F, pow(F, X)) 0.70/1.74 @_{o -> o}(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) 0.70/1.74 ~L1(/\x.~AP1(F, x)) >= F 0.70/1.74 ~L1(/\x.@_{o -> o}(op(F, G), x)) >= op(F, G) 0.70/1.74 ~AP1(F, X) > @_{o -> o}(F, X) 0.70/1.74 ~L1(F) >= F 0.70/1.74 0.70/1.74 With these choices, we have: 0.70/1.74 0.70/1.74 1] map(F, _|_) >= _|_ by (Bot) 0.70/1.74 0.70/1.74 2] map(F, cons(X, Y)) > cons(~AP1(F, X), map(F, Y)) because [3], by definition 0.70/1.74 3] map*(F, cons(X, Y)) >= cons(~AP1(F, X), map(F, Y)) because map > cons, [4] and [9], by (Copy) 0.70/1.74 4] map*(F, cons(X, Y)) >= ~AP1(F, X) because map = ~AP1, map in Mul, [5] and [6], by (Stat) 0.70/1.74 5] F >= F by (Meta) 0.70/1.74 6] cons(X, Y) > X because [7], by definition 0.70/1.74 7] cons*(X, Y) >= X because [8], by (Select) 0.70/1.74 8] X >= X by (Meta) 0.70/1.74 9] map*(F, cons(X, Y)) >= map(F, Y) because map in Mul, [5] and [10], by (Stat) 0.70/1.74 10] cons(X, Y) > Y because [11], by definition 0.70/1.74 11] cons*(X, Y) >= Y because [12], by (Select) 0.70/1.74 12] Y >= Y by (Meta) 0.70/1.74 0.70/1.74 13] pow(F, 0) > ~L1(/\x.x) because [14], by definition 0.70/1.74 14] pow*(F, 0) >= ~L1(/\x.x) because pow > ~L1 and [15], by (Copy) 0.70/1.74 15] pow*(F, 0) >= /\y.y because [16], by (F-Abs) 0.70/1.74 16] pow*(F, 0, x) >= x because [17], by (Select) 0.70/1.74 17] x >= x by (Var) 0.70/1.74 0.70/1.74 18] pow(F, s(X)) >= op(F, pow(F, X)) because [19], by (Star) 0.70/1.74 19] pow*(F, s(X)) >= op(F, pow(F, X)) because pow > op, [20] and [22], by (Copy) 0.70/1.74 20] pow*(F, s(X)) >= F because [21], by (Select) 0.70/1.74 21] F >= F by (Meta) 0.70/1.74 22] pow*(F, s(X)) >= pow(F, X) because pow in Mul, [23] and [24], by (Stat) 0.70/1.74 23] F >= F by (Meta) 0.70/1.74 24] s(X) > X because [25], by definition 0.70/1.74 25] s*(X) >= X because [26], by (Select) 0.70/1.74 26] X >= X by (Meta) 0.70/1.74 0.70/1.74 27] @_{o -> o}(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) because [28], by (Star) 0.70/1.74 28] @_{o -> o}*(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) because [29], by (Select) 0.70/1.74 29] op(F, G) @_{o -> o}*(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) because [30] 0.70/1.74 30] op*(F, G, @_{o -> o}*(op(F, G), X)) >= ~AP1(F, ~AP1(G, X)) because op > ~AP1, [31] and [33], by (Copy) 0.70/1.74 31] op*(F, G, @_{o -> o}*(op(F, G), X)) >= F because [32], by (Select) 0.70/1.74 32] F >= F by (Meta) 0.70/1.74 33] op*(F, G, @_{o -> o}*(op(F, G), X)) >= ~AP1(G, X) because op > ~AP1, [34] and [36], by (Copy) 0.70/1.74 34] op*(F, G, @_{o -> o}*(op(F, G), X)) >= G because [35], by (Select) 0.70/1.74 35] G >= G by (Meta) 0.70/1.74 36] op*(F, G, @_{o -> o}*(op(F, G), X)) >= X because [37], by (Select) 0.70/1.74 37] @_{o -> o}*(op(F, G), X) >= X because [38], by (Select) 0.70/1.74 38] X >= X by (Meta) 0.70/1.74 0.70/1.74 39] ~L1(/\x.~AP1(F, x)) >= F because [40], by (Star) 0.70/1.74 40] ~L1*(/\x.~AP1(F, x)) >= F because [41], by (Select) 0.70/1.74 41] /\x.~AP1(F, x) >= F because [42], by (Eta)[Kop13:2] 0.70/1.74 42] F >= F by (Meta) 0.70/1.74 0.70/1.74 43] ~L1(/\x.@_{o -> o}(op(F, G), x)) >= op(F, G) because [44], by (Star) 0.70/1.74 44] ~L1*(/\x.@_{o -> o}(op(F, G), x)) >= op(F, G) because ~L1 > op, [45] and [50], by (Copy) 0.70/1.74 45] ~L1*(/\x.@_{o -> o}(op(F, G), x)) >= F because [46], by (Select) 0.70/1.74 46] /\x.@_{o -> o}(op(F, G), x) >= F because [47], by (Eta)[Kop13:2] 0.70/1.74 47] op(F, G) >= F because [48], by (Star) 0.70/1.74 48] op*(F, G) >= F because [49], by (Select) 0.70/1.74 49] F >= F by (Meta) 0.70/1.74 50] ~L1*(/\x.@_{o -> o}(op(F, G), x)) >= G because [51], by (Select) 0.70/1.74 51] /\x.@_{o -> o}(op(F, G), x) >= G because [52], by (Eta)[Kop13:2] 0.70/1.74 52] op(F, G) >= G because [53], by (Star) 0.70/1.74 53] op*(F, G) >= G because [54], by (Select) 0.70/1.74 54] G >= G by (Meta) 0.70/1.74 0.70/1.74 55] ~AP1(F, X) > @_{o -> o}(F, X) because [56], by definition 0.70/1.74 56] ~AP1*(F, X) >= @_{o -> o}(F, X) because ~AP1 > @_{o -> o}, [57] and [59], by (Copy) 0.70/1.74 57] ~AP1*(F, X) >= F because [58], by (Select) 0.70/1.74 58] F >= F by (Meta) 0.70/1.74 59] ~AP1*(F, X) >= X because [60], by (Select) 0.70/1.74 60] X >= X by (Meta) 0.70/1.74 0.70/1.74 61] ~L1(F) >= F because [62], by (Star) 0.70/1.74 62] ~L1*(F) >= F because [63], by (Select) 0.70/1.74 63] F >= F by (Meta) 0.70/1.74 0.70/1.74 We can thus remove the following rules: 0.70/1.74 0.70/1.74 map(F, cons(X, Y)) => cons(~AP1(F, X), map(F, Y)) 0.70/1.74 pow(F, 0) => ~L1(/\x.x) 0.70/1.74 ~AP1(F, X) => F X 0.70/1.74 0.70/1.74 We use rule removal, following [Kop12, Theorem 2.23]. 0.70/1.74 0.70/1.74 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.70/1.74 0.70/1.74 map(F, nil) >? nil 0.70/1.74 pow(F, s(X)) >? op(F, pow(F, X)) 0.70/1.74 op(F, G) X >? ~AP1(F, ~AP1(G, X)) 0.70/1.74 ~L1(/\x.~AP1(F, x)) >? F 0.70/1.74 ~L1(/\x.op(F, G) x) >? op(F, G) 0.70/1.74 ~L1(F) >? F 0.70/1.74 0.70/1.74 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.70/1.74 0.70/1.74 Argument functions: 0.70/1.74 0.70/1.74 [[nil]] = _|_ 0.70/1.74 0.70/1.74 We choose Lex = {} and Mul = {@_{o -> o}, map, op, pow, s, ~AP1, ~L1}, and the following precedence: map > pow > s > ~L1 > @_{o -> o} > ~AP1 > op 0.70/1.74 0.70/1.74 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.70/1.74 0.70/1.74 map(F, _|_) >= _|_ 0.70/1.74 pow(F, s(X)) > op(F, pow(F, X)) 0.70/1.74 @_{o -> o}(op(F, G), X) > ~AP1(F, ~AP1(G, X)) 0.70/1.74 ~L1(/\x.~AP1(F, x)) >= F 0.70/1.74 ~L1(/\x.@_{o -> o}(op(F, G), x)) > op(F, G) 0.70/1.74 ~L1(F) >= F 0.70/1.74 0.70/1.74 With these choices, we have: 0.70/1.74 0.70/1.74 1] map(F, _|_) >= _|_ by (Bot) 0.70/1.74 0.70/1.74 2] pow(F, s(X)) > op(F, pow(F, X)) because [3], by definition 0.70/1.74 3] pow*(F, s(X)) >= op(F, pow(F, X)) because pow > op, [4] and [6], by (Copy) 0.70/1.74 4] pow*(F, s(X)) >= F because [5], by (Select) 0.70/1.74 5] F >= F by (Meta) 0.70/1.74 6] pow*(F, s(X)) >= pow(F, X) because pow in Mul, [7] and [8], by (Stat) 0.70/1.74 7] F >= F by (Meta) 0.70/1.74 8] s(X) > X because [9], by definition 0.70/1.74 9] s*(X) >= X because [10], by (Select) 0.70/1.74 10] X >= X by (Meta) 0.70/1.74 0.70/1.74 11] @_{o -> o}(op(F, G), X) > ~AP1(F, ~AP1(G, X)) because [12], by definition 0.70/1.74 12] @_{o -> o}*(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) because @_{o -> o} > ~AP1, [13] and [17], by (Copy) 0.70/1.74 13] @_{o -> o}*(op(F, G), X) >= F because [14], by (Select) 0.70/1.74 14] op(F, G) >= F because [15], by (Star) 0.70/1.74 15] op*(F, G) >= F because [16], by (Select) 0.70/1.74 16] F >= F by (Meta) 0.70/1.74 17] @_{o -> o}*(op(F, G), X) >= ~AP1(G, X) because @_{o -> o} > ~AP1, [18] and [22], by (Copy) 0.70/1.74 18] @_{o -> o}*(op(F, G), X) >= G because [19], by (Select) 0.70/1.74 19] op(F, G) >= G because [20], by (Star) 0.70/1.74 20] op*(F, G) >= G because [21], by (Select) 0.70/1.74 21] G >= G by (Meta) 0.70/1.74 22] @_{o -> o}*(op(F, G), X) >= X because [23], by (Select) 0.70/1.74 23] X >= X by (Meta) 0.70/1.74 0.70/1.74 24] ~L1(/\x.~AP1(F, x)) >= F because [25], by (Star) 0.70/1.74 25] ~L1*(/\x.~AP1(F, x)) >= F because [26], by (Select) 0.70/1.74 26] /\x.~AP1(F, x) >= F because [27], by (Eta)[Kop13:2] 0.70/1.74 27] F >= F by (Meta) 0.70/1.74 0.70/1.74 28] ~L1(/\x.@_{o -> o}(op(F, G), x)) > op(F, G) because [29], by definition 0.70/1.74 29] ~L1*(/\x.@_{o -> o}(op(F, G), x)) >= op(F, G) because ~L1 > op, [30] and [35], by (Copy) 0.70/1.74 30] ~L1*(/\x.@_{o -> o}(op(F, G), x)) >= F because [31], by (Select) 0.70/1.74 31] /\x.@_{o -> o}(op(F, G), x) >= F because [32], by (Eta)[Kop13:2] 0.70/1.74 32] op(F, G) >= F because [33], by (Star) 0.70/1.74 33] op*(F, G) >= F because [34], by (Select) 0.70/1.74 34] F >= F by (Meta) 0.70/1.74 35] ~L1*(/\x.@_{o -> o}(op(F, G), x)) >= G because [36], by (Select) 0.70/1.74 36] /\x.@_{o -> o}(op(F, G), x) >= G because [37], by (Eta)[Kop13:2] 0.70/1.74 37] op(F, G) >= G because [38], by (Star) 0.70/1.74 38] op*(F, G) >= G because [39], by (Select) 0.70/1.74 39] G >= G by (Meta) 0.70/1.74 0.70/1.74 40] ~L1(F) >= F because [41], by (Star) 0.70/1.74 41] ~L1*(F) >= F because [42], by (Select) 0.70/1.74 42] F >= F by (Meta) 0.70/1.74 0.70/1.74 We can thus remove the following rules: 0.70/1.74 0.70/1.74 pow(F, s(X)) => op(F, pow(F, X)) 0.70/1.74 op(F, G) X => ~AP1(F, ~AP1(G, X)) 0.70/1.74 ~L1(/\x.op(F, G) x) => op(F, G) 0.70/1.74 0.70/1.74 We use rule removal, following [Kop12, Theorem 2.23]. 0.70/1.74 0.70/1.74 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.70/1.74 0.70/1.74 map(F, nil) >? nil 0.70/1.74 ~L1(/\x.~AP1(F, x)) >? F 0.70/1.74 ~L1(F) >? F 0.70/1.74 0.70/1.74 We orient these requirements with a polynomial interpretation in the natural numbers. 0.70/1.74 0.70/1.74 The following interpretation satisfies the requirements: 0.70/1.74 0.70/1.74 map = \G0y1.3 + 3y1 + G0(0) 0.70/1.74 nil = 0 0.70/1.74 ~AP1 = \G0y1.3 + y1 + G0(y1) 0.70/1.74 ~L1 = \G0y1.3 + G0(y1) 0.70/1.74 0.70/1.74 Using this interpretation, the requirements translate to: 0.70/1.74 0.70/1.74 [[map(_F0, nil)]] = 3 + F0(0) > 0 = [[nil]] 0.70/1.74 [[~L1(/\x.~AP1(_F0, x))]] = \y0.6 + y0 + F0(y0) > \y0.F0(y0) = [[_F0]] 0.70/1.74 [[~L1(_F0)]] = \y0.3 + F0(y0) > \y0.F0(y0) = [[_F0]] 0.70/1.74 0.70/1.74 We can thus remove the following rules: 0.70/1.74 0.70/1.74 map(F, nil) => nil 0.70/1.74 ~L1(/\x.~AP1(F, x)) => F 0.70/1.74 ~L1(F) => F 0.70/1.74 0.70/1.74 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.70/1.74 0.70/1.74 0.70/1.74 +++ Citations +++ 0.70/1.74 0.70/1.74 [Kop11] C. Kop. Simplifying Algebraic Functional Systems. In Proceedings of CAI 2011, volume 6742 of LNCS. 201--215, Springer, 2011. 0.70/1.74 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 0.70/1.74 [Kop13:2] C. Kop. StarHorpo with an Eta-Rule. Unpublished manuscript, http://cl-informatik.uibk.ac.at/users/kop/etahorpo.pdf, 2013. 0.70/1.74 EOF