/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox/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) DependencyPairsProof [EQUIVALENT, 0 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) QDPSizeChangeProof [EQUIVALENT, 0 ms] (9) YES (10) QDP (11) TransformationProof [EQUIVALENT, 0 ms] (12) QDP (13) TransformationProof [EQUIVALENT, 0 ms] (14) QDP (15) DependencyGraphProof [EQUIVALENT, 0 ms] (16) QDP (17) TransformationProof [EQUIVALENT, 0 ms] (18) QDP (19) TransformationProof [EQUIVALENT, 0 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) QDP (23) TransformationProof [EQUIVALENT, 0 ms] (24) QDP (25) DependencyGraphProof [EQUIVALENT, 0 ms] (26) QDP (27) TransformationProof [EQUIVALENT, 0 ms] (28) QDP (29) TransformationProof [EQUIVALENT, 0 ms] (30) QDP (31) TransformationProof [EQUIVALENT, 0 ms] (32) QDP (33) DependencyGraphProof [EQUIVALENT, 0 ms] (34) QDP (35) TransformationProof [EQUIVALENT, 0 ms] (36) QDP (37) TransformationProof [EQUIVALENT, 0 ms] (38) QDP (39) DependencyGraphProof [EQUIVALENT, 0 ms] (40) QDP (41) TransformationProof [EQUIVALENT, 0 ms] (42) QDP (43) DependencyGraphProof [EQUIVALENT, 0 ms] (44) QDP (45) TransformationProof [EQUIVALENT, 0 ms] (46) QDP (47) DependencyGraphProof [EQUIVALENT, 0 ms] (48) QDP (49) TransformationProof [EQUIVALENT, 0 ms] (50) QDP (51) TransformationProof [EQUIVALENT, 0 ms] (52) QDP (53) DependencyGraphProof [EQUIVALENT, 0 ms] (54) QDP (55) TransformationProof [EQUIVALENT, 0 ms] (56) QDP (57) DependencyGraphProof [EQUIVALENT, 0 ms] (58) QDP (59) QDPOrderProof [EQUIVALENT, 32 ms] (60) QDP (61) QDPOrderProof [EQUIVALENT, 19 ms] (62) QDP (63) QDPOrderProof [EQUIVALENT, 22 ms] (64) QDP (65) NonTerminationLoopProof [COMPLETE, 3104 ms] (66) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(X), n__s(Y)) -> EQ(activate(X), activate(Y)) EQ(n__s(X), n__s(Y)) -> ACTIVATE(X) EQ(n__s(X), n__s(Y)) -> ACTIVATE(Y) INF(X) -> S(X) TAKE(s(X), cons(Y, L)) -> ACTIVATE(Y) TAKE(s(X), cons(Y, L)) -> ACTIVATE(X) TAKE(s(X), cons(Y, L)) -> ACTIVATE(L) LENGTH(nil) -> 0^1 LENGTH(cons(X, L)) -> S(n__length(activate(L))) LENGTH(cons(X, L)) -> ACTIVATE(L) ACTIVATE(n__0) -> 0^1 ACTIVATE(n__s(X)) -> S(X) ACTIVATE(n__inf(X)) -> INF(X) ACTIVATE(n__take(X1, X2)) -> TAKE(X1, X2) ACTIVATE(n__length(X)) -> LENGTH(X) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 8 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__take(X1, X2)) -> TAKE(X1, X2) TAKE(s(X), cons(Y, L)) -> ACTIVATE(Y) ACTIVATE(n__length(X)) -> LENGTH(X) LENGTH(cons(X, L)) -> ACTIVATE(L) TAKE(s(X), cons(Y, L)) -> ACTIVATE(X) TAKE(s(X), cons(Y, L)) -> ACTIVATE(L) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (6) 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. ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__take(X1, X2)) -> TAKE(X1, X2) TAKE(s(X), cons(Y, L)) -> ACTIVATE(Y) ACTIVATE(n__length(X)) -> LENGTH(X) LENGTH(cons(X, L)) -> ACTIVATE(L) TAKE(s(X), cons(Y, L)) -> ACTIVATE(X) TAKE(s(X), cons(Y, L)) -> ACTIVATE(L) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) 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: *LENGTH(cons(X, L)) -> ACTIVATE(L) The graph contains the following edges 1 > 1 *ACTIVATE(n__take(X1, X2)) -> TAKE(X1, X2) The graph contains the following edges 1 > 1, 1 > 2 *ACTIVATE(n__length(X)) -> LENGTH(X) The graph contains the following edges 1 > 1 *TAKE(s(X), cons(Y, L)) -> ACTIVATE(Y) The graph contains the following edges 2 > 1 *TAKE(s(X), cons(Y, L)) -> ACTIVATE(X) The graph contains the following edges 1 > 1 *TAKE(s(X), cons(Y, L)) -> ACTIVATE(L) The graph contains the following edges 2 > 1 ---------------------------------------- (9) YES ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(X), n__s(Y)) -> EQ(activate(X), activate(Y)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(X), n__s(Y)) -> EQ(activate(X), activate(Y)) at position [0] we obtained the following new rules [LPAR04]: (EQ(n__s(n__0), n__s(y1)) -> EQ(0, activate(y1)),EQ(n__s(n__0), n__s(y1)) -> EQ(0, activate(y1))) (EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(s(x0), activate(y1)),EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(s(x0), activate(y1))) (EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(inf(x0), activate(y1)),EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(inf(x0), activate(y1))) (EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(x0, x1), activate(y1)),EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(x0, x1), activate(y1))) (EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1)),EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1))) (EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)),EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1))) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__0), n__s(y1)) -> EQ(0, activate(y1)) EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(s(x0), activate(y1)) EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(inf(x0), activate(y1)) EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(x0, x1), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1)) EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__0), n__s(y1)) -> EQ(0, activate(y1)) at position [0] we obtained the following new rules [LPAR04]: (EQ(n__s(n__0), n__s(y0)) -> EQ(n__0, activate(y0)),EQ(n__s(n__0), n__s(y0)) -> EQ(n__0, activate(y0))) ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(s(x0), activate(y1)) EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(inf(x0), activate(y1)) EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(x0, x1), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1)) EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)) EQ(n__s(n__0), n__s(y0)) -> EQ(n__0, activate(y0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(s(x0), activate(y1)) EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(inf(x0), activate(y1)) EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(x0, x1), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1)) EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(s(x0), activate(y1)) at position [0] we obtained the following new rules [LPAR04]: (EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)),EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1))) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(inf(x0), activate(y1)) EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(x0, x1), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1)) EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)) EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(inf(x0), activate(y1)) at position [0] we obtained the following new rules [LPAR04]: (EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(cons(x0, n__inf(s(x0))), activate(y1)),EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(cons(x0, n__inf(s(x0))), activate(y1))) (EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(n__inf(x0), activate(y1)),EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(n__inf(x0), activate(y1))) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(x0, x1), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1)) EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)) EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(cons(x0, n__inf(s(x0))), activate(y1)) EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(n__inf(x0), activate(y1)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(x0, x1), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1)) EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)) EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(x0, x1), activate(y1)) at position [0] we obtained the following new rules [LPAR04]: (EQ(n__s(n__take(0, x0)), n__s(y2)) -> EQ(nil, activate(y2)),EQ(n__s(n__take(0, x0)), n__s(y2)) -> EQ(nil, activate(y2))) (EQ(n__s(n__take(s(x0), cons(x1, x2))), n__s(y2)) -> EQ(cons(activate(x1), n__take(activate(x0), activate(x2))), activate(y2)),EQ(n__s(n__take(s(x0), cons(x1, x2))), n__s(y2)) -> EQ(cons(activate(x1), n__take(activate(x0), activate(x2))), activate(y2))) (EQ(n__s(n__take(x0, x1)), n__s(y2)) -> EQ(n__take(x0, x1), activate(y2)),EQ(n__s(n__take(x0, x1)), n__s(y2)) -> EQ(n__take(x0, x1), activate(y2))) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1)) EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)) EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__take(0, x0)), n__s(y2)) -> EQ(nil, activate(y2)) EQ(n__s(n__take(s(x0), cons(x1, x2))), n__s(y2)) -> EQ(cons(activate(x1), n__take(activate(x0), activate(x2))), activate(y2)) EQ(n__s(n__take(x0, x1)), n__s(y2)) -> EQ(n__take(x0, x1), activate(y2)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1)) EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)) EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(x0), activate(y1)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(y0), 0),EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(y0), 0)) (EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), s(x0)),EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), s(x0))) (EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), inf(x0)),EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), inf(x0))) (EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), take(x0, x1)),EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), take(x0, x1))) (EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)),EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0))) (EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0),EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0)) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)) EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(y0), 0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), inf(x0)) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), take(x0, x1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(x0), n__s(y1)) -> EQ(x0, activate(y1)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0),EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0)) (EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)),EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0))) (EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)),EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0))) (EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)),EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1))) (EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)),EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0))) (EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0),EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0)) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(y0), 0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), inf(x0)) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), take(x0, x1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(y0), 0) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(y0), n__0),EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(y0), n__0)) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), inf(x0)) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), take(x0, x1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(y0), n__0) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), inf(x0)) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), take(x0, x1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), s(x0)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)),EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0))) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), inf(x0)) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), take(x0, x1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), inf(x0)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), cons(x0, n__inf(s(x0)))),EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), cons(x0, n__inf(s(x0))))) (EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), n__inf(x0)),EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), n__inf(x0))) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), take(x0, x1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), cons(x0, n__inf(s(x0)))) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(y0), n__inf(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), take(x0, x1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), take(x0, x1)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__length(y0)), n__s(n__take(0, x0))) -> EQ(length(y0), nil),EQ(n__s(n__length(y0)), n__s(n__take(0, x0))) -> EQ(length(y0), nil)) (EQ(n__s(n__length(y0)), n__s(n__take(s(x0), cons(x1, x2)))) -> EQ(length(y0), cons(activate(x1), n__take(activate(x0), activate(x2)))),EQ(n__s(n__length(y0)), n__s(n__take(s(x0), cons(x1, x2)))) -> EQ(length(y0), cons(activate(x1), n__take(activate(x0), activate(x2))))) (EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), n__take(x0, x1)),EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), n__take(x0, x1))) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) EQ(n__s(n__length(y0)), n__s(n__take(0, x0))) -> EQ(length(y0), nil) EQ(n__s(n__length(y0)), n__s(n__take(s(x0), cons(x1, x2)))) -> EQ(length(y0), cons(activate(x1), n__take(activate(x0), activate(x2)))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(y0), n__take(x0, x1)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(y0), n__s(n__0)) -> EQ(y0, 0) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(y0), n__s(n__0)) -> EQ(y0, n__0),EQ(n__s(y0), n__s(n__0)) -> EQ(y0, n__0)) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) EQ(n__s(y0), n__s(n__0)) -> EQ(y0, n__0) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, s(x0)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, n__s(x0)),EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, n__s(x0))) ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, n__s(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(x0)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, cons(x0, n__inf(s(x0)))),EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, cons(x0, n__inf(s(x0))))) (EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, n__inf(x0)),EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, n__inf(x0))) ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, n__s(x0)) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, cons(x0, n__inf(s(x0)))) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, n__inf(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, n__s(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(x0, x1)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(y0), n__s(n__take(0, x0))) -> EQ(y0, nil),EQ(n__s(y0), n__s(n__take(0, x0))) -> EQ(y0, nil)) (EQ(n__s(y0), n__s(n__take(s(x0), cons(x1, x2)))) -> EQ(y0, cons(activate(x1), n__take(activate(x0), activate(x2)))),EQ(n__s(y0), n__s(n__take(s(x0), cons(x1, x2)))) -> EQ(y0, cons(activate(x1), n__take(activate(x0), activate(x2))))) (EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, n__take(x0, x1)),EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, n__take(x0, x1))) ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, n__s(x0)) EQ(n__s(y0), n__s(n__take(0, x0))) -> EQ(y0, nil) EQ(n__s(y0), n__s(n__take(s(x0), cons(x1, x2)))) -> EQ(y0, cons(activate(x1), n__take(activate(x0), activate(x2)))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, n__take(x0, x1)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, n__s(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(y0), x0) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(y0), n__s(x0)) EQ(n__s(y0), n__s(n__s(x0))) -> EQ(y0, n__s(x0)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( EQ_2(x_1, x_2) ) = x_2 POL( cons_2(x_1, x_2) ) = 2x_2 + 2 POL( n__take_2(x_1, x_2) ) = max{0, x_2 - 2} POL( n__length_1(x_1) ) = max{0, x_1 - 2} POL( s_1(x_1) ) = x_1 + 2 POL( activate_1(x_1) ) = x_1 + 2 POL( n__0 ) = 0 POL( 0 ) = 0 POL( n__s_1(x_1) ) = x_1 + 2 POL( n__inf_1(x_1) ) = 0 POL( inf_1(x_1) ) = 2 POL( take_2(x_1, x_2) ) = x_2 POL( length_1(x_1) ) = x_1 POL( nil ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) length(X) -> n__length(X) take(0, X) -> nil take(X1, X2) -> n__take(X1, X2) take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) s(X) -> n__s(X) inf(X) -> cons(X, n__inf(s(X))) inf(X) -> n__inf(X) 0 -> n__0 ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. EQ(n__s(n__s(x0)), n__s(y1)) -> EQ(n__s(x0), activate(y1)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( EQ_2(x_1, x_2) ) = max{0, x_1 - 1} POL( cons_2(x_1, x_2) ) = max{0, x_1 - 2} POL( n__take_2(x_1, x_2) ) = x_1 + x_2 + 1 POL( n__length_1(x_1) ) = 0 POL( s_1(x_1) ) = 2x_1 + 1 POL( activate_1(x_1) ) = x_1 + 1 POL( n__0 ) = 0 POL( 0 ) = 0 POL( n__s_1(x_1) ) = 2x_1 + 1 POL( n__inf_1(x_1) ) = max{0, 2x_1 - 1} POL( inf_1(x_1) ) = 2x_1 POL( take_2(x_1, x_2) ) = x_1 + x_2 + 1 POL( length_1(x_1) ) = 1 POL( nil ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) length(X) -> n__length(X) take(0, X) -> nil take(X1, X2) -> n__take(X1, X2) take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) s(X) -> n__s(X) inf(X) -> cons(X, n__inf(s(X))) inf(X) -> n__inf(X) 0 -> n__0 ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(x0)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( EQ_2(x_1, x_2) ) = 2x_1 + x_2 + 2 POL( length_1(x_1) ) = 2 POL( nil ) = 0 POL( 0 ) = 0 POL( cons_2(x_1, x_2) ) = max{0, x_2 - 2} POL( s_1(x_1) ) = x_1 + 2 POL( n__length_1(x_1) ) = max{0, -2} POL( activate_1(x_1) ) = 2 POL( n__take_2(x_1, x_2) ) = max{0, -2} POL( take_2(x_1, x_2) ) = 0 POL( n__0 ) = 0 POL( n__s_1(x_1) ) = x_1 + 2 POL( n__inf_1(x_1) ) = max{0, x_1 - 2} POL( inf_1(x_1) ) = 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) length(X) -> n__length(X) activate(n__take(X1, X2)) -> take(X1, X2) take(0, X) -> nil take(X1, X2) -> n__take(X1, X2) take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) activate(n__length(X)) -> length(X) s(X) -> n__s(X) 0 -> n__0 ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) The TRS R consists of the following rules: eq(n__0, n__0) -> true eq(n__s(X), n__s(Y)) -> eq(activate(X), activate(Y)) eq(X, Y) -> false inf(X) -> cons(X, n__inf(s(X))) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) 0 -> n__0 s(X) -> n__s(X) inf(X) -> n__inf(X) take(X1, X2) -> n__take(X1, X2) length(X) -> n__length(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(n__inf(X)) -> inf(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(n__length(X)) -> length(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (65) 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 = EQ(length(activate(n__inf(X))), length(activate(n__inf(X')))) evaluates to t =EQ(length(activate(n__inf(s(X)))), length(activate(n__inf(s(X'))))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [X / s(X), X' / s(X')] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence EQ(length(activate(n__inf(X))), length(activate(n__inf(X')))) -> EQ(length(activate(n__inf(X))), length(inf(X'))) with rule activate(n__inf(X'')) -> inf(X'') at position [1,0] and matcher [X'' / X'] EQ(length(activate(n__inf(X))), length(inf(X'))) -> EQ(length(activate(n__inf(X))), length(cons(X', n__inf(s(X'))))) with rule inf(X'') -> cons(X'', n__inf(s(X''))) at position [1,0] and matcher [X'' / X'] EQ(length(activate(n__inf(X))), length(cons(X', n__inf(s(X'))))) -> EQ(length(activate(n__inf(X))), s(n__length(activate(n__inf(s(X')))))) with rule length(cons(X'', L)) -> s(n__length(activate(L))) at position [1] and matcher [X'' / X', L / n__inf(s(X'))] EQ(length(activate(n__inf(X))), s(n__length(activate(n__inf(s(X')))))) -> EQ(length(activate(n__inf(X))), n__s(n__length(activate(n__inf(s(X')))))) with rule s(X'') -> n__s(X'') at position [1] and matcher [X'' / n__length(activate(n__inf(s(X'))))] EQ(length(activate(n__inf(X))), n__s(n__length(activate(n__inf(s(X')))))) -> EQ(length(inf(X)), n__s(n__length(activate(n__inf(s(X')))))) with rule activate(n__inf(X'')) -> inf(X'') at position [0,0] and matcher [X'' / X] EQ(length(inf(X)), n__s(n__length(activate(n__inf(s(X')))))) -> EQ(length(cons(X, n__inf(s(X)))), n__s(n__length(activate(n__inf(s(X')))))) with rule inf(X'') -> cons(X'', n__inf(s(X''))) at position [0,0] and matcher [X'' / X] EQ(length(cons(X, n__inf(s(X)))), n__s(n__length(activate(n__inf(s(X')))))) -> EQ(s(n__length(activate(n__inf(s(X))))), n__s(n__length(activate(n__inf(s(X')))))) with rule length(cons(X'', L)) -> s(n__length(activate(L))) at position [0] and matcher [X'' / X, L / n__inf(s(X))] EQ(s(n__length(activate(n__inf(s(X))))), n__s(n__length(activate(n__inf(s(X')))))) -> EQ(n__s(n__length(activate(n__inf(s(X))))), n__s(n__length(activate(n__inf(s(X')))))) with rule s(X'') -> n__s(X'') at position [0] and matcher [X'' / n__length(activate(n__inf(s(X))))] EQ(n__s(n__length(activate(n__inf(s(X))))), n__s(n__length(activate(n__inf(s(X')))))) -> EQ(length(activate(n__inf(s(X)))), length(activate(n__inf(s(X'))))) with rule EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(y0), length(x0)) 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. ---------------------------------------- (66) NO