/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. 0 : [] --> o f : [o * o * o] --> o s : [o] --> o f(X, 0, 0) => s(X) f(0, X, 0) => s(X) f(0, 0, X) => s(X) f(s(0), X, Y) => f(0, s(X), s(Y)) f(s(X), s(Y), 0) => f(X, Y, s(0)) f(s(X), 0, s(Y)) => f(X, s(0), Y) f(0, s(0), s(0)) => s(s(0)) f(s(X), s(Y), s(Z)) => f(X, Y, f(s(X), s(Y), Z)) f(0, s(s(X)), s(0)) => f(0, X, s(0)) f(0, s(0), s(s(X))) => f(0, s(0), X) f(0, s(s(X)), s(s(Y))) => f(0, X, f(0, s(s(X)), s(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]): f(X, 0, 0) >? s(X) f(0, X, 0) >? s(X) f(0, 0, X) >? s(X) f(s(0), X, Y) >? f(0, s(X), s(Y)) f(s(X), s(Y), 0) >? f(X, Y, s(0)) f(s(X), 0, s(Y)) >? f(X, s(0), Y) f(0, s(0), s(0)) >? s(s(0)) f(s(X), s(Y), s(Z)) >? f(X, Y, f(s(X), s(Y), Z)) f(0, s(s(X)), s(0)) >? f(0, X, s(0)) f(0, s(0), s(s(X))) >? f(0, s(0), X) f(0, s(s(X)), s(s(Y))) >? f(0, X, f(0, s(s(X)), s(Y))) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {f} and Mul = {0, s}, and the following precedence: f > s > 0 With these choices, we have: 1] f(X, 0, 0) >= s(X) because [2], by (Star) 2] f*(X, 0, 0) >= s(X) because f > s and [3], by (Copy) 3] f*(X, 0, 0) >= X because [4], by (Select) 4] X >= X by (Meta) 5] f(0, X, 0) > s(X) because [6], by definition 6] f*(0, X, 0) >= s(X) because f > s and [7], by (Copy) 7] f*(0, X, 0) >= X because [8], by (Select) 8] X >= X by (Meta) 9] f(0, 0, X) > s(X) because [10], by definition 10] f*(0, 0, X) >= s(X) because f > s and [11], by (Copy) 11] f*(0, 0, X) >= X because [12], by (Select) 12] X >= X by (Meta) 13] f(s(0), X, Y) >= f(0, s(X), s(Y)) because [14], by (Star) 14] f*(s(0), X, Y) >= f(0, s(X), s(Y)) because [15], [17], [18] and [20], by (Stat) 15] s(0) > 0 because [16], by definition 16] s*(0) >= 0 because s > 0, by (Copy) 17] f*(s(0), X, Y) >= 0 because f > 0, by (Copy) 18] f*(s(0), X, Y) >= s(X) because f > s and [19], by (Copy) 19] f*(s(0), X, Y) >= X because [8], by (Select) 20] f*(s(0), X, Y) >= s(Y) because f > s and [21], by (Copy) 21] f*(s(0), X, Y) >= Y because [12], by (Select) 22] f(s(X), s(Y), 0) >= f(X, Y, s(0)) because [23], by (Star) 23] f*(s(X), s(Y), 0) >= f(X, Y, s(0)) because [24], [26], [28] and [31], by (Stat) 24] s(X) > X because [25], by definition 25] s*(X) >= X because [4], by (Select) 26] f*(s(X), s(Y), 0) >= X because [27], by (Select) 27] s(X) >= X because [25], by (Star) 28] f*(s(X), s(Y), 0) >= Y because [29], by (Select) 29] s(Y) >= Y because [30], by (Star) 30] s*(Y) >= Y because [8], by (Select) 31] f*(s(X), s(Y), 0) >= s(0) because f > s and [32], by (Copy) 32] f*(s(X), s(Y), 0) >= 0 because f > 0, by (Copy) 33] f(s(X), 0, s(Y)) >= f(X, s(0), Y) because [34], by (Star) 34] f*(s(X), 0, s(Y)) >= f(X, s(0), Y) because [24], [35], [36] and [38], by (Stat) 35] f*(s(X), 0, s(Y)) >= X because [27], by (Select) 36] f*(s(X), 0, s(Y)) >= s(0) because f > s and [37], by (Copy) 37] f*(s(X), 0, s(Y)) >= 0 because f > 0, by (Copy) 38] f*(s(X), 0, s(Y)) >= Y because [39], by (Select) 39] s(Y) >= Y because [40], by (Star) 40] s*(Y) >= Y because [12], by (Select) 41] f(0, s(0), s(0)) >= s(s(0)) because [42], by (Star) 42] f*(0, s(0), s(0)) >= s(s(0)) because f > s and [43], by (Copy) 43] f*(0, s(0), s(0)) >= s(0) because [44], by (Select) 44] s(0) >= s(0) because s in Mul and [45], by (Fun) 45] 0 >= 0 by (Fun) 46] f(s(X), s(Y), s(Z)) > f(X, Y, f(s(X), s(Y), Z)) because [47], by definition 47] f*(s(X), s(Y), s(Z)) >= f(X, Y, f(s(X), s(Y), Z)) because [24], [48], [49] and [50], by (Stat) 48] f*(s(X), s(Y), s(Z)) >= X because [27], by (Select) 49] f*(s(X), s(Y), s(Z)) >= Y because [29], by (Select) 50] f*(s(X), s(Y), s(Z)) >= f(s(X), s(Y), Z) because [51], [53], [55], [57], [58] and [59], by (Stat) 51] s(X) >= s(X) because s in Mul and [52], by (Fun) 52] X >= X by (Meta) 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 [12], by (Select) 57] f*(s(X), s(Y), s(Z)) >= s(X) because f > s and [48], by (Copy) 58] f*(s(X), s(Y), s(Z)) >= s(Y) because f > s and [49], by (Copy) 59] f*(s(X), s(Y), s(Z)) >= Z because [39], by (Select) 60] f(0, s(s(X)), s(0)) >= f(0, X, s(0)) because [45], [61] and [63], by (Fun) 61] s(s(X)) >= X because [62], by (Star) 62] s*(s(X)) >= X because [29], by (Select) 63] s(0) >= s(0) because s in Mul and [45], by (Fun) 64] f(0, s(0), s(s(X))) >= f(0, s(0), X) because [45], [63] and [65], by (Fun) 65] s(s(X)) >= X because [66], by (Star) 66] s*(s(X)) >= X because [39], by (Select) 67] f(0, s(s(X)), s(s(Y))) >= f(0, X, f(0, s(s(X)), s(Y))) because [68], by (Star) 68] f*(0, s(s(X)), s(s(Y))) >= f(0, X, f(0, s(s(X)), s(Y))) because [45], [69], [71], [72] and [73], by (Stat) 69] s(s(X)) > X because [70], by definition 70] s*(s(X)) >= X because [29], by (Select) 71] f*(0, s(s(X)), s(s(Y))) >= 0 because f > 0, by (Copy) 72] f*(0, s(s(X)), s(s(Y))) >= X because [61], by (Select) 73] f*(0, s(s(X)), s(s(Y))) >= f(0, s(s(X)), s(Y)) because [45], [74], [75], [71], [79] and [81], by (Stat) 74] s(s(X)) >= s(s(X)) because s in Mul and [53], by (Fun) 75] s(s(Y)) > s(Y) because [76], by definition 76] s*(s(Y)) >= s(Y) because [77], by (Select) 77] s(Y) >= s(Y) because s in Mul and [78], by (Fun) 78] Y >= Y by (Meta) 79] f*(0, s(s(X)), s(s(Y))) >= s(s(X)) because f > s and [80], by (Copy) 80] f*(0, s(s(X)), s(s(Y))) >= s(X) because f > s and [72], by (Copy) 81] f*(0, s(s(X)), s(s(Y))) >= s(Y) because f > s and [82], by (Copy) 82] f*(0, s(s(X)), s(s(Y))) >= Y because [65], by (Select) We can thus remove the following rules: f(0, X, 0) => s(X) f(0, 0, X) => s(X) f(s(X), s(Y), s(Z)) => f(X, Y, f(s(X), s(Y), Z)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): f(X, 0, 0) >? s(X) f(s(0), X, Y) >? f(0, s(X), s(Y)) f(s(X), s(Y), 0) >? f(X, Y, s(0)) f(s(X), 0, s(Y)) >? f(X, s(0), Y) f(0, s(0), s(0)) >? s(s(0)) f(0, s(s(X)), s(0)) >? f(0, X, s(0)) f(0, s(0), s(s(X))) >? f(0, s(0), X) f(0, s(s(X)), s(s(Y))) >? f(0, X, f(0, s(s(X)), s(Y))) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {f} and Mul = {0, s}, and the following precedence: f > s > 0 With these choices, we have: 1] f(X, 0, 0) >= s(X) because [2], by (Star) 2] f*(X, 0, 0) >= s(X) because f > s and [3], by (Copy) 3] f*(X, 0, 0) >= X because [4], by (Select) 4] X >= X by (Meta) 5] f(s(0), X, Y) >= f(0, s(X), s(Y)) because [6], by (Star) 6] f*(s(0), X, Y) >= f(0, s(X), s(Y)) because [7], [9], [10] and [13], by (Stat) 7] s(0) > 0 because [8], by definition 8] s*(0) >= 0 because s > 0, by (Copy) 9] f*(s(0), X, Y) >= 0 because f > 0, by (Copy) 10] f*(s(0), X, Y) >= s(X) because f > s and [11], by (Copy) 11] f*(s(0), X, Y) >= X because [12], by (Select) 12] X >= X by (Meta) 13] f*(s(0), X, Y) >= s(Y) because f > s and [14], by (Copy) 14] f*(s(0), X, Y) >= Y because [15], by (Select) 15] Y >= Y by (Meta) 16] f(s(X), s(Y), 0) >= f(X, Y, s(0)) because [17], by (Star) 17] f*(s(X), s(Y), 0) >= f(X, Y, s(0)) because [18], [20], [22] and [25], by (Stat) 18] s(X) > X because [19], by definition 19] s*(X) >= X because [4], by (Select) 20] f*(s(X), s(Y), 0) >= X because [21], by (Select) 21] s(X) >= X because [19], by (Star) 22] f*(s(X), s(Y), 0) >= Y because [23], by (Select) 23] s(Y) >= Y because [24], by (Star) 24] s*(Y) >= Y because [12], by (Select) 25] f*(s(X), s(Y), 0) >= s(0) because f > s and [26], by (Copy) 26] f*(s(X), s(Y), 0) >= 0 because f > 0, by (Copy) 27] f(s(X), 0, s(Y)) >= f(X, s(0), Y) because [28], by (Star) 28] f*(s(X), 0, s(Y)) >= f(X, s(0), Y) because [18], [29], [30] and [32], by (Stat) 29] f*(s(X), 0, s(Y)) >= X because [21], by (Select) 30] f*(s(X), 0, s(Y)) >= s(0) because f > s and [31], by (Copy) 31] f*(s(X), 0, s(Y)) >= 0 because f > 0, by (Copy) 32] f*(s(X), 0, s(Y)) >= Y because [33], by (Select) 33] s(Y) >= Y because [34], by (Star) 34] s*(Y) >= Y because [15], by (Select) 35] f(0, s(0), s(0)) > s(s(0)) because [36], by definition 36] f*(0, s(0), s(0)) >= s(s(0)) because f > s and [37], by (Copy) 37] f*(0, s(0), s(0)) >= s(0) because [38], by (Select) 38] s(0) >= s(0) because s in Mul and [39], by (Fun) 39] 0 >= 0 by (Fun) 40] f(0, s(s(X)), s(0)) >= f(0, X, s(0)) because [39], [41] and [43], by (Fun) 41] s(s(X)) >= X because [42], by (Star) 42] s*(s(X)) >= X because [23], by (Select) 43] s(0) >= s(0) because s in Mul and [39], by (Fun) 44] f(0, s(0), s(s(X))) > f(0, s(0), X) because [45], by definition 45] f*(0, s(0), s(s(X))) >= f(0, s(0), X) because [39], [43], [46], [48], [49] and [50], by (Stat) 46] s(s(X)) > X because [47], by definition 47] s*(s(X)) >= X because [33], by (Select) 48] f*(0, s(0), s(s(X))) >= 0 because f > 0, by (Copy) 49] f*(0, s(0), s(s(X))) >= s(0) because f > s and [48], by (Copy) 50] f*(0, s(0), s(s(X))) >= X because [51], by (Select) 51] s(s(X)) >= X because [47], by (Star) 52] f(0, s(s(X)), s(s(Y))) >= f(0, X, f(0, s(s(X)), s(Y))) because [53], by (Star) 53] f*(0, s(s(X)), s(s(Y))) >= f(0, X, f(0, s(s(X)), s(Y))) because [39], [54], [56], [57] and [58], by (Stat) 54] s(s(X)) > X because [55], by definition 55] s*(s(X)) >= X because [23], by (Select) 56] f*(0, s(s(X)), s(s(Y))) >= 0 because f > 0, by (Copy) 57] f*(0, s(s(X)), s(s(Y))) >= X because [41], by (Select) 58] f*(0, s(s(X)), s(s(Y))) >= f(0, s(s(X)), s(Y)) because [39], [59], [62], [56], [66] and [67], by (Stat) 59] s(s(X)) >= s(s(X)) because s in Mul and [60], by (Fun) 60] s(X) >= s(X) because s in Mul and [61], by (Fun) 61] X >= X by (Meta) 62] s(s(Y)) > s(Y) because [63], by definition 63] s*(s(Y)) >= s(Y) because [64], by (Select) 64] s(Y) >= s(Y) because s in Mul and [65], by (Fun) 65] Y >= Y by (Meta) 66] f*(0, s(s(X)), s(s(Y))) >= s(s(X)) because [59], by (Select) 67] f*(0, s(s(X)), s(s(Y))) >= s(Y) because f > s and [68], by (Copy) 68] f*(0, s(s(X)), s(s(Y))) >= Y because [51], by (Select) We can thus remove the following rules: f(0, s(0), s(0)) => s(s(0)) f(0, s(0), s(s(X))) => f(0, s(0), 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]): f(X, 0, 0) >? s(X) f(s(0), X, Y) >? f(0, s(X), s(Y)) f(s(X), s(Y), 0) >? f(X, Y, s(0)) f(s(X), 0, s(Y)) >? f(X, s(0), Y) f(0, s(s(X)), s(0)) >? f(0, X, s(0)) f(0, s(s(X)), s(s(Y))) >? f(0, X, f(0, s(s(X)), s(Y))) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {f} and Mul = {0, s}, and the following precedence: f > s > 0 With these choices, we have: 1] f(X, 0, 0) > s(X) because [2], by definition 2] f*(X, 0, 0) >= s(X) because f > s and [3], by (Copy) 3] f*(X, 0, 0) >= X because [4], by (Select) 4] X >= X by (Meta) 5] f(s(0), X, Y) >= f(0, s(X), s(Y)) because [6], by (Star) 6] f*(s(0), X, Y) >= f(0, s(X), s(Y)) because [7], [9], [10] and [13], by (Stat) 7] s(0) > 0 because [8], by definition 8] s*(0) >= 0 because s > 0, by (Copy) 9] f*(s(0), X, Y) >= 0 because f > 0, by (Copy) 10] f*(s(0), X, Y) >= s(X) because f > s and [11], by (Copy) 11] f*(s(0), X, Y) >= X because [12], by (Select) 12] X >= X by (Meta) 13] f*(s(0), X, Y) >= s(Y) because f > s and [14], by (Copy) 14] f*(s(0), X, Y) >= Y because [15], by (Select) 15] Y >= Y by (Meta) 16] f(s(X), s(Y), 0) > f(X, Y, s(0)) because [17], by definition 17] f*(s(X), s(Y), 0) >= f(X, Y, s(0)) because [18], [20], [22] and [25], by (Stat) 18] s(X) > X because [19], by definition 19] s*(X) >= X because [4], by (Select) 20] f*(s(X), s(Y), 0) >= X because [21], by (Select) 21] s(X) >= X because [19], by (Star) 22] f*(s(X), s(Y), 0) >= Y because [23], by (Select) 23] s(Y) >= Y because [24], by (Star) 24] s*(Y) >= Y because [12], by (Select) 25] f*(s(X), s(Y), 0) >= s(0) because f > s and [26], by (Copy) 26] f*(s(X), s(Y), 0) >= 0 because f > 0, by (Copy) 27] f(s(X), 0, s(Y)) >= f(X, s(0), Y) because [28], by (Star) 28] f*(s(X), 0, s(Y)) >= f(X, s(0), Y) because [18], [29], [30] and [32], by (Stat) 29] f*(s(X), 0, s(Y)) >= X because [21], by (Select) 30] f*(s(X), 0, s(Y)) >= s(0) because f > s and [31], by (Copy) 31] f*(s(X), 0, s(Y)) >= 0 because f > 0, by (Copy) 32] f*(s(X), 0, s(Y)) >= Y because [33], by (Select) 33] s(Y) >= Y because [34], by (Star) 34] s*(Y) >= Y because [15], by (Select) 35] f(0, s(s(X)), s(0)) >= f(0, X, s(0)) because [36], by (Star) 36] f*(0, s(s(X)), s(0)) >= f(0, X, s(0)) because [37], [38], [40], [41] and [43], by (Stat) 37] 0 >= 0 by (Fun) 38] s(s(X)) > X because [39], by definition 39] s*(s(X)) >= X because [23], by (Select) 40] f*(0, s(s(X)), s(0)) >= 0 because f > 0, by (Copy) 41] f*(0, s(s(X)), s(0)) >= X because [42], by (Select) 42] s(s(X)) >= X because [39], by (Star) 43] f*(0, s(s(X)), s(0)) >= s(0) because f > s and [40], by (Copy) 44] f(0, s(s(X)), s(s(Y))) > f(0, X, f(0, s(s(X)), s(Y))) because [45], by definition 45] f*(0, s(s(X)), s(s(Y))) >= f(0, X, f(0, s(s(X)), s(Y))) because [37], [38], [46], [47] and [48], by (Stat) 46] f*(0, s(s(X)), s(s(Y))) >= 0 because f > 0, by (Copy) 47] f*(0, s(s(X)), s(s(Y))) >= X because [42], by (Select) 48] f*(0, s(s(X)), s(s(Y))) >= f(0, s(s(X)), s(Y)) because [37], [49], [52], [46], [56] and [57], by (Stat) 49] s(s(X)) >= s(s(X)) because s in Mul and [50], by (Fun) 50] s(X) >= s(X) because s in Mul and [51], by (Fun) 51] X >= X by (Meta) 52] s(s(Y)) > s(Y) because [53], by definition 53] s*(s(Y)) >= s(Y) because s in Mul and [54], by (Stat) 54] s(Y) > Y because [55], by definition 55] s*(Y) >= Y because [15], by (Select) 56] f*(0, s(s(X)), s(s(Y))) >= s(s(X)) because [49], by (Select) 57] f*(0, s(s(X)), s(s(Y))) >= s(Y) because [58], by (Select) 58] s(s(Y)) >= s(Y) because [53], by (Star) We can thus remove the following rules: f(X, 0, 0) => s(X) f(s(X), s(Y), 0) => f(X, Y, s(0)) f(0, s(s(X)), s(s(Y))) => f(0, X, f(0, s(s(X)), s(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]): f(s(0), X, Y) >? f(0, s(X), s(Y)) f(s(X), 0, s(Y)) >? f(X, s(0), Y) f(0, s(s(X)), s(0)) >? f(0, X, s(0)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 f = \y0y1y2.y1 + 2y2 + 3y0 s = \y0.1 + y0 Using this interpretation, the requirements translate to: [[f(s(0), _x0, _x1)]] = 3 + x0 + 2x1 >= 3 + x0 + 2x1 = [[f(0, s(_x0), s(_x1))]] [[f(s(_x0), 0, s(_x1))]] = 5 + 2x1 + 3x0 > 1 + 2x1 + 3x0 = [[f(_x0, s(0), _x1)]] [[f(0, s(s(_x0)), s(0))]] = 4 + x0 > 2 + x0 = [[f(0, _x0, s(0))]] We can thus remove the following rules: f(s(X), 0, s(Y)) => f(X, s(0), Y) f(0, s(s(X)), s(0)) => f(0, X, s(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]): f(s(0), X, Y) >? f(0, s(X), s(Y)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 f = \y0y1y2.y1 + y2 + 3y0 s = \y0.1 + y0 Using this interpretation, the requirements translate to: [[f(s(0), _x0, _x1)]] = 3 + x0 + x1 > 2 + x0 + x1 = [[f(0, s(_x0), s(_x1))]] We can thus remove the following rules: f(s(0), X, Y) => f(0, s(X), s(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.