/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 activate : [o] --> o add : [o * o] --> o cons : [o * o] --> o dbl : [o] --> o first : [o * o] --> o n!6220!6220add : [o * o] --> o n!6220!6220dbl : [o] --> o n!6220!6220first : [o * o] --> o n!6220!6220s : [o] --> o n!6220!6220terms : [o] --> o nil : [] --> o recip : [o] --> o s : [o] --> o sqr : [o] --> o terms : [o] --> o terms(X) => cons(recip(sqr(X)), n!6220!6220terms(s(X))) sqr(0) => 0 sqr(s(X)) => s(n!6220!6220add(sqr(activate(X)), dbl(activate(X)))) dbl(0) => 0 dbl(s(X)) => s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) => X add(s(X), Y) => s(n!6220!6220add(activate(X), Y)) first(0, X) => nil first(s(X), cons(Y, Z)) => cons(Y, n!6220!6220first(activate(X), activate(Z))) terms(X) => n!6220!6220terms(X) add(X, Y) => n!6220!6220add(X, Y) s(X) => n!6220!6220s(X) dbl(X) => n!6220!6220dbl(X) first(X, Y) => n!6220!6220first(X, Y) activate(n!6220!6220terms(X)) => terms(X) activate(n!6220!6220add(X, Y)) => add(X, Y) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220dbl(X)) => dbl(X) activate(n!6220!6220first(X, Y)) => first(X, Y) 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] terms#(X) =#> sqr#(X) 1] terms#(X) =#> s#(X) 2] sqr#(s(X)) =#> s#(n!6220!6220add(sqr(activate(X)), dbl(activate(X)))) 3] sqr#(s(X)) =#> sqr#(activate(X)) 4] sqr#(s(X)) =#> activate#(X) 5] sqr#(s(X)) =#> dbl#(activate(X)) 6] sqr#(s(X)) =#> activate#(X) 7] dbl#(s(X)) =#> s#(n!6220!6220s(n!6220!6220dbl(activate(X)))) 8] dbl#(s(X)) =#> activate#(X) 9] add#(s(X), Y) =#> s#(n!6220!6220add(activate(X), Y)) 10] add#(s(X), Y) =#> activate#(X) 11] first#(s(X), cons(Y, Z)) =#> activate#(X) 12] first#(s(X), cons(Y, Z)) =#> activate#(Z) 13] activate#(n!6220!6220terms(X)) =#> terms#(X) 14] activate#(n!6220!6220add(X, Y)) =#> add#(X, Y) 15] activate#(n!6220!6220s(X)) =#> s#(X) 16] activate#(n!6220!6220dbl(X)) =#> dbl#(X) 17] activate#(n!6220!6220first(X, Y)) =#> first#(X, Y) Rules R_0: terms(X) => cons(recip(sqr(X)), n!6220!6220terms(s(X))) sqr(0) => 0 sqr(s(X)) => s(n!6220!6220add(sqr(activate(X)), dbl(activate(X)))) dbl(0) => 0 dbl(s(X)) => s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) => X add(s(X), Y) => s(n!6220!6220add(activate(X), Y)) first(0, X) => nil first(s(X), cons(Y, Z)) => cons(Y, n!6220!6220first(activate(X), activate(Z))) terms(X) => n!6220!6220terms(X) add(X, Y) => n!6220!6220add(X, Y) s(X) => n!6220!6220s(X) dbl(X) => n!6220!6220dbl(X) first(X, Y) => n!6220!6220first(X, Y) activate(n!6220!6220terms(X)) => terms(X) activate(n!6220!6220add(X, Y)) => add(X, Y) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220dbl(X)) => dbl(X) activate(n!6220!6220first(X, Y)) => first(X, Y) 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 : 2, 3, 4, 5, 6 * 1 : * 2 : * 3 : 2, 3, 4, 5, 6 * 4 : 13, 14, 15, 16, 17 * 5 : 7, 8 * 6 : 13, 14, 15, 16, 17 * 7 : * 8 : 13, 14, 15, 16, 17 * 9 : * 10 : 13, 14, 15, 16, 17 * 11 : 13, 14, 15, 16, 17 * 12 : 13, 14, 15, 16, 17 * 13 : 0, 1 * 14 : 9, 10 * 15 : * 16 : 7, 8 * 17 : 11, 12 This graph has the following strongly connected components: P_1: terms#(X) =#> sqr#(X) sqr#(s(X)) =#> sqr#(activate(X)) sqr#(s(X)) =#> activate#(X) sqr#(s(X)) =#> dbl#(activate(X)) sqr#(s(X)) =#> activate#(X) dbl#(s(X)) =#> activate#(X) add#(s(X), Y) =#> activate#(X) first#(s(X), cons(Y, Z)) =#> activate#(X) first#(s(X), cons(Y, Z)) =#> activate#(Z) activate#(n!6220!6220terms(X)) =#> terms#(X) activate#(n!6220!6220add(X, Y)) =#> add#(X, Y) activate#(n!6220!6220dbl(X)) =#> dbl#(X) activate#(n!6220!6220first(X, Y)) =#> first#(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). The formative rules of (P_1, R_0) are R_1 ::= terms(X) => cons(recip(sqr(X)), n!6220!6220terms(s(X))) sqr(0) => 0 sqr(s(X)) => s(n!6220!6220add(sqr(activate(X)), dbl(activate(X)))) dbl(0) => 0 dbl(s(X)) => s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) => X add(s(X), Y) => s(n!6220!6220add(activate(X), Y)) first(s(X), cons(Y, Z)) => cons(Y, n!6220!6220first(activate(X), activate(Z))) terms(X) => n!6220!6220terms(X) add(X, Y) => n!6220!6220add(X, Y) s(X) => n!6220!6220s(X) dbl(X) => n!6220!6220dbl(X) first(X, Y) => n!6220!6220first(X, Y) activate(n!6220!6220terms(X)) => terms(X) activate(n!6220!6220add(X, Y)) => add(X, Y) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220dbl(X)) => dbl(X) activate(n!6220!6220first(X, Y)) => first(X, Y) activate(X) => X By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_1, R_1, minimal, formative). Thus, the original system is terminating if (P_1, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_1, 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: terms#(X) >? sqr#(X) sqr#(s(X)) >? sqr#(activate(X)) sqr#(s(X)) >? activate#(X) sqr#(s(X)) >? dbl#(activate(X)) sqr#(s(X)) >? activate#(X) dbl#(s(X)) >? activate#(X) add#(s(X), Y) >? activate#(X) first#(s(X), cons(Y, Z)) >? activate#(X) first#(s(X), cons(Y, Z)) >? activate#(Z) activate#(n!6220!6220terms(X)) >? terms#(X) activate#(n!6220!6220add(X, Y)) >? add#(X, Y) activate#(n!6220!6220dbl(X)) >? dbl#(X) activate#(n!6220!6220first(X, Y)) >? first#(X, Y) terms(X) >= cons(recip(sqr(X)), n!6220!6220terms(s(X))) sqr(0) >= 0 sqr(s(X)) >= s(n!6220!6220add(sqr(activate(X)), dbl(activate(X)))) dbl(0) >= 0 dbl(s(X)) >= s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) >= X add(s(X), Y) >= s(n!6220!6220add(activate(X), Y)) first(s(X), cons(Y, Z)) >= cons(Y, n!6220!6220first(activate(X), activate(Z))) terms(X) >= n!6220!6220terms(X) add(X, Y) >= n!6220!6220add(X, Y) s(X) >= n!6220!6220s(X) dbl(X) >= n!6220!6220dbl(X) first(X, Y) >= n!6220!6220first(X, Y) activate(n!6220!6220terms(X)) >= terms(X) activate(n!6220!6220add(X, Y)) >= add(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220dbl(X)) >= dbl(X) activate(n!6220!6220first(X, Y)) >= first(X, Y) 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: recip(x_1) = recip() This leaves the following ordering requirements: terms#(X) >= sqr#(X) sqr#(s(X)) >= sqr#(activate(X)) sqr#(s(X)) >= activate#(X) sqr#(s(X)) >= dbl#(activate(X)) sqr#(s(X)) >= activate#(X) dbl#(s(X)) >= activate#(X) add#(s(X), Y) >= activate#(X) first#(s(X), cons(Y, Z)) >= activate#(X) first#(s(X), cons(Y, Z)) >= activate#(Z) activate#(n!6220!6220terms(X)) >= terms#(X) activate#(n!6220!6220add(X, Y)) > add#(X, Y) activate#(n!6220!6220dbl(X)) >= dbl#(X) activate#(n!6220!6220first(X, Y)) >= first#(X, Y) terms(X) >= cons(recip(sqr(X)), n!6220!6220terms(s(X))) dbl(0) >= 0 dbl(s(X)) >= s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) >= X add(s(X), Y) >= s(n!6220!6220add(activate(X), Y)) first(s(X), cons(Y, Z)) >= cons(Y, n!6220!6220first(activate(X), activate(Z))) terms(X) >= n!6220!6220terms(X) add(X, Y) >= n!6220!6220add(X, Y) s(X) >= n!6220!6220s(X) dbl(X) >= n!6220!6220dbl(X) first(X, Y) >= n!6220!6220first(X, Y) activate(n!6220!6220terms(X)) >= terms(X) activate(n!6220!6220add(X, Y)) >= add(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220dbl(X)) >= dbl(X) activate(n!6220!6220first(X, Y)) >= first(X, Y) activate(X) >= X The following interpretation satisfies the requirements: 0 = 0 activate = \y0.y0 activate# = \y0.y0 add = \y0y1.1 + y0 + y1 add# = \y0y1.y0 cons = \y0y1.y1 dbl = \y0.y0 dbl# = \y0.y0 first = \y0y1.y0 + y1 first# = \y0y1.y0 + y1 n!6220!6220add = \y0y1.1 + y0 + y1 n!6220!6220dbl = \y0.y0 n!6220!6220first = \y0y1.y0 + y1 n!6220!6220s = \y0.y0 n!6220!6220terms = \y0.y0 recip = \y0.0 s = \y0.y0 sqr = \y0.0 sqr# = \y0.y0 terms = \y0.y0 terms# = \y0.y0 Using this interpretation, the requirements translate to: [[terms#(_x0)]] = x0 >= x0 = [[sqr#(_x0)]] [[sqr#(s(_x0))]] = x0 >= x0 = [[sqr#(activate(_x0))]] [[sqr#(s(_x0))]] = x0 >= x0 = [[activate#(_x0)]] [[sqr#(s(_x0))]] = x0 >= x0 = [[dbl#(activate(_x0))]] [[sqr#(s(_x0))]] = x0 >= x0 = [[activate#(_x0)]] [[dbl#(s(_x0))]] = x0 >= x0 = [[activate#(_x0)]] [[add#(s(_x0), _x1)]] = x0 >= x0 = [[activate#(_x0)]] [[first#(s(_x0), cons(_x1, _x2))]] = x0 + x2 >= x0 = [[activate#(_x0)]] [[first#(s(_x0), cons(_x1, _x2))]] = x0 + x2 >= x2 = [[activate#(_x2)]] [[activate#(n!6220!6220terms(_x0))]] = x0 >= x0 = [[terms#(_x0)]] [[activate#(n!6220!6220add(_x0, _x1))]] = 1 + x0 + x1 > x0 = [[add#(_x0, _x1)]] [[activate#(n!6220!6220dbl(_x0))]] = x0 >= x0 = [[dbl#(_x0)]] [[activate#(n!6220!6220first(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[first#(_x0, _x1)]] [[terms(_x0)]] = x0 >= x0 = [[cons(recip(sqr(_x0)), n!6220!6220terms(s(_x0)))]] [[dbl(0)]] = 0 >= 0 = [[0]] [[dbl(s(_x0))]] = x0 >= x0 = [[s(n!6220!6220s(n!6220!6220dbl(activate(_x0))))]] [[add(0, _x0)]] = 1 + x0 >= x0 = [[_x0]] [[add(s(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[s(n!6220!6220add(activate(_x0), _x1))]] [[first(s(_x0), cons(_x1, _x2))]] = x0 + x2 >= x0 + x2 = [[cons(_x1, n!6220!6220first(activate(_x0), activate(_x2)))]] [[terms(_x0)]] = x0 >= x0 = [[n!6220!6220terms(_x0)]] [[add(_x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[n!6220!6220add(_x0, _x1)]] [[s(_x0)]] = x0 >= x0 = [[n!6220!6220s(_x0)]] [[dbl(_x0)]] = x0 >= x0 = [[n!6220!6220dbl(_x0)]] [[first(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220first(_x0, _x1)]] [[activate(n!6220!6220terms(_x0))]] = x0 >= x0 = [[terms(_x0)]] [[activate(n!6220!6220add(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[add(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = x0 >= x0 = [[s(_x0)]] [[activate(n!6220!6220dbl(_x0))]] = x0 >= x0 = [[dbl(_x0)]] [[activate(n!6220!6220first(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[first(_x0, _x1)]] [[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_1, minimal, formative) by (P_2, R_1, minimal, formative), where P_2 consists of: terms#(X) =#> sqr#(X) sqr#(s(X)) =#> sqr#(activate(X)) sqr#(s(X)) =#> activate#(X) sqr#(s(X)) =#> dbl#(activate(X)) sqr#(s(X)) =#> activate#(X) dbl#(s(X)) =#> activate#(X) add#(s(X), Y) =#> activate#(X) first#(s(X), cons(Y, Z)) =#> activate#(X) first#(s(X), cons(Y, Z)) =#> activate#(Z) activate#(n!6220!6220terms(X)) =#> terms#(X) activate#(n!6220!6220dbl(X)) =#> dbl#(X) activate#(n!6220!6220first(X, Y)) =#> first#(X, Y) Thus, the original system is terminating if (P_2, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_1, 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, 2, 3, 4 * 1 : 1, 2, 3, 4 * 2 : 9, 10, 11 * 3 : 5 * 4 : 9, 10, 11 * 5 : 9, 10, 11 * 6 : 9, 10, 11 * 7 : 9, 10, 11 * 8 : 9, 10, 11 * 9 : 0 * 10 : 5 * 11 : 7, 8 This graph has the following strongly connected components: P_3: terms#(X) =#> sqr#(X) sqr#(s(X)) =#> sqr#(activate(X)) sqr#(s(X)) =#> activate#(X) sqr#(s(X)) =#> dbl#(activate(X)) sqr#(s(X)) =#> activate#(X) dbl#(s(X)) =#> activate#(X) first#(s(X), cons(Y, Z)) =#> activate#(X) first#(s(X), cons(Y, Z)) =#> activate#(Z) activate#(n!6220!6220terms(X)) =#> terms#(X) activate#(n!6220!6220dbl(X)) =#> dbl#(X) activate#(n!6220!6220first(X, Y)) =#> first#(X, Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_2, R_1, m, f) by (P_3, R_1, m, f). Thus, the original system is terminating if (P_3, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_3, R_1, 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: terms#(X) >? sqr#(X) sqr#(s(X)) >? sqr#(activate(X)) sqr#(s(X)) >? activate#(X) sqr#(s(X)) >? dbl#(activate(X)) sqr#(s(X)) >? activate#(X) dbl#(s(X)) >? activate#(X) first#(s(X), cons(Y, Z)) >? activate#(X) first#(s(X), cons(Y, Z)) >? activate#(Z) activate#(n!6220!6220terms(X)) >? terms#(X) activate#(n!6220!6220dbl(X)) >? dbl#(X) activate#(n!6220!6220first(X, Y)) >? first#(X, Y) terms(X) >= cons(recip(sqr(X)), n!6220!6220terms(s(X))) sqr(0) >= 0 sqr(s(X)) >= s(n!6220!6220add(sqr(activate(X)), dbl(activate(X)))) dbl(0) >= 0 dbl(s(X)) >= s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) >= X add(s(X), Y) >= s(n!6220!6220add(activate(X), Y)) first(s(X), cons(Y, Z)) >= cons(Y, n!6220!6220first(activate(X), activate(Z))) terms(X) >= n!6220!6220terms(X) add(X, Y) >= n!6220!6220add(X, Y) s(X) >= n!6220!6220s(X) dbl(X) >= n!6220!6220dbl(X) first(X, Y) >= n!6220!6220first(X, Y) activate(n!6220!6220terms(X)) >= terms(X) activate(n!6220!6220add(X, Y)) >= add(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220dbl(X)) >= dbl(X) activate(n!6220!6220first(X, Y)) >= first(X, Y) 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: recip(x_1) = recip() This leaves the following ordering requirements: terms#(X) >= sqr#(X) sqr#(s(X)) >= sqr#(activate(X)) sqr#(s(X)) >= activate#(X) sqr#(s(X)) >= dbl#(activate(X)) sqr#(s(X)) >= activate#(X) dbl#(s(X)) >= activate#(X) first#(s(X), cons(Y, Z)) >= activate#(X) first#(s(X), cons(Y, Z)) >= activate#(Z) activate#(n!6220!6220terms(X)) >= terms#(X) activate#(n!6220!6220dbl(X)) > dbl#(X) activate#(n!6220!6220first(X, Y)) >= first#(X, Y) terms(X) >= cons(recip(sqr(X)), n!6220!6220terms(s(X))) dbl(0) >= 0 dbl(s(X)) >= s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) >= X add(s(X), Y) >= s(n!6220!6220add(activate(X), Y)) first(s(X), cons(Y, Z)) >= cons(Y, n!6220!6220first(activate(X), activate(Z))) terms(X) >= n!6220!6220terms(X) add(X, Y) >= n!6220!6220add(X, Y) s(X) >= n!6220!6220s(X) dbl(X) >= n!6220!6220dbl(X) first(X, Y) >= n!6220!6220first(X, Y) activate(n!6220!6220terms(X)) >= terms(X) activate(n!6220!6220add(X, Y)) >= add(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220dbl(X)) >= dbl(X) activate(n!6220!6220first(X, Y)) >= first(X, Y) activate(X) >= X The following interpretation satisfies the requirements: 0 = 0 activate = \y0.y0 activate# = \y0.y0 add = \y0y1.y1 cons = \y0y1.y0 + y1 dbl = \y0.1 + y0 dbl# = \y0.y0 first = \y0y1.2y0 + 2y1 first# = \y0y1.2y0 + 2y1 n!6220!6220add = \y0y1.y1 n!6220!6220dbl = \y0.1 + y0 n!6220!6220first = \y0y1.2y0 + 2y1 n!6220!6220s = \y0.y0 n!6220!6220terms = \y0.y0 recip = \y0.0 s = \y0.y0 sqr = \y0.0 sqr# = \y0.y0 terms = \y0.y0 terms# = \y0.y0 Using this interpretation, the requirements translate to: [[terms#(_x0)]] = x0 >= x0 = [[sqr#(_x0)]] [[sqr#(s(_x0))]] = x0 >= x0 = [[sqr#(activate(_x0))]] [[sqr#(s(_x0))]] = x0 >= x0 = [[activate#(_x0)]] [[sqr#(s(_x0))]] = x0 >= x0 = [[dbl#(activate(_x0))]] [[sqr#(s(_x0))]] = x0 >= x0 = [[activate#(_x0)]] [[dbl#(s(_x0))]] = x0 >= x0 = [[activate#(_x0)]] [[first#(s(_x0), cons(_x1, _x2))]] = 2x0 + 2x1 + 2x2 >= x0 = [[activate#(_x0)]] [[first#(s(_x0), cons(_x1, _x2))]] = 2x0 + 2x1 + 2x2 >= x2 = [[activate#(_x2)]] [[activate#(n!6220!6220terms(_x0))]] = x0 >= x0 = [[terms#(_x0)]] [[activate#(n!6220!6220dbl(_x0))]] = 1 + x0 > x0 = [[dbl#(_x0)]] [[activate#(n!6220!6220first(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[first#(_x0, _x1)]] [[terms(_x0)]] = x0 >= x0 = [[cons(recip(sqr(_x0)), n!6220!6220terms(s(_x0)))]] [[dbl(0)]] = 1 >= 0 = [[0]] [[dbl(s(_x0))]] = 1 + x0 >= 1 + x0 = [[s(n!6220!6220s(n!6220!6220dbl(activate(_x0))))]] [[add(0, _x0)]] = x0 >= x0 = [[_x0]] [[add(s(_x0), _x1)]] = x1 >= x1 = [[s(n!6220!6220add(activate(_x0), _x1))]] [[first(s(_x0), cons(_x1, _x2))]] = 2x0 + 2x1 + 2x2 >= x1 + 2x0 + 2x2 = [[cons(_x1, n!6220!6220first(activate(_x0), activate(_x2)))]] [[terms(_x0)]] = x0 >= x0 = [[n!6220!6220terms(_x0)]] [[add(_x0, _x1)]] = x1 >= x1 = [[n!6220!6220add(_x0, _x1)]] [[s(_x0)]] = x0 >= x0 = [[n!6220!6220s(_x0)]] [[dbl(_x0)]] = 1 + x0 >= 1 + x0 = [[n!6220!6220dbl(_x0)]] [[first(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[n!6220!6220first(_x0, _x1)]] [[activate(n!6220!6220terms(_x0))]] = x0 >= x0 = [[terms(_x0)]] [[activate(n!6220!6220add(_x0, _x1))]] = x1 >= x1 = [[add(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = x0 >= x0 = [[s(_x0)]] [[activate(n!6220!6220dbl(_x0))]] = 1 + x0 >= 1 + x0 = [[dbl(_x0)]] [[activate(n!6220!6220first(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[first(_x0, _x1)]] [[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_1, minimal, formative) by (P_4, R_1, minimal, formative), where P_4 consists of: terms#(X) =#> sqr#(X) sqr#(s(X)) =#> sqr#(activate(X)) sqr#(s(X)) =#> activate#(X) sqr#(s(X)) =#> dbl#(activate(X)) sqr#(s(X)) =#> activate#(X) dbl#(s(X)) =#> activate#(X) first#(s(X), cons(Y, Z)) =#> activate#(X) first#(s(X), cons(Y, Z)) =#> activate#(Z) activate#(n!6220!6220terms(X)) =#> terms#(X) activate#(n!6220!6220first(X, Y)) =#> first#(X, Y) Thus, the original system is terminating if (P_4, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_1, 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: terms#(X) >? sqr#(X) sqr#(s(X)) >? sqr#(activate(X)) sqr#(s(X)) >? activate#(X) sqr#(s(X)) >? dbl#(activate(X)) sqr#(s(X)) >? activate#(X) dbl#(s(X)) >? activate#(X) first#(s(X), cons(Y, Z)) >? activate#(X) first#(s(X), cons(Y, Z)) >? activate#(Z) activate#(n!6220!6220terms(X)) >? terms#(X) activate#(n!6220!6220first(X, Y)) >? first#(X, Y) terms(X) >= cons(recip(sqr(X)), n!6220!6220terms(s(X))) sqr(0) >= 0 sqr(s(X)) >= s(n!6220!6220add(sqr(activate(X)), dbl(activate(X)))) dbl(0) >= 0 dbl(s(X)) >= s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) >= X add(s(X), Y) >= s(n!6220!6220add(activate(X), Y)) first(s(X), cons(Y, Z)) >= cons(Y, n!6220!6220first(activate(X), activate(Z))) terms(X) >= n!6220!6220terms(X) add(X, Y) >= n!6220!6220add(X, Y) s(X) >= n!6220!6220s(X) dbl(X) >= n!6220!6220dbl(X) first(X, Y) >= n!6220!6220first(X, Y) activate(n!6220!6220terms(X)) >= terms(X) activate(n!6220!6220add(X, Y)) >= add(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220dbl(X)) >= dbl(X) activate(n!6220!6220first(X, Y)) >= first(X, Y) 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: recip(x_1) = recip() This leaves the following ordering requirements: terms#(X) >= sqr#(X) sqr#(s(X)) >= sqr#(activate(X)) sqr#(s(X)) >= activate#(X) sqr#(s(X)) >= dbl#(activate(X)) sqr#(s(X)) >= activate#(X) dbl#(s(X)) >= activate#(X) first#(s(X), cons(Y, Z)) > activate#(X) first#(s(X), cons(Y, Z)) > activate#(Z) activate#(n!6220!6220terms(X)) >= terms#(X) activate#(n!6220!6220first(X, Y)) >= first#(X, Y) terms(X) >= cons(recip(sqr(X)), n!6220!6220terms(s(X))) dbl(0) >= 0 dbl(s(X)) >= s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) >= X add(s(X), Y) >= s(n!6220!6220add(activate(X), Y)) first(s(X), cons(Y, Z)) >= cons(Y, n!6220!6220first(activate(X), activate(Z))) terms(X) >= n!6220!6220terms(X) add(X, Y) >= n!6220!6220add(X, Y) s(X) >= n!6220!6220s(X) dbl(X) >= n!6220!6220dbl(X) first(X, Y) >= n!6220!6220first(X, Y) activate(n!6220!6220terms(X)) >= terms(X) activate(n!6220!6220add(X, Y)) >= add(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220dbl(X)) >= dbl(X) activate(n!6220!6220first(X, Y)) >= first(X, Y) activate(X) >= X The following interpretation satisfies the requirements: 0 = 0 activate = \y0.y0 activate# = \y0.y0 add = \y0y1.y1 cons = \y0y1.y1 dbl = \y0.0 dbl# = \y0.y0 first = \y0y1.1 + y0 + 2y1 first# = \y0y1.1 + y0 + 2y1 n!6220!6220add = \y0y1.y1 n!6220!6220dbl = \y0.0 n!6220!6220first = \y0y1.1 + y0 + 2y1 n!6220!6220s = \y0.y0 n!6220!6220terms = \y0.y0 recip = \y0.0 s = \y0.y0 sqr = \y0.0 sqr# = \y0.y0 terms = \y0.y0 terms# = \y0.y0 Using this interpretation, the requirements translate to: [[terms#(_x0)]] = x0 >= x0 = [[sqr#(_x0)]] [[sqr#(s(_x0))]] = x0 >= x0 = [[sqr#(activate(_x0))]] [[sqr#(s(_x0))]] = x0 >= x0 = [[activate#(_x0)]] [[sqr#(s(_x0))]] = x0 >= x0 = [[dbl#(activate(_x0))]] [[sqr#(s(_x0))]] = x0 >= x0 = [[activate#(_x0)]] [[dbl#(s(_x0))]] = x0 >= x0 = [[activate#(_x0)]] [[first#(s(_x0), cons(_x1, _x2))]] = 1 + x0 + 2x2 > x0 = [[activate#(_x0)]] [[first#(s(_x0), cons(_x1, _x2))]] = 1 + x0 + 2x2 > x2 = [[activate#(_x2)]] [[activate#(n!6220!6220terms(_x0))]] = x0 >= x0 = [[terms#(_x0)]] [[activate#(n!6220!6220first(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[first#(_x0, _x1)]] [[terms(_x0)]] = x0 >= x0 = [[cons(recip(sqr(_x0)), n!6220!6220terms(s(_x0)))]] [[dbl(0)]] = 0 >= 0 = [[0]] [[dbl(s(_x0))]] = 0 >= 0 = [[s(n!6220!6220s(n!6220!6220dbl(activate(_x0))))]] [[add(0, _x0)]] = x0 >= x0 = [[_x0]] [[add(s(_x0), _x1)]] = x1 >= x1 = [[s(n!6220!6220add(activate(_x0), _x1))]] [[first(s(_x0), cons(_x1, _x2))]] = 1 + x0 + 2x2 >= 1 + x0 + 2x2 = [[cons(_x1, n!6220!6220first(activate(_x0), activate(_x2)))]] [[terms(_x0)]] = x0 >= x0 = [[n!6220!6220terms(_x0)]] [[add(_x0, _x1)]] = x1 >= x1 = [[n!6220!6220add(_x0, _x1)]] [[s(_x0)]] = x0 >= x0 = [[n!6220!6220s(_x0)]] [[dbl(_x0)]] = 0 >= 0 = [[n!6220!6220dbl(_x0)]] [[first(_x0, _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[n!6220!6220first(_x0, _x1)]] [[activate(n!6220!6220terms(_x0))]] = x0 >= x0 = [[terms(_x0)]] [[activate(n!6220!6220add(_x0, _x1))]] = x1 >= x1 = [[add(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = x0 >= x0 = [[s(_x0)]] [[activate(n!6220!6220dbl(_x0))]] = 0 >= 0 = [[dbl(_x0)]] [[activate(n!6220!6220first(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[first(_x0, _x1)]] [[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_4, R_1, minimal, formative) by (P_5, R_1, minimal, formative), where P_5 consists of: terms#(X) =#> sqr#(X) sqr#(s(X)) =#> sqr#(activate(X)) sqr#(s(X)) =#> activate#(X) sqr#(s(X)) =#> dbl#(activate(X)) sqr#(s(X)) =#> activate#(X) dbl#(s(X)) =#> activate#(X) activate#(n!6220!6220terms(X)) =#> terms#(X) activate#(n!6220!6220first(X, Y)) =#> first#(X, Y) Thus, the original system is terminating if (P_5, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_5, R_1, 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, 2, 3, 4 * 1 : 1, 2, 3, 4 * 2 : 6, 7 * 3 : 5 * 4 : 6, 7 * 5 : 6, 7 * 6 : 0 * 7 : This graph has the following strongly connected components: P_6: terms#(X) =#> sqr#(X) sqr#(s(X)) =#> sqr#(activate(X)) sqr#(s(X)) =#> activate#(X) sqr#(s(X)) =#> dbl#(activate(X)) sqr#(s(X)) =#> activate#(X) dbl#(s(X)) =#> activate#(X) activate#(n!6220!6220terms(X)) =#> terms#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_5, R_1, m, f) by (P_6, R_1, m, f). Thus, the original system is terminating if (P_6, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_6, R_1, minimal, formative). The formative rules of (P_6, R_1) are R_2 ::= sqr(0) => 0 sqr(s(X)) => s(n!6220!6220add(sqr(activate(X)), dbl(activate(X)))) dbl(0) => 0 dbl(s(X)) => s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) => X add(s(X), Y) => s(n!6220!6220add(activate(X), Y)) terms(X) => n!6220!6220terms(X) add(X, Y) => n!6220!6220add(X, Y) s(X) => n!6220!6220s(X) dbl(X) => n!6220!6220dbl(X) activate(n!6220!6220terms(X)) => terms(X) activate(n!6220!6220add(X, Y)) => add(X, Y) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220dbl(X)) => dbl(X) activate(X) => X By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_6, R_1, minimal, formative) by (P_6, R_2, minimal, formative). Thus, the original system is terminating if (P_6, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_6, R_2, minimal, formative). We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_6, R_2) are: dbl(0) => 0 dbl(s(X)) => s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) => X add(s(X), Y) => s(n!6220!6220add(activate(X), Y)) terms(X) => n!6220!6220terms(X) add(X, Y) => n!6220!6220add(X, Y) s(X) => n!6220!6220s(X) dbl(X) => n!6220!6220dbl(X) activate(n!6220!6220terms(X)) => terms(X) activate(n!6220!6220add(X, Y)) => add(X, Y) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220dbl(X)) => dbl(X) activate(X) => X It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: terms#(X) >? sqr#(X) sqr#(s(X)) >? sqr#(activate(X)) sqr#(s(X)) >? activate#(X) sqr#(s(X)) >? dbl#(activate(X)) sqr#(s(X)) >? activate#(X) dbl#(s(X)) >? activate#(X) activate#(n!6220!6220terms(X)) >? terms#(X) dbl(0) >= 0 dbl(s(X)) >= s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) >= X add(s(X), Y) >= s(n!6220!6220add(activate(X), Y)) terms(X) >= n!6220!6220terms(X) add(X, Y) >= n!6220!6220add(X, Y) s(X) >= n!6220!6220s(X) dbl(X) >= n!6220!6220dbl(X) activate(n!6220!6220terms(X)) >= terms(X) activate(n!6220!6220add(X, Y)) >= add(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220dbl(X)) >= dbl(X) activate(X) >= X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 activate = \y0.2y0 activate# = \y0.2y0 add = \y0y1.2y1 dbl = \y0.0 dbl# = \y0.1 + 2y0 n!6220!6220add = \y0y1.y1 n!6220!6220dbl = \y0.0 n!6220!6220s = \y0.y0 n!6220!6220terms = \y0.2 + 2y0 s = \y0.2y0 sqr# = \y0.1 + 2y0 terms = \y0.2 + 2y0 terms# = \y0.1 + 2y0 Using this interpretation, the requirements translate to: [[terms#(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[sqr#(_x0)]] [[sqr#(s(_x0))]] = 1 + 4x0 >= 1 + 4x0 = [[sqr#(activate(_x0))]] [[sqr#(s(_x0))]] = 1 + 4x0 > 2x0 = [[activate#(_x0)]] [[sqr#(s(_x0))]] = 1 + 4x0 >= 1 + 4x0 = [[dbl#(activate(_x0))]] [[sqr#(s(_x0))]] = 1 + 4x0 > 2x0 = [[activate#(_x0)]] [[dbl#(s(_x0))]] = 1 + 4x0 > 2x0 = [[activate#(_x0)]] [[activate#(n!6220!6220terms(_x0))]] = 4 + 4x0 > 1 + 2x0 = [[terms#(_x0)]] [[dbl(0)]] = 0 >= 0 = [[0]] [[dbl(s(_x0))]] = 0 >= 0 = [[s(n!6220!6220s(n!6220!6220dbl(activate(_x0))))]] [[add(0, _x0)]] = 2x0 >= x0 = [[_x0]] [[add(s(_x0), _x1)]] = 2x1 >= 2x1 = [[s(n!6220!6220add(activate(_x0), _x1))]] [[terms(_x0)]] = 2 + 2x0 >= 2 + 2x0 = [[n!6220!6220terms(_x0)]] [[add(_x0, _x1)]] = 2x1 >= x1 = [[n!6220!6220add(_x0, _x1)]] [[s(_x0)]] = 2x0 >= x0 = [[n!6220!6220s(_x0)]] [[dbl(_x0)]] = 0 >= 0 = [[n!6220!6220dbl(_x0)]] [[activate(n!6220!6220terms(_x0))]] = 4 + 4x0 >= 2 + 2x0 = [[terms(_x0)]] [[activate(n!6220!6220add(_x0, _x1))]] = 2x1 >= 2x1 = [[add(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = 2x0 >= 2x0 = [[s(_x0)]] [[activate(n!6220!6220dbl(_x0))]] = 0 >= 0 = [[dbl(_x0)]] [[activate(_x0)]] = 2x0 >= x0 = [[_x0]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_6, R_2, minimal, formative) by (P_7, R_2, minimal, formative), where P_7 consists of: terms#(X) =#> sqr#(X) sqr#(s(X)) =#> sqr#(activate(X)) sqr#(s(X)) =#> dbl#(activate(X)) Thus, the original system is terminating if (P_7, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_7, R_2, 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, 2 * 1 : 1, 2 * 2 : This graph has the following strongly connected components: P_8: sqr#(s(X)) =#> sqr#(activate(X)) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_7, R_2, m, f) by (P_8, R_2, m, f). Thus, the original system is terminating if (P_8, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_8, R_2, minimal, formative). The formative rules of (P_8, R_2) are R_3 ::= sqr(0) => 0 sqr(s(X)) => s(n!6220!6220add(sqr(activate(X)), dbl(activate(X)))) dbl(0) => 0 dbl(s(X)) => s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) => X add(s(X), Y) => s(n!6220!6220add(activate(X), Y)) add(X, Y) => n!6220!6220add(X, Y) s(X) => n!6220!6220s(X) dbl(X) => n!6220!6220dbl(X) activate(n!6220!6220add(X, Y)) => add(X, Y) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220dbl(X)) => dbl(X) activate(X) => X By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_8, R_2, minimal, formative) by (P_8, R_3, minimal, formative). Thus, the original system is terminating if (P_8, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_8, R_3, minimal, formative). We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_8, R_3) are: dbl(0) => 0 dbl(s(X)) => s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) => X add(s(X), Y) => s(n!6220!6220add(activate(X), Y)) add(X, Y) => n!6220!6220add(X, Y) s(X) => n!6220!6220s(X) dbl(X) => n!6220!6220dbl(X) activate(n!6220!6220add(X, Y)) => add(X, Y) activate(n!6220!6220s(X)) => s(X) activate(n!6220!6220dbl(X)) => dbl(X) activate(X) => X It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: sqr#(s(X)) >? sqr#(activate(X)) dbl(0) >= 0 dbl(s(X)) >= s(n!6220!6220s(n!6220!6220dbl(activate(X)))) add(0, X) >= X add(s(X), Y) >= s(n!6220!6220add(activate(X), Y)) add(X, Y) >= n!6220!6220add(X, Y) s(X) >= n!6220!6220s(X) dbl(X) >= n!6220!6220dbl(X) activate(n!6220!6220add(X, Y)) >= add(X, Y) activate(n!6220!6220s(X)) >= s(X) activate(n!6220!6220dbl(X)) >= dbl(X) activate(X) >= X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 activate = \y0.1 + 2y0 add = \y0y1.2 + 2y0 + 2y1 dbl = \y0.3 + 2y0 n!6220!6220add = \y0y1.1 + y0 + y1 n!6220!6220dbl = \y0.1 + y0 n!6220!6220s = \y0.1 + y0 s = \y0.3 + 2y0 sqr# = \y0.3y0 Using this interpretation, the requirements translate to: [[sqr#(s(_x0))]] = 9 + 6x0 > 3 + 6x0 = [[sqr#(activate(_x0))]] [[dbl(0)]] = 3 >= 0 = [[0]] [[dbl(s(_x0))]] = 9 + 4x0 >= 9 + 4x0 = [[s(n!6220!6220s(n!6220!6220dbl(activate(_x0))))]] [[add(0, _x0)]] = 2 + 2x0 >= x0 = [[_x0]] [[add(s(_x0), _x1)]] = 8 + 2x1 + 4x0 >= 7 + 2x1 + 4x0 = [[s(n!6220!6220add(activate(_x0), _x1))]] [[add(_x0, _x1)]] = 2 + 2x0 + 2x1 >= 1 + x0 + x1 = [[n!6220!6220add(_x0, _x1)]] [[s(_x0)]] = 3 + 2x0 >= 1 + x0 = [[n!6220!6220s(_x0)]] [[dbl(_x0)]] = 3 + 2x0 >= 1 + x0 = [[n!6220!6220dbl(_x0)]] [[activate(n!6220!6220add(_x0, _x1))]] = 3 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[add(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[s(_x0)]] [[activate(n!6220!6220dbl(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[dbl(_x0)]] [[activate(_x0)]] = 1 + 2x0 >= x0 = [[_x0]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_8, R_3) by ({}, R_3). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. 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.