/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. and : [o * o] --> o not : [o] --> o or : [o * o] --> o not(not(X)) => X not(or(X, Y)) => and(not(X), not(Y)) not(and(X, Y)) => or(not(X), not(Y)) and(X, or(Y, Z)) => or(and(X, Y), and(X, Z)) and(or(X, Y), Z) => or(and(Z, X), and(Z, 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]): not(not(X)) >? X not(or(X, Y)) >? and(not(X), not(Y)) not(and(X, Y)) >? or(not(X), not(Y)) and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) and(or(X, Y), Z) >? or(and(Z, X), and(Z, Y)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {not} and Mul = {and, or}, and the following precedence: not > and > or With these choices, we have: 1] not(not(X)) >= X because [2], by (Star) 2] not*(not(X)) >= X because [3], by (Select) 3] not(X) >= X because [4], by (Star) 4] not*(X) >= X because [5], by (Select) 5] X >= X by (Meta) 6] not(or(X, Y)) >= and(not(X), not(Y)) because [7], by (Star) 7] not*(or(X, Y)) >= and(not(X), not(Y)) because not > and, [8] and [13], by (Copy) 8] not*(or(X, Y)) >= not(X) because [9] and [11], by (Stat) 9] or(X, Y) > X because [10], by definition 10] or*(X, Y) >= X because [5], by (Select) 11] not*(or(X, Y)) >= X because [12], by (Select) 12] or(X, Y) >= X because [10], by (Star) 13] not*(or(X, Y)) >= not(Y) because [14] and [17], by (Stat) 14] or(X, Y) > Y because [15], by definition 15] or*(X, Y) >= Y because [16], by (Select) 16] Y >= Y by (Meta) 17] not*(or(X, Y)) >= Y because [18], by (Select) 18] or(X, Y) >= Y because [15], by (Star) 19] not(and(X, Y)) > or(not(X), not(Y)) because [20], by definition 20] not*(and(X, Y)) >= or(not(X), not(Y)) because not > or, [21] and [26], by (Copy) 21] not*(and(X, Y)) >= not(X) because [22] and [24], by (Stat) 22] and(X, Y) > X because [23], by definition 23] and*(X, Y) >= X because [5], by (Select) 24] not*(and(X, Y)) >= X because [25], by (Select) 25] and(X, Y) >= X because [23], by (Star) 26] not*(and(X, Y)) >= not(Y) because [27] and [29], by (Stat) 27] and(X, Y) > Y because [28], by definition 28] and*(X, Y) >= Y because [16], by (Select) 29] not*(and(X, Y)) >= Y because [30], by (Select) 30] and(X, Y) >= Y because [28], by (Star) 31] and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because [32], by (Star) 32] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because and > or, [33] and [37], by (Copy) 33] and*(X, or(Y, Z)) >= and(X, Y) because and in Mul, [34] and [35], by (Stat) 34] X >= X by (Meta) 35] or(Y, Z) > Y because [36], by definition 36] or*(Y, Z) >= Y because [16], by (Select) 37] and*(X, or(Y, Z)) >= and(X, Z) because and in Mul, [34] and [38], by (Stat) 38] or(Y, Z) > Z because [39], by definition 39] or*(Y, Z) >= Z because [40], by (Select) 40] Z >= Z by (Meta) 41] and(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because [42], by (Star) 42] and*(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because and > or, [43] and [44], by (Copy) 43] and*(or(X, Y), Z) >= and(Z, X) because and in Mul, [35] and [34], by (Stat) 44] and*(or(X, Y), Z) >= and(Z, Y) because and in Mul, [38] and [34], by (Stat) We can thus remove the following rules: not(and(X, Y)) => or(not(X), not(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]): not(not(X)) >? X not(or(X, Y)) >? and(not(X), not(Y)) and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) and(or(X, Y), Z) >? or(and(Z, X), and(Z, Y)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {} and Mul = {and, not, or}, and the following precedence: not > and > or With these choices, we have: 1] not(not(X)) > X because [2], by definition 2] not*(not(X)) >= X because [3], by (Select) 3] not(X) >= X because [4], by (Star) 4] not*(X) >= X because [5], by (Select) 5] X >= X by (Meta) 6] not(or(X, Y)) >= and(not(X), not(Y)) because [7], by (Star) 7] not*(or(X, Y)) >= and(not(X), not(Y)) because not > and, [8] and [11], by (Copy) 8] not*(or(X, Y)) >= not(X) because not in Mul and [9], by (Stat) 9] or(X, Y) > X because [10], by definition 10] or*(X, Y) >= X because [5], by (Select) 11] not*(or(X, Y)) >= not(Y) because not in Mul and [12], by (Stat) 12] or(X, Y) > Y because [13], by definition 13] or*(X, Y) >= Y because [14], by (Select) 14] Y >= Y by (Meta) 15] and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because [16], by (Star) 16] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because and > or, [17] and [21], by (Copy) 17] and*(X, or(Y, Z)) >= and(X, Y) because and in Mul, [18] and [19], by (Stat) 18] X >= X by (Meta) 19] or(Y, Z) > Y because [20], by definition 20] or*(Y, Z) >= Y because [14], by (Select) 21] and*(X, or(Y, Z)) >= and(X, Z) because and in Mul, [18] and [22], by (Stat) 22] or(Y, Z) > Z because [23], by definition 23] or*(Y, Z) >= Z because [24], by (Select) 24] Z >= Z by (Meta) 25] and(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because [26], by (Star) 26] and*(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because and > or, [27] and [28], by (Copy) 27] and*(or(X, Y), Z) >= and(Z, X) because and in Mul, [19] and [18], by (Stat) 28] and*(or(X, Y), Z) >= and(Z, Y) because and in Mul, [22] and [18], by (Stat) We can thus remove the following rules: not(not(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]): not(or(X, Y)) >? and(not(X), not(Y)) and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) and(or(X, Y), Z) >? or(and(Z, X), and(Z, Y)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {} and Mul = {and, not, or}, and the following precedence: not > and > or With these choices, we have: 1] not(or(X, Y)) > and(not(X), not(Y)) because [2], by definition 2] not*(or(X, Y)) >= and(not(X), not(Y)) because not > and, [3] and [7], by (Copy) 3] not*(or(X, Y)) >= not(X) because not in Mul and [4], by (Stat) 4] or(X, Y) > X because [5], by definition 5] or*(X, Y) >= X because [6], by (Select) 6] X >= X by (Meta) 7] not*(or(X, Y)) >= not(Y) because not in Mul and [8], by (Stat) 8] or(X, Y) > Y because [9], by definition 9] or*(X, Y) >= Y because [10], by (Select) 10] Y >= Y by (Meta) 11] and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because [12], by (Star) 12] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because and > or, [13] and [17], by (Copy) 13] and*(X, or(Y, Z)) >= and(X, Y) because and in Mul, [14] and [15], by (Stat) 14] X >= X by (Meta) 15] or(Y, Z) > Y because [16], by definition 16] or*(Y, Z) >= Y because [10], by (Select) 17] and*(X, or(Y, Z)) >= and(X, Z) because and in Mul, [14] and [18], by (Stat) 18] or(Y, Z) > Z because [19], by definition 19] or*(Y, Z) >= Z because [20], by (Select) 20] Z >= Z by (Meta) 21] and(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because [22], by (Star) 22] and*(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because and > or, [23] and [24], by (Copy) 23] and*(or(X, Y), Z) >= and(Z, X) because and in Mul, [15] and [14], by (Stat) 24] and*(or(X, Y), Z) >= and(Z, Y) because and in Mul, [18] and [14], by (Stat) We can thus remove the following rules: not(or(X, Y)) => and(not(X), not(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(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) and(or(X, Y), Z) >? or(and(Z, X), and(Z, Y)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {} and Mul = {and, or}, and the following precedence: and > or With these choices, we have: 1] and(X, or(Y, Z)) > or(and(X, Y), and(X, Z)) because [2], by definition 2] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) because and > or, [3] and [8], by (Copy) 3] and*(X, or(Y, Z)) >= and(X, Y) because and in Mul, [4] and [5], by (Stat) 4] X >= X by (Meta) 5] or(Y, Z) > Y because [6], by definition 6] or*(Y, Z) >= Y because [7], by (Select) 7] Y >= Y by (Meta) 8] and*(X, or(Y, Z)) >= and(X, Z) because and in Mul, [4] and [9], by (Stat) 9] or(Y, Z) > Z because [10], by definition 10] or*(Y, Z) >= Z because [11], by (Select) 11] Z >= Z by (Meta) 12] and(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because [13], by (Star) 13] and*(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because and > or, [14] and [15], by (Copy) 14] and*(or(X, Y), Z) >= and(Z, X) because and in Mul, [5] and [4], by (Stat) 15] and*(or(X, Y), Z) >= and(Z, Y) because and in Mul, [9] and [4], by (Stat) We can thus remove the following rules: and(X, or(Y, Z)) => or(and(X, Y), and(X, 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]): and(or(X, Y), Z) >? or(and(Z, X), and(Z, Y)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {} and Mul = {and, or}, and the following precedence: and > or With these choices, we have: 1] and(or(X, Y), Z) > or(and(Z, X), and(Z, Y)) because [2], by definition 2] and*(or(X, Y), Z) >= or(and(Z, X), and(Z, Y)) because and > or, [3] and [8], by (Copy) 3] and*(or(X, Y), Z) >= and(Z, X) because and in Mul, [4] and [7], by (Stat) 4] or(X, Y) > X because [5], by definition 5] or*(X, Y) >= X because [6], by (Select) 6] X >= X by (Meta) 7] Z >= Z by (Meta) 8] and*(or(X, Y), Z) >= and(Z, Y) because and in Mul, [9] and [7], by (Stat) 9] or(X, Y) > Y because [10], by definition 10] or*(X, Y) >= Y because [11], by (Select) 11] Y >= Y by (Meta) We can thus remove the following rules: and(or(X, Y), Z) => or(and(Z, X), and(Z, 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.