/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. false : [] --> o if : [o * o * o] --> o true : [] --> o if(true, X, Y) => X if(false, X, Y) => Y if(X, Y, Y) => Y if(if(X, Y, Z), U, V) => if(X, if(Y, U, V), if(Z, U, V)) if(X, if(X, Y, Z), Z) => if(X, Y, Z) if(X, Y, if(X, Y, Z)) => if(X, 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]): if(true, X, Y) >? X if(false, X, Y) >? Y if(X, Y, Y) >? Y if(if(X, Y, Z), U, V) >? if(X, if(Y, U, V), if(Z, U, V)) if(X, if(X, Y, Z), Z) >? if(X, Y, Z) if(X, Y, if(X, Y, Z)) >? if(X, Y, Z) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {if} and Mul = {false, true}, and the following precedence: if > false > true With these choices, we have: 1] if(true, X, Y) > X because [2], by definition 2] if*(true, X, Y) >= X because [3], by (Select) 3] X >= X by (Meta) 4] if(false, X, Y) >= Y because [5], by (Star) 5] if*(false, X, Y) >= Y because [6], by (Select) 6] Y >= Y by (Meta) 7] if(X, Y, Y) > Y because [8], by definition 8] if*(X, Y, Y) >= Y because [6], by (Select) 9] if(if(X, Y, Z), U, V) >= if(X, if(Y, U, V), if(Z, U, V)) because [10], by (Star) 10] if*(if(X, Y, Z), U, V) >= if(X, if(Y, U, V), if(Z, U, V)) because [11], [13], [15] and [24], by (Stat) 11] if(X, Y, Z) > X because [12], by definition 12] if*(X, Y, Z) >= X because [3], by (Select) 13] if*(if(X, Y, Z), U, V) >= X because [14], by (Select) 14] if(X, Y, Z) >= X because [12], by (Star) 15] if*(if(X, Y, Z), U, V) >= if(Y, U, V) because [16], [18], [20] and [22], by (Stat) 16] if(X, Y, Z) > Y because [17], by definition 17] if*(X, Y, Z) >= Y because [6], by (Select) 18] if*(if(X, Y, Z), U, V) >= Y because [19], by (Select) 19] if(X, Y, Z) >= Y because [17], by (Star) 20] if*(if(X, Y, Z), U, V) >= U because [21], by (Select) 21] U >= U by (Meta) 22] if*(if(X, Y, Z), U, V) >= V because [23], by (Select) 23] V >= V by (Meta) 24] if*(if(X, Y, Z), U, V) >= if(Z, U, V) because [25], [28], [20] and [22], by (Stat) 25] if(X, Y, Z) > Z because [26], by definition 26] if*(X, Y, Z) >= Z because [27], by (Select) 27] Z >= Z by (Meta) 28] if*(if(X, Y, Z), U, V) >= Z because [29], by (Select) 29] if(X, Y, Z) >= Z because [26], by (Star) 30] if(X, if(X, Y, Z), Z) >= if(X, Y, Z) because [31], [32] and [33], by (Fun) 31] X >= X by (Meta) 32] if(X, Y, Z) >= Y because [17], by (Star) 33] Z >= Z by (Meta) 34] if(X, Y, if(X, Y, Z)) > if(X, Y, Z) because [35], by definition 35] if*(X, Y, if(X, Y, Z)) >= if(X, Y, Z) because [36], by (Select) 36] if(X, Y, Z) >= if(X, Y, Z) because [31], [37] and [33], by (Fun) 37] Y >= Y by (Meta) We can thus remove the following rules: if(true, X, Y) => X if(X, Y, Y) => Y if(X, Y, if(X, Y, Z)) => if(X, 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]): if(false, X, Y) >? Y if(if(X, Y, Z), U, V) >? if(X, if(Y, U, V), if(Z, U, V)) if(X, if(X, Y, Z), Z) >? if(X, Y, Z) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {if} and Mul = {false}, and the following precedence: if > false With these choices, we have: 1] if(false, X, Y) > Y because [2], by definition 2] if*(false, X, Y) >= Y because [3], by (Select) 3] Y >= Y by (Meta) 4] if(if(X, Y, Z), U, V) >= if(X, if(Y, U, V), if(Z, U, V)) because [5], by (Star) 5] if*(if(X, Y, Z), U, V) >= if(X, if(Y, U, V), if(Z, U, V)) because [6], [9], [11] and [20], by (Stat) 6] if(X, Y, Z) > X because [7], by definition 7] if*(X, Y, Z) >= X because [8], by (Select) 8] X >= X by (Meta) 9] if*(if(X, Y, Z), U, V) >= X because [10], by (Select) 10] if(X, Y, Z) >= X because [7], by (Star) 11] if*(if(X, Y, Z), U, V) >= if(Y, U, V) because [12], [14], [16] and [18], by (Stat) 12] if(X, Y, Z) > Y because [13], by definition 13] if*(X, Y, Z) >= Y because [3], by (Select) 14] if*(if(X, Y, Z), U, V) >= Y because [15], by (Select) 15] if(X, Y, Z) >= Y because [13], by (Star) 16] if*(if(X, Y, Z), U, V) >= U because [17], by (Select) 17] U >= U by (Meta) 18] if*(if(X, Y, Z), U, V) >= V because [19], by (Select) 19] V >= V by (Meta) 20] if*(if(X, Y, Z), U, V) >= if(Z, U, V) because [21], [24], [16] and [18], by (Stat) 21] if(X, Y, Z) > Z because [22], by definition 22] if*(X, Y, Z) >= Z because [23], by (Select) 23] Z >= Z by (Meta) 24] if*(if(X, Y, Z), U, V) >= Z because [25], by (Select) 25] if(X, Y, Z) >= Z because [22], by (Star) 26] if(X, if(X, Y, Z), Z) >= if(X, Y, Z) because [27], [28] and [29], by (Fun) 27] X >= X by (Meta) 28] if(X, Y, Z) >= Y because [13], by (Star) 29] Z >= Z by (Meta) We can thus remove the following rules: if(false, 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]): if(if(X, Y, Z), U, V) >? if(X, if(Y, U, V), if(Z, U, V)) if(X, if(X, Y, Z), Z) >? if(X, Y, Z) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[if(x_1, x_2, x_3)]] = if(x_1, x_3, x_2) We choose Lex = {if} and Mul = {}, and the following precedence: if Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: if(if(X, Y, Z), U, V) >= if(X) (if(Y) U V) if(Z) if(X, if(X, Y, Z), Z) > if(X, Y, Z) With these choices, we have: 1] if(if(X, Y, Z), U, V) >= if(X) (if(Y) U V) if(Z) because [2], by (Star) 2] if*(if(X, Y, Z), U, V) >= if(X) (if(Y) U V) if(Z) because [3], [6], [8] and [18], by (Stat) 3] if(X, Y, Z) > X because [4], by definition 4] if*(X, Y, Z) >= X because [5], by (Select) 5] X >= X by (Meta) 6] if*(if(X, Y, Z), U, V) >= X because [7], by (Select) 7] if(X, Y, Z) >= X because [4], by (Star) 8] if*(if(X, Y, Z), U, V) >= if(Y, U, V) because [9], [12], [14] and [16], by (Stat) 9] if(X, Y, Z) > Y because [10], by definition 10] if*(X, Y, Z) >= Y because [11], by (Select) 11] Y >= Y by (Meta) 12] if*(if(X, Y, Z), U, V) >= Y because [13], by (Select) 13] if(X, Y, Z) >= Y because [10], by (Star) 14] if*(if(X, Y, Z), U, V) >= U because [15], by (Select) 15] U >= U by (Meta) 16] if*(if(X, Y, Z), U, V) >= V because [17], by (Select) 17] V >= V by (Meta) 18] if*(if(X, Y, Z), U, V) >= if(Z, U, V) because [19], [22], [14] and [16], by (Stat) 19] if(X, Y, Z) > Z because [20], by definition 20] if*(X, Y, Z) >= Z because [21], by (Select) 21] Z >= Z by (Meta) 22] if*(if(X, Y, Z), U, V) >= Z because [23], by (Select) 23] if(X, Y, Z) >= Z because [20], by (Star) 24] if(X, if(X, Y, Z), Z) > if(X, Y, Z) because [25], by definition 25] if*(X, if(X, Y, Z), Z) >= if(X, Y, Z) because [26], by (Select) 26] if(X, Y, Z) >= if(X, Y, Z) because [27], [28] and [29], by (Fun) 27] X >= X by (Meta) 28] Y >= Y by (Meta) 29] Z >= Z by (Meta) We can thus remove the following rules: if(X, if(X, Y, Z), Z) => if(X, 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]): if(if(X, Y, Z), U, V) >? if(X, if(Y, U, V), if(Z, U, V)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[if(x_1, x_2, x_3)]] = if(x_1, x_3, x_2) We choose Lex = {if} and Mul = {}, and the following precedence: if Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: if(if(X, Y, Z), U, V) > if(X) (if(Y) U V) if(Z) With these choices, we have: 1] if(if(X, Y, Z), U, V) > if(X) (if(Y) U V) if(Z) because [2], by definition 2] if*(if(X, Y, Z), U, V) >= if(X) (if(Y) U V) if(Z) because [3], [6], [8] and [18], by (Stat) 3] if(X, Y, Z) > X because [4], by definition 4] if*(X, Y, Z) >= X because [5], by (Select) 5] X >= X by (Meta) 6] if*(if(X, Y, Z), U, V) >= X because [7], by (Select) 7] if(X, Y, Z) >= X because [4], by (Star) 8] if*(if(X, Y, Z), U, V) >= if(Y, U, V) because [9], [12], [14] and [16], by (Stat) 9] if(X, Y, Z) > Y because [10], by definition 10] if*(X, Y, Z) >= Y because [11], by (Select) 11] Y >= Y by (Meta) 12] if*(if(X, Y, Z), U, V) >= Y because [13], by (Select) 13] if(X, Y, Z) >= Y because [10], by (Star) 14] if*(if(X, Y, Z), U, V) >= U because [15], by (Select) 15] U >= U by (Meta) 16] if*(if(X, Y, Z), U, V) >= V because [17], by (Select) 17] V >= V by (Meta) 18] if*(if(X, Y, Z), U, V) >= if(Z, U, V) because [19], [22], [14] and [16], by (Stat) 19] if(X, Y, Z) > Z because [20], by definition 20] if*(X, Y, Z) >= Z because [21], by (Select) 21] Z >= Z by (Meta) 22] if*(if(X, Y, Z), U, V) >= Z because [23], by (Select) 23] if(X, Y, Z) >= Z because [20], by (Star) We can thus remove the following rules: if(if(X, Y, Z), U, V) => if(X, if(Y, U, V), if(Z, U, V)) 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.