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