7.69/7.75 YES 7.69/7.77 We consider the system theBenchmark. 7.69/7.77 7.69/7.77 Alphabet: 7.69/7.77 7.69/7.77 0 : [] --> nat 7.69/7.77 rec : [nat * nat * nat -> nat -> nat] --> nat 7.69/7.77 s : [nat] --> nat 7.69/7.77 xap : [nat -> nat -> nat * nat] --> nat -> nat 7.69/7.77 xplus : [nat * nat] --> nat 7.69/7.77 xtimes : [nat * nat] --> nat 7.69/7.77 yap : [nat -> nat * nat] --> nat 7.69/7.77 7.69/7.77 Rules: 7.69/7.77 7.69/7.77 xplus(x, 0) => x 7.69/7.77 xplus(x, s(y)) => s(xplus(x, y)) 7.69/7.77 rec(0, x, /\y./\z.yap(xap(f, y), z)) => x 7.69/7.77 rec(s(x), y, /\z./\u.yap(xap(f, z), u)) => yap(xap(f, x), rec(x, y, /\v./\w.yap(xap(f, v), w))) 7.69/7.77 xtimes(x, y) => rec(y, 0, /\z./\u.xplus(x, u)) 7.69/7.77 xap(f, x) => f x 7.69/7.77 yap(f, x) => f x 7.69/7.77 7.69/7.77 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 7.69/7.77 7.69/7.77 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: 7.69/7.77 7.69/7.77 Alphabet: 7.69/7.77 7.69/7.77 0 : [] --> nat 7.69/7.77 rec : [nat * nat * nat -> nat -> nat] --> nat 7.69/7.77 s : [nat] --> nat 7.69/7.77 xplus : [nat * nat] --> nat 7.69/7.77 xtimes : [nat * nat] --> nat 7.69/7.77 yap : [nat -> nat * nat] --> nat 7.69/7.77 7.69/7.77 Rules: 7.69/7.77 7.69/7.77 xplus(X, 0) => X 7.69/7.77 xplus(X, s(Y)) => s(xplus(X, Y)) 7.69/7.77 rec(0, X, /\x./\y.yap(F(x), y)) => X 7.69/7.77 rec(s(X), Y, /\x./\y.yap(F(x), y)) => yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 7.69/7.77 xtimes(X, Y) => rec(Y, 0, /\x./\y.xplus(X, y)) 7.69/7.77 yap(F, X) => F X 7.69/7.77 7.69/7.77 We use rule removal, following [Kop12, Theorem 2.23]. 7.69/7.77 7.69/7.77 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 7.69/7.77 7.69/7.77 xplus(X, 0) >? X 7.69/7.77 xplus(X, s(Y)) >? s(xplus(X, Y)) 7.69/7.77 rec(0, X, /\x./\y.yap(F(x), y)) >? X 7.69/7.77 rec(s(X), Y, /\x./\y.yap(F(x), y)) >? yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 7.69/7.77 xtimes(X, Y) >? rec(Y, 0, /\x./\y.xplus(X, y)) 7.69/7.77 yap(F, X) >? F X 7.69/7.77 7.69/7.77 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 7.69/7.77 7.69/7.77 Argument functions: 7.69/7.77 7.69/7.77 [[0]] = _|_ 7.69/7.77 7.69/7.77 We choose Lex = {} and Mul = {@_{o -> o}, rec, s, xplus, xtimes, yap}, and the following precedence: xtimes > xplus > s > rec > yap > @_{o -> o} 7.69/7.77 7.69/7.77 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 7.69/7.77 7.69/7.77 xplus(X, _|_) >= X 7.69/7.77 xplus(X, s(Y)) >= s(xplus(X, Y)) 7.69/7.77 rec(_|_, X, /\x./\y.yap(F(x), y)) >= X 7.69/7.77 rec(s(X), Y, /\x./\y.yap(F(x), y)) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) 7.69/7.77 xtimes(X, Y) > rec(Y, _|_, /\x./\y.xplus(X, y)) 7.69/7.77 yap(F, X) > @_{o -> o}(F, X) 7.69/7.77 7.69/7.77 With these choices, we have: 7.69/7.77 7.69/7.77 1] xplus(X, _|_) >= X because [2], by (Star) 7.69/7.77 2] xplus*(X, _|_) >= X because [3], by (Select) 7.69/7.77 3] X >= X by (Meta) 7.69/7.77 7.69/7.77 4] xplus(X, s(Y)) >= s(xplus(X, Y)) because [5], by (Star) 7.69/7.77 5] xplus*(X, s(Y)) >= s(xplus(X, Y)) because xplus > s and [6], by (Copy) 7.69/7.77 6] xplus*(X, s(Y)) >= xplus(X, Y) because xplus in Mul, [7] and [8], by (Stat) 7.69/7.77 7] X >= X by (Meta) 7.69/7.77 8] s(Y) > Y because [9], by definition 7.69/7.77 9] s*(Y) >= Y because [10], by (Select) 7.69/7.77 10] Y >= Y by (Meta) 7.69/7.77 7.69/7.77 11] rec(_|_, X, /\x./\y.yap(F(x), y)) >= X because [12], by (Star) 7.69/7.77 12] rec*(_|_, X, /\x./\y.yap(F(x), y)) >= X because [13], by (Select) 7.69/7.77 13] X >= X by (Meta) 7.69/7.77 7.69/7.77 14] rec(s(X), Y, /\x./\y.yap(F(x), y)) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) because [15], by (Star) 7.69/7.77 15] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) because [16], by (Select) 7.69/7.77 16] yap(F(rec*(s(X), Y, /\x./\y.yap(F(x), y))), rec*(s(X), Y, /\z./\u.yap(F(z), u))) >= yap(F(X), rec(X, Y, /\x./\y.yap(F(x), y))) because yap in Mul, [17] and [22], by (Fun) 7.69/7.77 17] F(rec*(s(X), Y, /\x./\y.yap(F(x), y))) >= F(X) because [18], by (Meta) 7.69/7.77 18] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= X because [19], by (Select) 7.69/7.77 19] s(X) >= X because [20], by (Star) 7.69/7.77 20] s*(X) >= X because [21], by (Select) 7.69/7.77 21] X >= X by (Meta) 7.69/7.77 22] rec*(s(X), Y, /\x./\y.yap(F(x), y)) >= rec(X, Y, /\x./\y.yap(F(x), y)) because rec in Mul, [23], [25] and [26], by (Stat) 7.69/7.77 23] s(X) > X because [24], by definition 7.69/7.77 24] s*(X) >= X because [21], by (Select) 7.69/7.77 25] Y >= Y by (Meta) 7.69/7.77 26] /\x./\z.yap(F(x), z) >= /\x./\z.yap(F(x), z) because [27], by (Abs) 7.69/7.77 27] /\z.yap(F(y), z) >= /\z.yap(F(y), z) because [28], by (Abs) 7.69/7.77 28] yap(F(y), x) >= yap(F(y), x) because yap in Mul, [29] and [31], by (Fun) 7.69/7.77 29] F(y) >= F(y) because [30], by (Meta) 7.69/7.77 30] y >= y by (Var) 7.69/7.77 31] x >= x by (Var) 7.69/7.77 7.69/7.77 32] xtimes(X, Y) > rec(Y, _|_, /\x./\y.xplus(X, y)) because [33], by definition 7.69/7.77 33] xtimes*(X, Y) >= rec(Y, _|_, /\x./\y.xplus(X, y)) because xtimes > rec, [34], [36] and [37], by (Copy) 7.69/7.77 34] xtimes*(X, Y) >= Y because [35], by (Select) 7.69/7.77 35] Y >= Y by (Meta) 7.69/7.77 36] xtimes*(X, Y) >= _|_ by (Bot) 7.69/7.77 37] xtimes*(X, Y) >= /\y./\z.xplus(X, z) because [38], by (F-Abs) 7.69/7.77 38] xtimes*(X, Y, x) >= /\z.xplus(X, z) because [39], by (F-Abs) 7.69/7.77 39] xtimes*(X, Y, x, y) >= xplus(X, y) because xtimes > xplus, [40] and [42], by (Copy) 7.69/7.77 40] xtimes*(X, Y, x, y) >= X because [41], by (Select) 7.69/7.77 41] X >= X by (Meta) 7.69/7.77 42] xtimes*(X, Y, x, y) >= y because [43], by (Select) 7.69/7.77 43] y >= y by (Var) 7.69/7.77 7.69/7.77 44] yap(F, X) > @_{o -> o}(F, X) because [45], by definition 7.69/7.77 45] yap*(F, X) >= @_{o -> o}(F, X) because yap > @_{o -> o}, [46] and [48], by (Copy) 7.69/7.77 46] yap*(F, X) >= F because [47], by (Select) 7.69/7.77 47] F >= F by (Meta) 7.69/7.77 48] yap*(F, X) >= X because [49], by (Select) 7.69/7.77 49] X >= X by (Meta) 7.69/7.77 7.69/7.77 We can thus remove the following rules: 7.69/7.77 7.69/7.77 xtimes(X, Y) => rec(Y, 0, /\x./\y.xplus(X, y)) 7.69/7.77 yap(F, X) => F X 7.69/7.77 7.69/7.77 We use rule removal, following [Kop12, Theorem 2.23]. 7.69/7.77 7.69/7.77 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 7.69/7.77 7.69/7.77 xplus(X, 0) >? X 7.69/7.77 xplus(X, s(Y)) >? s(xplus(X, Y)) 7.69/7.77 rec(0, X, /\x./\y.yap(F(x), y)) >? X 7.69/7.77 rec(s(X), Y, /\x./\y.yap(F(x), y)) >? yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 7.69/7.77 7.69/7.77 We orient these requirements with a polynomial interpretation in the natural numbers. 7.69/7.77 7.69/7.77 The following interpretation satisfies the requirements: 7.69/7.77 7.69/7.77 0 = 3 7.69/7.77 rec = \y0y1G2.2 + y1 + 2y0 + G2(y1,y1) + 2y0y1G2(y1,y0) + 3y0y0G2(y0,y0) 7.69/7.77 s = \y0.3 + y0 7.69/7.77 xplus = \y0y1.y0 + 3y1 7.69/7.77 yap = \G0y1.y1 + G0(0) 7.69/7.77 7.69/7.77 Using this interpretation, the requirements translate to: 7.76/7.77 7.76/7.77 [[xplus(_x0, 0)]] = 9 + x0 > x0 = [[_x0]] 7.76/7.77 [[xplus(_x0, s(_x1))]] = 9 + x0 + 3x1 > 3 + x0 + 3x1 = [[s(xplus(_x0, _x1))]] 7.76/7.77 [[rec(0, _x0, /\x./\y.yap(_F1(x), y))]] = 89 + 20x0 + F1(x0,0) + 6x0F1(x0,0) + 27F1(3,0) > x0 = [[_x0]] 7.76/7.77 [[rec(s(_x0), _x1, /\x./\y.yap(_F2(x), y))]] = 89 + 2x0x0x1 + 3x0x0x0 + 12x0x1 + 20x1 + 27x0x0 + 83x0 + F2(x1,0) + 2x0x1F2(x1,0) + 3x0x0F2(3 + x0,0) + 6x1F2(x1,0) + 18x0F2(3 + x0,0) + 27F2(3 + x0,0) > 2 + 2x0 + 2x0x0x1 + 2x1 + 3x0x0x0 + F2(x0,0) + F2(x1,0) + 2x0x1F2(x1,0) + 3x0x0F2(x0,0) = [[yap(_F2(_x0), rec(_x0, _x1, /\x./\y.yap(_F2(x), y)))]] 7.76/7.77 7.76/7.77 We can thus remove the following rules: 7.76/7.77 7.76/7.77 xplus(X, 0) => X 7.76/7.77 xplus(X, s(Y)) => s(xplus(X, Y)) 7.76/7.77 rec(0, X, /\x./\y.yap(F(x), y)) => X 7.76/7.77 rec(s(X), Y, /\x./\y.yap(F(x), y)) => yap(F(X), rec(X, Y, /\z./\u.yap(F(z), u))) 7.76/7.77 7.76/7.77 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. 7.76/7.77 7.76/7.77 7.76/7.77 +++ Citations +++ 7.76/7.77 7.76/7.77 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 7.76/7.78 EOF