/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, 113 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 32 ms] (4) QTRS (5) DependencyPairsProof [EQUIVALENT, 0 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) QDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) QDP (12) UsableRulesReductionPairsProof [EQUIVALENT, 38 ms] (13) QDP (14) DependencyGraphProof [EQUIVALENT, 0 ms] (15) QDP (16) UsableRulesProof [EQUIVALENT, 0 ms] (17) QDP (18) QDPSizeChangeProof [EQUIVALENT, 0 ms] (19) YES (20) QDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) QDP (23) UsableRulesReductionPairsProof [EQUIVALENT, 16 ms] (24) QDP (25) UsableRulesProof [EQUIVALENT, 0 ms] (26) QDP (27) TransformationProof [EQUIVALENT, 0 ms] (28) QDP (29) TransformationProof [EQUIVALENT, 0 ms] (30) QDP (31) DependencyGraphProof [EQUIVALENT, 0 ms] (32) QDP (33) MRRProof [EQUIVALENT, 9 ms] (34) QDP (35) NonTerminationLoopProof [COMPLETE, 7 ms] (36) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: zeros -> cons(0, n__zeros) U11(tt, L) -> U12(tt, activate(L)) U12(tt, L) -> s(length(activate(L))) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) length(nil) -> 0 length(cons(N, L)) -> U11(tt, activate(L)) take(0, IL) -> nil take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) zeros -> n__zeros take(X1, X2) -> n__take(X1, X2) activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(U12(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(U21(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + 2*x_3 + 2*x_4 POL(U22(x_1, x_2, x_3, x_4)) = 2*x_1 + 2*x_2 + 2*x_3 + 2*x_4 POL(U23(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + 2*x_3 + 2*x_4 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(length(x_1)) = 1 + x_1 POL(n__take(x_1, x_2)) = 2*x_1 + 2*x_2 POL(n__zeros) = 0 POL(nil) = 0 POL(s(x_1)) = x_1 POL(take(x_1, x_2)) = 2*x_1 + 2*x_2 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: length(nil) -> 0 ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: zeros -> cons(0, n__zeros) U11(tt, L) -> U12(tt, activate(L)) U12(tt, L) -> s(length(activate(L))) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) length(cons(N, L)) -> U11(tt, activate(L)) take(0, IL) -> nil take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) zeros -> n__zeros take(X1, X2) -> n__take(X1, X2) activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = x_1 + x_2 POL(U12(x_1, x_2)) = 2*x_1 + x_2 POL(U21(x_1, x_2, x_3, x_4)) = 2 + 2*x_1 + x_2 + x_3 + 2*x_4 POL(U22(x_1, x_2, x_3, x_4)) = 2 + 2*x_1 + x_2 + x_3 + 2*x_4 POL(U23(x_1, x_2, x_3, x_4)) = 2 + 2*x_1 + x_2 + x_3 + 2*x_4 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(length(x_1)) = x_1 POL(n__take(x_1, x_2)) = 2 + x_1 + x_2 POL(n__zeros) = 0 POL(nil) = 0 POL(s(x_1)) = x_1 POL(take(x_1, x_2)) = 2 + x_1 + x_2 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: take(0, IL) -> nil ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: zeros -> cons(0, n__zeros) U11(tt, L) -> U12(tt, activate(L)) U12(tt, L) -> s(length(activate(L))) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) length(cons(N, L)) -> U11(tt, activate(L)) take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) zeros -> n__zeros take(X1, X2) -> n__take(X1, X2) activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X Q is empty. ---------------------------------------- (5) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: U11^1(tt, L) -> U12^1(tt, activate(L)) U11^1(tt, L) -> ACTIVATE(L) U12^1(tt, L) -> LENGTH(activate(L)) U12^1(tt, L) -> ACTIVATE(L) U21^1(tt, IL, M, N) -> U22^1(tt, activate(IL), activate(M), activate(N)) U21^1(tt, IL, M, N) -> ACTIVATE(IL) U21^1(tt, IL, M, N) -> ACTIVATE(M) U21^1(tt, IL, M, N) -> ACTIVATE(N) U22^1(tt, IL, M, N) -> U23^1(tt, activate(IL), activate(M), activate(N)) U22^1(tt, IL, M, N) -> ACTIVATE(IL) U22^1(tt, IL, M, N) -> ACTIVATE(M) U22^1(tt, IL, M, N) -> ACTIVATE(N) U23^1(tt, IL, M, N) -> ACTIVATE(N) U23^1(tt, IL, M, N) -> ACTIVATE(M) U23^1(tt, IL, M, N) -> ACTIVATE(IL) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) LENGTH(cons(N, L)) -> ACTIVATE(L) TAKE(s(M), cons(N, IL)) -> U21^1(tt, activate(IL), M, N) TAKE(s(M), cons(N, IL)) -> ACTIVATE(IL) ACTIVATE(n__zeros) -> ZEROS ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) The TRS R consists of the following rules: zeros -> cons(0, n__zeros) U11(tt, L) -> U12(tt, activate(L)) U12(tt, L) -> s(length(activate(L))) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) length(cons(N, L)) -> U11(tt, activate(L)) take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) zeros -> n__zeros take(X1, X2) -> n__take(X1, X2) activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: U22^1(tt, IL, M, N) -> U23^1(tt, activate(IL), activate(M), activate(N)) U23^1(tt, IL, M, N) -> ACTIVATE(N) ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) TAKE(s(M), cons(N, IL)) -> U21^1(tt, activate(IL), M, N) U21^1(tt, IL, M, N) -> U22^1(tt, activate(IL), activate(M), activate(N)) U22^1(tt, IL, M, N) -> ACTIVATE(IL) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) U22^1(tt, IL, M, N) -> ACTIVATE(M) U22^1(tt, IL, M, N) -> ACTIVATE(N) U21^1(tt, IL, M, N) -> ACTIVATE(IL) U21^1(tt, IL, M, N) -> ACTIVATE(M) U21^1(tt, IL, M, N) -> ACTIVATE(N) TAKE(s(M), cons(N, IL)) -> ACTIVATE(IL) U23^1(tt, IL, M, N) -> ACTIVATE(M) U23^1(tt, IL, M, N) -> ACTIVATE(IL) The TRS R consists of the following rules: zeros -> cons(0, n__zeros) U11(tt, L) -> U12(tt, activate(L)) U12(tt, L) -> s(length(activate(L))) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) length(cons(N, L)) -> U11(tt, activate(L)) take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) zeros -> n__zeros take(X1, X2) -> n__take(X1, X2) activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: U22^1(tt, IL, M, N) -> U23^1(tt, activate(IL), activate(M), activate(N)) U23^1(tt, IL, M, N) -> ACTIVATE(N) ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) TAKE(s(M), cons(N, IL)) -> U21^1(tt, activate(IL), M, N) U21^1(tt, IL, M, N) -> U22^1(tt, activate(IL), activate(M), activate(N)) U22^1(tt, IL, M, N) -> ACTIVATE(IL) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) U22^1(tt, IL, M, N) -> ACTIVATE(M) U22^1(tt, IL, M, N) -> ACTIVATE(N) U21^1(tt, IL, M, N) -> ACTIVATE(IL) U21^1(tt, IL, M, N) -> ACTIVATE(M) U21^1(tt, IL, M, N) -> ACTIVATE(N) TAKE(s(M), cons(N, IL)) -> ACTIVATE(IL) U23^1(tt, IL, M, N) -> ACTIVATE(M) U23^1(tt, IL, M, N) -> ACTIVATE(IL) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) take(X1, X2) -> n__take(X1, X2) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: TAKE(s(M), cons(N, IL)) -> U21^1(tt, activate(IL), M, N) TAKE(s(M), cons(N, IL)) -> ACTIVATE(IL) The following rules are removed from R: take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVATE(x_1)) = 2*x_1 POL(TAKE(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U21(x_1, x_2, x_3, x_4)) = 2*x_1 + 2*x_2 + 2*x_3 + 2*x_4 POL(U21^1(x_1, x_2, x_3, x_4)) = 2*x_1 + 2*x_2 + 2*x_3 + 2*x_4 POL(U22(x_1, x_2, x_3, x_4)) = 2*x_1 + 2*x_2 + 2*x_3 + 2*x_4 POL(U22^1(x_1, x_2, x_3, x_4)) = 2*x_1 + 2*x_2 + 2*x_3 + 2*x_4 POL(U23(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + 2*x_3 + 2*x_4 POL(U23^1(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + 2*x_3 + 2*x_4 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(n__take(x_1, x_2)) = x_1 + x_2 POL(n__zeros) = 0 POL(s(x_1)) = 2*x_1 POL(take(x_1, x_2)) = x_1 + x_2 POL(tt) = 0 POL(zeros) = 0 ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: U22^1(tt, IL, M, N) -> U23^1(tt, activate(IL), activate(M), activate(N)) U23^1(tt, IL, M, N) -> ACTIVATE(N) ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) U21^1(tt, IL, M, N) -> U22^1(tt, activate(IL), activate(M), activate(N)) U22^1(tt, IL, M, N) -> ACTIVATE(IL) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) U22^1(tt, IL, M, N) -> ACTIVATE(M) U22^1(tt, IL, M, N) -> ACTIVATE(N) U21^1(tt, IL, M, N) -> ACTIVATE(IL) U21^1(tt, IL, M, N) -> ACTIVATE(M) U21^1(tt, IL, M, N) -> ACTIVATE(N) U23^1(tt, IL, M, N) -> ACTIVATE(M) U23^1(tt, IL, M, N) -> ACTIVATE(IL) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X take(X1, X2) -> n__take(X1, X2) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 12 less nodes. ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X take(X1, X2) -> n__take(X1, X2) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) The graph contains the following edges 1 > 1 *ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) The graph contains the following edges 1 > 1 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt, L) -> LENGTH(activate(L)) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U11^1(tt, L) -> U12^1(tt, activate(L)) The TRS R consists of the following rules: zeros -> cons(0, n__zeros) U11(tt, L) -> U12(tt, activate(L)) U12(tt, L) -> s(length(activate(L))) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) length(cons(N, L)) -> U11(tt, activate(L)) take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) zeros -> n__zeros take(X1, X2) -> n__take(X1, X2) activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt, L) -> LENGTH(activate(L)) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U11^1(tt, L) -> U12^1(tt, activate(L)) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) take(X1, X2) -> n__take(X1, X2) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 0 POL(LENGTH(x_1)) = 2*x_1 POL(U11^1(x_1, x_2)) = x_1 + 2*x_2 POL(U12^1(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U21(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + 2*x_3 + x_4 POL(U22(x_1, x_2, x_3, x_4)) = 2*x_1 + 2*x_2 + 2*x_3 + x_4 POL(U23(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + 2*x_3 + x_4 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(n__take(x_1, x_2)) = x_1 + x_2 POL(n__zeros) = 0 POL(s(x_1)) = 2 + 2*x_1 POL(take(x_1, x_2)) = x_1 + x_2 POL(tt) = 0 POL(zeros) = 0 ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt, L) -> LENGTH(activate(L)) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U11^1(tt, L) -> U12^1(tt, activate(L)) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X take(X1, X2) -> n__take(X1, X2) U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt, L) -> LENGTH(activate(L)) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U11^1(tt, L) -> U12^1(tt, activate(L)) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X take(X1, X2) -> n__take(X1, X2) zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U12^1(tt, L) -> LENGTH(activate(L)) at position [0] we obtained the following new rules [LPAR04]: (U12^1(tt, n__zeros) -> LENGTH(zeros),U12^1(tt, n__zeros) -> LENGTH(zeros)) (U12^1(tt, n__take(x0, x1)) -> LENGTH(take(activate(x0), activate(x1))),U12^1(tt, n__take(x0, x1)) -> LENGTH(take(activate(x0), activate(x1)))) (U12^1(tt, x0) -> LENGTH(x0),U12^1(tt, x0) -> LENGTH(x0)) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U11^1(tt, L) -> U12^1(tt, activate(L)) U12^1(tt, n__zeros) -> LENGTH(zeros) U12^1(tt, n__take(x0, x1)) -> LENGTH(take(activate(x0), activate(x1))) U12^1(tt, x0) -> LENGTH(x0) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X take(X1, X2) -> n__take(X1, X2) zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U12^1(tt, n__zeros) -> LENGTH(zeros) at position [0] we obtained the following new rules [LPAR04]: (U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)),U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros))) (U12^1(tt, n__zeros) -> LENGTH(n__zeros),U12^1(tt, n__zeros) -> LENGTH(n__zeros)) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U11^1(tt, L) -> U12^1(tt, activate(L)) U12^1(tt, n__take(x0, x1)) -> LENGTH(take(activate(x0), activate(x1))) U12^1(tt, x0) -> LENGTH(x0) U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)) U12^1(tt, n__zeros) -> LENGTH(n__zeros) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X take(X1, X2) -> n__take(X1, X2) zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: U11^1(tt, L) -> U12^1(tt, activate(L)) U12^1(tt, n__take(x0, x1)) -> LENGTH(take(activate(x0), activate(x1))) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U12^1(tt, x0) -> LENGTH(x0) U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X take(X1, X2) -> n__take(X1, X2) zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) 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: U12^1(tt, n__take(x0, x1)) -> LENGTH(take(activate(x0), activate(x1))) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(LENGTH(x_1)) = x_1 POL(U11^1(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U12^1(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 + 2*x_2 POL(n__take(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(n__zeros) = 0 POL(take(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(tt) = 0 POL(zeros) = 0 ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: U11^1(tt, L) -> U12^1(tt, activate(L)) LENGTH(cons(N, L)) -> U11^1(tt, activate(L)) U12^1(tt, x0) -> LENGTH(x0) U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)) The TRS R consists of the following rules: activate(n__zeros) -> zeros activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(X) -> X take(X1, X2) -> n__take(X1, X2) zeros -> cons(0, n__zeros) zeros -> n__zeros Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) 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 = U12^1(tt, activate(activate(n__zeros))) evaluates to t =U12^1(tt, activate(activate(n__zeros))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence U12^1(tt, activate(activate(n__zeros))) -> U12^1(tt, activate(n__zeros)) with rule activate(X) -> X at position [1] and matcher [X / activate(n__zeros)] U12^1(tt, activate(n__zeros)) -> U12^1(tt, n__zeros) with rule activate(X) -> X at position [1] and matcher [X / n__zeros] U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)) with rule U12^1(tt, n__zeros) -> LENGTH(cons(0, n__zeros)) at position [] and matcher [ ] LENGTH(cons(0, n__zeros)) -> U11^1(tt, activate(n__zeros)) with rule LENGTH(cons(N, L')) -> U11^1(tt, activate(L')) at position [] and matcher [N / 0, L' / n__zeros] U11^1(tt, activate(n__zeros)) -> U12^1(tt, activate(activate(n__zeros))) with rule U11^1(tt, L) -> U12^1(tt, activate(L)) 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. ---------------------------------------- (36) NO