/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. !870 : [o * o] --> o 0 : [] --> o and : [o * o] --> o divp : [o * o] --> o false : [] --> o not : [o] --> o prime : [o] --> o prime1 : [o * o] --> o rem : [o * o] --> o s : [o] --> o true : [] --> o prime(0) => false prime(s(0)) => false prime(s(s(X))) => prime1(s(s(X)), s(X)) prime1(X, 0) => false prime1(X, s(0)) => true prime1(X, s(s(Y))) => and(not(divp(s(s(Y)), X)), prime1(X, s(Y))) divp(X, Y) => !870(rem(X, Y), 0) As the system is orthogonal, it is terminating if it is innermost terminating by [Gra95]. Then, by [FuhGieParSchSwi11], it suffices to prove (innermost) termination of the typed system, with sort annotations chosen to respect the rules, as follows: !870 : [vb * kb] --> xb 0 : [] --> kb and : [hb * mb] --> mb divp : [kb * kb] --> xb false : [] --> mb not : [xb] --> hb prime : [kb] --> mb prime1 : [kb * kb] --> mb rem : [kb * kb] --> vb s : [kb] --> kb true : [] --> mb We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): prime(0) >? false prime(s(0)) >? false prime(s(s(X))) >? prime1(s(s(X)), s(X)) prime1(X, 0) >? false prime1(X, s(0)) >? true prime1(X, s(s(Y))) >? and(not(divp(s(s(Y)), X)), prime1(X, s(Y))) divp(X, Y) >? !870(rem(X, Y), 0) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[false]] = _|_ [[true]] = _|_ We choose Lex = {} and Mul = {!870, and, divp, not, prime, prime1, rem, s}, and the following precedence: prime > prime1 > not > and > s > divp > !870 > rem Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: prime(_|_) >= _|_ prime(s(_|_)) >= _|_ prime(s(s(X))) > prime1(s(s(X)), s(X)) prime1(X, _|_) >= _|_ prime1(X, s(_|_)) >= _|_ prime1(X, s(s(Y))) >= and(not(divp(s(s(Y)), X)), prime1(X, s(Y))) divp(X, Y) >= !870(rem(X, Y), _|_) With these choices, we have: 1] prime(_|_) >= _|_ by (Bot) 2] prime(s(_|_)) >= _|_ by (Bot) 3] prime(s(s(X))) > prime1(s(s(X)), s(X)) because [4], by definition 4] prime*(s(s(X))) >= prime1(s(s(X)), s(X)) because prime > prime1, [5] and [9], by (Copy) 5] prime*(s(s(X))) >= s(s(X)) because [6], by (Select) 6] s(s(X)) >= s(s(X)) because s in Mul and [7], by (Fun) 7] s(X) >= s(X) because s in Mul and [8], by (Fun) 8] X >= X by (Meta) 9] prime*(s(s(X))) >= s(X) because [10], by (Select) 10] s(s(X)) >= s(X) because [11], by (Star) 11] s*(s(X)) >= s(X) because [7], by (Select) 12] prime1(X, _|_) >= _|_ by (Bot) 13] prime1(X, s(_|_)) >= _|_ by (Bot) 14] prime1(X, s(s(Y))) >= and(not(divp(s(s(Y)), X)), prime1(X, s(Y))) because [15], by (Star) 15] prime1*(X, s(s(Y))) >= and(not(divp(s(s(Y)), X)), prime1(X, s(Y))) because prime1 > and, [16] and [26], by (Copy) 16] prime1*(X, s(s(Y))) >= not(divp(s(s(Y)), X)) because prime1 > not and [17], by (Copy) 17] prime1*(X, s(s(Y))) >= divp(s(s(Y)), X) because prime1 > divp, [18] and [25], by (Copy) 18] prime1*(X, s(s(Y))) >= s(s(Y)) because prime1 > s and [19], by (Copy) 19] prime1*(X, s(s(Y))) >= s(Y) because [20], by (Select) 20] s(s(Y)) >= s(Y) because [21], by (Star) 21] s*(s(Y)) >= s(Y) because s in Mul and [22], by (Stat) 22] s(Y) > Y because [23], by definition 23] s*(Y) >= Y because [24], by (Select) 24] Y >= Y by (Meta) 25] prime1*(X, s(s(Y))) >= X because [8], by (Select) 26] prime1*(X, s(s(Y))) >= prime1(X, s(Y)) because prime1 in Mul, [8] and [27], by (Stat) 27] s(s(Y)) > s(Y) because [28], by definition 28] s*(s(Y)) >= s(Y) because s in Mul and [22], by (Stat) 29] divp(X, Y) >= !870(rem(X, Y), _|_) because [30], by (Star) 30] divp*(X, Y) >= !870(rem(X, Y), _|_) because divp > !870, [31] and [34], by (Copy) 31] divp*(X, Y) >= rem(X, Y) because divp > rem, [32] and [33], by (Copy) 32] divp*(X, Y) >= X because [8], by (Select) 33] divp*(X, Y) >= Y because [24], by (Select) 34] divp*(X, Y) >= _|_ by (Bot) We can thus remove the following rules: prime(s(s(X))) => prime1(s(s(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]): prime(0) >? false prime(s(0)) >? false prime1(X, 0) >? false prime1(X, s(0)) >? true prime1(X, s(s(Y))) >? and(not(divp(s(s(Y)), X)), prime1(X, s(Y))) divp(X, Y) >? !870(rem(X, Y), 0) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[false]] = _|_ [[not(x_1)]] = x_1 [[true]] = _|_ We choose Lex = {} and Mul = {!870, and, divp, prime, prime1, rem, s}, and the following precedence: s > prime1 > divp > !870 > prime > and > rem Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: prime(_|_) >= _|_ prime(s(_|_)) > _|_ prime1(X, _|_) >= _|_ prime1(X, s(_|_)) >= _|_ prime1(X, s(s(Y))) > and(divp(s(s(Y)), X), prime1(X, s(Y))) divp(X, Y) >= !870(rem(X, Y), _|_) With these choices, we have: 1] prime(_|_) >= _|_ by (Bot) 2] prime(s(_|_)) > _|_ because [3], by definition 3] prime*(s(_|_)) >= _|_ by (Bot) 4] prime1(X, _|_) >= _|_ by (Bot) 5] prime1(X, s(_|_)) >= _|_ by (Bot) 6] prime1(X, s(s(Y))) > and(divp(s(s(Y)), X), prime1(X, s(Y))) because [7], by definition 7] prime1*(X, s(s(Y))) >= and(divp(s(s(Y)), X), prime1(X, s(Y))) because prime1 > and, [8] and [15], by (Copy) 8] prime1*(X, s(s(Y))) >= divp(s(s(Y)), X) because prime1 > divp, [9] and [13], by (Copy) 9] prime1*(X, s(s(Y))) >= s(s(Y)) because [10], by (Select) 10] s(s(Y)) >= s(s(Y)) because s in Mul and [11], by (Fun) 11] s(Y) >= s(Y) because s in Mul and [12], by (Fun) 12] Y >= Y by (Meta) 13] prime1*(X, s(s(Y))) >= X because [14], by (Select) 14] X >= X by (Meta) 15] prime1*(X, s(s(Y))) >= prime1(X, s(Y)) because prime1 in Mul, [16] and [17], by (Stat) 16] X >= X by (Meta) 17] s(s(Y)) > s(Y) because [18], by definition 18] s*(s(Y)) >= s(Y) because [11], by (Select) 19] divp(X, Y) >= !870(rem(X, Y), _|_) because [20], by (Star) 20] divp*(X, Y) >= !870(rem(X, Y), _|_) because divp > !870, [21] and [24], by (Copy) 21] divp*(X, Y) >= rem(X, Y) because divp > rem, [22] and [23], by (Copy) 22] divp*(X, Y) >= X because [16], by (Select) 23] divp*(X, Y) >= Y because [12], by (Select) 24] divp*(X, Y) >= _|_ by (Bot) We can thus remove the following rules: prime(s(0)) => false prime1(X, s(s(Y))) => and(not(divp(s(s(Y)), X)), prime1(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]): prime(0) >? false prime1(X, 0) >? false prime1(X, s(0)) >? true divp(X, Y) >? !870(rem(X, Y), 0) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !870 = \y0y1.y0 + y1 0 = 0 divp = \y0y1.3 + 3y0 + 3y1 false = 0 prime = \y0.3 + 3y0 prime1 = \y0y1.3 + y0 + 3y1 rem = \y0y1.y0 + y1 s = \y0.3 + 3y0 true = 0 Using this interpretation, the requirements translate to: [[prime(0)]] = 3 > 0 = [[false]] [[prime1(_x0, 0)]] = 3 + x0 > 0 = [[false]] [[prime1(_x0, s(0))]] = 12 + x0 > 0 = [[true]] [[divp(_x0, _x1)]] = 3 + 3x0 + 3x1 > x0 + x1 = [[!870(rem(_x0, _x1), 0)]] We can thus remove the following rules: prime(0) => false prime1(X, 0) => false prime1(X, s(0)) => true divp(X, Y) => !870(rem(X, Y), 0) 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 +++ [FuhGieParSchSwi11] C. Fuhs, J. Giesl, M. Parting, P. Schneider-Kamp, and S. Swiderski. Proving Termination by Dependency Pairs and Inductive Theorem Proving. In volume 47(2) of Journal of Automated Reasoning. 133--160, 2011. [Gra95] B. Gramlich. Abstract Relations Between Restricted Termination and Confluence Properties of Rewrite Systems. In volume 24(1-2) of Fundamentae Informaticae. 3--23, 1995. [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012.