/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. 0 : [] --> o U11 : [o * o] --> o U12 : [o] --> o U21 : [o] --> o U31 : [o * o] --> o U41 : [o * o * o] --> o U42 : [o * o * o] --> o activate : [o] --> o isNat : [o] --> o n!6220!62200 : [] --> o n!6220!6220plus : [o * o] --> o n!6220!6220s : [o] --> o plus : [o * o] --> o s : [o] --> o tt : [] --> o U11(tt, X) => U12(isNat(activate(X))) U12(tt) => tt U21(tt) => tt U31(tt, X) => activate(X) U41(tt, X, Y) => U42(isNat(activate(Y)), activate(X), activate(Y)) U42(tt, X, Y) => s(plus(activate(Y), activate(X))) isNat(n!6220!62200) => tt isNat(n!6220!6220plus(X, Y)) => U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) => U21(isNat(activate(X))) plus(X, 0) => U31(isNat(X), X) plus(X, s(Y)) => U41(isNat(Y), Y, X) 0 => n!6220!62200 plus(X, Y) => n!6220!6220plus(X, Y) s(X) => n!6220!6220s(X) activate(n!6220!62200) => 0 activate(n!6220!6220plus(X, Y)) => plus(X, Y) activate(n!6220!6220s(X)) => s(X) activate(X) => X We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] U11#(tt, X) =#> U12#(isNat(activate(X))) 1] U11#(tt, X) =#> isNat#(activate(X)) 2] U11#(tt, X) =#> activate#(X) 3] U31#(tt, X) =#> activate#(X) 4] U41#(tt, X, Y) =#> U42#(isNat(activate(Y)), activate(X), activate(Y)) 5] U41#(tt, X, Y) =#> isNat#(activate(Y)) 6] U41#(tt, X, Y) =#> activate#(Y) 7] U41#(tt, X, Y) =#> activate#(X) 8] U41#(tt, X, Y) =#> activate#(Y) 9] U42#(tt, X, Y) =#> s#(plus(activate(Y), activate(X))) 10] U42#(tt, X, Y) =#> plus#(activate(Y), activate(X)) 11] U42#(tt, X, Y) =#> activate#(Y) 12] U42#(tt, X, Y) =#> activate#(X) 13] isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) 14] isNat#(n!6220!6220plus(X, Y)) =#> isNat#(activate(X)) 15] isNat#(n!6220!6220plus(X, Y)) =#> activate#(X) 16] isNat#(n!6220!6220plus(X, Y)) =#> activate#(Y) 17] isNat#(n!6220!6220s(X)) =#> U21#(isNat(activate(X))) 18] isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) 19] isNat#(n!6220!6220s(X)) =#> activate#(X) 20] plus#(X, 0) =#> U31#(isNat(X), X) 21] plus#(X, 0) =#> isNat#(X) 22] plus#(X, s(Y)) =#> U41#(isNat(Y), Y, X) 23] plus#(X, s(Y)) =#> isNat#(Y) 24] activate#(n!6220!62200) =#> 0# 25] activate#(n!6220!6220plus(X, Y)) =#> plus#(X, Y) 26] activate#(n!6220!6220s(X)) =#> s#(X) Rules R_0: U11(tt, X) => U12(isNat(activate(X))) U12(tt) => tt U21(tt) => tt U31(tt, X) => activate(X) U41(tt, X, Y) => U42(isNat(activate(Y)), activate(X), activate(Y)) U42(tt, X, Y) => s(plus(activate(Y), activate(X))) isNat(n!6220!62200) => tt isNat(n!6220!6220plus(X, Y)) => U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) => U21(isNat(activate(X))) plus(X, 0) => U31(isNat(X), X) plus(X, s(Y)) => U41(isNat(Y), Y, X) 0 => n!6220!62200 plus(X, Y) => n!6220!6220plus(X, Y) s(X) => n!6220!6220s(X) activate(n!6220!62200) => 0 activate(n!6220!6220plus(X, Y)) => plus(X, Y) activate(n!6220!6220s(X)) => s(X) activate(X) => X Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : * 1 : 13, 14, 15, 16, 17, 18, 19 * 2 : 24, 25, 26 * 3 : 24, 25, 26 * 4 : 9, 10, 11, 12 * 5 : 13, 14, 15, 16, 17, 18, 19 * 6 : 24, 25, 26 * 7 : 24, 25, 26 * 8 : 24, 25, 26 * 9 : * 10 : 20, 21, 22, 23 * 11 : 24, 25, 26 * 12 : 24, 25, 26 * 13 : 0, 1, 2 * 14 : 13, 14, 15, 16, 17, 18, 19 * 15 : 24, 25, 26 * 16 : 24, 25, 26 * 17 : * 18 : 13, 14, 15, 16, 17, 18, 19 * 19 : 24, 25, 26 * 20 : 3 * 21 : 13, 14, 15, 16, 17, 18, 19 * 22 : 4, 5, 6, 7, 8 * 23 : 13, 14, 15, 16, 17, 18, 19 * 24 : * 25 : 20, 21, 22, 23 * 26 : This graph has the following strongly connected components: P_1: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U31#(tt, X) =#> activate#(X) U41#(tt, X, Y) =#> U42#(isNat(activate(Y)), activate(X), activate(Y)) U41#(tt, X, Y) =#> isNat#(activate(Y)) U41#(tt, X, Y) =#> activate#(Y) U41#(tt, X, Y) =#> activate#(X) U41#(tt, X, Y) =#> activate#(Y) U42#(tt, X, Y) =#> plus#(activate(Y), activate(X)) U42#(tt, X, Y) =#> activate#(Y) U42#(tt, X, Y) =#> activate#(X) isNat#(n!6220!6220plus(X, Y)) =#> U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) =#> isNat#(activate(X)) isNat#(n!6220!6220plus(X, Y)) =#> activate#(X) isNat#(n!6220!6220plus(X, Y)) =#> activate#(Y) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> activate#(X) plus#(X, 0) =#> U31#(isNat(X), X) plus#(X, 0) =#> isNat#(X) plus#(X, s(Y)) =#> U41#(isNat(Y), Y, X) plus#(X, s(Y)) =#> isNat#(Y) activate#(n!6220!6220plus(X, Y)) =#> plus#(X, Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f). Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: U11#(tt, X) >? isNat#(activate(X)) U11#(tt, X) >? activate#(X) U31#(tt, X) >? activate#(X) U41#(tt, X, Y) >? U42#(isNat(activate(Y)), activate(X), activate(Y)) U41#(tt, X, Y) >? isNat#(activate(Y)) U41#(tt, X, Y) >? activate#(Y) U41#(tt, X, Y) >? activate#(X) U41#(tt, X, Y) >? activate#(Y) U42#(tt, X, Y) >? plus#(activate(Y), activate(X)) U42#(tt, X, Y) >? activate#(Y) U42#(tt, X, Y) >? activate#(X) isNat#(n!6220!6220plus(X, Y)) >? U11#(isNat(activate(X)), activate(Y)) isNat#(n!6220!6220plus(X, Y)) >? isNat#(activate(X)) isNat#(n!6220!6220plus(X, Y)) >? activate#(X) isNat#(n!6220!6220plus(X, Y)) >? activate#(Y) isNat#(n!6220!6220s(X)) >? isNat#(activate(X)) isNat#(n!6220!6220s(X)) >? activate#(X) plus#(X, 0) >? U31#(isNat(X), X) plus#(X, 0) >? isNat#(X) plus#(X, s(Y)) >? U41#(isNat(Y), Y, X) plus#(X, s(Y)) >? isNat#(Y) activate#(n!6220!6220plus(X, Y)) >? plus#(X, Y) U11(tt, X) >= U12(isNat(activate(X))) U12(tt) >= tt U21(tt) >= tt U31(tt, X) >= activate(X) U41(tt, X, Y) >= U42(isNat(activate(Y)), activate(X), activate(Y)) U42(tt, X, Y) >= s(plus(activate(Y), activate(X))) isNat(n!6220!62200) >= tt isNat(n!6220!6220plus(X, Y)) >= U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) >= U21(isNat(activate(X))) plus(X, 0) >= U31(isNat(X), X) plus(X, s(Y)) >= U41(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(X) >= X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.0 U11# = \y0y1.2y1 U12 = \y0.0 U21 = \y0.0 U31 = \y0y1.y1 U31# = \y0y1.2y1 U41 = \y0y1y2.1 + y1 + y2 U41# = \y0y1y2.2y1 + 2y2 U42 = \y0y1y2.1 + y1 + y2 U42# = \y0y1y2.2y1 + 2y2 activate = \y0.y0 activate# = \y0.2y0 isNat = \y0.0 isNat# = \y0.2y0 n!6220!62200 = 0 n!6220!6220plus = \y0y1.1 + y0 + y1 n!6220!6220s = \y0.y0 plus = \y0y1.1 + y0 + y1 plus# = \y0y1.2y0 + 2y1 s = \y0.y0 tt = 0 Using this interpretation, the requirements translate to: [[U11#(tt, _x0)]] = 2x0 >= 2x0 = [[isNat#(activate(_x0))]] [[U11#(tt, _x0)]] = 2x0 >= 2x0 = [[activate#(_x0)]] [[U31#(tt, _x0)]] = 2x0 >= 2x0 = [[activate#(_x0)]] [[U41#(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U42#(isNat(activate(_x1)), activate(_x0), activate(_x1))]] [[U41#(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x1 = [[isNat#(activate(_x1))]] [[U41#(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x1 = [[activate#(_x1)]] [[U41#(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x0 = [[activate#(_x0)]] [[U41#(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x1 = [[activate#(_x1)]] [[U42#(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus#(activate(_x1), activate(_x0))]] [[U42#(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x1 = [[activate#(_x1)]] [[U42#(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x0 = [[activate#(_x0)]] [[isNat#(n!6220!6220plus(_x0, _x1))]] = 2 + 2x0 + 2x1 > 2x1 = [[U11#(isNat(activate(_x0)), activate(_x1))]] [[isNat#(n!6220!6220plus(_x0, _x1))]] = 2 + 2x0 + 2x1 > 2x0 = [[isNat#(activate(_x0))]] [[isNat#(n!6220!6220plus(_x0, _x1))]] = 2 + 2x0 + 2x1 > 2x0 = [[activate#(_x0)]] [[isNat#(n!6220!6220plus(_x0, _x1))]] = 2 + 2x0 + 2x1 > 2x1 = [[activate#(_x1)]] [[isNat#(n!6220!6220s(_x0))]] = 2x0 >= 2x0 = [[isNat#(activate(_x0))]] [[isNat#(n!6220!6220s(_x0))]] = 2x0 >= 2x0 = [[activate#(_x0)]] [[plus#(_x0, 0)]] = 2x0 >= 2x0 = [[U31#(isNat(_x0), _x0)]] [[plus#(_x0, 0)]] = 2x0 >= 2x0 = [[isNat#(_x0)]] [[plus#(_x0, s(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U41#(isNat(_x1), _x1, _x0)]] [[plus#(_x0, s(_x1))]] = 2x0 + 2x1 >= 2x1 = [[isNat#(_x1)]] [[activate#(n!6220!6220plus(_x0, _x1))]] = 2 + 2x0 + 2x1 > 2x0 + 2x1 = [[plus#(_x0, _x1)]] [[U11(tt, _x0)]] = 0 >= 0 = [[U12(isNat(activate(_x0)))]] [[U12(tt)]] = 0 >= 0 = [[tt]] [[U21(tt)]] = 0 >= 0 = [[tt]] [[U31(tt, _x0)]] = x0 >= x0 = [[activate(_x0)]] [[U41(tt, _x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U42(isNat(activate(_x1)), activate(_x0), activate(_x1))]] [[U42(tt, _x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[s(plus(activate(_x1), activate(_x0)))]] [[isNat(n!6220!62200)]] = 0 >= 0 = [[tt]] [[isNat(n!6220!6220plus(_x0, _x1))]] = 0 >= 0 = [[U11(isNat(activate(_x0)), activate(_x1))]] [[isNat(n!6220!6220s(_x0))]] = 0 >= 0 = [[U21(isNat(activate(_x0)))]] [[plus(_x0, 0)]] = 1 + x0 >= x0 = [[U31(isNat(_x0), _x0)]] [[plus(_x0, s(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U41(isNat(_x1), _x1, _x0)]] [[0]] = 0 >= 0 = [[n!6220!62200]] [[plus(_x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[n!6220!6220plus(_x0, _x1)]] [[s(_x0)]] = x0 >= x0 = [[n!6220!6220s(_x0)]] [[activate(n!6220!62200)]] = 0 >= 0 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[plus(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = x0 >= x0 = [[s(_x0)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_2, R_0, minimal, formative), where P_2 consists of: U11#(tt, X) =#> isNat#(activate(X)) U11#(tt, X) =#> activate#(X) U31#(tt, X) =#> activate#(X) U41#(tt, X, Y) =#> U42#(isNat(activate(Y)), activate(X), activate(Y)) U41#(tt, X, Y) =#> isNat#(activate(Y)) U41#(tt, X, Y) =#> activate#(Y) U41#(tt, X, Y) =#> activate#(X) U41#(tt, X, Y) =#> activate#(Y) U42#(tt, X, Y) =#> plus#(activate(Y), activate(X)) U42#(tt, X, Y) =#> activate#(Y) U42#(tt, X, Y) =#> activate#(X) isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) isNat#(n!6220!6220s(X)) =#> activate#(X) plus#(X, 0) =#> U31#(isNat(X), X) plus#(X, 0) =#> isNat#(X) plus#(X, s(Y)) =#> U41#(isNat(Y), Y, X) plus#(X, s(Y)) =#> isNat#(Y) Thus, the original system is terminating if (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 11, 12 * 1 : * 2 : * 3 : 8, 9, 10 * 4 : 11, 12 * 5 : * 6 : * 7 : * 8 : 13, 14, 15, 16 * 9 : * 10 : * 11 : 11, 12 * 12 : * 13 : 2 * 14 : 11, 12 * 15 : 3, 4, 5, 6, 7 * 16 : 11, 12 This graph has the following strongly connected components: P_3: U41#(tt, X, Y) =#> U42#(isNat(activate(Y)), activate(X), activate(Y)) U42#(tt, X, Y) =#> plus#(activate(Y), activate(X)) plus#(X, s(Y)) =#> U41#(isNat(Y), Y, X) P_4: isNat#(n!6220!6220s(X)) =#> isNat#(activate(X)) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_2, R_0, m, f) by (P_3, R_0, m, f) and (P_4, R_0, m, f). Thus, the original system is terminating if each of (P_3, R_0, minimal, formative) and (P_4, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: isNat#(n!6220!6220s(X)) >? isNat#(activate(X)) U11(tt, X) >= U12(isNat(activate(X))) U12(tt) >= tt U21(tt) >= tt U31(tt, X) >= activate(X) U41(tt, X, Y) >= U42(isNat(activate(Y)), activate(X), activate(Y)) U42(tt, X, Y) >= s(plus(activate(Y), activate(X))) isNat(n!6220!62200) >= tt isNat(n!6220!6220plus(X, Y)) >= U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) >= U21(isNat(activate(X))) plus(X, 0) >= U31(isNat(X), X) plus(X, s(Y)) >= U41(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(X) >= X We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: U31(x_1,x_2) = U31(x_2) U41(x_1,x_2,x_3) = U41(x_2x_3) U42(x_1,x_2,x_3) = U42(x_2x_3) This leaves the following ordering requirements: isNat#(n!6220!6220s(X)) > isNat#(activate(X)) U31(tt, X) >= activate(X) U41(tt, X, Y) >= U42(isNat(activate(Y)), activate(X), activate(Y)) U42(tt, X, Y) >= s(plus(activate(Y), activate(X))) plus(X, 0) >= U31(isNat(X), X) plus(X, s(Y)) >= U41(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(X) >= X The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.0 U12 = \y0.0 U21 = \y0.0 U31 = \y0y1.y1 U41 = \y0y1y2.3 + y1 + y2 U42 = \y0y1y2.3 + y1 + y2 activate = \y0.y0 isNat = \y0.0 isNat# = \y0.3y0 n!6220!62200 = 0 n!6220!6220plus = \y0y1.y0 + y1 n!6220!6220s = \y0.3 + y0 plus = \y0y1.y0 + y1 s = \y0.3 + y0 tt = 0 Using this interpretation, the requirements translate to: [[isNat#(n!6220!6220s(_x0))]] = 9 + 3x0 > 3x0 = [[isNat#(activate(_x0))]] [[U31(tt, _x0)]] = x0 >= x0 = [[activate(_x0)]] [[U41(tt, _x0, _x1)]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[U42(isNat(activate(_x1)), activate(_x0), activate(_x1))]] [[U42(tt, _x0, _x1)]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[s(plus(activate(_x1), activate(_x0)))]] [[plus(_x0, 0)]] = x0 >= x0 = [[U31(isNat(_x0), _x0)]] [[plus(_x0, s(_x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[U41(isNat(_x1), _x1, _x0)]] [[0]] = 0 >= 0 = [[n!6220!62200]] [[plus(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220plus(_x0, _x1)]] [[s(_x0)]] = 3 + x0 >= 3 + x0 = [[n!6220!6220s(_x0)]] [[activate(n!6220!62200)]] = 0 >= 0 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[plus(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = 3 + x0 >= 3 + x0 = [[s(_x0)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_4, R_0) by ({}, R_0). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if (P_3, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_3, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: U41#(tt, X, Y) >? U42#(isNat(activate(Y)), activate(X), activate(Y)) U42#(tt, X, Y) >? plus#(activate(Y), activate(X)) plus#(X, s(Y)) >? U41#(isNat(Y), Y, X) U11(tt, X) >= U12(isNat(activate(X))) U12(tt) >= tt U21(tt) >= tt U31(tt, X) >= activate(X) U41(tt, X, Y) >= U42(isNat(activate(Y)), activate(X), activate(Y)) U42(tt, X, Y) >= s(plus(activate(Y), activate(X))) isNat(n!6220!62200) >= tt isNat(n!6220!6220plus(X, Y)) >= U11(isNat(activate(X)), activate(Y)) isNat(n!6220!6220s(X)) >= U21(isNat(activate(X))) plus(X, 0) >= U31(isNat(X), X) plus(X, s(Y)) >= U41(isNat(Y), Y, X) 0 >= n!6220!62200 plus(X, Y) >= n!6220!6220plus(X, Y) s(X) >= n!6220!6220s(X) activate(n!6220!62200) >= 0 activate(n!6220!6220plus(X, Y)) >= plus(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(X) >= X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U11 = \y0y1.y0 U12 = \y0.2 U21 = \y0.2 U31 = \y0y1.2y1 U41 = \y0y1y2.2y0 + 2y1 + 2y2 U41# = \y0y1y2.1 + y1 U42 = \y0y1y2.1 + y0 + 2y1 + 2y2 U42# = \y0y1y2.y1 activate = \y0.y0 isNat = \y0.2 n!6220!62200 = 0 n!6220!6220plus = \y0y1.2 + 2y0 + 2y1 n!6220!6220s = \y0.1 + y0 plus = \y0y1.2 + 2y0 + 2y1 plus# = \y0y1.y1 s = \y0.1 + y0 tt = 2 Using this interpretation, the requirements translate to: [[U41#(tt, _x0, _x1)]] = 1 + x0 > x0 = [[U42#(isNat(activate(_x1)), activate(_x0), activate(_x1))]] [[U42#(tt, _x0, _x1)]] = x0 >= x0 = [[plus#(activate(_x1), activate(_x0))]] [[plus#(_x0, s(_x1))]] = 1 + x1 >= 1 + x1 = [[U41#(isNat(_x1), _x1, _x0)]] [[U11(tt, _x0)]] = 2 >= 2 = [[U12(isNat(activate(_x0)))]] [[U12(tt)]] = 2 >= 2 = [[tt]] [[U21(tt)]] = 2 >= 2 = [[tt]] [[U31(tt, _x0)]] = 2x0 >= x0 = [[activate(_x0)]] [[U41(tt, _x0, _x1)]] = 4 + 2x0 + 2x1 >= 3 + 2x0 + 2x1 = [[U42(isNat(activate(_x1)), activate(_x0), activate(_x1))]] [[U42(tt, _x0, _x1)]] = 3 + 2x0 + 2x1 >= 3 + 2x0 + 2x1 = [[s(plus(activate(_x1), activate(_x0)))]] [[isNat(n!6220!62200)]] = 2 >= 2 = [[tt]] [[isNat(n!6220!6220plus(_x0, _x1))]] = 2 >= 2 = [[U11(isNat(activate(_x0)), activate(_x1))]] [[isNat(n!6220!6220s(_x0))]] = 2 >= 2 = [[U21(isNat(activate(_x0)))]] [[plus(_x0, 0)]] = 2 + 2x0 >= 2x0 = [[U31(isNat(_x0), _x0)]] [[plus(_x0, s(_x1))]] = 4 + 2x0 + 2x1 >= 4 + 2x0 + 2x1 = [[U41(isNat(_x1), _x1, _x0)]] [[0]] = 0 >= 0 = [[n!6220!62200]] [[plus(_x0, _x1)]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[n!6220!6220plus(_x0, _x1)]] [[s(_x0)]] = 1 + x0 >= 1 + x0 = [[n!6220!6220s(_x0)]] [[activate(n!6220!62200)]] = 0 >= 0 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[plus(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = 1 + x0 >= 1 + x0 = [[s(_x0)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_3, R_0, minimal, formative) by (P_5, R_0, minimal, formative), where P_5 consists of: U42#(tt, X, Y) =#> plus#(activate(Y), activate(X)) plus#(X, s(Y)) =#> U41#(isNat(Y), Y, X) Thus, the original system is terminating if (P_5, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_5, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 1 * 1 : This graph has no strongly connected components. By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem. As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. [KusIsoSakBla09] K. Kusakari, Y. Isogai, M. Sakai, and F. Blanqui. Static Dependency Pair Method Based On Strong Computability for Higher-Order Rewrite Systems. In volume 92(10) of IEICE Transactions on Information and Systems. 2007--2015, 2009.