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