/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] --> o U12 : [o * o * o] --> o U21 : [o * o] --> o U22 : [o * o] --> o U31 : [o * o] --> o U32 : [o * o] --> o U41 : [o * o * o] --> o U42 : [o * o * o] --> o U51 : [o * o] --> o U52 : [o * o] --> o U61 : [o * o * o * o] --> o U62 : [o * o * o * o] --> o U63 : [o * o * o * o] --> o U64 : [o * o] --> o U71 : [o * o] --> o U72 : [o * o] --> o U81 : [o * o * o] --> o U82 : [o * o * o] --> o activate : [o] --> o afterNth : [o * o] --> o cons : [o * o] --> o fst : [o] --> o head : [o] --> o n!6220!6220natsFrom : [o] --> o n!6220!6220s : [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) => U12(tt, activate(X), activate(Y)) U12(tt, X, Y) => snd(splitAt(activate(X), activate(Y))) U21(tt, X) => U22(tt, activate(X)) U22(tt, X) => activate(X) U31(tt, X) => U32(tt, activate(X)) U32(tt, X) => activate(X) U41(tt, X, Y) => U42(tt, activate(X), activate(Y)) U42(tt, X, Y) => head(afterNth(activate(X), activate(Y))) U51(tt, X) => U52(tt, activate(X)) U52(tt, X) => activate(X) U61(tt, X, Y, Z) => U62(tt, activate(X), activate(Y), activate(Z)) U62(tt, X, Y, Z) => U63(tt, activate(X), activate(Y), activate(Z)) U63(tt, X, Y, Z) => U64(splitAt(activate(X), activate(Z)), activate(Y)) U64(pair(X, Y), Z) => pair(cons(activate(Z), X), Y) U71(tt, X) => U72(tt, activate(X)) U72(tt, X) => activate(X) U81(tt, X, Y) => U82(tt, activate(X), activate(Y)) U82(tt, X, Y) => fst(splitAt(activate(X), activate(Y))) afterNth(X, Y) => U11(tt, X, Y) fst(pair(X, Y)) => U21(tt, X) head(cons(X, Y)) => U31(tt, X) natsFrom(X) => cons(X, n!6220!6220natsFrom(n!6220!6220s(X))) sel(X, Y) => U41(tt, X, Y) snd(pair(X, Y)) => U51(tt, Y) splitAt(0, X) => pair(nil, X) splitAt(s(X), cons(Y, Z)) => U61(tt, X, Y, activate(Z)) tail(cons(X, Y)) => U71(tt, activate(Y)) take(X, Y) => U81(tt, X, Y) natsFrom(X) => n!6220!6220natsFrom(X) s(X) => n!6220!6220s(X) activate(n!6220!6220natsFrom(X)) => natsFrom(activate(X)) activate(n!6220!6220s(X)) => s(activate(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) =#> U12#(tt, activate(X), activate(Y)) 1] U11#(tt, X, Y) =#> activate#(X) 2] U11#(tt, X, Y) =#> activate#(Y) 3] U12#(tt, X, Y) =#> snd#(splitAt(activate(X), activate(Y))) 4] U12#(tt, X, Y) =#> splitAt#(activate(X), activate(Y)) 5] U12#(tt, X, Y) =#> activate#(X) 6] U12#(tt, X, Y) =#> activate#(Y) 7] U21#(tt, X) =#> U22#(tt, activate(X)) 8] U21#(tt, X) =#> activate#(X) 9] U22#(tt, X) =#> activate#(X) 10] U31#(tt, X) =#> U32#(tt, activate(X)) 11] U31#(tt, X) =#> activate#(X) 12] U32#(tt, X) =#> activate#(X) 13] U41#(tt, X, Y) =#> U42#(tt, activate(X), activate(Y)) 14] U41#(tt, X, Y) =#> activate#(X) 15] U41#(tt, X, Y) =#> activate#(Y) 16] U42#(tt, X, Y) =#> head#(afterNth(activate(X), activate(Y))) 17] U42#(tt, X, Y) =#> afterNth#(activate(X), activate(Y)) 18] U42#(tt, X, Y) =#> activate#(X) 19] U42#(tt, X, Y) =#> activate#(Y) 20] U51#(tt, X) =#> U52#(tt, activate(X)) 21] U51#(tt, X) =#> activate#(X) 22] U52#(tt, X) =#> activate#(X) 23] U61#(tt, X, Y, Z) =#> U62#(tt, activate(X), activate(Y), activate(Z)) 24] U61#(tt, X, Y, Z) =#> activate#(X) 25] U61#(tt, X, Y, Z) =#> activate#(Y) 26] U61#(tt, X, Y, Z) =#> activate#(Z) 27] U62#(tt, X, Y, Z) =#> U63#(tt, activate(X), activate(Y), activate(Z)) 28] U62#(tt, X, Y, Z) =#> activate#(X) 29] U62#(tt, X, Y, Z) =#> activate#(Y) 30] U62#(tt, X, Y, Z) =#> activate#(Z) 31] U63#(tt, X, Y, Z) =#> U64#(splitAt(activate(X), activate(Z)), activate(Y)) 32] U63#(tt, X, Y, Z) =#> splitAt#(activate(X), activate(Z)) 33] U63#(tt, X, Y, Z) =#> activate#(X) 34] U63#(tt, X, Y, Z) =#> activate#(Z) 35] U63#(tt, X, Y, Z) =#> activate#(Y) 36] U64#(pair(X, Y), Z) =#> activate#(Z) 37] U71#(tt, X) =#> U72#(tt, activate(X)) 38] U71#(tt, X) =#> activate#(X) 39] U72#(tt, X) =#> activate#(X) 40] U81#(tt, X, Y) =#> U82#(tt, activate(X), activate(Y)) 41] U81#(tt, X, Y) =#> activate#(X) 42] U81#(tt, X, Y) =#> activate#(Y) 43] U82#(tt, X, Y) =#> fst#(splitAt(activate(X), activate(Y))) 44] U82#(tt, X, Y) =#> splitAt#(activate(X), activate(Y)) 45] U82#(tt, X, Y) =#> activate#(X) 46] U82#(tt, X, Y) =#> activate#(Y) 47] afterNth#(X, Y) =#> U11#(tt, X, Y) 48] fst#(pair(X, Y)) =#> U21#(tt, X) 49] head#(cons(X, Y)) =#> U31#(tt, X) 50] sel#(X, Y) =#> U41#(tt, X, Y) 51] snd#(pair(X, Y)) =#> U51#(tt, Y) 52] splitAt#(s(X), cons(Y, Z)) =#> U61#(tt, X, Y, activate(Z)) 53] splitAt#(s(X), cons(Y, Z)) =#> activate#(Z) 54] tail#(cons(X, Y)) =#> U71#(tt, activate(Y)) 55] tail#(cons(X, Y)) =#> activate#(Y) 56] take#(X, Y) =#> U81#(tt, X, Y) 57] activate#(n!6220!6220natsFrom(X)) =#> natsFrom#(activate(X)) 58] activate#(n!6220!6220natsFrom(X)) =#> activate#(X) 59] activate#(n!6220!6220s(X)) =#> s#(activate(X)) 60] activate#(n!6220!6220s(X)) =#> activate#(X) Rules R_0: U11(tt, X, Y) => U12(tt, activate(X), activate(Y)) U12(tt, X, Y) => snd(splitAt(activate(X), activate(Y))) U21(tt, X) => U22(tt, activate(X)) U22(tt, X) => activate(X) U31(tt, X) => U32(tt, activate(X)) U32(tt, X) => activate(X) U41(tt, X, Y) => U42(tt, activate(X), activate(Y)) U42(tt, X, Y) => head(afterNth(activate(X), activate(Y))) U51(tt, X) => U52(tt, activate(X)) U52(tt, X) => activate(X) U61(tt, X, Y, Z) => U62(tt, activate(X), activate(Y), activate(Z)) U62(tt, X, Y, Z) => U63(tt, activate(X), activate(Y), activate(Z)) U63(tt, X, Y, Z) => U64(splitAt(activate(X), activate(Z)), activate(Y)) U64(pair(X, Y), Z) => pair(cons(activate(Z), X), Y) U71(tt, X) => U72(tt, activate(X)) U72(tt, X) => activate(X) U81(tt, X, Y) => U82(tt, activate(X), activate(Y)) U82(tt, X, Y) => fst(splitAt(activate(X), activate(Y))) afterNth(X, Y) => U11(tt, X, Y) fst(pair(X, Y)) => U21(tt, X) head(cons(X, Y)) => U31(tt, X) natsFrom(X) => cons(X, n!6220!6220natsFrom(n!6220!6220s(X))) sel(X, Y) => U41(tt, X, Y) snd(pair(X, Y)) => U51(tt, Y) splitAt(0, X) => pair(nil, X) splitAt(s(X), cons(Y, Z)) => U61(tt, X, Y, activate(Z)) tail(cons(X, Y)) => U71(tt, activate(Y)) take(X, Y) => U81(tt, X, Y) natsFrom(X) => n!6220!6220natsFrom(X) s(X) => n!6220!6220s(X) activate(n!6220!6220natsFrom(X)) => natsFrom(activate(X)) activate(n!6220!6220s(X)) => s(activate(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 : 3, 4, 5, 6 * 1 : 57, 58, 59, 60 * 2 : 57, 58, 59, 60 * 3 : 51 * 4 : 52, 53 * 5 : 57, 58, 59, 60 * 6 : 57, 58, 59, 60 * 7 : 9 * 8 : 57, 58, 59, 60 * 9 : 57, 58, 59, 60 * 10 : 12 * 11 : 57, 58, 59, 60 * 12 : 57, 58, 59, 60 * 13 : 16, 17, 18, 19 * 14 : 57, 58, 59, 60 * 15 : 57, 58, 59, 60 * 16 : 49 * 17 : 47 * 18 : 57, 58, 59, 60 * 19 : 57, 58, 59, 60 * 20 : 22 * 21 : 57, 58, 59, 60 * 22 : 57, 58, 59, 60 * 23 : 27, 28, 29, 30 * 24 : 57, 58, 59, 60 * 25 : 57, 58, 59, 60 * 26 : 57, 58, 59, 60 * 27 : 31, 32, 33, 34, 35 * 28 : 57, 58, 59, 60 * 29 : 57, 58, 59, 60 * 30 : 57, 58, 59, 60 * 31 : 36 * 32 : 52, 53 * 33 : 57, 58, 59, 60 * 34 : 57, 58, 59, 60 * 35 : 57, 58, 59, 60 * 36 : 57, 58, 59, 60 * 37 : 39 * 38 : 57, 58, 59, 60 * 39 : 57, 58, 59, 60 * 40 : 43, 44, 45, 46 * 41 : 57, 58, 59, 60 * 42 : 57, 58, 59, 60 * 43 : 48 * 44 : 52, 53 * 45 : 57, 58, 59, 60 * 46 : 57, 58, 59, 60 * 47 : 0, 1, 2 * 48 : 7, 8 * 49 : 10, 11 * 50 : 13, 14, 15 * 51 : 20, 21 * 52 : 23, 24, 25, 26 * 53 : 57, 58, 59, 60 * 54 : 37, 38 * 55 : 57, 58, 59, 60 * 56 : 40, 41, 42 * 57 : * 58 : 57, 58, 59, 60 * 59 : * 60 : 57, 58, 59, 60 This graph has the following strongly connected components: P_1: U61#(tt, X, Y, Z) =#> U62#(tt, activate(X), activate(Y), activate(Z)) U62#(tt, X, Y, Z) =#> U63#(tt, activate(X), activate(Y), activate(Z)) U63#(tt, X, Y, Z) =#> splitAt#(activate(X), activate(Z)) splitAt#(s(X), cons(Y, Z)) =#> U61#(tt, X, Y, activate(Z)) P_2: activate#(n!6220!6220natsFrom(X)) =#> activate#(X) activate#(n!6220!6220s(X)) =#> activate#(X) 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) and (P_2, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(activate#) = 1 Thus, we can orient the dependency pairs as follows: nu(activate#(n!6220!6220natsFrom(X))) = n!6220!6220natsFrom(X) |> X = nu(activate#(X)) nu(activate#(n!6220!6220s(X))) = n!6220!6220s(X) |> X = nu(activate#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_2, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. 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(n!6220!6220s(X))) natsFrom(X) => n!6220!6220natsFrom(X) s(X) => n!6220!6220s(X) activate(n!6220!6220natsFrom(X)) => natsFrom(activate(X)) activate(n!6220!6220s(X)) => s(activate(X)) activate(X) => X It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: U61#(tt, X, Y, Z) >? U62#(tt, activate(X), activate(Y), activate(Z)) U62#(tt, X, Y, Z) >? U63#(tt, activate(X), activate(Y), activate(Z)) U63#(tt, X, Y, Z) >? splitAt#(activate(X), activate(Z)) splitAt#(s(X), cons(Y, Z)) >? U61#(tt, X, Y, activate(Z)) natsFrom(X) >= cons(X, n!6220!6220natsFrom(n!6220!6220s(X))) natsFrom(X) >= n!6220!6220natsFrom(X) s(X) >= n!6220!6220s(X) activate(n!6220!6220natsFrom(X)) >= natsFrom(activate(X)) activate(n!6220!6220s(X)) >= s(activate(X)) activate(X) >= X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U61# = \y0y1y2y3.1 + 2y1 U62# = \y0y1y2y3.y0 + 2y1 U63# = \y0y1y2y3.y1 activate = \y0.y0 cons = \y0y1.0 n!6220!6220natsFrom = \y0.0 n!6220!6220s = \y0.1 + 2y0 natsFrom = \y0.0 s = \y0.1 + 2y0 splitAt# = \y0y1.y0 tt = 1 Using this interpretation, the requirements translate to: [[U61#(tt, _x0, _x1, _x2)]] = 1 + 2x0 >= 1 + 2x0 = [[U62#(tt, activate(_x0), activate(_x1), activate(_x2))]] [[U62#(tt, _x0, _x1, _x2)]] = 1 + 2x0 > x0 = [[U63#(tt, activate(_x0), activate(_x1), activate(_x2))]] [[U63#(tt, _x0, _x1, _x2)]] = x0 >= x0 = [[splitAt#(activate(_x0), activate(_x2))]] [[splitAt#(s(_x0), cons(_x1, _x2))]] = 1 + 2x0 >= 1 + 2x0 = [[U61#(tt, _x0, _x1, activate(_x2))]] [[natsFrom(_x0)]] = 0 >= 0 = [[cons(_x0, n!6220!6220natsFrom(n!6220!6220s(_x0)))]] [[natsFrom(_x0)]] = 0 >= 0 = [[n!6220!6220natsFrom(_x0)]] [[s(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[n!6220!6220s(_x0)]] [[activate(n!6220!6220natsFrom(_x0))]] = 0 >= 0 = [[natsFrom(activate(_x0))]] [[activate(n!6220!6220s(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[s(activate(_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_3, R_0, minimal, formative), where P_3 consists of: U61#(tt, X, Y, Z) =#> U62#(tt, activate(X), activate(Y), activate(Z)) U63#(tt, X, Y, Z) =#> splitAt#(activate(X), activate(Z)) splitAt#(s(X), cons(Y, Z)) =#> U61#(tt, X, Y, activate(Z)) 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 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 * 2 : 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.