/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) QDPOrderProof [EQUIVALENT, 83 ms] (7) QDP (8) QDPOrderProof [EQUIVALENT, 52 ms] (9) QDP (10) DependencyGraphProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPOrderProof [EQUIVALENT, 33 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) TransformationProof [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) TransformationProof [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) TransformationProof [EQUIVALENT, 24 ms] (44) QDP (45) DependencyGraphProof [EQUIVALENT, 0 ms] (46) QDP (47) TransformationProof [EQUIVALENT, 14 ms] (48) QDP (49) TransformationProof [EQUIVALENT, 122 ms] (50) QDP (51) DependencyGraphProof [EQUIVALENT, 0 ms] (52) QDP (53) TransformationProof [EQUIVALENT, 133 ms] (54) QDP (55) TransformationProof [EQUIVALENT, 188 ms] (56) QDP (57) DependencyGraphProof [EQUIVALENT, 0 ms] (58) QDP (59) TransformationProof [EQUIVALENT, 97 ms] (60) QDP (61) QDPOrderProof [EQUIVALENT, 126 ms] (62) QDP (63) QDPOrderProof [EQUIVALENT, 33 ms] (64) QDP (65) NonTerminationLoopProof [COMPLETE, 52.5 s] (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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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) 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(activate(X)) ACTIVATE(n__inf(X)) -> ACTIVATE(X) 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__length(X)) -> LENGTH(activate(X)) ACTIVATE(n__length(X)) -> ACTIVATE(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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 7 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__inf(X)) -> ACTIVATE(X) ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) TAKE(s(X), cons(Y, L)) -> ACTIVATE(Y) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__length(X)) -> LENGTH(activate(X)) LENGTH(cons(X, L)) -> ACTIVATE(L) ACTIVATE(n__length(X)) -> ACTIVATE(X) 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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (6) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X2) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(ACTIVATE(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(n__inf(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(n__take(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(TAKE(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(activate(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(n__length(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(LENGTH(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(n__0) = [[0A]] >>> <<< POL(0) = [[0A]] >>> <<< POL(n__s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(inf(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(take(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(length(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> 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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X take(0, X) -> nil take(X1, X2) -> n__take(X1, X2) inf(X) -> cons(X, n__inf(n__s(X))) inf(X) -> n__inf(X) length(nil) -> 0 length(X) -> n__length(X) length(cons(X, L)) -> s(n__length(activate(L))) s(X) -> n__s(X) take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) 0 -> n__0 ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__inf(X)) -> ACTIVATE(X) ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) TAKE(s(X), cons(Y, L)) -> ACTIVATE(Y) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__length(X)) -> LENGTH(activate(X)) LENGTH(cons(X, L)) -> ACTIVATE(L) ACTIVATE(n__length(X)) -> ACTIVATE(X) 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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVATE(n__length(X)) -> LENGTH(activate(X)) ACTIVATE(n__length(X)) -> ACTIVATE(X) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO,RATPOLO]: POL(0) = 0 POL(ACTIVATE(x_1)) = x_1 POL(LENGTH(x_1)) = [4]x_1 POL(TAKE(x_1, x_2)) = [4]x_1 + [4]x_2 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = [1/4]x_1 + [1/4]x_2 POL(inf(x_1)) = x_1 POL(length(x_1)) = [1/4] + [4]x_1 POL(n__0) = 0 POL(n__inf(x_1)) = x_1 POL(n__length(x_1)) = [1/4] + [4]x_1 POL(n__s(x_1)) = [1/4]x_1 POL(n__take(x_1, x_2)) = [4]x_1 + [4]x_2 POL(nil) = 0 POL(s(x_1)) = [1/4]x_1 POL(take(x_1, x_2)) = [4]x_1 + [4]x_2 The value of delta used in the strict ordering is 1/4. 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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X take(0, X) -> nil take(X1, X2) -> n__take(X1, X2) inf(X) -> cons(X, n__inf(n__s(X))) inf(X) -> n__inf(X) length(nil) -> 0 length(X) -> n__length(X) length(cons(X, L)) -> s(n__length(activate(L))) s(X) -> n__s(X) take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) 0 -> n__0 ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__inf(X)) -> ACTIVATE(X) ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) TAKE(s(X), cons(Y, L)) -> ACTIVATE(Y) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) 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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) TAKE(s(X), cons(Y, L)) -> ACTIVATE(Y) ACTIVATE(n__inf(X)) -> ACTIVATE(X) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) 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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVATE(n__take(X1, X2)) -> TAKE(activate(X1), activate(X2)) ACTIVATE(n__take(X1, X2)) -> ACTIVATE(X1) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO,RATPOLO]: POL(0) = 0 POL(ACTIVATE(x_1)) = x_1 POL(TAKE(x_1, x_2)) = [4]x_1 + [4]x_2 POL(activate(x_1)) = x_1 POL(cons(x_1, x_2)) = [1/4]x_1 + [1/4]x_2 POL(inf(x_1)) = [2]x_1 POL(length(x_1)) = 0 POL(n__0) = 0 POL(n__inf(x_1)) = [2]x_1 POL(n__length(x_1)) = 0 POL(n__s(x_1)) = [1/4]x_1 POL(n__take(x_1, x_2)) = [1/2] + [4]x_1 + [4]x_2 POL(nil) = [1/2] POL(s(x_1)) = [1/4]x_1 POL(take(x_1, x_2)) = [1/2] + [4]x_1 + [4]x_2 The value of delta used in the strict ordering is 1/2. 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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X take(0, X) -> nil take(X1, X2) -> n__take(X1, X2) inf(X) -> cons(X, n__inf(n__s(X))) inf(X) -> n__inf(X) length(nil) -> 0 length(X) -> n__length(X) length(cons(X, L)) -> s(n__length(activate(L))) s(X) -> n__s(X) take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) 0 -> n__0 ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: TAKE(s(X), cons(Y, L)) -> ACTIVATE(Y) ACTIVATE(n__inf(X)) -> ACTIVATE(X) 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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X 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 3 less nodes. ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__inf(X)) -> ACTIVATE(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X 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__inf(X)) -> ACTIVATE(X) 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__inf(X)) -> ACTIVATE(X) The graph contains the following edges 1 > 1 ---------------------------------------- (19) YES ---------------------------------------- (20) 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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(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 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(activate(x0)), activate(y1)),EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(inf(activate(x0)), activate(y1))) (EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(activate(x0), activate(x1)), activate(y1)),EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(activate(x0), activate(x1)), activate(y1))) (EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(activate(x0)), activate(y1)),EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(activate(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))) ---------------------------------------- (22) 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(activate(x0)), activate(y1)) EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(activate(x0), activate(x1)), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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__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))) ---------------------------------------- (24) 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(activate(x0)), activate(y1)) EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(activate(x0), activate(x1)), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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 1 less node. ---------------------------------------- (26) 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(activate(x0)), activate(y1)) EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(activate(x0), activate(x1)), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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__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))) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__inf(x0)), n__s(y1)) -> EQ(inf(activate(x0)), activate(y1)) EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(activate(x0), activate(x1)), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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(n__inf(x0)), n__s(y1)) -> EQ(inf(activate(x0)), activate(y1)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__inf(y0)), n__s(n__0)) -> EQ(inf(activate(y0)), 0),EQ(n__s(n__inf(y0)), n__s(n__0)) -> EQ(inf(activate(y0)), 0)) (EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), s(x0)),EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), s(x0))) (EQ(n__s(n__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))),EQ(n__s(n__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0)))) (EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))),EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1)))) (EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))),EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0)))) (EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0),EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0)) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__take(x0, x1)), n__s(y1)) -> EQ(take(activate(x0), activate(x1)), activate(y1)) EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(activate(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(y0)), n__s(n__0)) -> EQ(inf(activate(y0)), 0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), s(x0)) EQ(n__s(n__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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__take(x0, x1)), n__s(y1)) -> EQ(take(activate(x0), activate(x1)), activate(y1)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), 0),EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), 0)) (EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0)),EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0))) (EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))),EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0)))) (EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))),EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1)))) (EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))),EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0)))) (EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0),EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0)) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(activate(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(y0)), n__s(n__0)) -> EQ(inf(activate(y0)), 0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), s(x0)) EQ(n__s(n__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), 0) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), 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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__length(x0)), n__s(y1)) -> EQ(length(activate(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(activate(y0)), 0),EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), 0)) (EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)),EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0))) (EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))),EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0)))) (EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))),EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1)))) (EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))),EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0)))) (EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(y0)), x0),EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(y0)), x0)) ---------------------------------------- (34) 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__inf(y0)), n__s(n__0)) -> EQ(inf(activate(y0)), 0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), s(x0)) EQ(n__s(n__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), 0) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), 0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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(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(activate(x0))),EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(activate(x0)))) (EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))),EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1)))) (EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))),EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0)))) (EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0),EQ(n__s(y0), n__s(x0)) -> EQ(y0, 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__inf(y0)), n__s(n__0)) -> EQ(inf(activate(y0)), 0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), s(x0)) EQ(n__s(n__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), 0) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), 0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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__inf(y0)), n__s(n__0)) -> EQ(inf(activate(y0)), 0) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__inf(y0)), n__s(n__0)) -> EQ(inf(activate(y0)), n__0),EQ(n__s(n__inf(y0)), n__s(n__0)) -> EQ(inf(activate(y0)), n__0)) ---------------------------------------- (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__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), s(x0)) EQ(n__s(n__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), 0) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), 0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__0)) -> EQ(inf(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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 1 less node. ---------------------------------------- (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__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), s(x0)) EQ(n__s(n__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), 0) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), 0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), s(x0)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0)),EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0))) ---------------------------------------- (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__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), 0) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), 0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), 0) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), n__0),EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), n__0)) ---------------------------------------- (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__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), 0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__0)) -> EQ(take(activate(y0), activate(y1)), 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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (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__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), 0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), s(x0)) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), n__s(x0)),EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), n__s(x0))) ---------------------------------------- (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__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), 0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), 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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), 0) at position [1] we obtained the following new rules [LPAR04]: (EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), n__0),EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(y0)), n__0)) ---------------------------------------- (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__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), n__s(x0)) EQ(n__s(n__length(y0)), n__s(n__0)) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (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__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), s(x0)) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), 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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(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(activate(y0)), n__s(x0)),EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(y0)), n__s(x0))) ---------------------------------------- (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__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), n__s(x0)) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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__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)) ---------------------------------------- (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__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), n__s(x0)) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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 1 less node. ---------------------------------------- (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__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(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(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), n__s(x0)) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) 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))) ---------------------------------------- (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__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(y0)), x0) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), n__s(x0)) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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)) EQ(n__s(n__inf(y0)), n__s(n__inf(x0))) -> EQ(inf(activate(y0)), inf(activate(x0))) EQ(n__s(n__inf(y0)), n__s(n__take(x0, x1))) -> EQ(inf(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__inf(y0)), n__s(n__length(x0))) -> EQ(inf(activate(y0)), length(activate(x0))) EQ(n__s(n__inf(y0)), n__s(x0)) -> EQ(inf(activate(y0)), x0) EQ(n__s(n__take(y0, y1)), n__s(n__inf(x0))) -> EQ(take(activate(y0), activate(y1)), inf(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(n__take(x0, x1))) -> EQ(take(activate(y0), activate(y1)), take(activate(x0), activate(x1))) EQ(n__s(n__take(y0, y1)), n__s(n__length(x0))) -> EQ(take(activate(y0), activate(y1)), length(activate(x0))) EQ(n__s(n__take(y0, y1)), n__s(x0)) -> EQ(take(activate(y0), activate(y1)), x0) EQ(n__s(y0), n__s(n__inf(x0))) -> EQ(y0, inf(activate(x0))) EQ(n__s(y0), n__s(n__take(x0, x1))) -> EQ(y0, take(activate(x0), activate(x1))) EQ(n__s(y0), n__s(n__length(x0))) -> EQ(y0, length(activate(x0))) EQ(n__s(y0), n__s(x0)) -> EQ(y0, x0) EQ(n__s(n__inf(y0)), n__s(n__s(x0))) -> EQ(inf(activate(y0)), n__s(x0)) EQ(n__s(n__take(y0, y1)), n__s(n__s(x0))) -> EQ(take(activate(y0), activate(y1)), 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) ) = 2x_1 + 2 POL( cons_2(x_1, x_2) ) = max{0, 2x_2 - 2} POL( inf_1(x_1) ) = max{0, -2} POL( length_1(x_1) ) = 2 POL( take_2(x_1, x_2) ) = 2 POL( n__take_2(x_1, x_2) ) = 2 POL( n__length_1(x_1) ) = max{0, -2} POL( s_1(x_1) ) = 2x_1 + 2 POL( activate_1(x_1) ) = 2 POL( n__0 ) = 0 POL( 0 ) = 2 POL( n__s_1(x_1) ) = 2x_1 + 2 POL( n__inf_1(x_1) ) = 0 POL( nil ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__inf(X)) -> inf(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) inf(X) -> cons(X, n__inf(n__s(X))) inf(X) -> n__inf(X) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) take(X1, X2) -> n__take(X1, X2) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) length(X) -> n__length(X) s(X) -> n__s(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__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(x0))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(y0)), x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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(n__length(y0)), n__s(n__inf(x0))) -> EQ(length(activate(y0)), inf(activate(x0))) EQ(n__s(n__length(y0)), n__s(n__take(x0, x1))) -> EQ(length(activate(y0)), take(activate(x0), activate(x1))) EQ(n__s(n__length(y0)), n__s(x0)) -> EQ(length(activate(y0)), x0) EQ(n__s(n__length(y0)), n__s(n__s(x0))) -> EQ(length(activate(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) ) = max{0, 2x_2 - 2} POL( cons_2(x_1, x_2) ) = max{0, -2} POL( inf_1(x_1) ) = 2 POL( length_1(x_1) ) = 2 POL( take_2(x_1, x_2) ) = 1 POL( n__take_2(x_1, x_2) ) = 1 POL( n__length_1(x_1) ) = max{0, -2} POL( s_1(x_1) ) = 2x_1 + 2 POL( activate_1(x_1) ) = 2 POL( n__0 ) = 0 POL( 0 ) = 0 POL( n__s_1(x_1) ) = 2x_1 + 2 POL( n__inf_1(x_1) ) = 1 POL( nil ) = 1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__inf(X)) -> inf(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(X)) length(nil) -> 0 length(cons(X, L)) -> s(n__length(activate(L))) length(X) -> n__length(X) inf(X) -> cons(X, n__inf(n__s(X))) inf(X) -> n__inf(X) take(0, X) -> nil take(s(X), cons(Y, L)) -> cons(activate(Y), n__take(activate(X), activate(L))) take(X1, X2) -> n__take(X1, X2) 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(activate(y0)), length(activate(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(n__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(activate(X)) activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) activate(n__length(X)) -> length(activate(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(activate(n__inf(X)))), length(activate(activate(n__inf(X'))))) evaluates to t =EQ(length(activate(activate(n__inf(n__s(activate(X)))))), length(activate(activate(n__inf(n__s(activate(X'))))))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [X / n__s(activate(X)), X' / n__s(activate(X'))] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence EQ(length(activate(activate(n__inf(X)))), length(activate(activate(n__inf(X'))))) -> EQ(length(activate(activate(n__inf(X)))), length(activate(n__inf(X')))) with rule activate(X'') -> X'' at position [1,0] and matcher [X'' / activate(n__inf(X'))] EQ(length(activate(activate(n__inf(X)))), length(activate(n__inf(X')))) -> EQ(length(activate(activate(n__inf(X)))), length(inf(activate(X')))) with rule activate(n__inf(X'')) -> inf(activate(X'')) at position [1,0] and matcher [X'' / X'] EQ(length(activate(activate(n__inf(X)))), length(inf(activate(X')))) -> EQ(length(activate(activate(n__inf(X)))), length(cons(activate(X'), n__inf(n__s(activate(X')))))) with rule inf(X'') -> cons(X'', n__inf(n__s(X''))) at position [1,0] and matcher [X'' / activate(X')] EQ(length(activate(activate(n__inf(X)))), length(cons(activate(X'), n__inf(n__s(activate(X')))))) -> EQ(length(activate(activate(n__inf(X)))), s(n__length(activate(n__inf(n__s(activate(X'))))))) with rule length(cons(X'', L)) -> s(n__length(activate(L))) at position [1] and matcher [X'' / activate(X'), L / n__inf(n__s(activate(X')))] EQ(length(activate(activate(n__inf(X)))), s(n__length(activate(n__inf(n__s(activate(X'))))))) -> EQ(length(activate(activate(n__inf(X)))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) with rule s(X'') -> n__s(X'') at position [1] and matcher [X'' / n__length(activate(n__inf(n__s(activate(X')))))] EQ(length(activate(activate(n__inf(X)))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) -> EQ(length(activate(n__inf(X))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) with rule activate(X'') -> X'' at position [0,0] and matcher [X'' / activate(n__inf(X))] EQ(length(activate(n__inf(X))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) -> EQ(length(inf(activate(X))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) with rule activate(n__inf(X'')) -> inf(activate(X'')) at position [0,0] and matcher [X'' / X] EQ(length(inf(activate(X))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) -> EQ(length(cons(activate(X), n__inf(n__s(activate(X))))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) with rule inf(X'') -> cons(X'', n__inf(n__s(X''))) at position [0,0] and matcher [X'' / activate(X)] EQ(length(cons(activate(X), n__inf(n__s(activate(X))))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) -> EQ(s(n__length(activate(n__inf(n__s(activate(X)))))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) with rule length(cons(X'', L)) -> s(n__length(activate(L))) at position [0] and matcher [X'' / activate(X), L / n__inf(n__s(activate(X)))] EQ(s(n__length(activate(n__inf(n__s(activate(X)))))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) -> EQ(n__s(n__length(activate(n__inf(n__s(activate(X)))))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) with rule s(X'') -> n__s(X'') at position [0] and matcher [X'' / n__length(activate(n__inf(n__s(activate(X)))))] EQ(n__s(n__length(activate(n__inf(n__s(activate(X)))))), n__s(n__length(activate(n__inf(n__s(activate(X'))))))) -> EQ(length(activate(activate(n__inf(n__s(activate(X)))))), length(activate(activate(n__inf(n__s(activate(X'))))))) with rule EQ(n__s(n__length(y0)), n__s(n__length(x0))) -> EQ(length(activate(y0)), length(activate(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