/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. a : [o * o * o] --> o app : [o * o] --> o cons : [o * o] --> o h : [] --> o nil : [] --> o s : [o] --> o sum : [o] --> o app(nil, X) => X app(X, nil) => X app(cons(X, Y), Z) => cons(X, app(Y, Z)) sum(cons(X, nil)) => cons(X, nil) sum(cons(X, cons(Y, Z))) => sum(cons(a(X, Y, h), Z)) a(h, h, X) => s(X) a(X, s(Y), h) => a(X, Y, s(h)) a(X, s(Y), s(Z)) => a(X, Y, a(X, s(Y), Z)) a(s(X), h, Y) => a(X, Y, 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]): app(nil, X) >? X app(X, nil) >? X app(cons(X, Y), Z) >? cons(X, app(Y, Z)) sum(cons(X, nil)) >? cons(X, nil) sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h), Z)) a(h, h, X) >? s(X) a(X, s(Y), h) >? a(X, Y, s(h)) a(X, s(Y), s(Z)) >? a(X, Y, a(X, s(Y), Z)) a(s(X), h, Y) >? a(X, Y, Y) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[cons(x_1, x_2)]] = cons(x_2, x_1) [[h]] = _|_ We choose Lex = {a, cons} and Mul = {app, nil, s, sum}, and the following precedence: nil > sum > app > cons > a > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: app(nil, X) >= X app(X, nil) > X app(cons(X, Y), Z) > cons(X, app(Y, Z)) sum(cons(X, nil)) >= cons(X, nil) sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_), Z)) a(_|_, _|_, X) >= s(X) a(X, s(Y), _|_) > a(X, Y, s(_|_)) a(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) a(s(X), _|_, Y) >= a(X, Y, Y) With these choices, we have: 1] app(nil, X) >= X because [2], by (Star) 2] app*(nil, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] app(X, nil) > X because [5], by definition 5] app*(X, nil) >= X because [6], by (Select) 6] X >= X by (Meta) 7] app(cons(X, Y), Z) > cons(X, app(Y, Z)) because [8], by definition 8] app*(cons(X, Y), Z) >= cons(X, app(Y, Z)) because app > cons, [9] and [13], by (Copy) 9] app*(cons(X, Y), Z) >= X because [10], by (Select) 10] cons(X, Y) >= X because [11], by (Star) 11] cons*(X, Y) >= X because [12], by (Select) 12] X >= X by (Meta) 13] app*(cons(X, Y), Z) >= app(Y, Z) because app in Mul, [14] and [16], by (Stat) 14] cons(X, Y) > Y because [15], by definition 15] cons*(X, Y) >= Y because [6], by (Select) 16] Z >= Z by (Meta) 17] sum(cons(X, nil)) >= cons(X, nil) because [18], by (Star) 18] sum*(cons(X, nil)) >= cons(X, nil) because [19], by (Select) 19] cons(X, nil) >= cons(X, nil) because [20] and [21], by (Fun) 20] X >= X by (Meta) 21] nil >= nil by (Fun) 22] sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_), Z)) because sum in Mul and [23], by (Fun) 23] cons(X, cons(Y, Z)) >= cons(a(X, Y, _|_), Z) because [24], by (Star) 24] cons*(X, cons(Y, Z)) >= cons(a(X, Y, _|_), Z) because [25], [27] and [34], by (Stat) 25] cons(Y, Z) > Z because [26], by definition 26] cons*(Y, Z) >= Z because [6], by (Select) 27] cons*(X, cons(Y, Z)) >= a(X, Y, _|_) because cons > a, [28], [29] and [33], by (Copy) 28] cons*(X, cons(Y, Z)) >= X because [20], by (Select) 29] cons*(X, cons(Y, Z)) >= Y because [30], by (Select) 30] cons(Y, Z) >= Y because [31], by (Star) 31] cons*(Y, Z) >= Y because [32], by (Select) 32] Y >= Y by (Meta) 33] cons*(X, cons(Y, Z)) >= _|_ by (Bot) 34] cons*(X, cons(Y, Z)) >= Z because [35], by (Select) 35] cons(Y, Z) >= Z because [26], by (Star) 36] a(_|_, _|_, X) >= s(X) because [37], by (Star) 37] a*(_|_, _|_, X) >= s(X) because a > s and [38], by (Copy) 38] a*(_|_, _|_, X) >= X because [20], by (Select) 39] a(X, s(Y), _|_) > a(X, Y, s(_|_)) because [40], by definition 40] a*(X, s(Y), _|_) >= a(X, Y, s(_|_)) because [20], [41], [43], [44] and [46], by (Stat) 41] s(Y) > Y because [42], by definition 42] s*(Y) >= Y because [32], by (Select) 43] a*(X, s(Y), _|_) >= X because [20], by (Select) 44] a*(X, s(Y), _|_) >= Y because [45], by (Select) 45] s(Y) >= Y because [42], by (Star) 46] a*(X, s(Y), _|_) >= s(_|_) because a > s and [47], by (Copy) 47] a*(X, s(Y), _|_) >= _|_ by (Bot) 48] a(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) because [49], by (Star) 49] a*(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) because [20], [41], [50], [51] and [52], by (Stat) 50] a*(X, s(Y), s(Z)) >= X because [20], by (Select) 51] a*(X, s(Y), s(Z)) >= Y because [45], by (Select) 52] a*(X, s(Y), s(Z)) >= a(X, s(Y), Z) because [20], [53], [55], [50], [58] and [59], by (Stat) 53] s(Y) >= s(Y) because s in Mul and [54], by (Fun) 54] Y >= Y by (Meta) 55] s(Z) > Z because [56], by definition 56] s*(Z) >= Z because [57], by (Select) 57] Z >= Z by (Meta) 58] a*(X, s(Y), s(Z)) >= s(Y) because a > s and [51], by (Copy) 59] a*(X, s(Y), s(Z)) >= Z because [60], by (Select) 60] s(Z) >= Z because [56], by (Star) 61] a(s(X), _|_, Y) >= a(X, Y, Y) because [62], by (Star) 62] a*(s(X), _|_, Y) >= a(X, Y, Y) because [63], [65], [67] and [67], by (Stat) 63] s(X) > X because [64], by definition 64] s*(X) >= X because [20], by (Select) 65] a*(s(X), _|_, Y) >= X because [66], by (Select) 66] s(X) >= X because [64], by (Star) 67] a*(s(X), _|_, Y) >= Y because [57], by (Select) We can thus remove the following rules: app(X, nil) => X app(cons(X, Y), Z) => cons(X, app(Y, Z)) a(X, s(Y), h) => a(X, Y, s(h)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): app(nil, X) >? X sum(cons(X, nil)) >? cons(X, nil) sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h), Z)) a(h, h, X) >? s(X) a(X, s(Y), s(Z)) >? a(X, Y, a(X, s(Y), Z)) a(s(X), h, Y) >? a(X, Y, Y) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[cons(x_1, x_2)]] = cons(x_2, x_1) [[h]] = _|_ [[nil]] = _|_ We choose Lex = {a, cons} and Mul = {app, s, sum}, and the following precedence: app > cons > a > s > sum Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: app(_|_, X) >= X sum(cons(X, _|_)) > cons(X, _|_) sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_), Z)) a(_|_, _|_, X) >= s(X) a(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) a(s(X), _|_, Y) > a(X, Y, Y) With these choices, we have: 1] app(_|_, X) >= X because [2], by (Star) 2] app*(_|_, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] sum(cons(X, _|_)) > cons(X, _|_) because [5], by definition 5] sum*(cons(X, _|_)) >= cons(X, _|_) because [6], by (Select) 6] cons(X, _|_) >= cons(X, _|_) because [7] and [8], by (Fun) 7] X >= X by (Meta) 8] _|_ >= _|_ by (Bot) 9] sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_), Z)) because [10], by (Star) 10] sum*(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_), Z)) because sum in Mul and [11], by (Stat) 11] cons(X, cons(Y, Z)) > cons(a(X, Y, _|_), Z) because [12], by definition 12] cons*(X, cons(Y, Z)) >= cons(a(X, Y, _|_), Z) because [13], [16] and [23], by (Stat) 13] cons(Y, Z) > Z because [14], by definition 14] cons*(Y, Z) >= Z because [15], by (Select) 15] Z >= Z by (Meta) 16] cons*(X, cons(Y, Z)) >= a(X, Y, _|_) because cons > a, [17], [18] and [22], by (Copy) 17] cons*(X, cons(Y, Z)) >= X because [7], by (Select) 18] cons*(X, cons(Y, Z)) >= Y because [19], by (Select) 19] cons(Y, Z) >= Y because [20], by (Star) 20] cons*(Y, Z) >= Y because [21], by (Select) 21] Y >= Y by (Meta) 22] cons*(X, cons(Y, Z)) >= _|_ by (Bot) 23] cons*(X, cons(Y, Z)) >= Z because [24], by (Select) 24] cons(Y, Z) >= Z because [14], by (Star) 25] a(_|_, _|_, X) >= s(X) because [26], by (Star) 26] a*(_|_, _|_, X) >= s(X) because a > s and [27], by (Copy) 27] a*(_|_, _|_, X) >= X because [7], by (Select) 28] a(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) because [29], by (Star) 29] a*(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) because [7], [30], [32], [33] and [35], by (Stat) 30] s(Y) > Y because [31], by definition 31] s*(Y) >= Y because [21], by (Select) 32] a*(X, s(Y), s(Z)) >= X because [7], by (Select) 33] a*(X, s(Y), s(Z)) >= Y because [34], by (Select) 34] s(Y) >= Y because [31], by (Star) 35] a*(X, s(Y), s(Z)) >= a(X, s(Y), Z) because [7], [36], [38], [32], [41] and [42], by (Stat) 36] s(Y) >= s(Y) because s in Mul and [37], by (Fun) 37] Y >= Y by (Meta) 38] s(Z) > Z because [39], by definition 39] s*(Z) >= Z because [40], by (Select) 40] Z >= Z by (Meta) 41] a*(X, s(Y), s(Z)) >= s(Y) because a > s and [33], by (Copy) 42] a*(X, s(Y), s(Z)) >= Z because [43], by (Select) 43] s(Z) >= Z because [39], by (Star) 44] a(s(X), _|_, Y) > a(X, Y, Y) because [45], by definition 45] a*(s(X), _|_, Y) >= a(X, Y, Y) because [46], [48], [50] and [50], by (Stat) 46] s(X) > X because [47], by definition 47] s*(X) >= X because [7], by (Select) 48] a*(s(X), _|_, Y) >= X because [49], by (Select) 49] s(X) >= X because [47], by (Star) 50] a*(s(X), _|_, Y) >= Y because [40], by (Select) We can thus remove the following rules: sum(cons(X, nil)) => cons(X, nil) a(s(X), h, Y) => a(X, Y, 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]): app(nil, X) >? X sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h), Z)) a(h, h, X) >? s(X) a(X, s(Y), s(Z)) >? a(X, Y, a(X, s(Y), Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[cons(x_1, x_2)]] = cons(x_2, x_1) [[h]] = _|_ We choose Lex = {a, cons} and Mul = {app, nil, s, sum}, and the following precedence: cons > sum > a > s > nil > app Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: app(nil, X) > X sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_), Z)) a(_|_, _|_, X) >= s(X) a(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) With these choices, we have: 1] app(nil, X) > X because [2], by definition 2] app*(nil, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_), Z)) because sum in Mul and [5], by (Fun) 5] cons(X, cons(Y, Z)) >= cons(a(X, Y, _|_), Z) because [6], by (Star) 6] cons*(X, cons(Y, Z)) >= cons(a(X, Y, _|_), Z) because [7], [10] and [18], by (Stat) 7] cons(Y, Z) > Z because [8], by definition 8] cons*(Y, Z) >= Z because [9], by (Select) 9] Z >= Z by (Meta) 10] cons*(X, cons(Y, Z)) >= a(X, Y, _|_) because cons > a, [11], [13] and [17], by (Copy) 11] cons*(X, cons(Y, Z)) >= X because [12], by (Select) 12] X >= X by (Meta) 13] cons*(X, cons(Y, Z)) >= Y because [14], by (Select) 14] cons(Y, Z) >= Y because [15], by (Star) 15] cons*(Y, Z) >= Y because [16], by (Select) 16] Y >= Y by (Meta) 17] cons*(X, cons(Y, Z)) >= _|_ by (Bot) 18] cons*(X, cons(Y, Z)) >= Z because [19], by (Select) 19] cons(Y, Z) >= Z because [8], by (Star) 20] a(_|_, _|_, X) >= s(X) because [21], by (Star) 21] a*(_|_, _|_, X) >= s(X) because a > s and [22], by (Copy) 22] a*(_|_, _|_, X) >= X because [12], by (Select) 23] a(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) because [24], by (Star) 24] a*(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) because [25], [26], [28], [29] and [31], by (Stat) 25] X >= X by (Meta) 26] s(Y) > Y because [27], by definition 27] s*(Y) >= Y because [16], by (Select) 28] a*(X, s(Y), s(Z)) >= X because [25], by (Select) 29] a*(X, s(Y), s(Z)) >= Y because [30], by (Select) 30] s(Y) >= Y because [27], by (Star) 31] a*(X, s(Y), s(Z)) >= a(X, s(Y), Z) because [25], [32], [34], [28], [37] and [38], by (Stat) 32] s(Y) >= s(Y) because s in Mul and [33], by (Fun) 33] Y >= Y by (Meta) 34] s(Z) > Z because [35], by definition 35] s*(Z) >= Z because [36], by (Select) 36] Z >= Z by (Meta) 37] a*(X, s(Y), s(Z)) >= s(Y) because a > s and [29], by (Copy) 38] a*(X, s(Y), s(Z)) >= Z because [39], by (Select) 39] s(Z) >= Z because [35], by (Star) We can thus remove the following rules: app(nil, 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]): sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h), Z)) a(h, h, X) >? s(X) a(X, s(Y), s(Z)) >? a(X, Y, a(X, s(Y), Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[a(x_1, x_2, x_3)]] = a(x_2, x_3, x_1) [[cons(x_1, x_2)]] = cons(x_2, x_1) [[h]] = _|_ [[sum(x_1)]] = x_1 We choose Lex = {a, cons} and Mul = {s}, and the following precedence: a = cons > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: cons(X, cons(Y, Z)) > cons(a(X, Y, _|_), Z) a(_|_, _|_, X) > s(X) a(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) With these choices, we have: 1] cons(X, cons(Y, Z)) > cons(a(X, Y, _|_), Z) because [2], by definition 2] cons*(X, cons(Y, Z)) >= cons(a(X, Y, _|_), Z) because [3], [6] and [15], by (Stat) 3] cons(Y, Z) > Z because [4], by definition 4] cons*(Y, Z) >= Z because [5], by (Select) 5] Z >= Z by (Meta) 6] cons*(X, cons(Y, Z)) >= a(X, Y, _|_) because cons = a, [7], [10], [12] and [14], by (Stat) 7] cons(Y, Z) > Y because [8], by definition 8] cons*(Y, Z) >= Y because [9], by (Select) 9] Y >= Y by (Meta) 10] cons*(X, cons(Y, Z)) >= X because [11], by (Select) 11] X >= X by (Meta) 12] cons*(X, cons(Y, Z)) >= Y because [13], by (Select) 13] cons(Y, Z) >= Y because [8], by (Star) 14] cons*(X, cons(Y, Z)) >= _|_ by (Bot) 15] cons*(X, cons(Y, Z)) >= Z because [16], by (Select) 16] cons(Y, Z) >= Z because [4], by (Star) 17] a(_|_, _|_, X) > s(X) because [18], by definition 18] a*(_|_, _|_, X) >= s(X) because a > s and [19], by (Copy) 19] a*(_|_, _|_, X) >= X because [11], by (Select) 20] a(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) because [21], by (Star) 21] a*(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) because [22], [24], [25] and [27], by (Stat) 22] s(Y) > Y because [23], by definition 23] s*(Y) >= Y because [9], by (Select) 24] a*(X, s(Y), s(Z)) >= X because [11], by (Select) 25] a*(X, s(Y), s(Z)) >= Y because [26], by (Select) 26] s(Y) >= Y because [23], by (Star) 27] a*(X, s(Y), s(Z)) >= a(X, s(Y), Z) because [28], [30], [24], [33] and [34], by (Stat) 28] s(Y) >= s(Y) because s in Mul and [29], by (Fun) 29] Y >= Y by (Meta) 30] s(Z) > Z because [31], by definition 31] s*(Z) >= Z because [32], by (Select) 32] Z >= Z by (Meta) 33] a*(X, s(Y), s(Z)) >= s(Y) because a > s and [25], by (Copy) 34] a*(X, s(Y), s(Z)) >= Z because [35], by (Select) 35] s(Z) >= Z because [31], by (Star) We can thus remove the following rules: sum(cons(X, cons(Y, Z))) => sum(cons(a(X, Y, h), Z)) a(h, h, X) => s(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]): a(X, s(Y), s(Z)) >? a(X, Y, a(X, s(Y), Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[a(x_1, x_2, x_3)]] = a(x_2, x_3, x_1) We choose Lex = {a} and Mul = {s}, and the following precedence: s > a Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a(X, s(Y), s(Z)) > a(X, Y, a(X, s(Y), Z)) With these choices, we have: 1] a(X, s(Y), s(Z)) > a(X, Y, a(X, s(Y), Z)) because [2], by definition 2] a*(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) because [3], [6], [8] and [10], by (Stat) 3] s(Y) > Y because [4], by definition 4] s*(Y) >= Y because [5], by (Select) 5] Y >= Y by (Meta) 6] a*(X, s(Y), s(Z)) >= X because [7], by (Select) 7] X >= X by (Meta) 8] a*(X, s(Y), s(Z)) >= Y because [9], by (Select) 9] s(Y) >= Y because [4], by (Star) 10] a*(X, s(Y), s(Z)) >= a(X, s(Y), Z) because [11], [13], [6], [16] and [17], by (Stat) 11] s(Y) >= s(Y) because s in Mul and [12], by (Fun) 12] Y >= Y by (Meta) 13] s(Z) > Z because [14], by definition 14] s*(Z) >= Z because [15], by (Select) 15] Z >= Z by (Meta) 16] a*(X, s(Y), s(Z)) >= s(Y) because [11], by (Select) 17] a*(X, s(Y), s(Z)) >= Z because [18], by (Select) 18] s(Z) >= Z because [14], by (Star) We can thus remove the following rules: a(X, s(Y), s(Z)) => a(X, Y, a(X, s(Y), Z)) 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.