30.71/30.74 YES 30.91/30.93 We consider the system theBenchmark. 30.91/30.93 30.91/30.93 Alphabet: 30.91/30.93 30.91/30.93 0 : [] --> c 30.91/30.93 add : [] --> a -> c -> c 30.91/30.93 cons : [a * b] --> b 30.91/30.93 fold : [a -> c -> c * c] --> b -> c 30.91/30.93 mul : [] --> a -> c -> c 30.91/30.93 nil : [] --> b 30.91/30.93 plus : [c * c] --> c 30.91/30.93 prod : [] --> b -> c 30.91/30.93 s : [c] --> c 30.91/30.93 sum : [] --> b -> c 30.91/30.93 times : [c * c] --> c 30.91/30.93 xap : [a -> c -> c * a] --> c -> c 30.91/30.93 yap : [c -> c * c] --> c 30.91/30.93 30.91/30.93 Rules: 30.91/30.93 30.91/30.93 fold(/\x./\y.yap(xap(f, x), y), z) nil => z 30.91/30.93 fold(/\x./\y.yap(xap(f, x), y), z) cons(u, v) => yap(xap(f, u), fold(/\w./\x'.yap(xap(f, w), x'), z) v) 30.91/30.93 plus(0, x) => x 30.91/30.93 plus(s(x), y) => s(plus(x, y)) 30.91/30.93 times(0, x) => 0 30.91/30.93 times(s(x), y) => plus(times(x, y), y) 30.91/30.93 sum => fold(/\x./\y.yap(xap(add, x), y), 0) 30.91/30.93 prod => fold(/\x./\y.yap(xap(mul, x), y), s(0)) 30.91/30.93 xap(f, x) => f x 30.91/30.93 yap(f, x) => f x 30.91/30.93 30.91/30.93 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 30.91/30.93 30.91/30.93 Symbol xap is an encoding for application that is only used in innocuous ways. We can simplify the program (without losing non-termination) by removing it. This gives: 30.91/30.93 30.91/30.93 Alphabet: 30.91/30.93 30.91/30.93 0 : [] --> c 30.91/30.93 add : [a] --> c -> c 30.91/30.93 cons : [a * b] --> b 30.91/30.93 fold : [a -> c -> c * c] --> b -> c 30.91/30.93 mul : [a] --> c -> c 30.91/30.93 nil : [] --> b 30.91/30.93 plus : [c * c] --> c 30.91/30.93 prod : [] --> b -> c 30.91/30.93 s : [c] --> c 30.91/30.93 sum : [] --> b -> c 30.91/30.93 times : [c * c] --> c 30.91/30.93 yap : [c -> c * c] --> c 30.91/30.93 30.91/30.93 Rules: 30.91/30.93 30.91/30.93 fold(/\x./\y.yap(F(x), y), X) nil => X 30.91/30.93 fold(/\x./\y.yap(F(x), y), X) cons(Y, Z) => yap(F(Y), fold(/\z./\u.yap(F(z), u), X) Z) 30.91/30.93 plus(0, X) => X 30.91/30.93 plus(s(X), Y) => s(plus(X, Y)) 30.91/30.93 times(0, X) => 0 30.91/30.93 times(s(X), Y) => plus(times(X, Y), Y) 30.91/30.93 sum => fold(/\x./\y.yap(add(x), y), 0) 30.91/30.93 prod => fold(/\x./\y.yap(mul(x), y), s(0)) 30.91/30.93 yap(F, X) => F X 30.91/30.93 30.91/30.93 We use rule removal, following [Kop12, Theorem 2.23]. 30.91/30.93 30.91/30.93 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 30.91/30.93 30.91/30.93 fold(/\x./\y.yap(F(x), y), X) nil >? X 30.91/30.93 fold(/\x./\y.yap(F(x), y), X) cons(Y, Z) >? yap(F(Y), fold(/\z./\u.yap(F(z), u), X) Z) 30.91/30.93 plus(0, X) >? X 30.91/30.93 plus(s(X), Y) >? s(plus(X, Y)) 30.91/30.93 times(0, X) >? 0 30.91/30.93 times(s(X), Y) >? plus(times(X, Y), Y) 30.91/30.93 sum >? fold(/\x./\y.yap(add(x), y), 0) 30.91/30.93 prod >? fold(/\x./\y.yap(mul(x), y), s(0)) 30.91/30.93 yap(F, X) >? F X 30.91/30.93 30.91/30.93 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 30.91/30.93 30.91/30.93 Argument functions: 30.91/30.93 30.91/30.93 [[0]] = _|_ 30.91/30.93 30.91/30.93 We choose Lex = {} and Mul = {@_{o -> o}, add, cons, fold, mul, nil, plus, prod, s, sum, times, yap}, and the following precedence: cons > prod > mul > nil > sum > add > fold > times > plus > s > yap > @_{o -> o} 30.91/30.93 30.91/30.93 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 30.91/30.93 30.91/30.93 @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), nil) >= X 30.91/30.93 @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) 30.91/30.93 plus(_|_, X) >= X 30.91/30.93 plus(s(X), Y) >= s(plus(X, Y)) 30.91/30.93 times(_|_, X) >= _|_ 30.91/30.93 times(s(X), Y) > plus(times(X, Y), Y) 30.91/30.93 sum >= fold(/\x./\y.yap(add(x), y), _|_) 30.91/30.93 prod >= fold(/\x./\y.yap(mul(x), y), s(_|_)) 30.91/30.93 yap(F, X) >= @_{o -> o}(F, X) 30.91/30.93 30.91/30.93 With these choices, we have: 30.91/30.93 30.91/30.93 1] @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), nil) >= X because [2], by (Star) 30.91/30.93 2] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), nil) >= X because [3], by (Select) 30.91/30.93 3] fold(/\x./\y.yap(F(x), y), X) @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), nil) >= X because [4] 30.91/30.93 4] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), nil)) >= X because [5], by (Select) 30.91/30.93 5] X >= X by (Meta) 30.91/30.93 30.91/30.93 6] @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [7], by (Star) 30.91/30.93 7] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [8], by (Select) 30.91/30.93 8] fold(/\x./\y.yap(F(x), y), X) @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [9] 30.91/30.93 9] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because fold > yap, [10] and [18], by (Copy) 30.91/30.93 10] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= F(Y) because [11], by (Select) 30.91/30.93 11] /\x.yap(F(fold*(/\y./\z.yap(F(y), z), X, @_{o -> o}*(fold(/\u./\v.yap(F(u), v), X), cons(Y, Z)))), x) >= F(Y) because [12], by (Eta)[Kop13:2] 30.91/30.93 12] F(fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)))) >= F(Y) because [13], by (Meta) 30.91/30.93 13] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= Y because [14], by (Select) 30.91/30.93 14] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= Y because [15], by (Select) 30.91/30.93 15] cons(Y, Z) >= Y because [16], by (Star) 30.91/30.93 16] cons*(Y, Z) >= Y because [17], by (Select) 30.91/30.93 17] Y >= Y by (Meta) 30.91/30.93 18] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z) because [19], by (Select) 30.91/30.93 19] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z) because @_{o -> o} in Mul, [20] and [28], by (Stat) 30.91/30.93 20] fold(/\x./\y.yap(F(x), y), X) >= fold(/\x./\y.yap(F(x), y), X) because fold in Mul, [21] and [27], by (Fun) 30.91/30.93 21] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [22], by (Abs) 30.91/30.93 22] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [23], by (Abs) 30.91/30.93 23] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [24] and [26], by (Fun) 30.91/30.93 24] F(y) >= F(y) because [25], by (Meta) 30.91/30.93 25] y >= y by (Var) 30.91/30.93 26] x >= x by (Var) 30.91/30.93 27] X >= X by (Meta) 30.91/30.93 28] cons(Y, Z) > Z because [29], by definition 30.91/30.93 29] cons*(Y, Z) >= Z because [30], by (Select) 30.91/30.93 30] Z >= Z by (Meta) 30.91/30.93 30.91/30.93 31] plus(_|_, X) >= X because [32], by (Star) 30.91/30.93 32] plus*(_|_, X) >= X because [33], by (Select) 30.91/30.93 33] X >= X by (Meta) 30.91/30.93 30.91/30.93 34] plus(s(X), Y) >= s(plus(X, Y)) because [35], by (Star) 30.91/30.93 35] plus*(s(X), Y) >= s(plus(X, Y)) because plus > s and [36], by (Copy) 30.91/30.93 36] plus*(s(X), Y) >= plus(X, Y) because plus in Mul, [37] and [40], by (Stat) 30.91/30.93 37] s(X) > X because [38], by definition 30.91/30.93 38] s*(X) >= X because [39], by (Select) 30.91/30.93 39] X >= X by (Meta) 30.91/30.93 40] Y >= Y by (Meta) 30.91/30.93 30.91/30.93 41] times(_|_, X) >= _|_ by (Bot) 30.91/30.93 30.91/30.93 42] times(s(X), Y) > plus(times(X, Y), Y) because [43], by definition 30.91/30.93 43] times*(s(X), Y) >= plus(times(X, Y), Y) because times > plus, [44] and [49], by (Copy) 30.91/30.93 44] times*(s(X), Y) >= times(X, Y) because times in Mul, [45] and [48], by (Stat) 30.91/30.93 45] s(X) > X because [46], by definition 30.91/30.93 46] s*(X) >= X because [47], by (Select) 30.91/30.93 47] X >= X by (Meta) 30.91/30.93 48] Y >= Y by (Meta) 30.91/30.93 49] times*(s(X), Y) >= Y because [48], by (Select) 30.91/30.93 30.91/30.93 50] sum >= fold(/\x./\y.yap(add(x), y), _|_) because [51], by (Star) 30.91/30.93 51] sum* >= fold(/\x./\y.yap(add(x), y), _|_) because sum > fold, [52] and [60], by (Copy) 30.91/30.93 52] sum* >= /\y./\z.yap(add(y), z) because [53], by (F-Abs) 30.91/30.93 53] sum*(x) >= /\z.yap(add(x), z) because [54], by (F-Abs) 30.91/30.93 54] sum*(x, y) >= yap(add(x), y) because sum > yap, [55] and [58], by (Copy) 30.91/30.93 55] sum*(x, y) >= add(x) because sum > add and [56], by (Copy) 30.91/30.93 56] sum*(x, y) >= x because [57], by (Select) 30.91/30.93 57] x >= x by (Var) 30.91/30.93 58] sum*(x, y) >= y because [59], by (Select) 30.91/30.93 59] y >= y by (Var) 30.91/30.93 60] sum* >= _|_ by (Bot) 30.91/30.93 30.91/30.93 61] prod >= fold(/\x./\y.yap(mul(x), y), s(_|_)) because [62], by (Star) 30.91/30.93 62] prod* >= fold(/\x./\y.yap(mul(x), y), s(_|_)) because prod > fold, [63] and [71], by (Copy) 30.91/30.93 63] prod* >= /\y./\z.yap(mul(y), z) because [64], by (F-Abs) 30.91/30.93 64] prod*(x) >= /\z.yap(mul(x), z) because [65], by (F-Abs) 30.91/30.93 65] prod*(x, y) >= yap(mul(x), y) because prod > yap, [66] and [69], by (Copy) 30.91/30.93 66] prod*(x, y) >= mul(x) because prod > mul and [67], by (Copy) 30.91/30.93 67] prod*(x, y) >= x because [68], by (Select) 30.91/30.93 68] x >= x by (Var) 30.91/30.93 69] prod*(x, y) >= y because [70], by (Select) 30.91/30.93 70] y >= y by (Var) 30.91/30.93 71] prod* >= s(_|_) because prod > s and [72], by (Copy) 30.91/30.93 72] prod* >= _|_ by (Bot) 30.91/30.93 30.91/30.93 73] yap(F, X) >= @_{o -> o}(F, X) because [74], by (Star) 30.91/30.93 74] yap*(F, X) >= @_{o -> o}(F, X) because yap > @_{o -> o}, [75] and [77], by (Copy) 30.91/30.93 75] yap*(F, X) >= F because [76], by (Select) 30.91/30.93 76] F >= F by (Meta) 30.91/30.93 77] yap*(F, X) >= X because [78], by (Select) 30.91/30.93 78] X >= X by (Meta) 30.91/30.93 30.91/30.93 We can thus remove the following rules: 30.91/30.93 30.91/30.93 times(s(X), Y) => plus(times(X, Y), Y) 30.91/30.93 30.91/30.93 We use rule removal, following [Kop12, Theorem 2.23]. 30.91/30.93 30.91/30.93 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 30.91/30.93 30.91/30.93 fold(/\x./\y.yap(F(x), y), X) nil >? X 30.91/30.93 fold(/\x./\y.yap(F(x), y), X) cons(Y, Z) >? yap(F(Y), fold(/\z./\u.yap(F(z), u), X) Z) 30.91/30.93 plus(0, X) >? X 30.91/30.93 plus(s(X), Y) >? s(plus(X, Y)) 30.91/30.93 times(0, X) >? 0 30.91/30.93 sum >? fold(/\x./\y.yap(add(x), y), 0) 30.91/30.93 prod >? fold(/\x./\y.yap(mul(x), y), s(0)) 30.91/30.93 yap(F, X) >? F X 30.91/30.93 30.91/30.93 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 30.91/30.93 30.91/30.93 Argument functions: 30.91/30.93 30.91/30.93 [[0]] = _|_ 30.91/30.93 [[s(x_1)]] = x_1 30.91/30.93 30.91/30.93 We choose Lex = {} and Mul = {@_{o -> o}, add, cons, fold, mul, nil, plus, prod, sum, times, yap}, and the following precedence: nil > prod > mul > plus > sum > add > times > cons > yap > fold > @_{o -> o} 30.91/30.93 30.91/30.93 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 30.91/30.93 30.91/30.93 @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), nil) >= X 30.91/30.93 @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) 30.91/30.93 plus(_|_, X) > X 30.91/30.93 plus(X, Y) >= plus(X, Y) 30.91/30.93 times(_|_, X) >= _|_ 30.91/30.93 sum >= fold(/\x./\y.yap(add(x), y), _|_) 30.91/30.93 prod >= fold(/\x./\y.yap(mul(x), y), _|_) 30.91/30.93 yap(F, X) > @_{o -> o}(F, X) 30.91/30.93 30.91/30.93 With these choices, we have: 30.91/30.93 30.91/30.93 1] @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), nil) >= X because [2], by (Star) 30.91/30.93 2] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), nil) >= X because [3], by (Select) 30.91/30.93 3] fold(/\x./\y.yap(F(x), y), X) @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), nil) >= X because [4] 30.91/30.93 4] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), nil)) >= X because [5], by (Select) 30.91/30.93 5] X >= X by (Meta) 30.91/30.93 30.91/30.93 6] @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [7], by (Star) 30.91/30.93 7] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [8], by (Select) 30.91/30.93 8] fold(/\x./\y.yap(F(x), y), X) @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [9] 30.91/30.93 9] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [10], by (Select) 30.91/30.93 10] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [11], by (Select) 30.91/30.93 11] fold(/\x./\y.yap(F(x), y), X) @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [12] 30.91/30.93 12] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [13], by (Select) 30.91/30.93 13] yap(F(fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)))), fold*(/\v./\w.yap(F(v), w), X, @_{o -> o}*(fold(/\x'./\y'.yap(F(x'), y'), X), cons(Y, Z)))) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because yap in Mul, [14] and [20], by (Fun) 30.91/30.93 14] F(fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)))) >= F(Y) because [15], by (Meta) 30.91/30.93 15] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= Y because [16], by (Select) 30.91/30.93 16] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= Y because [17], by (Select) 30.91/30.93 17] cons(Y, Z) >= Y because [18], by (Star) 30.91/30.93 18] cons*(Y, Z) >= Y because [19], by (Select) 30.91/30.93 19] Y >= Y by (Meta) 30.91/30.93 20] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z) because [21], by (Select) 30.91/30.93 21] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z) because @_{o -> o} in Mul, [22] and [30], by (Stat) 30.91/30.93 22] fold(/\x./\y.yap(F(x), y), X) >= fold(/\x./\y.yap(F(x), y), X) because fold in Mul, [23] and [29], by (Fun) 30.91/30.93 23] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [24], by (Abs) 30.91/30.93 24] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [25], by (Abs) 30.91/30.93 25] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [26] and [28], by (Fun) 30.91/30.93 26] F(y) >= F(y) because [27], by (Meta) 30.91/30.93 27] y >= y by (Var) 30.91/30.93 28] x >= x by (Var) 30.91/30.93 29] X >= X by (Meta) 30.91/30.93 30] cons(Y, Z) > Z because [31], by definition 30.91/30.93 31] cons*(Y, Z) >= Z because [32], by (Select) 30.91/30.93 32] Z >= Z by (Meta) 30.91/30.93 30.91/30.93 33] plus(_|_, X) > X because [34], by definition 30.91/30.93 34] plus*(_|_, X) >= X because [35], by (Select) 30.91/30.93 35] X >= X by (Meta) 30.91/30.93 30.91/30.93 36] plus(X, Y) >= plus(X, Y) because plus in Mul, [37] and [38], by (Fun) 30.91/30.93 37] X >= X by (Meta) 30.91/30.93 38] Y >= Y by (Meta) 30.91/30.93 30.91/30.93 39] times(_|_, X) >= _|_ by (Bot) 30.91/30.93 30.91/30.93 40] sum >= fold(/\x./\y.yap(add(x), y), _|_) because [41], by (Star) 30.91/30.93 41] sum* >= fold(/\x./\y.yap(add(x), y), _|_) because sum > fold, [42] and [50], by (Copy) 30.91/30.93 42] sum* >= /\y./\z.yap(add(y), z) because [43], by (F-Abs) 30.91/30.93 43] sum*(x) >= /\z.yap(add(x), z) because [44], by (F-Abs) 30.91/30.93 44] sum*(x, y) >= yap(add(x), y) because sum > yap, [45] and [48], by (Copy) 30.91/30.93 45] sum*(x, y) >= add(x) because sum > add and [46], by (Copy) 30.91/30.93 46] sum*(x, y) >= x because [47], by (Select) 30.91/30.93 47] x >= x by (Var) 30.91/30.93 48] sum*(x, y) >= y because [49], by (Select) 30.91/30.93 49] y >= y by (Var) 30.91/30.93 50] sum* >= _|_ by (Bot) 30.91/30.93 30.91/30.93 51] prod >= fold(/\x./\y.yap(mul(x), y), _|_) because [52], by (Star) 30.91/30.93 52] prod* >= fold(/\x./\y.yap(mul(x), y), _|_) because prod > fold, [53] and [61], by (Copy) 30.91/30.93 53] prod* >= /\y./\z.yap(mul(y), z) because [54], by (F-Abs) 30.91/30.93 54] prod*(x) >= /\z.yap(mul(x), z) because [55], by (F-Abs) 30.91/30.93 55] prod*(x, y) >= yap(mul(x), y) because prod > yap, [56] and [59], by (Copy) 30.91/30.93 56] prod*(x, y) >= mul(x) because prod > mul and [57], by (Copy) 30.91/30.93 57] prod*(x, y) >= x because [58], by (Select) 30.91/30.93 58] x >= x by (Var) 30.91/30.93 59] prod*(x, y) >= y because [60], by (Select) 30.91/30.93 60] y >= y by (Var) 30.91/30.93 61] prod* >= _|_ by (Bot) 30.91/30.93 30.91/30.93 62] yap(F, X) > @_{o -> o}(F, X) because [63], by definition 30.91/30.93 63] yap*(F, X) >= @_{o -> o}(F, X) because yap > @_{o -> o}, [64] and [66], by (Copy) 30.91/30.93 64] yap*(F, X) >= F because [65], by (Select) 30.91/30.93 65] F >= F by (Meta) 30.91/30.93 66] yap*(F, X) >= X because [67], by (Select) 30.91/30.93 67] X >= X by (Meta) 30.91/30.93 30.91/30.93 We can thus remove the following rules: 30.91/30.93 30.91/30.93 plus(0, X) => X 30.91/30.93 yap(F, X) => F X 30.91/30.93 30.91/30.93 We use rule removal, following [Kop12, Theorem 2.23]. 30.91/30.93 30.91/30.93 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 30.91/30.93 30.91/30.93 fold(/\x./\y.yap(F(x), y), X) nil >? X 30.91/30.93 fold(/\x./\y.yap(F(x), y), X) cons(Y, Z) >? yap(F(Y), fold(/\z./\u.yap(F(z), u), X) Z) 30.91/30.93 plus(s(X), Y) >? s(plus(X, Y)) 30.91/30.93 times(0, X) >? 0 30.91/30.93 sum >? fold(/\x./\y.yap(add(x), y), 0) 30.91/30.93 prod >? fold(/\x./\y.yap(mul(x), y), s(0)) 30.91/30.93 30.91/30.93 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 30.91/30.93 30.91/30.93 Argument functions: 30.91/30.93 30.91/30.93 [[0]] = _|_ 30.91/30.93 [[s(x_1)]] = x_1 30.91/30.93 30.91/30.93 We choose Lex = {} and Mul = {@_{o -> o}, add, cons, fold, mul, nil, plus, prod, sum, times, yap}, and the following precedence: nil > cons > plus > prod > mul > sum > add > times > yap > fold > @_{o -> o} 30.91/30.93 30.91/30.93 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 30.91/30.93 30.91/30.93 @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), nil) > X 30.91/30.93 @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) 30.91/30.93 plus(X, Y) >= plus(X, Y) 30.91/30.93 times(_|_, X) >= _|_ 30.91/30.93 sum >= fold(/\x./\y.yap(add(x), y), _|_) 30.91/30.93 prod > fold(/\x./\y.yap(mul(x), y), _|_) 30.91/30.93 30.91/30.93 With these choices, we have: 30.91/30.93 30.91/30.93 1] @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), nil) > X because [2], by definition 30.91/30.93 2] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), nil) >= X because [3], by (Select) 30.91/30.93 3] fold(/\x./\y.yap(F(x), y), X) @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), nil) >= X because [4] 30.91/30.93 4] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), nil)) >= X because [5], by (Select) 30.91/30.93 5] X >= X by (Meta) 30.91/30.93 30.91/30.93 6] @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [7], by (Star) 30.91/30.93 7] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [8], by (Select) 30.91/30.93 8] fold(/\x./\y.yap(F(x), y), X) @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [9] 30.91/30.93 9] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [10], by (Select) 30.91/30.93 10] yap(F(fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)))), fold*(/\v./\w.yap(F(v), w), X, @_{o -> o}*(fold(/\x'./\y'.yap(F(x'), y'), X), cons(Y, Z)))) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because yap in Mul, [11] and [17], by (Fun) 30.91/30.93 11] F(fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)))) >= F(Y) because [12], by (Meta) 30.91/30.93 12] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= Y because [13], by (Select) 30.91/30.93 13] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= Y because [14], by (Select) 30.91/30.93 14] cons(Y, Z) >= Y because [15], by (Star) 30.91/30.93 15] cons*(Y, Z) >= Y because [16], by (Select) 30.91/30.93 16] Y >= Y by (Meta) 30.91/30.93 17] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z) because [18], by (Select) 30.91/30.93 18] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z) because @_{o -> o} in Mul, [19] and [27], by (Stat) 30.91/30.93 19] fold(/\x./\y.yap(F(x), y), X) >= fold(/\x./\y.yap(F(x), y), X) because fold in Mul, [20] and [26], by (Fun) 30.91/30.93 20] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [21], by (Abs) 30.91/30.93 21] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [22], by (Abs) 30.91/30.93 22] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [23] and [25], by (Fun) 30.91/30.93 23] F(y) >= F(y) because [24], by (Meta) 30.91/30.93 24] y >= y by (Var) 30.91/30.93 25] x >= x by (Var) 30.91/30.93 26] X >= X by (Meta) 30.91/30.93 27] cons(Y, Z) > Z because [28], by definition 30.91/30.93 28] cons*(Y, Z) >= Z because [29], by (Select) 30.91/30.93 29] Z >= Z by (Meta) 30.91/30.93 30.91/30.93 30] plus(X, Y) >= plus(X, Y) because plus in Mul, [31] and [32], by (Fun) 30.91/30.93 31] X >= X by (Meta) 30.91/30.93 32] Y >= Y by (Meta) 30.91/30.93 30.91/30.93 33] times(_|_, X) >= _|_ by (Bot) 30.91/30.93 30.91/30.93 34] sum >= fold(/\x./\y.yap(add(x), y), _|_) because [35], by (Star) 30.91/30.93 35] sum* >= fold(/\x./\y.yap(add(x), y), _|_) because sum > fold, [36] and [44], by (Copy) 30.91/30.93 36] sum* >= /\y./\z.yap(add(y), z) because [37], by (F-Abs) 30.91/30.93 37] sum*(x) >= /\z.yap(add(x), z) because [38], by (F-Abs) 30.91/30.93 38] sum*(x, y) >= yap(add(x), y) because sum > yap, [39] and [42], by (Copy) 30.91/30.93 39] sum*(x, y) >= add(x) because sum > add and [40], by (Copy) 30.91/30.93 40] sum*(x, y) >= x because [41], by (Select) 30.91/30.93 41] x >= x by (Var) 30.91/30.93 42] sum*(x, y) >= y because [43], by (Select) 30.91/30.93 43] y >= y by (Var) 30.91/30.93 44] sum* >= _|_ by (Bot) 30.91/30.93 30.91/30.93 45] prod > fold(/\x./\y.yap(mul(x), y), _|_) because [46], by definition 30.91/30.93 46] prod* >= fold(/\x./\y.yap(mul(x), y), _|_) because prod > fold, [47] and [55], by (Copy) 30.91/30.93 47] prod* >= /\y./\z.yap(mul(y), z) because [48], by (F-Abs) 30.91/30.93 48] prod*(x) >= /\z.yap(mul(x), z) because [49], by (F-Abs) 30.91/30.93 49] prod*(x, y) >= yap(mul(x), y) because prod > yap, [50] and [53], by (Copy) 30.91/30.93 50] prod*(x, y) >= mul(x) because prod > mul and [51], by (Copy) 30.91/30.93 51] prod*(x, y) >= x because [52], by (Select) 30.91/30.93 52] x >= x by (Var) 30.91/30.93 53] prod*(x, y) >= y because [54], by (Select) 30.91/30.93 54] y >= y by (Var) 30.91/30.93 55] prod* >= _|_ by (Bot) 30.91/30.93 30.91/30.93 We can thus remove the following rules: 30.91/30.93 30.91/30.93 fold(/\x./\y.yap(F(x), y), X) nil => X 30.91/30.93 prod => fold(/\x./\y.yap(mul(x), y), s(0)) 30.91/30.93 30.91/30.93 We use rule removal, following [Kop12, Theorem 2.23]. 30.91/30.93 30.91/30.93 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 30.91/30.93 30.91/30.93 fold(/\x./\y.yap(F(x), y), X) cons(Y, Z) >? yap(F(Y), fold(/\z./\u.yap(F(z), u), X) Z) 30.91/30.93 plus(s(X), Y) >? s(plus(X, Y)) 30.91/30.93 times(0, X) >? 0 30.91/30.93 sum >? fold(/\x./\y.yap(add(x), y), 0) 30.91/30.93 30.91/30.93 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 30.91/30.93 30.91/30.93 Argument functions: 30.91/30.93 30.91/30.93 [[0]] = _|_ 30.91/30.93 30.91/30.93 We choose Lex = {} and Mul = {@_{o -> o}, add, cons, fold, plus, s, sum, times, yap}, and the following precedence: plus > s > cons > sum > add > times > yap > fold > @_{o -> o} 30.91/30.93 30.91/30.93 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 30.91/30.93 30.91/30.93 @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) 30.91/30.93 plus(s(X), Y) >= s(plus(X, Y)) 30.91/30.93 times(_|_, X) >= _|_ 30.91/30.93 sum > fold(/\x./\y.yap(add(x), y), _|_) 30.91/30.93 30.91/30.93 With these choices, we have: 30.91/30.93 30.91/30.93 1] @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [2], by (Star) 30.91/30.93 2] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [3], by (Select) 30.91/30.93 3] fold(/\x./\y.yap(F(x), y), X) @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [4] 30.91/30.93 4] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because [5], by (Select) 30.91/30.93 5] yap(F(fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)))), fold*(/\v./\w.yap(F(v), w), X, @_{o -> o}*(fold(/\x'./\y'.yap(F(x'), y'), X), cons(Y, Z)))) >= yap(F(Y), @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z)) because yap in Mul, [6] and [12], by (Fun) 30.91/30.93 6] F(fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z)))) >= F(Y) because [7], by (Meta) 30.91/30.93 7] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= Y because [8], by (Select) 30.91/30.93 8] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= Y because [9], by (Select) 30.91/30.93 9] cons(Y, Z) >= Y because [10], by (Star) 30.91/30.93 10] cons*(Y, Z) >= Y because [11], by (Select) 30.91/30.93 11] Y >= Y by (Meta) 30.91/30.93 12] fold*(/\x./\y.yap(F(x), y), X, @_{o -> o}*(fold(/\z./\u.yap(F(z), u), X), cons(Y, Z))) >= @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z) because [13], by (Select) 30.91/30.93 13] @_{o -> o}*(fold(/\x./\y.yap(F(x), y), X), cons(Y, Z)) >= @_{o -> o}(fold(/\x./\y.yap(F(x), y), X), Z) because @_{o -> o} in Mul, [14] and [22], by (Stat) 30.91/30.93 14] fold(/\x./\y.yap(F(x), y), X) >= fold(/\x./\y.yap(F(x), y), X) because fold in Mul, [15] and [21], by (Fun) 30.91/30.93 15] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [16], by (Abs) 30.91/30.93 16] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [17], by (Abs) 30.91/30.93 17] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [18] and [20], by (Fun) 30.91/30.93 18] F(y) >= F(y) because [19], by (Meta) 30.91/30.93 19] y >= y by (Var) 30.91/30.93 20] x >= x by (Var) 30.91/30.93 21] X >= X by (Meta) 30.91/30.93 22] cons(Y, Z) > Z because [23], by definition 30.91/30.93 23] cons*(Y, Z) >= Z because [24], by (Select) 30.91/30.93 24] Z >= Z by (Meta) 30.91/30.93 30.91/30.93 25] plus(s(X), Y) >= s(plus(X, Y)) because [26], by (Star) 30.91/30.93 26] plus*(s(X), Y) >= s(plus(X, Y)) because plus > s and [27], by (Copy) 30.91/30.93 27] plus*(s(X), Y) >= plus(X, Y) because plus in Mul, [28] and [31], by (Stat) 30.91/30.93 28] s(X) > X because [29], by definition 30.91/30.93 29] s*(X) >= X because [30], by (Select) 30.91/30.93 30] X >= X by (Meta) 30.91/30.93 31] Y >= Y by (Meta) 30.91/30.93 30.91/30.93 32] times(_|_, X) >= _|_ by (Bot) 30.91/30.93 30.91/30.93 33] sum > fold(/\x./\y.yap(add(x), y), _|_) because [34], by definition 30.91/30.93 34] sum* >= fold(/\x./\y.yap(add(x), y), _|_) because sum > fold, [35] and [43], by (Copy) 30.91/30.93 35] sum* >= /\y./\z.yap(add(y), z) because [36], by (F-Abs) 30.91/30.93 36] sum*(x) >= /\z.yap(add(x), z) because [37], by (F-Abs) 30.91/30.93 37] sum*(x, y) >= yap(add(x), y) because sum > yap, [38] and [41], by (Copy) 30.91/30.93 38] sum*(x, y) >= add(x) because sum > add and [39], by (Copy) 30.91/30.93 39] sum*(x, y) >= x because [40], by (Select) 30.91/30.93 40] x >= x by (Var) 30.91/30.93 41] sum*(x, y) >= y because [42], by (Select) 30.91/30.93 42] y >= y by (Var) 30.91/30.93 43] sum* >= _|_ by (Bot) 30.91/30.93 30.91/30.93 We can thus remove the following rules: 30.91/30.93 30.91/30.93 sum => fold(/\x./\y.yap(add(x), y), 0) 30.91/30.93 30.91/30.93 We use rule removal, following [Kop12, Theorem 2.23]. 30.91/30.93 30.91/30.93 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 30.91/30.93 30.91/30.93 fold(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >? yap(F(Y), fold(/\z./\u.yap(F(z), u), X, Z)) 30.91/30.93 plus(s(X), Y) >? s(plus(X, Y)) 30.91/30.93 times(0, X) >? 0 30.91/30.93 30.91/30.93 We orient these requirements with a polynomial interpretation in the natural numbers. 30.91/30.93 30.91/30.93 The following interpretation satisfies the requirements: 30.91/30.93 30.91/30.93 0 = 0 30.91/30.93 cons = \y0y1.3 + 2y0 + 3y1 30.91/30.93 fold = \G0y1y2.1 + y1 + y2 + 2y2y2G0(y2,y2) + 2G0(y1,y1) 30.91/30.93 plus = \y0y1.2y1 + 3y0 30.91/30.93 s = \y0.3 + y0 30.91/30.93 times = \y0y1.3 + 2y1 + 3y0 30.91/30.93 yap = \G0y1.y1 + G0(0) 30.91/30.93 30.91/30.93 Using this interpretation, the requirements translate to: 30.91/30.93 30.91/30.93 [[fold(/\x./\y.yap(_F0(x), y), _x1, cons(_x2, _x3))]] = 58 + 3x1 + 16x2x2x2 + 54x3x3x3 + 72x2x2 + 72x2x2x3 + 108x2x3x3 + 110x2 + 162x3x3 + 165x3 + 216x2x3 + 2F0(x1,0) + 8x2x2F0(3 + 2x2 + 3x3,0) + 18x3x3F0(3 + 2x2 + 3x3,0) + 18F0(3 + 2x2 + 3x3,0) + 24x2x3F0(3 + 2x2 + 3x3,0) + 24x2F0(3 + 2x2 + 3x3,0) + 36x3F0(3 + 2x2 + 3x3,0) > 1 + x3 + 2x3x3x3 + 3x1 + F0(x2,0) + 2x3x3F0(x3,0) + 2F0(x1,0) = [[yap(_F0(_x2), fold(/\x./\y.yap(_F0(x), y), _x1, _x3))]] 30.91/30.93 [[plus(s(_x0), _x1)]] = 9 + 2x1 + 3x0 > 3 + 2x1 + 3x0 = [[s(plus(_x0, _x1))]] 30.91/30.93 [[times(0, _x0)]] = 3 + 2x0 > 0 = [[0]] 30.91/30.93 30.91/30.93 We can thus remove the following rules: 30.91/30.93 30.91/30.93 fold(/\x./\y.yap(F(x), y), X, cons(Y, Z)) => yap(F(Y), fold(/\z./\u.yap(F(z), u), X, Z)) 30.91/30.93 plus(s(X), Y) => s(plus(X, Y)) 30.91/30.93 times(0, X) => 0 30.91/30.93 30.91/30.93 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. 30.91/30.93 30.91/30.93 30.91/30.93 +++ Citations +++ 30.91/30.93 30.91/30.93 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 30.91/30.93 [Kop13:2] C. Kop. StarHorpo with an Eta-Rule. Unpublished manuscript, http://cl-informatik.uibk.ac.at/users/kop/etahorpo.pdf, 2013. 30.93/30.96 EOF