/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o U11 : [o * o] --> o U21 : [o * o * o] --> o U31 : [o] --> o U41 : [o * o * o] --> o activate : [o] --> o and : [o * o] --> o isNat : [o] --> o n!6220!62200 : [] --> o n!6220!6220isNat : [o] --> o n!6220!6220plus : [o * o] --> o n!6220!6220s : [o] --> o n!6220!6220x : [o * o] --> o plus : [o * o] --> o s : [o] --> o tt : [] --> o x : [o * o] --> o U11(tt, X) => activate(X) U21(tt, X, Y) => s(plus(activate(Y), activate(X))) U31(tt) => 0 U41(tt, X, Y) => plus(x(activate(Y), activate(X)), activate(Y)) and(tt, X) => activate(X) isNat(n!6220!62200) => tt isNat(n!6220!6220plus(X, Y)) => and(isNat(activate(X)), n!6220!6220isNat(activate(Y))) isNat(n!6220!6220s(X)) => isNat(activate(X)) isNat(n!6220!6220x(X, Y)) => and(isNat(activate(X)), n!6220!6220isNat(activate(Y))) plus(X, 0) => U11(isNat(X), X) plus(X, s(Y)) => U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) x(X, 0) => U31(isNat(X)) x(X, s(Y)) => U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) 0 => n!6220!62200 plus(X, Y) => n!6220!6220plus(X, Y) isNat(X) => n!6220!6220isNat(X) s(X) => n!6220!6220s(X) x(X, Y) => n!6220!6220x(X, Y) activate(n!6220!62200) => 0 activate(n!6220!6220plus(X, Y)) => plus(X, Y) activate(n!6220!6220isNat(X)) => isNat(X) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220x(X, Y)) => x(X, Y) activate(X) => 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]): U11(tt, X) >? activate(X) U21(tt, X, Y) >? s(plus(activate(Y), activate(X))) U31(tt) >? 0 U41(tt, X, Y) >? plus(x(activate(Y), activate(X)), activate(Y)) and(tt, X) >? activate(X) isNat(n!6220!62200) >? tt isNat(n!6220!6220plus(X, Y)) >? and(isNat(activate(X)), n!6220!6220isNat(activate(Y))) isNat(n!6220!6220s(X)) >? isNat(activate(X)) isNat(n!6220!6220x(X, Y)) >? and(isNat(activate(X)), n!6220!6220isNat(activate(Y))) plus(X, 0) >? U11(isNat(X), X) plus(X, s(Y)) >? U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) x(X, 0) >? U31(isNat(X)) x(X, s(Y)) >? U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) x(X, Y) >? n!6220!6220x(X, Y) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(X, Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(n!6220!6220s(X)) >? s(X) activate(n!6220!6220x(X, Y)) >? x(X, Y) activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U21(x_1, x_2, x_3)]] = U21(x_2, x_3, x_1) [[U41(x_1, x_2, x_3)]] = U41(x_2, x_3, x_1) [[activate(x_1)]] = x_1 [[n!6220!62200]] = _|_ [[n!6220!6220plus(x_1, x_2)]] = n!6220!6220plus(x_2, x_1) [[n!6220!6220x(x_1, x_2)]] = n!6220!6220x(x_2, x_1) [[plus(x_1, x_2)]] = plus(x_2, x_1) [[tt]] = _|_ [[x(x_1, x_2)]] = x(x_2, x_1) We choose Lex = {U21, U41, n!6220!6220plus, n!6220!6220x, plus, x} and Mul = {U11, U31, and, isNat, n!6220!6220isNat, n!6220!6220s, s}, and the following precedence: U41 = n!6220!6220x = x > U31 > U21 = n!6220!6220plus = plus > U11 > and > isNat = n!6220!6220isNat > n!6220!6220s = s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11(_|_, X) >= X U21(_|_, X, Y) > s(plus(Y, X)) U31(_|_) >= _|_ U41(_|_, X, Y) >= plus(x(Y, X), Y) and(_|_, X) >= X isNat(_|_) >= _|_ isNat(n!6220!6220plus(X, Y)) > and(isNat(X), n!6220!6220isNat(Y)) isNat(n!6220!6220s(X)) >= isNat(X) isNat(n!6220!6220x(X, Y)) > and(isNat(X), n!6220!6220isNat(Y)) plus(X, _|_) > U11(isNat(X), X) plus(X, s(Y)) > U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) x(X, _|_) > U31(isNat(X)) x(X, s(Y)) >= U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) isNat(X) >= n!6220!6220isNat(X) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220isNat(X) >= isNat(X) n!6220!6220s(X) >= s(X) n!6220!6220x(X, Y) >= x(X, Y) X >= X With these choices, we have: 1] U11(_|_, X) >= X because [2], by (Star) 2] U11*(_|_, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] U21(_|_, X, Y) > s(plus(Y, X)) because [5], by definition 5] U21*(_|_, X, Y) >= s(plus(Y, X)) because U21 > s and [6], by (Copy) 6] U21*(_|_, X, Y) >= plus(Y, X) because U21 = plus, [7], [8], [9] and [10], by (Stat) 7] X >= X by (Meta) 8] Y >= Y by (Meta) 9] U21*(_|_, X, Y) >= Y because [8], by (Select) 10] U21*(_|_, X, Y) >= X because [7], by (Select) 11] U31(_|_) >= _|_ by (Bot) 12] U41(_|_, X, Y) >= plus(x(Y, X), Y) because [13], by (Star) 13] U41*(_|_, X, Y) >= plus(x(Y, X), Y) because U41 > plus, [14] and [15], by (Copy) 14] U41*(_|_, X, Y) >= x(Y, X) because U41 = x, [7], [8], [15] and [16], by (Stat) 15] U41*(_|_, X, Y) >= Y because [8], by (Select) 16] U41*(_|_, X, Y) >= X because [7], by (Select) 17] and(_|_, X) >= X because [18], by (Star) 18] and*(_|_, X) >= X because [19], by (Select) 19] X >= X by (Meta) 20] isNat(_|_) >= _|_ by (Bot) 21] isNat(n!6220!6220plus(X, Y)) > and(isNat(X), n!6220!6220isNat(Y)) because [22], by definition 22] isNat*(n!6220!6220plus(X, Y)) >= and(isNat(X), n!6220!6220isNat(Y)) because [23], by (Select) 23] n!6220!6220plus(X, Y) >= and(isNat(X), n!6220!6220isNat(Y)) because [24], by (Star) 24] n!6220!6220plus*(X, Y) >= and(isNat(X), n!6220!6220isNat(Y)) because n!6220!6220plus > and, [25] and [28], by (Copy) 25] n!6220!6220plus*(X, Y) >= isNat(X) because n!6220!6220plus > isNat and [26], by (Copy) 26] n!6220!6220plus*(X, Y) >= X because [27], by (Select) 27] X >= X by (Meta) 28] n!6220!6220plus*(X, Y) >= n!6220!6220isNat(Y) because n!6220!6220plus > n!6220!6220isNat and [29], by (Copy) 29] n!6220!6220plus*(X, Y) >= Y because [30], by (Select) 30] Y >= Y by (Meta) 31] isNat(n!6220!6220s(X)) >= isNat(X) because [32], by (Star) 32] isNat*(n!6220!6220s(X)) >= isNat(X) because isNat in Mul and [33], by (Stat) 33] n!6220!6220s(X) > X because [34], by definition 34] n!6220!6220s*(X) >= X because [27], by (Select) 35] isNat(n!6220!6220x(X, Y)) > and(isNat(X), n!6220!6220isNat(Y)) because [36], by definition 36] isNat*(n!6220!6220x(X, Y)) >= and(isNat(X), n!6220!6220isNat(Y)) because [37], by (Select) 37] n!6220!6220x(X, Y) >= and(isNat(X), n!6220!6220isNat(Y)) because [38], by (Star) 38] n!6220!6220x*(X, Y) >= and(isNat(X), n!6220!6220isNat(Y)) because n!6220!6220x > and, [39] and [41], by (Copy) 39] n!6220!6220x*(X, Y) >= isNat(X) because n!6220!6220x > isNat and [40], by (Copy) 40] n!6220!6220x*(X, Y) >= X because [27], by (Select) 41] n!6220!6220x*(X, Y) >= n!6220!6220isNat(Y) because n!6220!6220x > n!6220!6220isNat and [42], by (Copy) 42] n!6220!6220x*(X, Y) >= Y because [30], by (Select) 43] plus(X, _|_) > U11(isNat(X), X) because [44], by definition 44] plus*(X, _|_) >= U11(isNat(X), X) because plus > U11, [45] and [46], by (Copy) 45] plus*(X, _|_) >= isNat(X) because plus > isNat and [46], by (Copy) 46] plus*(X, _|_) >= X because [8], by (Select) 47] plus(X, s(Y)) > U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) because [48], by definition 48] plus*(X, s(Y)) >= U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) because plus = U21, [49], [51], [53] and [56], by (Stat) 49] s(Y) > Y because [50], by definition 50] s*(Y) >= Y because [7], by (Select) 51] plus*(X, s(Y)) >= and(isNat(Y), n!6220!6220isNat(X)) because plus > and, [52] and [55], by (Copy) 52] plus*(X, s(Y)) >= isNat(Y) because plus > isNat and [53], by (Copy) 53] plus*(X, s(Y)) >= Y because [54], by (Select) 54] s(Y) >= Y because [50], by (Star) 55] plus*(X, s(Y)) >= n!6220!6220isNat(X) because plus > n!6220!6220isNat and [56], by (Copy) 56] plus*(X, s(Y)) >= X because [8], by (Select) 57] x(X, _|_) > U31(isNat(X)) because [58], by definition 58] x*(X, _|_) >= U31(isNat(X)) because x > U31 and [59], by (Copy) 59] x*(X, _|_) >= isNat(X) because x > isNat and [60], by (Copy) 60] x*(X, _|_) >= X because [8], by (Select) 61] x(X, s(Y)) >= U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) because [62], by (Star) 62] x*(X, s(Y)) >= U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) because x = U41, [49], [63], [65] and [67], by (Stat) 63] x*(X, s(Y)) >= and(isNat(Y), n!6220!6220isNat(X)) because x > and, [64] and [66], by (Copy) 64] x*(X, s(Y)) >= isNat(Y) because x > isNat and [65], by (Copy) 65] x*(X, s(Y)) >= Y because [54], by (Select) 66] x*(X, s(Y)) >= n!6220!6220isNat(X) because x > n!6220!6220isNat and [67], by (Copy) 67] x*(X, s(Y)) >= X because [8], by (Select) 68] _|_ >= _|_ by (Bot) 69] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, [70] and [71], by (Fun) 70] X >= X by (Meta) 71] Y >= Y by (Meta) 72] isNat(X) >= n!6220!6220isNat(X) because isNat = n!6220!6220isNat, isNat in Mul and [73], by (Fun) 73] X >= X by (Meta) 74] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [73], by (Fun) 75] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, [70] and [71], by (Fun) 76] _|_ >= _|_ by (Bot) 77] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, [70] and [71], by (Fun) 78] n!6220!6220isNat(X) >= isNat(X) because n!6220!6220isNat = isNat, n!6220!6220isNat in Mul and [73], by (Fun) 79] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [73], by (Fun) 80] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, [70] and [71], by (Fun) 81] X >= X by (Meta) We can thus remove the following rules: U21(tt, X, Y) => s(plus(activate(Y), activate(X))) isNat(n!6220!6220plus(X, Y)) => and(isNat(activate(X)), n!6220!6220isNat(activate(Y))) isNat(n!6220!6220x(X, Y)) => and(isNat(activate(X)), n!6220!6220isNat(activate(Y))) plus(X, 0) => U11(isNat(X), X) plus(X, s(Y)) => U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) x(X, 0) => U31(isNat(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]): U11(tt, X) >? activate(X) U31(tt) >? 0 U41(tt, X, Y) >? plus(x(activate(Y), activate(X)), activate(Y)) and(tt, X) >? activate(X) isNat(n!6220!62200) >? tt isNat(n!6220!6220s(X)) >? isNat(activate(X)) x(X, s(Y)) >? U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) x(X, Y) >? n!6220!6220x(X, Y) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(X, Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(n!6220!6220s(X)) >? s(X) activate(n!6220!6220x(X, Y)) >? x(X, Y) activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U41(x_1, x_2, x_3)]] = U41(x_2, x_3, x_1) [[activate(x_1)]] = x_1 [[n!6220!62200]] = _|_ [[n!6220!6220x(x_1, x_2)]] = n!6220!6220x(x_2, x_1) [[tt]] = _|_ [[x(x_1, x_2)]] = x(x_2, x_1) We choose Lex = {U41, n!6220!6220x, x} and Mul = {U11, U31, and, isNat, n!6220!6220isNat, n!6220!6220plus, n!6220!6220s, plus, s}, and the following precedence: U11 > n!6220!6220s = s > U31 > U41 = n!6220!6220x = x > and > isNat = n!6220!6220isNat > n!6220!6220plus = plus Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11(_|_, X) >= X U31(_|_) >= _|_ U41(_|_, X, Y) > plus(x(Y, X), Y) and(_|_, X) >= X isNat(_|_) >= _|_ isNat(n!6220!6220s(X)) >= isNat(X) x(X, s(Y)) >= U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) isNat(X) >= n!6220!6220isNat(X) s(X) >= n!6220!6220s(X) x(X, Y) >= n!6220!6220x(X, Y) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220isNat(X) >= isNat(X) n!6220!6220s(X) >= s(X) n!6220!6220x(X, Y) >= x(X, Y) X >= X With these choices, we have: 1] U11(_|_, X) >= X because [2], by (Star) 2] U11*(_|_, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] U31(_|_) >= _|_ by (Bot) 5] U41(_|_, X, Y) > plus(x(Y, X), Y) because [6], by definition 6] U41*(_|_, X, Y) >= plus(x(Y, X), Y) because U41 > plus, [7] and [10], by (Copy) 7] U41*(_|_, X, Y) >= x(Y, X) because U41 = x, [8], [9], [10] and [11], by (Stat) 8] X >= X by (Meta) 9] Y >= Y by (Meta) 10] U41*(_|_, X, Y) >= Y because [9], by (Select) 11] U41*(_|_, X, Y) >= X because [8], by (Select) 12] and(_|_, X) >= X because [13], by (Star) 13] and*(_|_, X) >= X because [14], by (Select) 14] X >= X by (Meta) 15] isNat(_|_) >= _|_ by (Bot) 16] isNat(n!6220!6220s(X)) >= isNat(X) because [17], by (Star) 17] isNat*(n!6220!6220s(X)) >= isNat(X) because [18], by (Select) 18] n!6220!6220s(X) >= isNat(X) because [19], by (Star) 19] n!6220!6220s*(X) >= isNat(X) because n!6220!6220s > isNat and [20], by (Copy) 20] n!6220!6220s*(X) >= X because [21], by (Select) 21] X >= X by (Meta) 22] x(X, s(Y)) >= U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) because [23], by (Star) 23] x*(X, s(Y)) >= U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) because x = U41, [24], [26], [28] and [31], by (Stat) 24] s(Y) > Y because [25], by definition 25] s*(Y) >= Y because [8], by (Select) 26] x*(X, s(Y)) >= and(isNat(Y), n!6220!6220isNat(X)) because x > and, [27] and [30], by (Copy) 27] x*(X, s(Y)) >= isNat(Y) because x > isNat and [28], by (Copy) 28] x*(X, s(Y)) >= Y because [29], by (Select) 29] s(Y) >= Y because [25], by (Star) 30] x*(X, s(Y)) >= n!6220!6220isNat(X) because x > n!6220!6220isNat and [31], by (Copy) 31] x*(X, s(Y)) >= X because [9], by (Select) 32] _|_ >= _|_ by (Bot) 33] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, plus in Mul, [34] and [35], by (Fun) 34] X >= X by (Meta) 35] Y >= Y by (Meta) 36] isNat(X) >= n!6220!6220isNat(X) because isNat = n!6220!6220isNat, isNat in Mul and [37], by (Fun) 37] X >= X by (Meta) 38] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [37], by (Fun) 39] x(X, Y) >= n!6220!6220x(X, Y) because x = n!6220!6220x, [34] and [35], by (Fun) 40] _|_ >= _|_ by (Bot) 41] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, n!6220!6220plus in Mul, [34] and [35], by (Fun) 42] n!6220!6220isNat(X) >= isNat(X) because n!6220!6220isNat = isNat, n!6220!6220isNat in Mul and [37], by (Fun) 43] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [37], by (Fun) 44] n!6220!6220x(X, Y) >= x(X, Y) because n!6220!6220x = x, [34] and [35], by (Fun) 45] X >= X by (Meta) We can thus remove the following rules: U41(tt, X, Y) => plus(x(activate(Y), activate(X)), activate(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]): U11(tt, X) >? activate(X) U31(tt) >? 0 and(tt, X) >? activate(X) isNat(n!6220!62200) >? tt isNat(n!6220!6220s(X)) >? isNat(activate(X)) x(X, s(Y)) >? U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) x(X, Y) >? n!6220!6220x(X, Y) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(X, Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(n!6220!6220s(X)) >? s(X) activate(n!6220!6220x(X, Y)) >? x(X, Y) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.3 + 3y0 + 3y1 U31 = \y0.3 + 3y0 U41 = \y0y1y2.y0 + y1 + y2 activate = \y0.y0 and = \y0y1.y0 + 2y1 isNat = \y0.y0 n!6220!62200 = 0 n!6220!6220isNat = \y0.y0 n!6220!6220plus = \y0y1.y1 + 2y0 n!6220!6220s = \y0.2y0 n!6220!6220x = \y0y1.y1 + 3y0 plus = \y0y1.y1 + 2y0 s = \y0.2y0 tt = 0 x = \y0y1.y1 + 3y0 Using this interpretation, the requirements translate to: [[U11(tt, _x0)]] = 3 + 3x0 > x0 = [[activate(_x0)]] [[U31(tt)]] = 3 > 0 = [[0]] [[and(tt, _x0)]] = 2x0 >= x0 = [[activate(_x0)]] [[isNat(n!6220!62200)]] = 0 >= 0 = [[tt]] [[isNat(n!6220!6220s(_x0))]] = 2x0 >= x0 = [[isNat(activate(_x0))]] [[x(_x0, s(_x1))]] = 2x1 + 3x0 >= 2x1 + 3x0 = [[U41(and(isNat(_x1), n!6220!6220isNat(_x0)), _x1, _x0)]] [[0]] = 0 >= 0 = [[n!6220!62200]] [[plus(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220plus(_x0, _x1)]] [[isNat(_x0)]] = x0 >= x0 = [[n!6220!6220isNat(_x0)]] [[s(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220s(_x0)]] [[x(_x0, _x1)]] = x1 + 3x0 >= x1 + 3x0 = [[n!6220!6220x(_x0, _x1)]] [[activate(n!6220!62200)]] = 0 >= 0 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[activate(n!6220!6220isNat(_x0))]] = x0 >= x0 = [[isNat(_x0)]] [[activate(n!6220!6220s(_x0))]] = 2x0 >= 2x0 = [[s(_x0)]] [[activate(n!6220!6220x(_x0, _x1))]] = x1 + 3x0 >= x1 + 3x0 = [[x(_x0, _x1)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: U11(tt, X) => activate(X) U31(tt) => 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]): and(tt, X) >? activate(X) isNat(n!6220!62200) >? tt isNat(n!6220!6220s(X)) >? isNat(activate(X)) x(X, s(Y)) >? U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) x(X, Y) >? n!6220!6220x(X, Y) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(X, Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(n!6220!6220s(X)) >? s(X) activate(n!6220!6220x(X, Y)) >? x(X, Y) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U41 = \y0y1y2.y0 + y1 + y2 activate = \y0.y0 and = \y0y1.1 + y0 + y1 isNat = \y0.2y0 n!6220!62200 = 0 n!6220!6220isNat = \y0.2y0 n!6220!6220plus = \y0y1.y0 + y1 n!6220!6220s = \y0.3y0 n!6220!6220x = \y0y1.1 + y1 + 3y0 plus = \y0y1.y0 + y1 s = \y0.3y0 tt = 0 x = \y0y1.1 + y1 + 3y0 Using this interpretation, the requirements translate to: [[and(tt, _x0)]] = 1 + x0 > x0 = [[activate(_x0)]] [[isNat(n!6220!62200)]] = 0 >= 0 = [[tt]] [[isNat(n!6220!6220s(_x0))]] = 6x0 >= 2x0 = [[isNat(activate(_x0))]] [[x(_x0, s(_x1))]] = 1 + 3x0 + 3x1 >= 1 + 3x0 + 3x1 = [[U41(and(isNat(_x1), n!6220!6220isNat(_x0)), _x1, _x0)]] [[0]] = 0 >= 0 = [[n!6220!62200]] [[plus(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220plus(_x0, _x1)]] [[isNat(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isNat(_x0)]] [[s(_x0)]] = 3x0 >= 3x0 = [[n!6220!6220s(_x0)]] [[x(_x0, _x1)]] = 1 + x1 + 3x0 >= 1 + x1 + 3x0 = [[n!6220!6220x(_x0, _x1)]] [[activate(n!6220!62200)]] = 0 >= 0 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[plus(_x0, _x1)]] [[activate(n!6220!6220isNat(_x0))]] = 2x0 >= 2x0 = [[isNat(_x0)]] [[activate(n!6220!6220s(_x0))]] = 3x0 >= 3x0 = [[s(_x0)]] [[activate(n!6220!6220x(_x0, _x1))]] = 1 + x1 + 3x0 >= 1 + x1 + 3x0 = [[x(_x0, _x1)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: and(tt, X) => activate(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]): isNat(n!6220!62200) >? tt isNat(n!6220!6220s(X)) >? isNat(activate(X)) x(X, s(Y)) >? U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) x(X, Y) >? n!6220!6220x(X, Y) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(X, Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(n!6220!6220s(X)) >? s(X) activate(n!6220!6220x(X, Y)) >? x(X, Y) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U41 = \y0y1y2.y0 + y1 + y2 activate = \y0.y0 and = \y0y1.y0 + y1 isNat = \y0.1 + y0 n!6220!62200 = 0 n!6220!6220isNat = \y0.1 + y0 n!6220!6220plus = \y0y1.2y0 + 2y1 n!6220!6220s = \y0.2y0 n!6220!6220x = \y0y1.2 + y1 + 2y0 plus = \y0y1.2y0 + 2y1 s = \y0.2y0 tt = 0 x = \y0y1.2 + y1 + 2y0 Using this interpretation, the requirements translate to: [[isNat(n!6220!62200)]] = 1 > 0 = [[tt]] [[isNat(n!6220!6220s(_x0))]] = 1 + 2x0 >= 1 + x0 = [[isNat(activate(_x0))]] [[x(_x0, s(_x1))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[U41(and(isNat(_x1), n!6220!6220isNat(_x0)), _x1, _x0)]] [[0]] = 0 >= 0 = [[n!6220!62200]] [[plus(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[n!6220!6220plus(_x0, _x1)]] [[isNat(_x0)]] = 1 + x0 >= 1 + x0 = [[n!6220!6220isNat(_x0)]] [[s(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220s(_x0)]] [[x(_x0, _x1)]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[n!6220!6220x(_x0, _x1)]] [[activate(n!6220!62200)]] = 0 >= 0 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[activate(n!6220!6220isNat(_x0))]] = 1 + x0 >= 1 + x0 = [[isNat(_x0)]] [[activate(n!6220!6220s(_x0))]] = 2x0 >= 2x0 = [[s(_x0)]] [[activate(n!6220!6220x(_x0, _x1))]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[x(_x0, _x1)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: isNat(n!6220!62200) => tt We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): isNat(n!6220!6220s(X)) >? isNat(activate(X)) x(X, s(Y)) >? U41(and(isNat(Y), n!6220!6220isNat(X)), Y, X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) x(X, Y) >? n!6220!6220x(X, Y) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(X, Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(n!6220!6220s(X)) >? s(X) activate(n!6220!6220x(X, Y)) >? x(X, Y) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U41 = \y0y1y2.y0 + y1 + y2 activate = \y0.y0 and = \y0y1.y0 + y1 isNat = \y0.y0 n!6220!62200 = 0 n!6220!6220isNat = \y0.y0 n!6220!6220plus = \y0y1.2y0 + 2y1 n!6220!6220s = \y0.2 + y0 n!6220!6220x = \y0y1.2y0 + 2y1 plus = \y0y1.2y0 + 2y1 s = \y0.2 + y0 x = \y0y1.2y0 + 2y1 Using this interpretation, the requirements translate to: [[isNat(n!6220!6220s(_x0))]] = 2 + x0 > x0 = [[isNat(activate(_x0))]] [[x(_x0, s(_x1))]] = 4 + 2x0 + 2x1 > 2x0 + 2x1 = [[U41(and(isNat(_x1), n!6220!6220isNat(_x0)), _x1, _x0)]] [[0]] = 0 >= 0 = [[n!6220!62200]] [[plus(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[n!6220!6220plus(_x0, _x1)]] [[isNat(_x0)]] = x0 >= x0 = [[n!6220!6220isNat(_x0)]] [[s(_x0)]] = 2 + x0 >= 2 + x0 = [[n!6220!6220s(_x0)]] [[x(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[n!6220!6220x(_x0, _x1)]] [[activate(n!6220!62200)]] = 0 >= 0 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[activate(n!6220!6220isNat(_x0))]] = x0 >= x0 = [[isNat(_x0)]] [[activate(n!6220!6220s(_x0))]] = 2 + x0 >= 2 + x0 = [[s(_x0)]] [[activate(n!6220!6220x(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, _x1)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: isNat(n!6220!6220s(X)) => isNat(activate(X)) x(X, s(Y)) => U41(and(isNat(Y), n!6220!6220isNat(X)), Y, 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]): 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) x(X, Y) >? n!6220!6220x(X, Y) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(X, Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(n!6220!6220s(X)) >? s(X) activate(n!6220!6220x(X, Y)) >? x(X, Y) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 activate = \y0.3 + 3y0 isNat = \y0.2 + 2y0 n!6220!62200 = 0 n!6220!6220isNat = \y0.y0 n!6220!6220plus = \y0y1.y0 + y1 n!6220!6220s = \y0.3y0 n!6220!6220x = \y0y1.y0 + y1 plus = \y0y1.2 + 2y0 + 2y1 s = \y0.3y0 x = \y0y1.y1 + 2y0 Using this interpretation, the requirements translate to: [[0]] = 0 >= 0 = [[n!6220!62200]] [[plus(_x0, _x1)]] = 2 + 2x0 + 2x1 > x0 + x1 = [[n!6220!6220plus(_x0, _x1)]] [[isNat(_x0)]] = 2 + 2x0 > x0 = [[n!6220!6220isNat(_x0)]] [[s(_x0)]] = 3x0 >= 3x0 = [[n!6220!6220s(_x0)]] [[x(_x0, _x1)]] = x1 + 2x0 >= x0 + x1 = [[n!6220!6220x(_x0, _x1)]] [[activate(n!6220!62200)]] = 3 > 0 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = 3 + 3x0 + 3x1 > 2 + 2x0 + 2x1 = [[plus(_x0, _x1)]] [[activate(n!6220!6220isNat(_x0))]] = 3 + 3x0 > 2 + 2x0 = [[isNat(_x0)]] [[activate(n!6220!6220s(_x0))]] = 3 + 9x0 > 3x0 = [[s(_x0)]] [[activate(n!6220!6220x(_x0, _x1))]] = 3 + 3x0 + 3x1 > x1 + 2x0 = [[x(_x0, _x1)]] [[activate(_x0)]] = 3 + 3x0 > x0 = [[_x0]] We can thus remove the following rules: plus(X, Y) => n!6220!6220plus(X, Y) isNat(X) => n!6220!6220isNat(X) activate(n!6220!62200) => 0 activate(n!6220!6220plus(X, Y)) => plus(X, Y) activate(n!6220!6220isNat(X)) => isNat(X) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220x(X, Y)) => x(X, Y) activate(X) => 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]): 0 >? n!6220!62200 s(X) >? n!6220!6220s(X) x(X, Y) >? n!6220!6220x(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 3 n!6220!62200 = 0 n!6220!6220s = \y0.y0 n!6220!6220x = \y0y1.y0 + y1 s = \y0.3 + y0 x = \y0y1.3 + y0 + y1 Using this interpretation, the requirements translate to: [[0]] = 3 > 0 = [[n!6220!62200]] [[s(_x0)]] = 3 + x0 > x0 = [[n!6220!6220s(_x0)]] [[x(_x0, _x1)]] = 3 + x0 + x1 > x0 + x1 = [[n!6220!6220x(_x0, _x1)]] We can thus remove the following rules: 0 => n!6220!62200 s(X) => n!6220!6220s(X) x(X, Y) => n!6220!6220x(X, 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.