/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 ack!6220in : [o * o] --> o ack!6220out : [o] --> o s : [o] --> o u11 : [o] --> o u21 : [o * o] --> o u22 : [o] --> o ack!6220in(0, X) => ack!6220out(s(X)) ack!6220in(s(X), 0) => u11(ack!6220in(X, s(0))) u11(ack!6220out(X)) => ack!6220out(X) ack!6220in(s(X), s(Y)) => u21(ack!6220in(s(X), Y), X) u21(ack!6220out(X), Y) => u22(ack!6220in(Y, X)) u22(ack!6220out(X)) => ack!6220out(X) 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: 0 : [] --> ra ack!6220in : [ra * ra] --> lb ack!6220out : [ra] --> lb s : [ra] --> ra u11 : [lb] --> lb u21 : [lb * ra] --> lb u22 : [lb] --> lb We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): ack!6220in(0, X) >? ack!6220out(s(X)) ack!6220in(s(X), 0) >? u11(ack!6220in(X, s(0))) u11(ack!6220out(X)) >? ack!6220out(X) ack!6220in(s(X), s(Y)) >? u21(ack!6220in(s(X), Y), X) u21(ack!6220out(X), Y) >? u22(ack!6220in(Y, X)) u22(ack!6220out(X)) >? ack!6220out(X) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[u21(x_1, x_2)]] = u21(x_2, x_1) [[u22(x_1)]] = x_1 We choose Lex = {ack!6220in, u21} and Mul = {ack!6220out, s, u11}, and the following precedence: ack!6220in = u21 > s > u11 > ack!6220out Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: ack!6220in(_|_, X) >= ack!6220out(s(X)) ack!6220in(s(X), _|_) > u11(ack!6220in(X, s(_|_))) u11(ack!6220out(X)) >= ack!6220out(X) ack!6220in(s(X), s(Y)) > u21(ack!6220in(s(X), Y), X) u21(ack!6220out(X), Y) >= ack!6220in(Y, X) ack!6220out(X) >= ack!6220out(X) With these choices, we have: 1] ack!6220in(_|_, X) >= ack!6220out(s(X)) because [2], by (Star) 2] ack!6220in*(_|_, X) >= ack!6220out(s(X)) because ack!6220in > ack!6220out and [3], by (Copy) 3] ack!6220in*(_|_, X) >= s(X) because ack!6220in > s and [4], by (Copy) 4] ack!6220in*(_|_, X) >= X because [5], by (Select) 5] X >= X by (Meta) 6] ack!6220in(s(X), _|_) > u11(ack!6220in(X, s(_|_))) because [7], by definition 7] ack!6220in*(s(X), _|_) >= u11(ack!6220in(X, s(_|_))) because ack!6220in > u11 and [8], by (Copy) 8] ack!6220in*(s(X), _|_) >= ack!6220in(X, s(_|_)) because [9], [12] and [14], by (Stat) 9] s(X) > X because [10], by definition 10] s*(X) >= X because [11], by (Select) 11] X >= X by (Meta) 12] ack!6220in*(s(X), _|_) >= X because [13], by (Select) 13] s(X) >= X because [10], by (Star) 14] ack!6220in*(s(X), _|_) >= s(_|_) because ack!6220in > s and [15], by (Copy) 15] ack!6220in*(s(X), _|_) >= _|_ by (Bot) 16] u11(ack!6220out(X)) >= ack!6220out(X) because [17], by (Star) 17] u11*(ack!6220out(X)) >= ack!6220out(X) because u11 > ack!6220out and [18], by (Copy) 18] u11*(ack!6220out(X)) >= X because [19], by (Select) 19] ack!6220out(X) >= X because [20], by (Star) 20] ack!6220out*(X) >= X because [5], by (Select) 21] ack!6220in(s(X), s(Y)) > u21(ack!6220in(s(X), Y), X) because [22], by definition 22] ack!6220in*(s(X), s(Y)) >= u21(ack!6220in(s(X), Y), X) because ack!6220in = u21, [9], [23] and [31], by (Stat) 23] ack!6220in*(s(X), s(Y)) >= ack!6220in(s(X), Y) because [24], [26], [28] and [29], by (Stat) 24] s(X) >= s(X) because s in Mul and [25], by (Fun) 25] X >= X by (Meta) 26] s(Y) > Y because [27], by definition 27] s*(Y) >= Y because [5], by (Select) 28] ack!6220in*(s(X), s(Y)) >= s(X) because [24], by (Select) 29] ack!6220in*(s(X), s(Y)) >= Y because [30], by (Select) 30] s(Y) >= Y because [27], by (Star) 31] ack!6220in*(s(X), s(Y)) >= X because [13], by (Select) 32] u21(ack!6220out(X), Y) >= ack!6220in(Y, X) because u21 = ack!6220in, [33] and [25], by (Fun) 33] ack!6220out(X) >= X because [20], by (Star) 34] ack!6220out(X) >= ack!6220out(X) because ack!6220out in Mul and [35], by (Fun) 35] X >= X by (Meta) We can thus remove the following rules: ack!6220in(s(X), 0) => u11(ack!6220in(X, s(0))) ack!6220in(s(X), s(Y)) => u21(ack!6220in(s(X), Y), 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]): ack!6220in(0, X) >? ack!6220out(s(X)) u11(ack!6220out(X)) >? ack!6220out(X) u21(ack!6220out(X), Y) >? u22(ack!6220in(Y, X)) u22(ack!6220out(X)) >? ack!6220out(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 3 ack!6220in = \y0y1.2 + y0 + 3y1 ack!6220out = \y0.3 + 3y0 s = \y0.y0 u11 = \y0.3 + 3y0 u21 = \y0y1.3 + 3y0 + 3y1 u22 = \y0.2y0 Using this interpretation, the requirements translate to: [[ack!6220in(0, _x0)]] = 5 + 3x0 > 3 + 3x0 = [[ack!6220out(s(_x0))]] [[u11(ack!6220out(_x0))]] = 12 + 9x0 > 3 + 3x0 = [[ack!6220out(_x0)]] [[u21(ack!6220out(_x0), _x1)]] = 12 + 3x1 + 9x0 > 4 + 2x1 + 6x0 = [[u22(ack!6220in(_x1, _x0))]] [[u22(ack!6220out(_x0))]] = 6 + 6x0 > 3 + 3x0 = [[ack!6220out(_x0)]] We can thus remove the following rules: ack!6220in(0, X) => ack!6220out(s(X)) u11(ack!6220out(X)) => ack!6220out(X) u21(ack!6220out(X), Y) => u22(ack!6220in(Y, X)) u22(ack!6220out(X)) => ack!6220out(X) 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.