/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be disproven: (0) QTRS (1) QTRSRRRProof [EQUIVALENT, 123 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 43 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 23 ms] (6) QTRS (7) QTRSRRRProof [EQUIVALENT, 23 ms] (8) QTRS (9) DependencyPairsProof [EQUIVALENT, 33 ms] (10) QDP (11) DependencyGraphProof [EQUIVALENT, 0 ms] (12) QDP (13) MRRProof [EQUIVALENT, 34 ms] (14) QDP (15) MRRProof [EQUIVALENT, 31 ms] (16) QDP (17) MRRProof [EQUIVALENT, 0 ms] (18) QDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) QDP (21) TransformationProof [EQUIVALENT, 0 ms] (22) QDP (23) QDPOrderProof [EQUIVALENT, 128 ms] (24) QDP (25) TransformationProof [EQUIVALENT, 0 ms] (26) QDP (27) MRRProof [EQUIVALENT, 21 ms] (28) QDP (29) MRRProof [EQUIVALENT, 18 ms] (30) QDP (31) MRRProof [EQUIVALENT, 0 ms] (32) QDP (33) NonTerminationLoopProof [COMPLETE, 51 ms] (34) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(0, XS) -> nil take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(nil, XS) -> nil zip(X, nil) -> nil zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) tail(cons(X, XS)) -> activate(XS) repItems(nil) -> nil repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + x_2 POL(incr(x_1)) = 2*x_1 POL(n__cons(x_1, x_2)) = x_1 + x_2 POL(n__incr(x_1)) = 2*x_1 POL(n__oddNs) = 0 POL(n__repItems(x_1)) = 2*x_1 POL(n__take(x_1, x_2)) = 2*x_1 + 2*x_2 POL(n__zip(x_1, x_2)) = x_1 + x_2 POL(nil) = 0 POL(oddNs) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(pairNs) = 0 POL(repItems(x_1)) = 2*x_1 POL(s(x_1)) = 2*x_1 POL(tail(x_1)) = 2 + 2*x_1 POL(take(x_1, x_2)) = 2*x_1 + 2*x_2 POL(zip(x_1, x_2)) = x_1 + x_2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: tail(cons(X, XS)) -> activate(XS) ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(0, XS) -> nil take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(nil, XS) -> nil zip(X, nil) -> nil zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(nil) -> nil repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + x_2 POL(incr(x_1)) = 2*x_1 POL(n__cons(x_1, x_2)) = x_1 + x_2 POL(n__incr(x_1)) = 2*x_1 POL(n__oddNs) = 0 POL(n__repItems(x_1)) = 2*x_1 POL(n__take(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(n__zip(x_1, x_2)) = x_1 + 2*x_2 POL(nil) = 1 POL(oddNs) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(pairNs) = 0 POL(repItems(x_1)) = 2*x_1 POL(s(x_1)) = x_1 POL(take(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(zip(x_1, x_2)) = x_1 + 2*x_2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: zip(X, nil) -> nil repItems(nil) -> nil ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(0, XS) -> nil take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(nil, XS) -> nil zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + x_2 POL(incr(x_1)) = 2*x_1 POL(n__cons(x_1, x_2)) = x_1 + x_2 POL(n__incr(x_1)) = 2*x_1 POL(n__oddNs) = 0 POL(n__repItems(x_1)) = 2*x_1 POL(n__take(x_1, x_2)) = x_1 + 2*x_2 POL(n__zip(x_1, x_2)) = 2 + x_1 + x_2 POL(nil) = 0 POL(oddNs) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(pairNs) = 0 POL(repItems(x_1)) = 2*x_1 POL(s(x_1)) = 2*x_1 POL(take(x_1, x_2)) = x_1 + 2*x_2 POL(zip(x_1, x_2)) = 2 + x_1 + x_2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: zip(nil, XS) -> nil ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(0, XS) -> nil take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. ---------------------------------------- (7) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + x_2 POL(incr(x_1)) = 2*x_1 POL(n__cons(x_1, x_2)) = x_1 + x_2 POL(n__incr(x_1)) = 2*x_1 POL(n__oddNs) = 0 POL(n__repItems(x_1)) = 2*x_1 POL(n__take(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(n__zip(x_1, x_2)) = x_1 + x_2 POL(nil) = 0 POL(oddNs) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(pairNs) = 0 POL(repItems(x_1)) = 2*x_1 POL(s(x_1)) = x_1 POL(take(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(zip(x_1, x_2)) = x_1 + x_2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: take(0, XS) -> nil ---------------------------------------- (8) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. ---------------------------------------- (9) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: PAIRNS -> CONS(0, n__incr(n__oddNs)) ODDNS -> INCR(pairNs) ODDNS -> PAIRNS INCR(cons(X, XS)) -> CONS(s(X), n__incr(activate(XS))) INCR(cons(X, XS)) -> ACTIVATE(XS) TAKE(s(N), cons(X, XS)) -> CONS(X, n__take(N, activate(XS))) TAKE(s(N), cons(X, XS)) -> ACTIVATE(XS) ZIP(cons(X, XS), cons(Y, YS)) -> CONS(pair(X, Y), n__zip(activate(XS), activate(YS))) ZIP(cons(X, XS), cons(Y, YS)) -> ACTIVATE(XS) ZIP(cons(X, XS), cons(Y, YS)) -> ACTIVATE(YS) REPITEMS(cons(X, XS)) -> CONS(X, n__cons(X, n__repItems(activate(XS)))) REPITEMS(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> INCR(activate(X)) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__zip(X1, X2)) -> ZIP(activate(X1), activate(X2)) ACTIVATE(n__zip(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__zip(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__cons(X1, X2)) -> CONS(activate(X1), X2) ACTIVATE(n__cons(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__repItems(X)) -> REPITEMS(activate(X)) ACTIVATE(n__repItems(X)) -> ACTIVATE(X) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 7 less nodes. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: ODDNS -> INCR(pairNs) INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> INCR(activate(X)) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) TAKE(s(N), cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__zip(X1, X2)) -> ZIP(activate(X1), activate(X2)) ZIP(cons(X, XS), cons(Y, YS)) -> ACTIVATE(XS) ACTIVATE(n__zip(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__zip(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__cons(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__repItems(X)) -> REPITEMS(activate(X)) REPITEMS(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__repItems(X)) -> ACTIVATE(X) ZIP(cons(X, XS), cons(Y, YS)) -> ACTIVATE(YS) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: ACTIVATE(n__repItems(X)) -> REPITEMS(activate(X)) REPITEMS(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__repItems(X)) -> ACTIVATE(X) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVATE(x_1)) = 2*x_1 POL(INCR(x_1)) = 2*x_1 POL(ODDNS) = 0 POL(REPITEMS(x_1)) = 1 + 2*x_1 POL(TAKE(x_1, x_2)) = 2*x_1 + 2*x_2 POL(ZIP(x_1, x_2)) = 2*x_1 + 2*x_2 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(incr(x_1)) = 2*x_1 POL(n__cons(x_1, x_2)) = 2*x_1 + x_2 POL(n__incr(x_1)) = 2*x_1 POL(n__oddNs) = 0 POL(n__repItems(x_1)) = 2 + 2*x_1 POL(n__take(x_1, x_2)) = 2*x_1 + 2*x_2 POL(n__zip(x_1, x_2)) = x_1 + x_2 POL(oddNs) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(pairNs) = 0 POL(repItems(x_1)) = 2 + 2*x_1 POL(s(x_1)) = x_1 POL(take(x_1, x_2)) = 2*x_1 + 2*x_2 POL(zip(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: ODDNS -> INCR(pairNs) INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> INCR(activate(X)) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) TAKE(s(N), cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__zip(X1, X2)) -> ZIP(activate(X1), activate(X2)) ZIP(cons(X, XS), cons(Y, YS)) -> ACTIVATE(XS) ACTIVATE(n__zip(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__zip(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__cons(X1, X2)) -> ACTIVATE(X1) ZIP(cons(X, XS), cons(Y, YS)) -> ACTIVATE(YS) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) TAKE(s(N), cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVATE(x_1)) = x_1 POL(INCR(x_1)) = x_1 POL(ODDNS) = 0 POL(TAKE(x_1, x_2)) = 1 + x_1 + x_2 POL(ZIP(x_1, x_2)) = x_1 + 2*x_2 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + x_2 POL(incr(x_1)) = 2*x_1 POL(n__cons(x_1, x_2)) = x_1 + x_2 POL(n__incr(x_1)) = 2*x_1 POL(n__oddNs) = 0 POL(n__repItems(x_1)) = 2*x_1 POL(n__take(x_1, x_2)) = 2 + x_1 + x_2 POL(n__zip(x_1, x_2)) = x_1 + 2*x_2 POL(oddNs) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(pairNs) = 0 POL(repItems(x_1)) = 2*x_1 POL(s(x_1)) = x_1 POL(take(x_1, x_2)) = 2 + x_1 + x_2 POL(zip(x_1, x_2)) = x_1 + 2*x_2 ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: ODDNS -> INCR(pairNs) INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> INCR(activate(X)) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ACTIVATE(n__zip(X1, X2)) -> ZIP(activate(X1), activate(X2)) ZIP(cons(X, XS), cons(Y, YS)) -> ACTIVATE(XS) ACTIVATE(n__zip(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__zip(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__cons(X1, X2)) -> ACTIVATE(X1) ZIP(cons(X, XS), cons(Y, YS)) -> ACTIVATE(YS) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: ACTIVATE(n__zip(X1, X2)) -> ZIP(activate(X1), activate(X2)) ACTIVATE(n__zip(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__zip(X1, X2)) -> ACTIVATE(X2) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVATE(x_1)) = x_1 POL(INCR(x_1)) = x_1 POL(ODDNS) = 0 POL(ZIP(x_1, x_2)) = x_1 + 2*x_2 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(incr(x_1)) = 2*x_1 POL(n__cons(x_1, x_2)) = 2*x_1 + x_2 POL(n__incr(x_1)) = 2*x_1 POL(n__oddNs) = 0 POL(n__repItems(x_1)) = 2*x_1 POL(n__take(x_1, x_2)) = 2*x_1 + x_2 POL(n__zip(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(oddNs) = 0 POL(pair(x_1, x_2)) = 2*x_1 + x_2 POL(pairNs) = 0 POL(repItems(x_1)) = 2*x_1 POL(s(x_1)) = x_1 POL(take(x_1, x_2)) = 2*x_1 + x_2 POL(zip(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: ODDNS -> INCR(pairNs) INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> INCR(activate(X)) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ZIP(cons(X, XS), cons(Y, YS)) -> ACTIVATE(XS) ACTIVATE(n__cons(X1, X2)) -> ACTIVATE(X1) ZIP(cons(X, XS), cons(Y, YS)) -> ACTIVATE(YS) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> INCR(activate(X)) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ODDNS -> INCR(pairNs) ACTIVATE(n__cons(X1, X2)) -> ACTIVATE(X1) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule ODDNS -> INCR(pairNs) at position [0] we obtained the following new rules [LPAR04]: (ODDNS -> INCR(cons(0, n__incr(n__oddNs))),ODDNS -> INCR(cons(0, n__incr(n__oddNs)))) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> INCR(activate(X)) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ACTIVATE(n__cons(X1, X2)) -> ACTIVATE(X1) ODDNS -> INCR(cons(0, n__incr(n__oddNs))) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVATE(n__cons(X1, X2)) -> ACTIVATE(X1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(INCR(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(ACTIVATE(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(n__incr(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(activate(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(n__oddNs) = [[1A]] >>> <<< POL(ODDNS) = [[1A]] >>> <<< POL(n__cons(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(incr(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(oddNs) = [[1A]] >>> <<< POL(n__take(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(take(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(n__zip(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[-I]] * x_2 >>> <<< POL(zip(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[-I]] * x_2 >>> <<< POL(n__repItems(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(repItems(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[0A]] + [[-I]] * x_1 >>> <<< POL(pairNs) = [[1A]] >>> <<< POL(pair(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[-I]] * x_2 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X cons(X1, X2) -> n__cons(X1, X2) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) incr(X) -> n__incr(X) oddNs -> n__oddNs oddNs -> incr(pairNs) pairNs -> cons(0, n__incr(n__oddNs)) take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) repItems(X) -> n__repItems(X) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> INCR(activate(X)) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ODDNS -> INCR(cons(0, n__incr(n__oddNs))) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule ACTIVATE(n__incr(X)) -> INCR(activate(X)) at position [0] we obtained the following new rules [LPAR04]: (ACTIVATE(n__incr(n__incr(x0))) -> INCR(incr(activate(x0))),ACTIVATE(n__incr(n__incr(x0))) -> INCR(incr(activate(x0)))) (ACTIVATE(n__incr(n__oddNs)) -> INCR(oddNs),ACTIVATE(n__incr(n__oddNs)) -> INCR(oddNs)) (ACTIVATE(n__incr(n__take(x0, x1))) -> INCR(take(activate(x0), activate(x1))),ACTIVATE(n__incr(n__take(x0, x1))) -> INCR(take(activate(x0), activate(x1)))) (ACTIVATE(n__incr(n__zip(x0, x1))) -> INCR(zip(activate(x0), activate(x1))),ACTIVATE(n__incr(n__zip(x0, x1))) -> INCR(zip(activate(x0), activate(x1)))) (ACTIVATE(n__incr(n__cons(x0, x1))) -> INCR(cons(activate(x0), x1)),ACTIVATE(n__incr(n__cons(x0, x1))) -> INCR(cons(activate(x0), x1))) (ACTIVATE(n__incr(n__repItems(x0))) -> INCR(repItems(activate(x0))),ACTIVATE(n__incr(n__repItems(x0))) -> INCR(repItems(activate(x0)))) (ACTIVATE(n__incr(x0)) -> INCR(x0),ACTIVATE(n__incr(x0)) -> INCR(x0)) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ODDNS -> INCR(cons(0, n__incr(n__oddNs))) ACTIVATE(n__incr(n__incr(x0))) -> INCR(incr(activate(x0))) ACTIVATE(n__incr(n__oddNs)) -> INCR(oddNs) ACTIVATE(n__incr(n__take(x0, x1))) -> INCR(take(activate(x0), activate(x1))) ACTIVATE(n__incr(n__zip(x0, x1))) -> INCR(zip(activate(x0), activate(x1))) ACTIVATE(n__incr(n__cons(x0, x1))) -> INCR(cons(activate(x0), x1)) ACTIVATE(n__incr(n__repItems(x0))) -> INCR(repItems(activate(x0))) ACTIVATE(n__incr(x0)) -> INCR(x0) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: ACTIVATE(n__incr(n__take(x0, x1))) -> INCR(take(activate(x0), activate(x1))) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVATE(x_1)) = x_1 POL(INCR(x_1)) = x_1 POL(ODDNS) = 0 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(incr(x_1)) = 2*x_1 POL(n__cons(x_1, x_2)) = 2*x_1 + x_2 POL(n__incr(x_1)) = 2*x_1 POL(n__oddNs) = 0 POL(n__repItems(x_1)) = 2*x_1 POL(n__take(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(n__zip(x_1, x_2)) = x_1 + 2*x_2 POL(oddNs) = 0 POL(pair(x_1, x_2)) = x_1 + 2*x_2 POL(pairNs) = 0 POL(repItems(x_1)) = 2*x_1 POL(s(x_1)) = 2*x_1 POL(take(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(zip(x_1, x_2)) = x_1 + 2*x_2 ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ODDNS -> INCR(cons(0, n__incr(n__oddNs))) ACTIVATE(n__incr(n__incr(x0))) -> INCR(incr(activate(x0))) ACTIVATE(n__incr(n__oddNs)) -> INCR(oddNs) ACTIVATE(n__incr(n__zip(x0, x1))) -> INCR(zip(activate(x0), activate(x1))) ACTIVATE(n__incr(n__cons(x0, x1))) -> INCR(cons(activate(x0), x1)) ACTIVATE(n__incr(n__repItems(x0))) -> INCR(repItems(activate(x0))) ACTIVATE(n__incr(x0)) -> INCR(x0) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: ACTIVATE(n__incr(n__repItems(x0))) -> INCR(repItems(activate(x0))) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVATE(x_1)) = 2*x_1 POL(INCR(x_1)) = 2*x_1 POL(ODDNS) = 0 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(incr(x_1)) = 2*x_1 POL(n__cons(x_1, x_2)) = 2*x_1 + x_2 POL(n__incr(x_1)) = 2*x_1 POL(n__oddNs) = 0 POL(n__repItems(x_1)) = 1 + 2*x_1 POL(n__take(x_1, x_2)) = 2*x_1 + x_2 POL(n__zip(x_1, x_2)) = 2*x_1 + 2*x_2 POL(oddNs) = 0 POL(pair(x_1, x_2)) = 2*x_1 + 2*x_2 POL(pairNs) = 0 POL(repItems(x_1)) = 1 + 2*x_1 POL(s(x_1)) = 2*x_1 POL(take(x_1, x_2)) = 2*x_1 + x_2 POL(zip(x_1, x_2)) = 2*x_1 + 2*x_2 ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ODDNS -> INCR(cons(0, n__incr(n__oddNs))) ACTIVATE(n__incr(n__incr(x0))) -> INCR(incr(activate(x0))) ACTIVATE(n__incr(n__oddNs)) -> INCR(oddNs) ACTIVATE(n__incr(n__zip(x0, x1))) -> INCR(zip(activate(x0), activate(x1))) ACTIVATE(n__incr(n__cons(x0, x1))) -> INCR(cons(activate(x0), x1)) ACTIVATE(n__incr(x0)) -> INCR(x0) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: ACTIVATE(n__incr(n__zip(x0, x1))) -> INCR(zip(activate(x0), activate(x1))) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVATE(x_1)) = 2*x_1 POL(INCR(x_1)) = 2*x_1 POL(ODDNS) = 0 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(incr(x_1)) = 2*x_1 POL(n__cons(x_1, x_2)) = 2*x_1 + x_2 POL(n__incr(x_1)) = 2*x_1 POL(n__oddNs) = 0 POL(n__repItems(x_1)) = 2*x_1 POL(n__take(x_1, x_2)) = 2*x_1 + x_2 POL(n__zip(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(oddNs) = 0 POL(pair(x_1, x_2)) = 2*x_1 + x_2 POL(pairNs) = 0 POL(repItems(x_1)) = 2*x_1 POL(s(x_1)) = x_1 POL(take(x_1, x_2)) = 2*x_1 + x_2 POL(zip(x_1, x_2)) = 1 + 2*x_1 + x_2 ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: INCR(cons(X, XS)) -> ACTIVATE(XS) ACTIVATE(n__incr(X)) -> ACTIVATE(X) ACTIVATE(n__oddNs) -> ODDNS ODDNS -> INCR(cons(0, n__incr(n__oddNs))) ACTIVATE(n__incr(n__incr(x0))) -> INCR(incr(activate(x0))) ACTIVATE(n__incr(n__oddNs)) -> INCR(oddNs) ACTIVATE(n__incr(n__cons(x0, x1))) -> INCR(cons(activate(x0), x1)) ACTIVATE(n__incr(x0)) -> INCR(x0) The TRS R consists of the following rules: pairNs -> cons(0, n__incr(n__oddNs)) oddNs -> incr(pairNs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), n__zip(activate(XS), activate(YS))) repItems(cons(X, XS)) -> cons(X, n__cons(X, n__repItems(activate(XS)))) incr(X) -> n__incr(X) oddNs -> n__oddNs take(X1, X2) -> n__take(X1, X2) zip(X1, X2) -> n__zip(X1, X2) cons(X1, X2) -> n__cons(X1, X2) repItems(X) -> n__repItems(X) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs) -> oddNs activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__zip(X1, X2)) -> zip(activate(X1), activate(X2)) activate(n__cons(X1, X2)) -> cons(activate(X1), X2) activate(n__repItems(X)) -> repItems(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = ACTIVATE(n__incr(n__oddNs)) evaluates to t =ACTIVATE(n__incr(n__oddNs)) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence ACTIVATE(n__incr(n__oddNs)) -> ACTIVATE(n__oddNs) with rule ACTIVATE(n__incr(X)) -> ACTIVATE(X) at position [] and matcher [X / n__oddNs] ACTIVATE(n__oddNs) -> ODDNS with rule ACTIVATE(n__oddNs) -> ODDNS at position [] and matcher [ ] ODDNS -> INCR(cons(0, n__incr(n__oddNs))) with rule ODDNS -> INCR(cons(0, n__incr(n__oddNs))) at position [] and matcher [ ] INCR(cons(0, n__incr(n__oddNs))) -> ACTIVATE(n__incr(n__oddNs)) with rule INCR(cons(X, XS)) -> ACTIVATE(XS) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (34) NO