/export/starexec/sandbox2/solver/bin/starexec_run_HigherOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. Alphabet: 0 : [] --> nat cons : [nat * list] --> list map : [nat -> nat * list] --> list nil : [] --> list op : [nat -> nat * nat -> nat] --> nat -> nat pow : [nat -> nat * nat] --> nat -> nat s : [nat] --> nat Rules: map(f, nil) => nil map(f, cons(x, y)) => cons(f x, map(f, y)) pow(f, 0) => /\x.x pow(f, s(x)) => op(f, pow(f, x)) op(f, g) x => f (g x) /\x.f x => f 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. 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: Alphabet: 0 : [] --> nat cons : [nat * list] --> list map : [nat -> nat * list] --> list nil : [] --> list op : [nat -> nat * nat -> nat] --> nat -> nat pow : [nat -> nat * nat] --> nat -> nat s : [nat] --> nat ~AP1 : [nat -> nat * nat] --> nat ~L1 : [nat -> nat] --> nat -> nat Rules: map(F, nil) => nil map(F, cons(X, Y)) => cons(~AP1(F, X), map(F, Y)) pow(F, 0) => ~L1(/\x.x) pow(F, s(X)) => op(F, pow(F, X)) op(F, G) X => ~AP1(F, ~AP1(G, X)) ~L1(/\x.~AP1(F, x)) => F ~L1(/\x.op(F, G) x) => op(F, G) ~L1(/\x.pow(F, X) x) => pow(F, X) ~AP1(F, X) => F X ~L1(F) => F We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): map(F, nil) >? nil map(F, cons(X, Y)) >? cons(~AP1(F, X), map(F, Y)) pow(F, 0) >? ~L1(/\x.x) pow(F, s(X)) >? op(F, pow(F, X)) op(F, G) X >? ~AP1(F, ~AP1(G, X)) ~L1(/\x.~AP1(F, x)) >? F ~L1(/\x.op(F, G) x) >? op(F, G) ~L1(/\x.pow(F, X) x) >? pow(F, X) ~AP1(F, X) >? F X ~L1(F) >? F about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[nil]] = _|_ We choose Lex = {} and Mul = {0, @_{o -> o}, cons, map, op, pow, s, ~AP1, ~L1}, and the following precedence: 0 > map > cons > pow > s > ~L1 > op > ~AP1 > @_{o -> o} Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: map(F, _|_) >= _|_ map(F, cons(X, Y)) >= cons(~AP1(F, X), map(F, Y)) pow(F, 0) >= ~L1(/\x.x) pow(F, s(X)) >= op(F, pow(F, X)) @_{o -> o}(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) ~L1(/\x.~AP1(F, x)) >= F ~L1(/\x.@_{o -> o}(op(F, G), x)) > op(F, G) ~L1(/\x.@_{o -> o}(pow(F, X), x)) >= pow(F, X) ~AP1(F, X) > @_{o -> o}(F, X) ~L1(F) >= F With these choices, we have: 1] map(F, _|_) >= _|_ by (Bot) 2] map(F, cons(X, Y)) >= cons(~AP1(F, X), map(F, Y)) because [3], by (Star) 3] map*(F, cons(X, Y)) >= cons(~AP1(F, X), map(F, Y)) because map > cons, [4] and [11], by (Copy) 4] map*(F, cons(X, Y)) >= ~AP1(F, X) because map > ~AP1, [5] and [7], by (Copy) 5] map*(F, cons(X, Y)) >= F because [6], by (Select) 6] F >= F by (Meta) 7] map*(F, cons(X, Y)) >= X because [8], by (Select) 8] cons(X, Y) >= X because [9], by (Star) 9] cons*(X, Y) >= X because [10], by (Select) 10] X >= X by (Meta) 11] map*(F, cons(X, Y)) >= map(F, Y) because map in Mul, [12] and [13], by (Stat) 12] F >= F by (Meta) 13] cons(X, Y) > Y because [14], by definition 14] cons*(X, Y) >= Y because [15], by (Select) 15] Y >= Y by (Meta) 16] pow(F, 0) >= ~L1(/\x.x) because [17], by (Star) 17] pow*(F, 0) >= ~L1(/\x.x) because pow > ~L1 and [18], by (Copy) 18] pow*(F, 0) >= /\y.y because [19], by (F-Abs) 19] pow*(F, 0, x) >= x because [20], by (Select) 20] x >= x by (Var) 21] pow(F, s(X)) >= op(F, pow(F, X)) because [22], by (Star) 22] pow*(F, s(X)) >= op(F, pow(F, X)) because pow > op, [23] and [25], by (Copy) 23] pow*(F, s(X)) >= F because [24], by (Select) 24] F >= F by (Meta) 25] pow*(F, s(X)) >= pow(F, X) because pow in Mul, [26] and [27], by (Stat) 26] F >= F by (Meta) 27] s(X) > X because [28], by definition 28] s*(X) >= X because [29], by (Select) 29] X >= X by (Meta) 30] @_{o -> o}(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) because [31], by (Star) 31] @_{o -> o}*(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) because [32], by (Select) 32] op(F, G) @_{o -> o}*(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) because [33] 33] op*(F, G, @_{o -> o}*(op(F, G), X)) >= ~AP1(F, ~AP1(G, X)) because op > ~AP1, [34] and [36], by (Copy) 34] op*(F, G, @_{o -> o}*(op(F, G), X)) >= F because [35], by (Select) 35] F >= F by (Meta) 36] op*(F, G, @_{o -> o}*(op(F, G), X)) >= ~AP1(G, X) because op > ~AP1, [37] and [39], by (Copy) 37] op*(F, G, @_{o -> o}*(op(F, G), X)) >= G because [38], by (Select) 38] G >= G by (Meta) 39] op*(F, G, @_{o -> o}*(op(F, G), X)) >= X because [40], by (Select) 40] @_{o -> o}*(op(F, G), X) >= X because [41], by (Select) 41] X >= X by (Meta) 42] ~L1(/\x.~AP1(F, x)) >= F because [43], by (Star) 43] ~L1*(/\x.~AP1(F, x)) >= F because [44], by (Select) 44] /\x.~AP1(F, x) >= F because [45], by (Eta)[Kop13:2] 45] F >= F by (Meta) 46] ~L1(/\x.@_{o -> o}(op(F, G), x)) > op(F, G) because [47], by definition 47] ~L1*(/\x.@_{o -> o}(op(F, G), x)) >= op(F, G) because ~L1 > op, [48] and [53], by (Copy) 48] ~L1*(/\x.@_{o -> o}(op(F, G), x)) >= F because [49], by (Select) 49] /\x.@_{o -> o}(op(F, G), x) >= F because [50], by (Eta)[Kop13:2] 50] op(F, G) >= F because [51], by (Star) 51] op*(F, G) >= F because [52], by (Select) 52] F >= F by (Meta) 53] ~L1*(/\x.@_{o -> o}(op(F, G), x)) >= G because [54], by (Select) 54] /\x.@_{o -> o}(op(F, G), x) >= G because [55], by (Eta)[Kop13:2] 55] op(F, G) >= G because [56], by (Star) 56] op*(F, G) >= G because [57], by (Select) 57] G >= G by (Meta) 58] ~L1(/\x.@_{o -> o}(pow(F, X), x)) >= pow(F, X) because [59], by (Star) 59] ~L1*(/\x.@_{o -> o}(pow(F, X), x)) >= pow(F, X) because [60], by (Select) 60] /\x.@_{o -> o}(pow(F, X), x) >= pow(F, X) because [61], by (Eta)[Kop13:2] 61] pow(F, X) >= pow(F, X) because pow in Mul, [62] and [63], by (Fun) 62] F >= F by (Meta) 63] X >= X by (Meta) 64] ~AP1(F, X) > @_{o -> o}(F, X) because [65], by definition 65] ~AP1*(F, X) >= @_{o -> o}(F, X) because ~AP1 > @_{o -> o}, [66] and [68], by (Copy) 66] ~AP1*(F, X) >= F because [67], by (Select) 67] F >= F by (Meta) 68] ~AP1*(F, X) >= X because [69], by (Select) 69] X >= X by (Meta) 70] ~L1(F) >= F because [71], by (Star) 71] ~L1*(F) >= F because [72], by (Select) 72] F >= F by (Meta) We can thus remove the following rules: ~L1(/\x.op(F, G) x) => op(F, G) ~AP1(F, X) => F 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]): map(F, nil) >? nil map(F, cons(X, Y)) >? cons(~AP1(F, X), map(F, Y)) pow(F, 0) >? ~L1(/\x.x) pow(F, s(X)) >? op(F, pow(F, X)) op(F, G) X >? ~AP1(F, ~AP1(G, X)) ~L1(/\x.~AP1(F, x)) >? F ~L1(/\x.pow(F, X) x) >? pow(F, X) ~L1(F) >? F about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[nil]] = _|_ We choose Lex = {} and Mul = {0, @_{o -> o}, cons, map, op, pow, s, ~AP1, ~L1}, and the following precedence: 0 > map > cons > pow > s > op > @_{o -> o} > ~AP1 > ~L1 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: map(F, _|_) >= _|_ map(F, cons(X, Y)) > cons(~AP1(F, X), map(F, Y)) pow(F, 0) >= ~L1(/\x.x) pow(F, s(X)) > op(F, pow(F, X)) @_{o -> o}(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) ~L1(/\x.~AP1(F, x)) > F ~L1(/\x.@_{o -> o}(pow(F, X), x)) > pow(F, X) ~L1(F) >= F With these choices, we have: 1] map(F, _|_) >= _|_ by (Bot) 2] map(F, cons(X, Y)) > cons(~AP1(F, X), map(F, Y)) because [3], by definition 3] map*(F, cons(X, Y)) >= cons(~AP1(F, X), map(F, Y)) because map > cons, [4] and [11], by (Copy) 4] map*(F, cons(X, Y)) >= ~AP1(F, X) because map > ~AP1, [5] and [7], by (Copy) 5] map*(F, cons(X, Y)) >= F because [6], by (Select) 6] F >= F by (Meta) 7] map*(F, cons(X, Y)) >= X because [8], by (Select) 8] cons(X, Y) >= X because [9], by (Star) 9] cons*(X, Y) >= X because [10], by (Select) 10] X >= X by (Meta) 11] map*(F, cons(X, Y)) >= map(F, Y) because map in Mul, [12] and [13], by (Stat) 12] F >= F by (Meta) 13] cons(X, Y) > Y because [14], by definition 14] cons*(X, Y) >= Y because [15], by (Select) 15] Y >= Y by (Meta) 16] pow(F, 0) >= ~L1(/\x.x) because [17], by (Star) 17] pow*(F, 0) >= ~L1(/\x.x) because pow > ~L1 and [18], by (Copy) 18] pow*(F, 0) >= /\y.y because [19], by (F-Abs) 19] pow*(F, 0, x) >= x because [20], by (Select) 20] x >= x by (Var) 21] pow(F, s(X)) > op(F, pow(F, X)) because [22], by definition 22] pow*(F, s(X)) >= op(F, pow(F, X)) because pow > op, [23] and [25], by (Copy) 23] pow*(F, s(X)) >= F because [24], by (Select) 24] F >= F by (Meta) 25] pow*(F, s(X)) >= pow(F, X) because pow in Mul, [26] and [27], by (Stat) 26] F >= F by (Meta) 27] s(X) > X because [28], by definition 28] s*(X) >= X because [29], by (Select) 29] X >= X by (Meta) 30] @_{o -> o}(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) because [31], by (Star) 31] @_{o -> o}*(op(F, G), X) >= ~AP1(F, ~AP1(G, X)) because @_{o -> o} > ~AP1, [32] and [36], by (Copy) 32] @_{o -> o}*(op(F, G), X) >= F because [33], by (Select) 33] op(F, G) >= F because [34], by (Star) 34] op*(F, G) >= F because [35], by (Select) 35] F >= F by (Meta) 36] @_{o -> o}*(op(F, G), X) >= ~AP1(G, X) because [37], by (Select) 37] op(F, G) @_{o -> o}*(op(F, G), X) >= ~AP1(G, X) because [38] 38] op*(F, G, @_{o -> o}*(op(F, G), X)) >= ~AP1(G, X) because op > ~AP1, [39] and [41], by (Copy) 39] op*(F, G, @_{o -> o}*(op(F, G), X)) >= G because [40], by (Select) 40] G >= G by (Meta) 41] op*(F, G, @_{o -> o}*(op(F, G), X)) >= X because [42], by (Select) 42] @_{o -> o}*(op(F, G), X) >= X because [43], by (Select) 43] X >= X by (Meta) 44] ~L1(/\x.~AP1(F, x)) > F because [45], by definition 45] ~L1*(/\x.~AP1(F, x)) >= F because [46], by (Select) 46] /\x.~AP1(F, x) >= F because [47], by (Eta)[Kop13:2] 47] F >= F by (Meta) 48] ~L1(/\x.@_{o -> o}(pow(F, X), x)) > pow(F, X) because [49], by definition 49] ~L1*(/\x.@_{o -> o}(pow(F, X), x)) >= pow(F, X) because [50], by (Select) 50] /\x.@_{o -> o}(pow(F, X), x) >= pow(F, X) because [51], by (Eta)[Kop13:2] 51] pow(F, X) >= pow(F, X) because pow in Mul, [52] and [53], by (Fun) 52] F >= F by (Meta) 53] X >= X by (Meta) 54] ~L1(F) >= F because [55], by (Star) 55] ~L1*(F) >= F because [56], by (Select) 56] F >= F by (Meta) We can thus remove the following rules: map(F, cons(X, Y)) => cons(~AP1(F, X), map(F, Y)) pow(F, s(X)) => op(F, pow(F, X)) ~L1(/\x.~AP1(F, x)) => F ~L1(/\x.pow(F, X) x) => pow(F, 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]): map(F, nil) >? nil pow(F, 0) >? ~L1(/\x.x) op(F, G, X) >? ~AP1(F, ~AP1(G, X)) ~L1(F) >? F We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 3 map = \G0y1.3 + 3y1 + G0(0) nil = 0 op = \G0G1y2.3 + 3y2 + 2G0(y2) + 3G0(0) + 3G1(0) + 3G1(y2) pow = \G0y1y2.3 + 3y1 + 3y2 + G0(0) ~AP1 = \G0y1.y1 + 2G0(0) ~L1 = \G0y1.G0(y1) Using this interpretation, the requirements translate to: [[map(_F0, nil)]] = 3 + F0(0) > 0 = [[nil]] [[pow(_F0, 0)]] = \y0.12 + 3y0 + F0(0) > \y0.y0 = [[~L1(/\x.x)]] [[op(_F0, _F1, _x2)]] = 3 + 3x2 + 2F0(x2) + 3F0(0) + 3F1(0) + 3F1(x2) > x2 + 2F0(0) + 2F1(0) = [[~AP1(_F0, ~AP1(_F1, _x2))]] [[~L1(_F0)]] = \y0.F0(y0) >= \y0.F0(y0) = [[_F0]] We can thus remove the following rules: map(F, nil) => nil pow(F, 0) => ~L1(/\x.x) op(F, G, X) => ~AP1(F, ~AP1(G, 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]): ~L1(F) >? F We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: ~L1 = \G0y1.1 + G0(y1) Using this interpretation, the requirements translate to: [[~L1(_F0)]] = \y0.1 + F0(y0) > \y0.F0(y0) = [[_F0]] We can thus remove the following rules: ~L1(F) => F 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 +++ [Kop11] C. Kop. Simplifying Algebraic Functional Systems. In Proceedings of CAI 2011, volume 6742 of LNCS. 201--215, Springer, 2011. [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. [Kop13:2] C. Kop. StarHorpo with an Eta-Rule. Unpublished manuscript, http://cl-informatik.uibk.ac.at/users/kop/etahorpo.pdf, 2013.