/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] --> o U12 : [o * o] --> o activate : [o] --> o afterNth : [o * o] --> o and : [o * o] --> o cons : [o * o] --> o fst : [o] --> o head : [o] --> o n!6220!6220natsFrom : [o] --> o natsFrom : [o] --> o nil : [] --> o pair : [o * o] --> o s : [o] --> o sel : [o * o] --> o snd : [o] --> o splitAt : [o * o] --> o tail : [o] --> o take : [o * o] --> o tt : [] --> o U11(tt, X, Y, Z) => U12(splitAt(activate(X), activate(Z)), activate(Y)) U12(pair(X, Y), Z) => pair(cons(activate(Z), X), Y) afterNth(X, Y) => snd(splitAt(X, Y)) and(tt, X) => activate(X) fst(pair(X, Y)) => X head(cons(X, Y)) => X natsFrom(X) => cons(X, n!6220!6220natsFrom(s(X))) sel(X, Y) => head(afterNth(X, Y)) snd(pair(X, Y)) => Y splitAt(0, X) => pair(nil, X) splitAt(s(X), cons(Y, Z)) => U11(tt, X, Y, activate(Z)) tail(cons(X, Y)) => activate(Y) take(X, Y) => fst(splitAt(X, Y)) natsFrom(X) => n!6220!6220natsFrom(X) activate(n!6220!6220natsFrom(X)) => natsFrom(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, Y, Z) =#> U12#(splitAt(activate(X), activate(Z)), activate(Y)) 1] U11#(tt, X, Y, Z) =#> splitAt#(activate(X), activate(Z)) 2] U11#(tt, X, Y, Z) =#> activate#(X) 3] U11#(tt, X, Y, Z) =#> activate#(Z) 4] U11#(tt, X, Y, Z) =#> activate#(Y) 5] U12#(pair(X, Y), Z) =#> activate#(Z) 6] afterNth#(X, Y) =#> snd#(splitAt(X, Y)) 7] afterNth#(X, Y) =#> splitAt#(X, Y) 8] and#(tt, X) =#> activate#(X) 9] sel#(X, Y) =#> head#(afterNth(X, Y)) 10] sel#(X, Y) =#> afterNth#(X, Y) 11] splitAt#(s(X), cons(Y, Z)) =#> U11#(tt, X, Y, activate(Z)) 12] splitAt#(s(X), cons(Y, Z)) =#> activate#(Z) 13] tail#(cons(X, Y)) =#> activate#(Y) 14] take#(X, Y) =#> fst#(splitAt(X, Y)) 15] take#(X, Y) =#> splitAt#(X, Y) 16] activate#(n!6220!6220natsFrom(X)) =#> natsFrom#(X) Rules R_0: U11(tt, X, Y, Z) => U12(splitAt(activate(X), activate(Z)), activate(Y)) U12(pair(X, Y), Z) => pair(cons(activate(Z), X), Y) afterNth(X, Y) => snd(splitAt(X, Y)) and(tt, X) => activate(X) fst(pair(X, Y)) => X head(cons(X, Y)) => X natsFrom(X) => cons(X, n!6220!6220natsFrom(s(X))) sel(X, Y) => head(afterNth(X, Y)) snd(pair(X, Y)) => Y splitAt(0, X) => pair(nil, X) splitAt(s(X), cons(Y, Z)) => U11(tt, X, Y, activate(Z)) tail(cons(X, Y)) => activate(Y) take(X, Y) => fst(splitAt(X, Y)) natsFrom(X) => n!6220!6220natsFrom(X) activate(n!6220!6220natsFrom(X)) => natsFrom(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 : 5 * 1 : 11, 12 * 2 : 16 * 3 : 16 * 4 : 16 * 5 : 16 * 6 : * 7 : 11, 12 * 8 : 16 * 9 : * 10 : 6, 7 * 11 : 0, 1, 2, 3, 4 * 12 : 16 * 13 : 16 * 14 : * 15 : 11, 12 * 16 : This graph has the following strongly connected components: P_1: U11#(tt, X, Y, Z) =#> splitAt#(activate(X), activate(Z)) splitAt#(s(X), cons(Y, Z)) =#> U11#(tt, X, Y, activate(Z)) 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 with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_1, R_0) are: natsFrom(X) => cons(X, n!6220!6220natsFrom(s(X))) natsFrom(X) => n!6220!6220natsFrom(X) activate(n!6220!6220natsFrom(X)) => natsFrom(X) activate(X) => X It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: U11#(tt, X, Y, Z) >? splitAt#(activate(X), activate(Z)) splitAt#(s(X), cons(Y, Z)) >? U11#(tt, X, Y, activate(Z)) natsFrom(X) >= cons(X, n!6220!6220natsFrom(s(X))) natsFrom(X) >= n!6220!6220natsFrom(X) activate(n!6220!6220natsFrom(X)) >= natsFrom(X) activate(X) >= X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11# = \y0y1y2y3.2y1 activate = \y0.y0 cons = \y0y1.0 n!6220!6220natsFrom = \y0.2y0 natsFrom = \y0.2y0 s = \y0.2 + 2y0 splitAt# = \y0y1.2y0 tt = 0 Using this interpretation, the requirements translate to: [[U11#(tt, _x0, _x1, _x2)]] = 2x0 >= 2x0 = [[splitAt#(activate(_x0), activate(_x2))]] [[splitAt#(s(_x0), cons(_x1, _x2))]] = 4 + 4x0 > 2x0 = [[U11#(tt, _x0, _x1, activate(_x2))]] [[natsFrom(_x0)]] = 2x0 >= 0 = [[cons(_x0, n!6220!6220natsFrom(s(_x0)))]] [[natsFrom(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220natsFrom(_x0)]] [[activate(n!6220!6220natsFrom(_x0))]] = 2x0 >= 2x0 = [[natsFrom(_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, Y, Z) =#> splitAt#(activate(X), activate(Z)) 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 : 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.