/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 : [] --> b cons : [b * a] --> a curry : [b -> b -> b * b] --> b -> b double : [] --> a -> a inc : [] --> a -> a map : [b -> b] --> a -> a nil : [] --> a plus : [] --> b -> b -> b s : [b] --> b times : [] --> b -> b -> b Rules: plus 0 x => x plus s(x) y => s(plus x y) times 0 x => 0 times s(x) y => plus (times x y) y curry(f, x) y => f x y map(f) nil => nil map(f) cons(x, y) => cons(f x, map(f) y) inc => map(curry(plus, s(0))) double => map(curry(times, s(s(0)))) 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]): plus 0 X >? X plus s(X) Y >? s(plus X Y) times 0 X >? 0 times s(X) Y >? plus (times X Y) Y curry(F, X) Y >? F X Y map(F) nil >? nil map(F) cons(X, Y) >? cons(F X, map(F) Y) inc >? map(curry(plus, s(0))) double >? map(curry(times, s(s(0)))) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[nil]] = _|_ We choose Lex = {} and Mul = {@_{o -> o -> o}, @_{o -> o}, cons, curry, double, inc, map, plus, s, times}, and the following precedence: double > times > inc > map > curry > @_{o -> o -> o} > plus > @_{o -> o} > cons > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: @_{o -> o}(@_{o -> o -> o}(plus, _|_), X) > X @_{o -> o}(@_{o -> o -> o}(plus, s(X)), Y) > s(@_{o -> o}(@_{o -> o -> o}(plus, X), Y)) @_{o -> o}(@_{o -> o -> o}(times, _|_), X) >= _|_ @_{o -> o}(@_{o -> o -> o}(times, s(X)), Y) >= @_{o -> o}(@_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)), Y) @_{o -> o}(curry(F, X), Y) > @_{o -> o}(@_{o -> o -> o}(F, X), Y) @_{o -> o}(map(F), _|_) >= _|_ @_{o -> o}(map(F), cons(X, Y)) >= cons(@_{o -> o}(F, X), @_{o -> o}(map(F), Y)) inc > map(curry(plus, s(_|_))) double > map(curry(times, s(s(_|_)))) With these choices, we have: 1] @_{o -> o}(@_{o -> o -> o}(plus, _|_), X) > X because [2], by definition 2] @_{o -> o}*(@_{o -> o -> o}(plus, _|_), X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] @_{o -> o}(@_{o -> o -> o}(plus, s(X)), Y) > s(@_{o -> o}(@_{o -> o -> o}(plus, X), Y)) because [5], by definition 5] @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y) >= s(@_{o -> o}(@_{o -> o -> o}(plus, X), Y)) because [6], by (Select) 6] @_{o -> o -> o}(plus, s(X)) @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y) >= s(@_{o -> o}(@_{o -> o -> o}(plus, X), Y)) because [7] 7] @_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y)) >= s(@_{o -> o}(@_{o -> o -> o}(plus, X), Y)) because [8], by (Select) 8] @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y) >= s(@_{o -> o}(@_{o -> o -> o}(plus, X), Y)) because [9], by (Select) 9] @_{o -> o -> o}(plus, s(X)) @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y) >= s(@_{o -> o}(@_{o -> o -> o}(plus, X), Y)) because [10] 10] @_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y)) >= s(@_{o -> o}(@_{o -> o -> o}(plus, X), Y)) because [11], by (Select) 11] plus @_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y)) @_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y)) >= s(@_{o -> o}(@_{o -> o -> o}(plus, X), Y)) because [12] 12] plus*(@_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y)), @_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y))) >= s(@_{o -> o}(@_{o -> o -> o}(plus, X), Y)) because plus > s and [13], by (Copy) 13] plus*(@_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y)), @_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y))) >= @_{o -> o}(@_{o -> o -> o}(plus, X), Y) because [14], by (Select) 14] @_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y)) >= @_{o -> o}(@_{o -> o -> o}(plus, X), Y) because @_{o -> o -> o} > @_{o -> o}, [15] and [20], by (Copy) 15] @_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y)) >= @_{o -> o -> o}(plus, X) because @_{o -> o -> o} in Mul, [16] and [17], by (Stat) 16] plus >= plus by (Fun) 17] s(X) > X because [18], by definition 18] s*(X) >= X because [19], by (Select) 19] X >= X by (Meta) 20] @_{o -> o -> o}*(plus, s(X), @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y)) >= Y because [21], by (Select) 21] @_{o -> o}*(@_{o -> o -> o}(plus, s(X)), Y) >= Y because [22], by (Select) 22] Y >= Y by (Meta) 23] @_{o -> o}(@_{o -> o -> o}(times, _|_), X) >= _|_ by (Bot) 24] @_{o -> o}(@_{o -> o -> o}(times, s(X)), Y) >= @_{o -> o}(@_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)), Y) because [25], by (Star) 25] @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y) >= @_{o -> o}(@_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)), Y) because [26], by (Select) 26] @_{o -> o -> o}(times, s(X)) @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y) >= @_{o -> o}(@_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)), Y) because [27] 27] @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= @_{o -> o}(@_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)), Y) because [28], by (Select) 28] @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y) >= @_{o -> o}(@_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)), Y) because [29], by (Select) 29] @_{o -> o -> o}(times, s(X)) @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y) >= @_{o -> o}(@_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)), Y) because [30] 30] @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= @_{o -> o}(@_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)), Y) because [31], by (Select) 31] times @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= @_{o -> o}(@_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)), Y) because [32] 32] times*(@_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)), @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y))) >= @_{o -> o}(@_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)), Y) because times > @_{o -> o}, [33] and [54], by (Copy) 33] times*(@_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)), @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y))) >= @_{o -> o -> o}(plus, @_{o -> o}(@_{o -> o -> o}(times, X), Y)) because times > @_{o -> o -> o}, [34] and [35], by (Copy) 34] times*(@_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)), @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y))) >= plus because times > plus, by (Copy) 35] times*(@_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)), @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y))) >= @_{o -> o}(@_{o -> o -> o}(times, X), Y) because [36], by (Select) 36] @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= @_{o -> o}(@_{o -> o -> o}(times, X), Y) because @_{o -> o -> o} > @_{o -> o}, [37] and [42], by (Copy) 37] @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= @_{o -> o -> o}(times, X) because @_{o -> o -> o} in Mul, [38] and [39], by (Stat) 38] times >= times by (Fun) 39] s(X) > X because [40], by definition 40] s*(X) >= X because [41], by (Select) 41] X >= X by (Meta) 42] @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= Y because [43], by (Select) 43] times @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= Y because [44] 44] times*(@_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)), @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y))) >= Y because [45], by (Select) 45] @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= Y because [46], by (Select) 46] times @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= Y because [47] 47] times*(@_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)), @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y))) >= Y because [48], by (Select) 48] @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= Y because [49], by (Select) 49] times @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= Y because [50] 50] times*(@_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)), @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y))) >= Y because [51], by (Select) 51] @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)) >= Y because [52], by (Select) 52] @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y) >= Y because [53], by (Select) 53] Y >= Y by (Meta) 54] times*(@_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y)), @_{o -> o -> o}*(times, s(X), @_{o -> o}*(@_{o -> o -> o}(times, s(X)), Y))) >= Y because [42], by (Select) 55] @_{o -> o}(curry(F, X), Y) > @_{o -> o}(@_{o -> o -> o}(F, X), Y) because [56], by definition 56] @_{o -> o}*(curry(F, X), Y) >= @_{o -> o}(@_{o -> o -> o}(F, X), Y) because [57], by (Select) 57] curry(F, X) @_{o -> o}*(curry(F, X), Y) >= @_{o -> o}(@_{o -> o -> o}(F, X), Y) because [58] 58] curry*(F, X, @_{o -> o}*(curry(F, X), Y)) >= @_{o -> o}(@_{o -> o -> o}(F, X), Y) because curry > @_{o -> o}, [59] and [64], by (Copy) 59] curry*(F, X, @_{o -> o}*(curry(F, X), Y)) >= @_{o -> o -> o}(F, X) because curry > @_{o -> o -> o}, [60] and [62], by (Copy) 60] curry*(F, X, @_{o -> o}*(curry(F, X), Y)) >= F because [61], by (Select) 61] F >= F by (Meta) 62] curry*(F, X, @_{o -> o}*(curry(F, X), Y)) >= X because [63], by (Select) 63] X >= X by (Meta) 64] curry*(F, X, @_{o -> o}*(curry(F, X), Y)) >= Y because [65], by (Select) 65] @_{o -> o}*(curry(F, X), Y) >= Y because [66], by (Select) 66] curry(F, X) @_{o -> o}*(curry(F, X), Y) >= Y because [67] 67] curry*(F, X, @_{o -> o}*(curry(F, X), Y)) >= Y because [68], by (Select) 68] @_{o -> o}*(curry(F, X), Y) >= Y because [69], by (Select) 69] Y >= Y by (Meta) 70] @_{o -> o}(map(F), _|_) >= _|_ by (Bot) 71] @_{o -> o}(map(F), cons(X, Y)) >= cons(@_{o -> o}(F, X), @_{o -> o}(map(F), Y)) because [72], by (Star) 72] @_{o -> o}*(map(F), cons(X, Y)) >= cons(@_{o -> o}(F, X), @_{o -> o}(map(F), Y)) because [73], by (Select) 73] map(F) @_{o -> o}*(map(F), cons(X, Y)) >= cons(@_{o -> o}(F, X), @_{o -> o}(map(F), Y)) because [74] 74] map*(F, @_{o -> o}*(map(F), cons(X, Y))) >= cons(@_{o -> o}(F, X), @_{o -> o}(map(F), Y)) because map > cons, [75] and [83], by (Copy) 75] map*(F, @_{o -> o}*(map(F), cons(X, Y))) >= @_{o -> o}(F, X) because map > @_{o -> o}, [76] and [78], by (Copy) 76] map*(F, @_{o -> o}*(map(F), cons(X, Y))) >= F because [77], by (Select) 77] F >= F by (Meta) 78] map*(F, @_{o -> o}*(map(F), cons(X, Y))) >= X because [79], by (Select) 79] @_{o -> o}*(map(F), cons(X, Y)) >= X because [80], by (Select) 80] cons(X, Y) >= X because [81], by (Star) 81] cons*(X, Y) >= X because [82], by (Select) 82] X >= X by (Meta) 83] map*(F, @_{o -> o}*(map(F), cons(X, Y))) >= @_{o -> o}(map(F), Y) because [84], by (Select) 84] @_{o -> o}*(map(F), cons(X, Y)) >= @_{o -> o}(map(F), Y) because @_{o -> o} in Mul, [85] and [87], by (Stat) 85] map(F) >= map(F) because map in Mul and [86], by (Fun) 86] F >= F by (Meta) 87] cons(X, Y) > Y because [88], by definition 88] cons*(X, Y) >= Y because [89], by (Select) 89] Y >= Y by (Meta) 90] inc > map(curry(plus, s(_|_))) because [91], by definition 91] inc* >= map(curry(plus, s(_|_))) because inc > map and [92], by (Copy) 92] inc* >= curry(plus, s(_|_)) because inc > curry, [93] and [94], by (Copy) 93] inc* >= plus because inc > plus, by (Copy) 94] inc* >= s(_|_) because inc > s and [95], by (Copy) 95] inc* >= _|_ by (Bot) 96] double > map(curry(times, s(s(_|_)))) because [97], by definition 97] double* >= map(curry(times, s(s(_|_)))) because double > map and [98], by (Copy) 98] double* >= curry(times, s(s(_|_))) because double > curry, [99] and [100], by (Copy) 99] double* >= times because double > times, by (Copy) 100] double* >= s(s(_|_)) because double > s and [101], by (Copy) 101] double* >= s(_|_) because double > s and [102], by (Copy) 102] double* >= _|_ by (Bot) We can thus remove the following rules: plus 0 X => X plus s(X) Y => s(plus X Y) curry(F, X) Y => F X Y inc => map(curry(plus, s(0))) double => map(curry(times, s(s(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]): times(0, X) >? 0 times(s(X), Y) >? plus(times(X, Y), Y) map(F, nil) >? nil map(F, cons(X, Y)) >? cons(F X, map(F, Y)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[nil]] = _|_ We choose Lex = {} and Mul = {@_{o -> o}, cons, map, plus, s, times}, and the following precedence: map > cons > times > plus > @_{o -> o} > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: times(_|_, X) > _|_ times(s(X), Y) > plus(times(X, Y), Y) map(F, _|_) >= _|_ map(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) With these choices, we have: 1] times(_|_, X) > _|_ because [2], by definition 2] times*(_|_, X) >= _|_ by (Bot) 3] times(s(X), Y) > plus(times(X, Y), Y) because [4], by definition 4] times*(s(X), Y) >= plus(times(X, Y), Y) because times > plus, [5] and [10], by (Copy) 5] times*(s(X), Y) >= times(X, Y) because times in Mul, [6] and [9], by (Stat) 6] s(X) > X because [7], by definition 7] s*(X) >= X because [8], by (Select) 8] X >= X by (Meta) 9] Y >= Y by (Meta) 10] times*(s(X), Y) >= Y because [9], by (Select) 11] map(F, _|_) >= _|_ by (Bot) 12] map(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) because [13], by (Star) 13] map*(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) because map > cons, [14] and [21], by (Copy) 14] map*(F, cons(X, Y)) >= @_{o -> o}(F, X) because map > @_{o -> o}, [15] and [17], by (Copy) 15] map*(F, cons(X, Y)) >= F because [16], by (Select) 16] F >= F by (Meta) 17] map*(F, cons(X, Y)) >= 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] map*(F, cons(X, Y)) >= map(F, Y) because map in Mul, [22] and [23], by (Stat) 22] F >= F by (Meta) 23] cons(X, Y) > Y because [24], by definition 24] cons*(X, Y) >= Y because [25], by (Select) 25] Y >= Y by (Meta) We can thus remove the following rules: times(0, X) => 0 times(s(X), Y) => plus(times(X, Y), Y) 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(F X, map(F, Y)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: cons = \y0y1.3 + y0 + y1 map = \G0y1.3 + 3y1 + G0(y1) + 3y1G0(y1) nil = 2 Using this interpretation, the requirements translate to: [[map(_F0, nil)]] = 9 + 7F0(2) > 2 = [[nil]] [[map(_F0, cons(_x1, _x2))]] = 12 + 3x1 + 3x2 + 3x1F0(3 + x1 + x2) + 3x2F0(3 + x1 + x2) + 10F0(3 + x1 + x2) > 6 + x1 + 3x2 + F0(x1) + F0(x2) + 3x2F0(x2) = [[cons(_F0 _x1, map(_F0, _x2))]] We can thus remove the following rules: map(F, nil) => nil map(F, cons(X, Y)) => cons(F X, map(F, Y)) 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.