10.33/10.45 YES 10.48/10.53 We consider the system theBenchmark. 10.48/10.53 10.48/10.53 Alphabet: 10.48/10.53 10.48/10.53 app : [list * list] --> list 10.48/10.53 cons : [nat * list] --> list 10.48/10.53 foldl : [list -> nat -> list * list * list] --> list 10.48/10.53 iconsc : [] --> list -> nat -> list 10.48/10.53 nil : [] --> list 10.48/10.53 reverse : [list] --> list 10.48/10.53 reverse1 : [list] --> list 10.48/10.53 xap : [list -> nat -> list * list] --> nat -> list 10.48/10.53 yap : [nat -> list * nat] --> list 10.48/10.53 10.48/10.53 Rules: 10.48/10.53 10.48/10.53 app(nil, x) => x 10.48/10.53 app(cons(x, y), z) => cons(x, app(y, z)) 10.48/10.53 foldl(/\x./\y.yap(xap(f, x), y), z, nil) => z 10.48/10.53 foldl(/\x./\y.yap(xap(f, x), y), z, cons(u, v)) => foldl(/\w./\x'.yap(xap(f, w), x'), yap(xap(f, z), u), v) 10.48/10.53 iconsc x y => cons(y, x) 10.48/10.53 reverse(x) => foldl(/\y./\z.yap(xap(iconsc, y), z), nil, x) 10.48/10.53 reverse1(x) => foldl(/\y./\z.app(cons(z, nil), y), nil, x) 10.48/10.53 xap(f, x) => f x 10.48/10.53 yap(f, x) => f x 10.48/10.53 10.48/10.53 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 10.48/10.53 10.48/10.53 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: 10.48/10.53 10.48/10.53 Alphabet: 10.48/10.53 10.48/10.53 app : [list * list] --> list 10.48/10.53 cons : [nat * list] --> list 10.48/10.53 foldl : [list -> nat -> list * list * list] --> list 10.48/10.53 iconsc : [list] --> nat -> list 10.48/10.53 nil : [] --> list 10.48/10.53 reverse : [list] --> list 10.48/10.53 reverse1 : [list] --> list 10.48/10.53 yap : [nat -> list * nat] --> list 10.48/10.53 10.48/10.53 Rules: 10.48/10.53 10.48/10.53 app(nil, X) => X 10.48/10.53 app(cons(X, Y), Z) => cons(X, app(Y, Z)) 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, nil) => X 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, cons(Y, Z)) => foldl(/\z./\u.yap(F(z), u), yap(F(X), Y), Z) 10.48/10.53 iconsc(X) Y => cons(Y, X) 10.48/10.53 reverse(X) => foldl(/\x./\y.yap(iconsc(x), y), nil, X) 10.48/10.53 reverse1(X) => foldl(/\x./\y.app(cons(y, nil), x), nil, X) 10.48/10.53 yap(F, X) => F X 10.48/10.53 10.48/10.53 We use rule removal, following [Kop12, Theorem 2.23]. 10.48/10.53 10.48/10.53 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 10.48/10.53 10.48/10.53 app(nil, X) >? X 10.48/10.53 app(cons(X, Y), Z) >? cons(X, app(Y, Z)) 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, nil) >? X 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >? foldl(/\z./\u.yap(F(z), u), yap(F(X), Y), Z) 10.48/10.53 iconsc(X) Y >? cons(Y, X) 10.48/10.53 reverse(X) >? foldl(/\x./\y.yap(iconsc(x), y), nil, X) 10.48/10.53 reverse1(X) >? foldl(/\x./\y.app(cons(y, nil), x), nil, X) 10.48/10.53 yap(F, X) >? F X 10.48/10.53 10.48/10.53 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 10.48/10.53 10.48/10.53 Argument functions: 10.48/10.53 10.48/10.53 [[foldl(x_1, x_2, x_3)]] = foldl(x_3, x_2, x_1) 10.48/10.53 [[nil]] = _|_ 10.48/10.53 10.48/10.53 We choose Lex = {foldl} and Mul = {@_{o -> o}, app, cons, iconsc, reverse, reverse1, yap}, and the following precedence: reverse > iconsc > reverse1 > app > foldl > yap > @_{o -> o} > cons 10.48/10.53 10.48/10.53 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 10.48/10.53 10.48/10.53 app(_|_, X) >= X 10.48/10.53 app(cons(X, Y), Z) >= cons(X, app(Y, Z)) 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, _|_) >= X 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= foldl(/\x./\y.yap(F(x), y), yap(F(X), Y), Z) 10.48/10.53 @_{o -> o}(iconsc(X), Y) >= cons(Y, X) 10.48/10.53 reverse(X) >= foldl(/\x./\y.yap(iconsc(x), y), _|_, X) 10.48/10.53 reverse1(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X) 10.48/10.53 yap(F, X) > @_{o -> o}(F, X) 10.48/10.53 10.48/10.53 With these choices, we have: 10.48/10.53 10.48/10.53 1] app(_|_, X) >= X because [2], by (Star) 10.48/10.53 2] app*(_|_, X) >= X because [3], by (Select) 10.48/10.53 3] X >= X by (Meta) 10.48/10.53 10.48/10.53 4] app(cons(X, Y), Z) >= cons(X, app(Y, Z)) because [5], by (Star) 10.48/10.53 5] app*(cons(X, Y), Z) >= cons(X, app(Y, Z)) because app > cons, [6] and [10], by (Copy) 10.48/10.53 6] app*(cons(X, Y), Z) >= X because [7], by (Select) 10.48/10.53 7] cons(X, Y) >= X because [8], by (Star) 10.48/10.53 8] cons*(X, Y) >= X because [9], by (Select) 10.48/10.53 9] X >= X by (Meta) 10.48/10.53 10] app*(cons(X, Y), Z) >= app(Y, Z) because app in Mul, [11] and [14], by (Stat) 10.48/10.53 11] cons(X, Y) > Y because [12], by definition 10.48/10.53 12] cons*(X, Y) >= Y because [13], by (Select) 10.48/10.53 13] Y >= Y by (Meta) 10.48/10.53 14] Z >= Z by (Meta) 10.48/10.53 10.48/10.53 15] foldl(/\x./\y.yap(F(x), y), X, _|_) >= X because [16], by (Star) 10.48/10.53 16] foldl*(/\x./\y.yap(F(x), y), X, _|_) >= X because [17], by (Select) 10.48/10.53 17] X >= X by (Meta) 10.48/10.53 10.48/10.53 18] foldl(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= foldl(/\x./\y.yap(F(x), y), yap(F(X), Y), Z) because [19], by (Star) 10.48/10.53 19] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= foldl(/\x./\y.yap(F(x), y), yap(F(X), Y), Z) because [20], [23], [34] and [44], by (Stat) 10.48/10.53 20] cons(Y, Z) > Z because [21], by definition 10.48/10.53 21] cons*(Y, Z) >= Z because [22], by (Select) 10.48/10.53 22] Z >= Z by (Meta) 10.48/10.53 23] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= /\x./\y.yap(F(x), y) because [24], by (F-Abs) 10.48/10.53 24] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z), z) >= /\x.yap(F(z), x) because [25], by (Select) 10.48/10.53 25] /\x.yap(F(foldl*(/\y./\v.yap(F(y), v), X, cons(Y, Z), z)), x) >= /\x.yap(F(z), x) because [26], by (Abs) 10.48/10.53 26] yap(F(foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z), z)), u) >= yap(F(z), u) because yap in Mul, [27] and [33], by (Fun) 10.48/10.53 27] F(foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z), z)) >= F(z) because [28], by (Meta) 10.48/10.53 28] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z), z) >= z because [29], by (Select) 10.48/10.53 29] yap(F(foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z), z)), foldl*(/\v./\w.yap(F(v), w), X, cons(Y, Z), z)) >= z because [30], by (Star) 10.48/10.53 30] yap*(F(foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z), z)), foldl*(/\v./\w.yap(F(v), w), X, cons(Y, Z), z)) >= z because [31], by (Select) 10.48/10.53 31] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z), z) >= z because [32], by (Select) 10.48/10.53 32] z >= z by (Var) 10.48/10.53 33] u >= u by (Var) 10.48/10.53 34] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= yap(F(X), Y) because foldl > yap, [35] and [40], by (Copy) 10.48/10.53 35] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= F(X) because [36], by (Select) 10.48/10.53 36] /\x.yap(F(foldl*(/\y./\v.yap(F(y), v), X, cons(Y, Z))), x) >= F(X) because [37], by (Eta)[Kop13:2] 10.48/10.53 37] F(foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z))) >= F(X) because [38], by (Meta) 10.48/10.53 38] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= X because [39], by (Select) 10.48/10.53 39] X >= X by (Meta) 10.48/10.53 40] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= Y because [41], by (Select) 10.48/10.53 41] cons(Y, Z) >= Y because [42], by (Star) 10.48/10.53 42] cons*(Y, Z) >= Y because [43], by (Select) 10.48/10.53 43] Y >= Y by (Meta) 10.48/10.53 44] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= Z because [45], by (Select) 10.48/10.53 45] yap(F(foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z))), foldl*(/\v./\w.yap(F(v), w), X, cons(Y, Z))) >= Z because [46], by (Star) 10.48/10.53 46] yap*(F(foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z))), foldl*(/\v./\w.yap(F(v), w), X, cons(Y, Z))) >= Z because [47], by (Select) 10.48/10.53 47] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= Z because [48], by (Select) 10.48/10.53 48] cons(Y, Z) >= Z because [21], by (Star) 10.48/10.53 10.48/10.53 49] @_{o -> o}(iconsc(X), Y) >= cons(Y, X) because [50], by (Star) 10.48/10.53 50] @_{o -> o}*(iconsc(X), Y) >= cons(Y, X) because @_{o -> o} > cons, [51] and [56], by (Copy) 10.48/10.53 51] @_{o -> o}*(iconsc(X), Y) >= Y because [52], by (Select) 10.48/10.53 52] iconsc(X) @_{o -> o}*(iconsc(X), Y) >= Y because [53] 10.48/10.53 53] iconsc*(X, @_{o -> o}*(iconsc(X), Y)) >= Y because [54], by (Select) 10.48/10.53 54] @_{o -> o}*(iconsc(X), Y) >= Y because [55], by (Select) 10.48/10.53 55] Y >= Y by (Meta) 10.48/10.53 56] @_{o -> o}*(iconsc(X), Y) >= X because [57], by (Select) 10.48/10.53 57] iconsc(X) @_{o -> o}*(iconsc(X), Y) >= X because [58] 10.48/10.53 58] iconsc*(X, @_{o -> o}*(iconsc(X), Y)) >= X because [59], by (Select) 10.48/10.53 59] X >= X by (Meta) 10.48/10.53 10.48/10.53 60] reverse(X) >= foldl(/\x./\y.yap(iconsc(x), y), _|_, X) because [61], by (Star) 10.48/10.53 61] reverse*(X) >= foldl(/\x./\y.yap(iconsc(x), y), _|_, X) because reverse > foldl, [62], [70] and [71], by (Copy) 10.48/10.53 62] reverse*(X) >= /\y./\z.yap(iconsc(y), z) because [63], by (F-Abs) 10.48/10.53 63] reverse*(X, x) >= /\z.yap(iconsc(x), z) because [64], by (F-Abs) 10.48/10.53 64] reverse*(X, x, y) >= yap(iconsc(x), y) because reverse > yap, [65] and [68], by (Copy) 10.48/10.53 65] reverse*(X, x, y) >= iconsc(x) because reverse > iconsc and [66], by (Copy) 10.48/10.53 66] reverse*(X, x, y) >= x because [67], by (Select) 10.48/10.53 67] x >= x by (Var) 10.48/10.53 68] reverse*(X, x, y) >= y because [69], by (Select) 10.48/10.53 69] y >= y by (Var) 10.48/10.53 70] reverse*(X) >= _|_ by (Bot) 10.48/10.53 71] reverse*(X) >= X because [72], by (Select) 10.48/10.53 72] X >= X by (Meta) 10.48/10.53 10.48/10.53 73] reverse1(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X) because [74], by (Star) 10.48/10.53 74] reverse1*(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X) because reverse1 > foldl, [75], [84] and [85], by (Copy) 10.48/10.53 75] reverse1*(X) >= /\y./\z.app(cons(z, _|_), y) because [76], by (F-Abs) 10.48/10.53 76] reverse1*(X, x) >= /\z.app(cons(z, _|_), x) because [77], by (F-Abs) 10.48/10.53 77] reverse1*(X, x, y) >= app(cons(y, _|_), x) because reverse1 > app, [78] and [82], by (Copy) 10.48/10.53 78] reverse1*(X, x, y) >= cons(y, _|_) because reverse1 > cons, [79] and [81], by (Copy) 10.48/10.53 79] reverse1*(X, x, y) >= y because [80], by (Select) 10.48/10.53 80] y >= y by (Var) 10.48/10.53 81] reverse1*(X, x, y) >= _|_ by (Bot) 10.48/10.53 82] reverse1*(X, x, y) >= x because [83], by (Select) 10.48/10.53 83] x >= x by (Var) 10.48/10.53 84] reverse1*(X) >= _|_ by (Bot) 10.48/10.53 85] reverse1*(X) >= X because [86], by (Select) 10.48/10.53 86] X >= X by (Meta) 10.48/10.53 10.48/10.53 87] yap(F, X) > @_{o -> o}(F, X) because [88], by definition 10.48/10.53 88] yap*(F, X) >= @_{o -> o}(F, X) because yap > @_{o -> o}, [89] and [91], by (Copy) 10.48/10.53 89] yap*(F, X) >= F because [90], by (Select) 10.48/10.53 90] F >= F by (Meta) 10.48/10.53 91] yap*(F, X) >= X because [92], by (Select) 10.48/10.53 92] X >= X by (Meta) 10.48/10.53 10.48/10.53 We can thus remove the following rules: 10.48/10.53 10.48/10.53 yap(F, X) => F X 10.48/10.53 10.48/10.53 We use rule removal, following [Kop12, Theorem 2.23]. 10.48/10.53 10.48/10.53 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 10.48/10.53 10.48/10.53 app(nil, X) >? X 10.48/10.53 app(cons(X, Y), Z) >? cons(X, app(Y, Z)) 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, nil) >? X 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >? foldl(/\z./\u.yap(F(z), u), yap(F(X), Y), Z) 10.48/10.53 iconsc(X) Y >? cons(Y, X) 10.48/10.53 reverse(X) >? foldl(/\x./\y.yap(iconsc(x), y), nil, X) 10.48/10.53 reverse1(X) >? foldl(/\x./\y.app(cons(y, nil), x), nil, X) 10.48/10.53 10.48/10.53 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 10.48/10.53 10.48/10.53 Argument functions: 10.48/10.53 10.48/10.53 [[foldl(x_1, x_2, x_3)]] = foldl(x_3, x_1, x_2) 10.48/10.53 [[nil]] = _|_ 10.48/10.53 10.48/10.53 We choose Lex = {foldl} and Mul = {@_{o -> o}, app, cons, iconsc, reverse, reverse1, yap}, and the following precedence: @_{o -> o} > reverse > iconsc > reverse1 > app > cons > foldl > yap 10.48/10.53 10.48/10.53 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 10.48/10.53 10.48/10.53 app(_|_, X) > X 10.48/10.53 app(cons(X, Y), Z) > cons(X, app(Y, Z)) 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, _|_) > X 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, cons(Y, Z)) > foldl(/\x./\y.yap(F(x), y), yap(F(X), Y), Z) 10.48/10.53 @_{o -> o}(iconsc(X), Y) >= cons(Y, X) 10.48/10.53 reverse(X) >= foldl(/\x./\y.yap(iconsc(x), y), _|_, X) 10.48/10.53 reverse1(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X) 10.48/10.53 10.48/10.53 With these choices, we have: 10.48/10.53 10.48/10.53 1] app(_|_, X) > X because [2], by definition 10.48/10.53 2] app*(_|_, X) >= X because [3], by (Select) 10.48/10.53 3] X >= X by (Meta) 10.48/10.53 10.48/10.53 4] app(cons(X, Y), Z) > cons(X, app(Y, Z)) because [5], by definition 10.48/10.53 5] app*(cons(X, Y), Z) >= cons(X, app(Y, Z)) because app > cons, [6] and [10], by (Copy) 10.48/10.53 6] app*(cons(X, Y), Z) >= X because [7], by (Select) 10.48/10.53 7] cons(X, Y) >= X because [8], by (Star) 10.48/10.53 8] cons*(X, Y) >= X because [9], by (Select) 10.48/10.53 9] X >= X by (Meta) 10.48/10.53 10] app*(cons(X, Y), Z) >= app(Y, Z) because app in Mul, [11] and [14], by (Stat) 10.48/10.53 11] cons(X, Y) > Y because [12], by definition 10.48/10.53 12] cons*(X, Y) >= Y because [13], by (Select) 10.48/10.53 13] Y >= Y by (Meta) 10.48/10.53 14] Z >= Z by (Meta) 10.48/10.53 10.48/10.53 15] foldl(/\x./\y.yap(F(x), y), X, _|_) > X because [16], by definition 10.48/10.53 16] foldl*(/\x./\y.yap(F(x), y), X, _|_) >= X because [17], by (Select) 10.48/10.53 17] X >= X by (Meta) 10.48/10.53 10.48/10.53 18] foldl(/\x./\y.yap(F(x), y), X, cons(Y, Z)) > foldl(/\x./\y.yap(F(x), y), yap(F(X), Y), Z) because [19], by definition 10.48/10.53 19] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= foldl(/\x./\y.yap(F(x), y), yap(F(X), Y), Z) because [20], [23], [30] and [40], by (Stat) 10.48/10.53 20] cons(Y, Z) > Z because [21], by definition 10.48/10.53 21] cons*(Y, Z) >= Z because [22], by (Select) 10.48/10.53 22] Z >= Z by (Meta) 10.48/10.53 23] foldl*(/\x./\y.yap(F(x), y), X, cons(Y, Z)) >= /\x./\y.yap(F(x), y) because [24], by (Select) 10.48/10.53 24] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [25], by (Abs) 10.48/10.53 25] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [26], by (Abs) 10.48/10.53 26] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [27] and [29], by (Fun) 10.48/10.53 27] F(y) >= F(y) because [28], by (Meta) 10.48/10.53 28] y >= y by (Var) 10.48/10.53 29] x >= x by (Var) 10.48/10.53 30] foldl*(/\z./\u.yap(F(z), u), X, cons(Y, Z)) >= yap(F(X), Y) because foldl > yap, [31] and [36], by (Copy) 10.48/10.53 31] foldl*(/\z./\u.yap(F(z), u), X, cons(Y, Z)) >= F(X) because [32], by (Select) 10.48/10.53 32] /\z.yap(F(foldl*(/\u./\v.yap(F(u), v), X, cons(Y, Z))), z) >= F(X) because [33], by (Eta)[Kop13:2] 10.48/10.53 33] F(foldl*(/\z./\u.yap(F(z), u), X, cons(Y, Z))) >= F(X) because [34], by (Meta) 10.48/10.53 34] foldl*(/\z./\u.yap(F(z), u), X, cons(Y, Z)) >= X because [35], by (Select) 10.48/10.53 35] X >= X by (Meta) 10.48/10.53 36] foldl*(/\z./\u.yap(F(z), u), X, cons(Y, Z)) >= Y because [37], by (Select) 10.48/10.53 37] cons(Y, Z) >= Y because [38], by (Star) 10.48/10.53 38] cons*(Y, Z) >= Y because [39], by (Select) 10.48/10.53 39] Y >= Y by (Meta) 10.48/10.53 40] foldl*(/\z./\u.yap(F(z), u), X, cons(Y, Z)) >= Z because [41], by (Select) 10.48/10.53 41] cons(Y, Z) >= Z because [21], by (Star) 10.48/10.53 10.48/10.53 42] @_{o -> o}(iconsc(X), Y) >= cons(Y, X) because [43], by (Star) 10.48/10.53 43] @_{o -> o}*(iconsc(X), Y) >= cons(Y, X) because [44], by (Select) 10.48/10.53 44] iconsc(X) @_{o -> o}*(iconsc(X), Y) >= cons(Y, X) because [45] 10.48/10.53 45] iconsc*(X, @_{o -> o}*(iconsc(X), Y)) >= cons(Y, X) because iconsc > cons, [46] and [49], by (Copy) 10.48/10.53 46] iconsc*(X, @_{o -> o}*(iconsc(X), Y)) >= Y because [47], by (Select) 10.48/10.53 47] @_{o -> o}*(iconsc(X), Y) >= Y because [48], by (Select) 10.48/10.53 48] Y >= Y by (Meta) 10.48/10.53 49] iconsc*(X, @_{o -> o}*(iconsc(X), Y)) >= X because [50], by (Select) 10.48/10.53 50] X >= X by (Meta) 10.48/10.53 10.48/10.53 51] reverse(X) >= foldl(/\x./\y.yap(iconsc(x), y), _|_, X) because [52], by (Star) 10.48/10.53 52] reverse*(X) >= foldl(/\x./\y.yap(iconsc(x), y), _|_, X) because reverse > foldl, [53], [61] and [62], by (Copy) 10.48/10.53 53] reverse*(X) >= /\y./\z.yap(iconsc(y), z) because [54], by (F-Abs) 10.48/10.53 54] reverse*(X, x) >= /\z.yap(iconsc(x), z) because [55], by (F-Abs) 10.48/10.53 55] reverse*(X, x, y) >= yap(iconsc(x), y) because reverse > yap, [56] and [59], by (Copy) 10.48/10.53 56] reverse*(X, x, y) >= iconsc(x) because reverse > iconsc and [57], by (Copy) 10.48/10.53 57] reverse*(X, x, y) >= x because [58], by (Select) 10.48/10.53 58] x >= x by (Var) 10.48/10.53 59] reverse*(X, x, y) >= y because [60], by (Select) 10.48/10.53 60] y >= y by (Var) 10.48/10.53 61] reverse*(X) >= _|_ by (Bot) 10.48/10.53 62] reverse*(X) >= X because [63], by (Select) 10.48/10.53 63] X >= X by (Meta) 10.48/10.53 10.48/10.53 64] reverse1(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X) because [65], by (Star) 10.48/10.53 65] reverse1*(X) >= foldl(/\x./\y.app(cons(y, _|_), x), _|_, X) because reverse1 > foldl, [66], [75] and [76], by (Copy) 10.48/10.53 66] reverse1*(X) >= /\y./\z.app(cons(z, _|_), y) because [67], by (F-Abs) 10.48/10.53 67] reverse1*(X, x) >= /\z.app(cons(z, _|_), x) because [68], by (F-Abs) 10.48/10.53 68] reverse1*(X, x, y) >= app(cons(y, _|_), x) because reverse1 > app, [69] and [73], by (Copy) 10.48/10.53 69] reverse1*(X, x, y) >= cons(y, _|_) because reverse1 > cons, [70] and [72], by (Copy) 10.48/10.53 70] reverse1*(X, x, y) >= y because [71], by (Select) 10.48/10.53 71] y >= y by (Var) 10.48/10.53 72] reverse1*(X, x, y) >= _|_ by (Bot) 10.48/10.53 73] reverse1*(X, x, y) >= x because [74], by (Select) 10.48/10.53 74] x >= x by (Var) 10.48/10.53 75] reverse1*(X) >= _|_ by (Bot) 10.48/10.53 76] reverse1*(X) >= X because [77], by (Select) 10.48/10.53 77] X >= X by (Meta) 10.48/10.53 10.48/10.53 We can thus remove the following rules: 10.48/10.53 10.48/10.53 app(nil, X) => X 10.48/10.53 app(cons(X, Y), Z) => cons(X, app(Y, Z)) 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, nil) => X 10.48/10.53 foldl(/\x./\y.yap(F(x), y), X, cons(Y, Z)) => foldl(/\z./\u.yap(F(z), u), yap(F(X), Y), Z) 10.48/10.53 10.48/10.53 We use rule removal, following [Kop12, Theorem 2.23]. 10.48/10.53 10.48/10.53 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 10.48/10.53 10.48/10.53 iconsc(X) Y >? cons(Y, X) 10.48/10.53 reverse(X) >? foldl(/\x./\y.yap(iconsc(x), y), nil, X) 10.48/10.53 reverse1(X) >? foldl(/\x./\y.app(cons(y, nil), x), nil, X) 10.48/10.53 10.48/10.53 We orient these requirements with a polynomial interpretation in the natural numbers. 10.48/10.53 10.48/10.53 The following interpretation satisfies the requirements: 10.48/10.53 10.48/10.53 app = \y0y1.y0 + y1 10.48/10.53 cons = \y0y1.y0 + y1 10.48/10.53 foldl = \G0y1y2.y1 + y2 + 2G0(0,0) 10.48/10.53 iconsc = \y0y1.1 + y0 10.48/10.53 nil = 0 10.48/10.53 reverse = \y0.3 + 3y0 10.48/10.53 reverse1 = \y0.3 + 3y0 10.48/10.53 yap = \G0y1.y1 + G0(0) 10.48/10.53 10.48/10.53 Using this interpretation, the requirements translate to: 10.48/10.53 10.48/10.53 [[iconsc(_x0) _x1]] = 1 + x0 + x1 > x0 + x1 = [[cons(_x1, _x0)]] 10.48/10.53 [[reverse(_x0)]] = 3 + 3x0 > 2 + x0 = [[foldl(/\x./\y.yap(iconsc(x), y), nil, _x0)]] 10.48/10.53 [[reverse1(_x0)]] = 3 + 3x0 > x0 = [[foldl(/\x./\y.app(cons(y, nil), x), nil, _x0)]] 10.48/10.53 10.48/10.53 We can thus remove the following rules: 10.48/10.53 10.48/10.53 iconsc(X) Y => cons(Y, X) 10.48/10.53 reverse(X) => foldl(/\x./\y.yap(iconsc(x), y), nil, X) 10.48/10.53 reverse1(X) => foldl(/\x./\y.app(cons(y, nil), x), nil, X) 10.48/10.53 10.48/10.53 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. 10.48/10.53 10.48/10.53 10.48/10.53 +++ Citations +++ 10.48/10.53 10.48/10.53 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 10.48/10.53 [Kop13:2] C. Kop. StarHorpo with an Eta-Rule. Unpublished manuscript, http://cl-informatik.uibk.ac.at/users/kop/etahorpo.pdf, 2013. 10.49/10.53 EOF