/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 active : [o] --> o and : [o * o] --> o mark : [o] --> o plus : [o * o] --> o s : [o] --> o tt : [] --> o x : [o * o] --> o active(and(tt, X)) => mark(X) active(plus(X, 0)) => mark(X) active(plus(X, s(Y))) => mark(s(plus(X, Y))) active(x(X, 0)) => mark(0) active(x(X, s(Y))) => mark(plus(x(X, Y), X)) mark(and(X, Y)) => active(and(mark(X), Y)) mark(tt) => active(tt) mark(plus(X, Y)) => active(plus(mark(X), mark(Y))) mark(0) => active(0) mark(s(X)) => active(s(mark(X))) mark(x(X, Y)) => active(x(mark(X), mark(Y))) and(mark(X), Y) => and(X, Y) and(X, mark(Y)) => and(X, Y) and(active(X), Y) => and(X, Y) and(X, active(Y)) => and(X, Y) plus(mark(X), Y) => plus(X, Y) plus(X, mark(Y)) => plus(X, Y) plus(active(X), Y) => plus(X, Y) plus(X, active(Y)) => plus(X, Y) s(mark(X)) => s(X) s(active(X)) => s(X) x(mark(X), Y) => x(X, Y) x(X, mark(Y)) => x(X, Y) x(active(X), Y) => x(X, Y) x(X, active(Y)) => x(X, 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]): active(and(tt, X)) >? mark(X) active(plus(X, 0)) >? mark(X) active(plus(X, s(Y))) >? mark(s(plus(X, Y))) active(x(X, 0)) >? mark(0) active(x(X, s(Y))) >? mark(plus(x(X, Y), X)) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(plus(X, Y)) >? active(plus(mark(X), mark(Y))) mark(0) >? active(0) mark(s(X)) >? active(s(mark(X))) mark(x(X, Y)) >? active(x(mark(X), mark(Y))) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[active(x_1)]] = x_1 [[mark(x_1)]] = x_1 [[tt]] = _|_ We choose Lex = {} and Mul = {0, and, plus, s, x}, and the following precedence: x > plus > s > and > 0 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: and(_|_, X) > X plus(X, 0) > X plus(X, s(Y)) >= s(plus(X, Y)) x(X, 0) >= 0 x(X, s(Y)) >= plus(x(X, Y), X) and(X, Y) >= and(X, Y) _|_ >= _|_ plus(X, Y) >= plus(X, Y) 0 >= 0 s(X) >= s(X) x(X, Y) >= x(X, Y) and(X, Y) >= and(X, Y) and(X, Y) >= and(X, Y) and(X, Y) >= and(X, Y) and(X, Y) >= and(X, Y) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) s(X) >= s(X) s(X) >= s(X) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) With these choices, we have: 1] and(_|_, X) > X because [2], by definition 2] and*(_|_, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] plus(X, 0) > X because [5], by definition 5] plus*(X, 0) >= X because [6], by (Select) 6] X >= X by (Meta) 7] plus(X, s(Y)) >= s(plus(X, Y)) because [8], by (Star) 8] plus*(X, s(Y)) >= s(plus(X, Y)) because plus > s and [9], by (Copy) 9] plus*(X, s(Y)) >= plus(X, Y) because plus in Mul, [10] and [11], by (Stat) 10] X >= X by (Meta) 11] s(Y) > Y because [12], by definition 12] s*(Y) >= Y because [13], by (Select) 13] Y >= Y by (Meta) 14] x(X, 0) >= 0 because [15], by (Star) 15] x*(X, 0) >= 0 because [16], by (Select) 16] 0 >= 0 by (Fun) 17] x(X, s(Y)) >= plus(x(X, Y), X) because [18], by (Star) 18] x*(X, s(Y)) >= plus(x(X, Y), X) because x > plus, [19] and [20], by (Copy) 19] x*(X, s(Y)) >= x(X, Y) because x in Mul, [10] and [11], by (Stat) 20] x*(X, s(Y)) >= X because [10], by (Select) 21] and(X, Y) >= and(X, Y) because and in Mul, [22] and [23], by (Fun) 22] X >= X by (Meta) 23] Y >= Y by (Meta) 24] _|_ >= _|_ by (Bot) 25] plus(X, Y) >= plus(X, Y) because plus in Mul, [22] and [26], by (Fun) 26] Y >= Y by (Meta) 27] 0 >= 0 by (Fun) 28] s(X) >= s(X) because s in Mul and [29], by (Fun) 29] X >= X by (Meta) 30] x(X, Y) >= x(X, Y) because x in Mul, [22] and [26], by (Fun) 31] and(X, Y) >= and(X, Y) because and in Mul, [32] and [26], by (Fun) 32] X >= X by (Meta) 33] and(X, Y) >= and(X, Y) because and in Mul, [22] and [34], by (Fun) 34] Y >= Y by (Meta) 35] and(X, Y) >= and(X, Y) because and in Mul, [36] and [26], by (Fun) 36] X >= X by (Meta) 37] and(X, Y) >= and(X, Y) because and in Mul, [22] and [38], by (Fun) 38] Y >= Y by (Meta) 39] plus(X, Y) >= plus(X, Y) because plus in Mul, [32] and [26], by (Fun) 40] plus(X, Y) >= plus(X, Y) because plus in Mul, [22] and [34], by (Fun) 41] plus(X, Y) >= plus(X, Y) because plus in Mul, [36] and [26], by (Fun) 42] plus(X, Y) >= plus(X, Y) because plus in Mul, [22] and [38], by (Fun) 43] s(X) >= s(X) because s in Mul and [44], by (Fun) 44] X >= X by (Meta) 45] s(X) >= s(X) because s in Mul and [46], by (Fun) 46] X >= X by (Meta) 47] x(X, Y) >= x(X, Y) because x in Mul, [32] and [26], by (Fun) 48] x(X, Y) >= x(X, Y) because x in Mul, [22] and [34], by (Fun) 49] x(X, Y) >= x(X, Y) because x in Mul, [36] and [26], by (Fun) 50] x(X, Y) >= x(X, Y) because x in Mul, [22] and [38], by (Fun) We can thus remove the following rules: active(and(tt, X)) => mark(X) active(plus(X, 0)) => mark(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]): active(plus(X, s(Y))) >? mark(s(plus(X, Y))) active(x(X, 0)) >? mark(0) active(x(X, s(Y))) >? mark(plus(x(X, Y), X)) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(plus(X, Y)) >? active(plus(mark(X), mark(Y))) mark(0) >? active(0) mark(s(X)) >? active(s(mark(X))) mark(x(X, Y)) >? active(x(mark(X), mark(Y))) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[active(x_1)]] = x_1 [[mark(x_1)]] = x_1 [[tt]] = _|_ We choose Lex = {} and Mul = {0, and, plus, s, x}, and the following precedence: 0 > x > and > plus > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: plus(X, s(Y)) >= s(plus(X, Y)) x(X, 0) > 0 x(X, s(Y)) >= plus(x(X, Y), X) and(X, Y) >= and(X, Y) _|_ >= _|_ plus(X, Y) >= plus(X, Y) 0 >= 0 s(X) >= s(X) x(X, Y) >= x(X, Y) and(X, Y) >= and(X, Y) and(X, Y) >= and(X, Y) and(X, Y) >= and(X, Y) and(X, Y) >= and(X, Y) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) s(X) >= s(X) s(X) >= s(X) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) With these choices, we have: 1] plus(X, s(Y)) >= s(plus(X, Y)) because [2], by (Star) 2] plus*(X, s(Y)) >= s(plus(X, Y)) because plus > s and [3], by (Copy) 3] plus*(X, s(Y)) >= plus(X, Y) because plus in Mul, [4] and [5], by (Stat) 4] X >= X by (Meta) 5] s(Y) > Y because [6], by definition 6] s*(Y) >= Y because [7], by (Select) 7] Y >= Y by (Meta) 8] x(X, 0) > 0 because [9], by definition 9] x*(X, 0) >= 0 because [10], by (Select) 10] 0 >= 0 by (Fun) 11] x(X, s(Y)) >= plus(x(X, Y), X) because [12], by (Star) 12] x*(X, s(Y)) >= plus(x(X, Y), X) because x > plus, [13] and [14], by (Copy) 13] x*(X, s(Y)) >= x(X, Y) because x in Mul, [4] and [5], by (Stat) 14] x*(X, s(Y)) >= X because [4], by (Select) 15] and(X, Y) >= and(X, Y) because and in Mul, [16] and [17], by (Fun) 16] X >= X by (Meta) 17] Y >= Y by (Meta) 18] _|_ >= _|_ by (Bot) 19] plus(X, Y) >= plus(X, Y) because plus in Mul, [16] and [20], by (Fun) 20] Y >= Y by (Meta) 21] 0 >= 0 by (Fun) 22] s(X) >= s(X) because s in Mul and [23], by (Fun) 23] X >= X by (Meta) 24] x(X, Y) >= x(X, Y) because x in Mul, [16] and [20], by (Fun) 25] and(X, Y) >= and(X, Y) because and in Mul, [26] and [20], by (Fun) 26] X >= X by (Meta) 27] and(X, Y) >= and(X, Y) because and in Mul, [16] and [28], by (Fun) 28] Y >= Y by (Meta) 29] and(X, Y) >= and(X, Y) because and in Mul, [30] and [20], by (Fun) 30] X >= X by (Meta) 31] and(X, Y) >= and(X, Y) because and in Mul, [16] and [32], by (Fun) 32] Y >= Y by (Meta) 33] plus(X, Y) >= plus(X, Y) because plus in Mul, [26] and [20], by (Fun) 34] plus(X, Y) >= plus(X, Y) because plus in Mul, [16] and [28], by (Fun) 35] plus(X, Y) >= plus(X, Y) because plus in Mul, [30] and [20], by (Fun) 36] plus(X, Y) >= plus(X, Y) because plus in Mul, [16] and [32], by (Fun) 37] s(X) >= s(X) because s in Mul and [38], by (Fun) 38] X >= X by (Meta) 39] s(X) >= s(X) because s in Mul and [40], by (Fun) 40] X >= X by (Meta) 41] x(X, Y) >= x(X, Y) because x in Mul, [26] and [20], by (Fun) 42] x(X, Y) >= x(X, Y) because x in Mul, [16] and [28], by (Fun) 43] x(X, Y) >= x(X, Y) because x in Mul, [30] and [20], by (Fun) 44] x(X, Y) >= x(X, Y) because x in Mul, [16] and [32], by (Fun) We can thus remove the following rules: active(x(X, 0)) => mark(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]): active(plus(X, s(Y))) >? mark(s(plus(X, Y))) active(x(X, s(Y))) >? mark(plus(x(X, Y), X)) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(plus(X, Y)) >? active(plus(mark(X), mark(Y))) mark(0) >? active(0) mark(s(X)) >? active(s(mark(X))) mark(x(X, Y)) >? active(x(mark(X), mark(Y))) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[active(x_1)]] = x_1 [[mark(x_1)]] = x_1 We choose Lex = {} and Mul = {0, and, plus, s, tt, x}, and the following precedence: and > 0 > x > tt > plus > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: plus(X, s(Y)) >= s(plus(X, Y)) x(X, s(Y)) > plus(x(X, Y), X) and(X, Y) >= and(X, Y) tt >= tt plus(X, Y) >= plus(X, Y) 0 >= 0 s(X) >= s(X) x(X, Y) >= x(X, Y) and(X, Y) >= and(X, Y) and(X, Y) >= and(X, Y) and(X, Y) >= and(X, Y) and(X, Y) >= and(X, Y) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) s(X) >= s(X) s(X) >= s(X) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) With these choices, we have: 1] plus(X, s(Y)) >= s(plus(X, Y)) because [2], by (Star) 2] plus*(X, s(Y)) >= s(plus(X, Y)) because plus > s and [3], by (Copy) 3] plus*(X, s(Y)) >= plus(X, Y) because plus in Mul, [4] and [5], by (Stat) 4] X >= X by (Meta) 5] s(Y) > Y because [6], by definition 6] s*(Y) >= Y because [7], by (Select) 7] Y >= Y by (Meta) 8] x(X, s(Y)) > plus(x(X, Y), X) because [9], by definition 9] x*(X, s(Y)) >= plus(x(X, Y), X) because x > plus, [10] and [11], by (Copy) 10] x*(X, s(Y)) >= x(X, Y) because x in Mul, [4] and [5], by (Stat) 11] x*(X, s(Y)) >= X because [4], by (Select) 12] and(X, Y) >= and(X, Y) because and in Mul, [13] and [14], by (Fun) 13] X >= X by (Meta) 14] Y >= Y by (Meta) 15] tt >= tt by (Fun) 16] plus(X, Y) >= plus(X, Y) because plus in Mul, [13] and [17], by (Fun) 17] Y >= Y by (Meta) 18] 0 >= 0 by (Fun) 19] s(X) >= s(X) because s in Mul and [20], by (Fun) 20] X >= X by (Meta) 21] x(X, Y) >= x(X, Y) because x in Mul, [13] and [17], by (Fun) 22] and(X, Y) >= and(X, Y) because and in Mul, [23] and [17], by (Fun) 23] X >= X by (Meta) 24] and(X, Y) >= and(X, Y) because and in Mul, [13] and [25], by (Fun) 25] Y >= Y by (Meta) 26] and(X, Y) >= and(X, Y) because and in Mul, [27] and [17], by (Fun) 27] X >= X by (Meta) 28] and(X, Y) >= and(X, Y) because and in Mul, [13] and [29], by (Fun) 29] Y >= Y by (Meta) 30] plus(X, Y) >= plus(X, Y) because plus in Mul, [23] and [17], by (Fun) 31] plus(X, Y) >= plus(X, Y) because plus in Mul, [13] and [25], by (Fun) 32] plus(X, Y) >= plus(X, Y) because plus in Mul, [27] and [17], by (Fun) 33] plus(X, Y) >= plus(X, Y) because plus in Mul, [13] and [29], by (Fun) 34] s(X) >= s(X) because s in Mul and [35], by (Fun) 35] X >= X by (Meta) 36] s(X) >= s(X) because s in Mul and [37], by (Fun) 37] X >= X by (Meta) 38] x(X, Y) >= x(X, Y) because x in Mul, [23] and [17], by (Fun) 39] x(X, Y) >= x(X, Y) because x in Mul, [13] and [25], by (Fun) 40] x(X, Y) >= x(X, Y) because x in Mul, [27] and [17], by (Fun) 41] x(X, Y) >= x(X, Y) because x in Mul, [13] and [29], by (Fun) We can thus remove the following rules: active(x(X, s(Y))) => mark(plus(x(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]): active(plus(X, s(Y))) >? mark(s(plus(X, Y))) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(plus(X, Y)) >? active(plus(mark(X), mark(Y))) mark(0) >? active(0) mark(s(X)) >? active(s(mark(X))) mark(x(X, Y)) >? active(x(mark(X), mark(Y))) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 and = \y0y1.y0 + 2y1 mark = \y0.y0 plus = \y0y1.y0 + 2y1 s = \y0.1 + y0 tt = 0 x = \y0y1.y0 + 2y1 Using this interpretation, the requirements translate to: [[active(plus(_x0, s(_x1)))]] = 2 + x0 + 2x1 > 1 + x0 + 2x1 = [[mark(s(plus(_x0, _x1)))]] [[mark(and(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(plus(mark(_x0), mark(_x1)))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(s(_x0))]] = 1 + x0 >= 1 + x0 = [[active(s(mark(_x0)))]] [[mark(x(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(x(mark(_x0), mark(_x1)))]] [[and(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[plus(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, _x1)]] [[s(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[s(_x0)]] [[s(active(_x0))]] = 1 + x0 >= 1 + x0 = [[s(_x0)]] [[x(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[x(_x0, _x1)]] [[x(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[x(_x0, _x1)]] [[x(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[x(_x0, _x1)]] [[x(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[x(_x0, _x1)]] We can thus remove the following rules: active(plus(X, s(Y))) => mark(s(plus(X, 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]): mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(plus(X, Y)) >? active(plus(mark(X), mark(Y))) mark(0) >? active(0) mark(s(X)) >? active(s(mark(X))) mark(x(X, Y)) >? active(x(mark(X), mark(Y))) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 2 active = \y0.y0 and = \y0y1.2y0 + 2y1 mark = \y0.2y0 plus = \y0y1.2y0 + 2y1 s = \y0.2y0 tt = 0 x = \y0y1.2y0 + 2y1 Using this interpretation, the requirements translate to: [[mark(and(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(plus(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[active(plus(mark(_x0), mark(_x1)))]] [[mark(0)]] = 4 > 2 = [[active(0)]] [[mark(s(_x0))]] = 4x0 >= 4x0 = [[active(s(mark(_x0)))]] [[mark(x(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[active(x(mark(_x0), mark(_x1)))]] [[and(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[plus(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[s(mark(_x0))]] = 4x0 >= 2x0 = [[s(_x0)]] [[s(active(_x0))]] = 2x0 >= 2x0 = [[s(_x0)]] [[x(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[x(_x0, _x1)]] [[x(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[x(_x0, _x1)]] [[x(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, _x1)]] [[x(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, _x1)]] We can thus remove the following rules: mark(0) => active(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]): mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(plus(X, Y)) >? active(plus(mark(X), mark(Y))) mark(s(X)) >? active(s(mark(X))) mark(x(X, Y)) >? active(x(mark(X), mark(Y))) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: active = \y0.y0 and = \y0y1.2 + y0 + y1 mark = \y0.2y0 plus = \y0y1.y0 + 2y1 s = \y0.2y0 tt = 0 x = \y0y1.2y0 + 2y1 Using this interpretation, the requirements translate to: [[mark(and(_x0, _x1))]] = 4 + 2x0 + 2x1 > 2 + x1 + 2x0 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(plus(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[active(plus(mark(_x0), mark(_x1)))]] [[mark(s(_x0))]] = 4x0 >= 4x0 = [[active(s(mark(_x0)))]] [[mark(x(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[active(x(mark(_x0), mark(_x1)))]] [[and(mark(_x0), _x1)]] = 2 + x1 + 2x0 >= 2 + x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 2 + x0 + 2x1 >= 2 + x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[and(_x0, _x1)]] [[plus(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, _x1)]] [[s(mark(_x0))]] = 4x0 >= 2x0 = [[s(_x0)]] [[s(active(_x0))]] = 2x0 >= 2x0 = [[s(_x0)]] [[x(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[x(_x0, _x1)]] [[x(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[x(_x0, _x1)]] [[x(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, _x1)]] [[x(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, _x1)]] We can thus remove the following rules: mark(and(X, Y)) => active(and(mark(X), 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]): mark(tt) >? active(tt) mark(plus(X, Y)) >? active(plus(mark(X), mark(Y))) mark(s(X)) >? active(s(mark(X))) mark(x(X, Y)) >? active(x(mark(X), mark(Y))) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: active = \y0.y0 and = \y0y1.2y0 + 2y1 mark = \y0.2y0 plus = \y0y1.y0 + y1 s = \y0.y0 tt = 2 x = \y0y1.2y0 + 2y1 Using this interpretation, the requirements translate to: [[mark(tt)]] = 4 > 2 = [[active(tt)]] [[mark(plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(plus(mark(_x0), mark(_x1)))]] [[mark(s(_x0))]] = 2x0 >= 2x0 = [[active(s(mark(_x0)))]] [[mark(x(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[active(x(mark(_x0), mark(_x1)))]] [[and(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[plus(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[plus(_x0, _x1)]] [[s(mark(_x0))]] = 2x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[x(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[x(_x0, _x1)]] [[x(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[x(_x0, _x1)]] [[x(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, _x1)]] [[x(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, _x1)]] We can thus remove the following rules: mark(tt) => active(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]): mark(plus(X, Y)) >? active(plus(mark(X), mark(Y))) mark(s(X)) >? active(s(mark(X))) mark(x(X, Y)) >? active(x(mark(X), mark(Y))) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: active = \y0.y0 and = \y0y1.y1 + 2y0 mark = \y0.2y0 plus = \y0y1.2y0 + 2y1 s = \y0.2y0 x = \y0y1.1 + y1 + 2y0 Using this interpretation, the requirements translate to: [[mark(plus(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[active(plus(mark(_x0), mark(_x1)))]] [[mark(s(_x0))]] = 4x0 >= 4x0 = [[active(s(mark(_x0)))]] [[mark(x(_x0, _x1))]] = 2 + 2x1 + 4x0 > 1 + 2x1 + 4x0 = [[active(x(mark(_x0), mark(_x1)))]] [[and(mark(_x0), _x1)]] = x1 + 4x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[plus(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, _x1)]] [[s(mark(_x0))]] = 4x0 >= 2x0 = [[s(_x0)]] [[s(active(_x0))]] = 2x0 >= 2x0 = [[s(_x0)]] [[x(mark(_x0), _x1)]] = 1 + x1 + 4x0 >= 1 + x1 + 2x0 = [[x(_x0, _x1)]] [[x(_x0, mark(_x1))]] = 1 + 2x0 + 2x1 >= 1 + x1 + 2x0 = [[x(_x0, _x1)]] [[x(active(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[x(_x0, _x1)]] [[x(_x0, active(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[x(_x0, _x1)]] We can thus remove the following rules: mark(x(X, Y)) => active(x(mark(X), mark(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]): mark(plus(X, Y)) >? active(plus(mark(X), mark(Y))) mark(s(X)) >? active(s(mark(X))) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: active = \y0.y0 and = \y0y1.y1 + 2y0 mark = \y0.2y0 plus = \y0y1.y1 + 2y0 s = \y0.2 + y0 x = \y0y1.y1 + 2y0 Using this interpretation, the requirements translate to: [[mark(plus(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[active(plus(mark(_x0), mark(_x1)))]] [[mark(s(_x0))]] = 4 + 2x0 > 2 + 2x0 = [[active(s(mark(_x0)))]] [[and(mark(_x0), _x1)]] = x1 + 4x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[plus(mark(_x0), _x1)]] = x1 + 4x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, _x1)]] [[s(mark(_x0))]] = 2 + 2x0 >= 2 + x0 = [[s(_x0)]] [[s(active(_x0))]] = 2 + x0 >= 2 + x0 = [[s(_x0)]] [[x(mark(_x0), _x1)]] = x1 + 4x0 >= x1 + 2x0 = [[x(_x0, _x1)]] [[x(_x0, mark(_x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[x(_x0, _x1)]] [[x(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[x(_x0, _x1)]] [[x(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[x(_x0, _x1)]] We can thus remove the following rules: mark(s(X)) => active(s(mark(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]): mark(plus(X, Y)) >? active(plus(mark(X), mark(Y))) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: active = \y0.y0 and = \y0y1.y0 + y1 mark = \y0.2y0 plus = \y0y1.1 + 2y0 + 2y1 s = \y0.y0 x = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[mark(plus(_x0, _x1))]] = 2 + 4x0 + 4x1 > 1 + 4x0 + 4x1 = [[active(plus(mark(_x0), mark(_x1)))]] [[and(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[plus(mark(_x0), _x1)]] = 1 + 2x1 + 4x0 >= 1 + 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = 1 + 2x0 + 4x1 >= 1 + 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[plus(_x0, _x1)]] [[s(mark(_x0))]] = 2x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[x(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[x(_x0, _x1)]] [[x(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[x(_x0, _x1)]] [[x(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[x(_x0, _x1)]] [[x(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[x(_x0, _x1)]] We can thus remove the following rules: mark(plus(X, Y)) => active(plus(mark(X), mark(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]): and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) plus(mark(X), Y) >? plus(X, Y) plus(X, mark(Y)) >? plus(X, Y) plus(active(X), Y) >? plus(X, Y) plus(X, active(Y)) >? plus(X, Y) s(mark(X)) >? s(X) s(active(X)) >? s(X) x(mark(X), Y) >? x(X, Y) x(X, mark(Y)) >? x(X, Y) x(active(X), Y) >? x(X, Y) x(X, active(Y)) >? x(X, Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: active = \y0.3 + 3y0 and = \y0y1.y0 + y1 mark = \y0.3 + 3y0 plus = \y0y1.y0 + y1 s = \y0.y0 x = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[and(mark(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[and(_x0, _x1)]] [[plus(mark(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[plus(_x0, _x1)]] [[plus(_x0, mark(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[plus(_x0, _x1)]] [[plus(active(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[plus(_x0, _x1)]] [[plus(_x0, active(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[plus(_x0, _x1)]] [[s(mark(_x0))]] = 3 + 3x0 > x0 = [[s(_x0)]] [[s(active(_x0))]] = 3 + 3x0 > x0 = [[s(_x0)]] [[x(mark(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[x(_x0, _x1)]] [[x(_x0, mark(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[x(_x0, _x1)]] [[x(active(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[x(_x0, _x1)]] [[x(_x0, active(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[x(_x0, _x1)]] We can thus remove the following rules: and(mark(X), Y) => and(X, Y) and(X, mark(Y)) => and(X, Y) and(active(X), Y) => and(X, Y) and(X, active(Y)) => and(X, Y) plus(mark(X), Y) => plus(X, Y) plus(X, mark(Y)) => plus(X, Y) plus(active(X), Y) => plus(X, Y) plus(X, active(Y)) => plus(X, Y) s(mark(X)) => s(X) s(active(X)) => s(X) x(mark(X), Y) => x(X, Y) x(X, mark(Y)) => x(X, Y) x(active(X), Y) => x(X, Y) x(X, active(Y)) => x(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.