/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Outermost Termination of the given OTRS could be proven: (0) OTRS (1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) QDP (13) TransformationProof [EQUIVALENT, 0 ms] (14) QDP (15) DependencyGraphProof [EQUIVALENT, 0 ms] (16) QDP (17) QDPOrderProof [EQUIVALENT, 28 ms] (18) QDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) QDP (21) QDPOrderProof [EQUIVALENT, 25 ms] (22) QDP (23) QDPOrderProof [EQUIVALENT, 5887 ms] (24) QDP (25) PisEmptyProof [EQUIVALENT, 0 ms] (26) YES ---------------------------------------- (0) Obligation: Term rewrite system R: 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 Outermost Strategy. ---------------------------------------- (1) Raffelsieper-Zantema-Transformation (SOUND) We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) eq_flat(up(x_1), block(x_2)) -> up(eq(x_1, x_2)) eq_flat(block(x_1), up(x_2)) -> up(eq(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) inf_flat(up(x_1)) -> up(inf(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) s_flat(up(x_1)) -> up(s(x_1)) take_flat(up(x_1), block(x_2)) -> up(take(x_1, x_2)) take_flat(block(x_1), up(x_2)) -> up(take(x_1, x_2)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) n__length_flat(up(x_1)) -> up(n__length(x_1)) Q is empty. ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) TOP(up(x)) -> DOWN(x) DOWN(n__s(y2)) -> N__S_FLAT(down(y2)) DOWN(n__s(y2)) -> DOWN(y2) DOWN(cons(y5, y6)) -> CONS_FLAT(down(y5), block(y6)) DOWN(cons(y5, y6)) -> DOWN(y5) DOWN(cons(y5, y6)) -> CONS_FLAT(block(y5), down(y6)) DOWN(cons(y5, y6)) -> DOWN(y6) DOWN(n__inf(y7)) -> N__INF_FLAT(down(y7)) DOWN(n__inf(y7)) -> DOWN(y7) DOWN(n__take(y11, y12)) -> N__TAKE_FLAT(down(y11), block(y12)) DOWN(n__take(y11, y12)) -> DOWN(y11) DOWN(n__take(y11, y12)) -> N__TAKE_FLAT(block(y11), down(y12)) DOWN(n__take(y11, y12)) -> DOWN(y12) DOWN(n__length(y14)) -> N__LENGTH_FLAT(down(y14)) DOWN(n__length(y14)) -> DOWN(y14) The TRS R consists of the following rules: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) eq_flat(up(x_1), block(x_2)) -> up(eq(x_1, x_2)) eq_flat(block(x_1), up(x_2)) -> up(eq(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) inf_flat(up(x_1)) -> up(inf(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) s_flat(up(x_1)) -> up(s(x_1)) take_flat(up(x_1), block(x_2)) -> up(take(x_1, x_2)) take_flat(block(x_1), up(x_2)) -> up(take(x_1, x_2)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) n__length_flat(up(x_1)) -> up(n__length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 8 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(cons(y5, y6)) -> DOWN(y5) DOWN(n__s(y2)) -> DOWN(y2) DOWN(cons(y5, y6)) -> DOWN(y6) DOWN(n__inf(y7)) -> DOWN(y7) DOWN(n__take(y11, y12)) -> DOWN(y11) DOWN(n__take(y11, y12)) -> DOWN(y12) DOWN(n__length(y14)) -> DOWN(y14) The TRS R consists of the following rules: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) eq_flat(up(x_1), block(x_2)) -> up(eq(x_1, x_2)) eq_flat(block(x_1), up(x_2)) -> up(eq(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) inf_flat(up(x_1)) -> up(inf(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) s_flat(up(x_1)) -> up(s(x_1)) take_flat(up(x_1), block(x_2)) -> up(take(x_1, x_2)) take_flat(block(x_1), up(x_2)) -> up(take(x_1, x_2)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) n__length_flat(up(x_1)) -> up(n__length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) 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. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(cons(y5, y6)) -> DOWN(y5) DOWN(n__s(y2)) -> DOWN(y2) DOWN(cons(y5, y6)) -> DOWN(y6) DOWN(n__inf(y7)) -> DOWN(y7) DOWN(n__take(y11, y12)) -> DOWN(y11) DOWN(n__take(y11, y12)) -> DOWN(y12) DOWN(n__length(y14)) -> DOWN(y14) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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: *DOWN(cons(y5, y6)) -> DOWN(y5) The graph contains the following edges 1 > 1 *DOWN(n__s(y2)) -> DOWN(y2) The graph contains the following edges 1 > 1 *DOWN(cons(y5, y6)) -> DOWN(y6) The graph contains the following edges 1 > 1 *DOWN(n__inf(y7)) -> DOWN(y7) The graph contains the following edges 1 > 1 *DOWN(n__take(y11, y12)) -> DOWN(y11) The graph contains the following edges 1 > 1 *DOWN(n__take(y11, y12)) -> DOWN(y12) The graph contains the following edges 1 > 1 *DOWN(n__length(y14)) -> DOWN(y14) The graph contains the following edges 1 > 1 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) eq_flat(up(x_1), block(x_2)) -> up(eq(x_1, x_2)) eq_flat(block(x_1), up(x_2)) -> up(eq(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) inf_flat(up(x_1)) -> up(inf(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) s_flat(up(x_1)) -> up(s(x_1)) take_flat(up(x_1), block(x_2)) -> up(take(x_1, x_2)) take_flat(block(x_1), up(x_2)) -> up(take(x_1, x_2)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) n__length_flat(up(x_1)) -> up(n__length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(eq(n__0, n__0))) -> TOP(up(true)),TOP(up(eq(n__0, n__0))) -> TOP(up(true))) (TOP(up(eq(n__s(x0), n__s(x1)))) -> TOP(up(eq(activate(x0), activate(x1)))),TOP(up(eq(n__s(x0), n__s(x1)))) -> TOP(up(eq(activate(x0), activate(x1))))) (TOP(up(eq(x0, x1))) -> TOP(up(false)),TOP(up(eq(x0, x1))) -> TOP(up(false))) (TOP(up(inf(x0))) -> TOP(up(cons(x0, n__inf(s(x0))))),TOP(up(inf(x0))) -> TOP(up(cons(x0, n__inf(s(x0)))))) (TOP(up(take(0, x0))) -> TOP(up(nil)),TOP(up(take(0, x0))) -> TOP(up(nil))) (TOP(up(take(s(x0), cons(x1, x2)))) -> TOP(up(cons(activate(x1), n__take(activate(x0), activate(x2))))),TOP(up(take(s(x0), cons(x1, x2)))) -> TOP(up(cons(activate(x1), n__take(activate(x0), activate(x2)))))) (TOP(up(length(nil))) -> TOP(up(0)),TOP(up(length(nil))) -> TOP(up(0))) (TOP(up(length(cons(x0, x1)))) -> TOP(up(s(n__length(activate(x1))))),TOP(up(length(cons(x0, x1)))) -> TOP(up(s(n__length(activate(x1)))))) (TOP(up(0)) -> TOP(up(n__0)),TOP(up(0)) -> TOP(up(n__0))) (TOP(up(s(x0))) -> TOP(up(n__s(x0))),TOP(up(s(x0))) -> TOP(up(n__s(x0)))) (TOP(up(inf(x0))) -> TOP(up(n__inf(x0))),TOP(up(inf(x0))) -> TOP(up(n__inf(x0)))) (TOP(up(take(x0, x1))) -> TOP(up(n__take(x0, x1))),TOP(up(take(x0, x1))) -> TOP(up(n__take(x0, x1)))) (TOP(up(length(x0))) -> TOP(up(n__length(x0))),TOP(up(length(x0))) -> TOP(up(n__length(x0)))) (TOP(up(activate(n__0))) -> TOP(up(0)),TOP(up(activate(n__0))) -> TOP(up(0))) (TOP(up(activate(n__s(x0)))) -> TOP(up(s(x0))),TOP(up(activate(n__s(x0)))) -> TOP(up(s(x0)))) (TOP(up(activate(n__inf(x0)))) -> TOP(up(inf(x0))),TOP(up(activate(n__inf(x0)))) -> TOP(up(inf(x0)))) (TOP(up(activate(n__take(x0, x1)))) -> TOP(up(take(x0, x1))),TOP(up(activate(n__take(x0, x1)))) -> TOP(up(take(x0, x1)))) (TOP(up(activate(n__length(x0)))) -> TOP(up(length(x0))),TOP(up(activate(n__length(x0)))) -> TOP(up(length(x0)))) (TOP(up(activate(x0))) -> TOP(up(x0)),TOP(up(activate(x0))) -> TOP(up(x0))) (TOP(up(n__s(x0))) -> TOP(n__s_flat(down(x0))),TOP(up(n__s(x0))) -> TOP(n__s_flat(down(x0)))) (TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))),TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))) (TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))),TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))) (TOP(up(n__inf(x0))) -> TOP(n__inf_flat(down(x0))),TOP(up(n__inf(x0))) -> TOP(n__inf_flat(down(x0)))) (TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(down(x0), block(x1))),TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(down(x0), block(x1)))) (TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(block(x0), down(x1))),TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(block(x0), down(x1)))) (TOP(up(n__length(x0))) -> TOP(n__length_flat(down(x0))),TOP(up(n__length(x0))) -> TOP(n__length_flat(down(x0)))) ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(eq(n__0, n__0))) -> TOP(up(true)) TOP(up(eq(n__s(x0), n__s(x1)))) -> TOP(up(eq(activate(x0), activate(x1)))) TOP(up(eq(x0, x1))) -> TOP(up(false)) TOP(up(inf(x0))) -> TOP(up(cons(x0, n__inf(s(x0))))) TOP(up(take(0, x0))) -> TOP(up(nil)) TOP(up(take(s(x0), cons(x1, x2)))) -> TOP(up(cons(activate(x1), n__take(activate(x0), activate(x2))))) TOP(up(length(nil))) -> TOP(up(0)) TOP(up(length(cons(x0, x1)))) -> TOP(up(s(n__length(activate(x1))))) TOP(up(0)) -> TOP(up(n__0)) TOP(up(s(x0))) -> TOP(up(n__s(x0))) TOP(up(inf(x0))) -> TOP(up(n__inf(x0))) TOP(up(take(x0, x1))) -> TOP(up(n__take(x0, x1))) TOP(up(length(x0))) -> TOP(up(n__length(x0))) TOP(up(activate(n__0))) -> TOP(up(0)) TOP(up(activate(n__s(x0)))) -> TOP(up(s(x0))) TOP(up(activate(n__inf(x0)))) -> TOP(up(inf(x0))) TOP(up(activate(n__take(x0, x1)))) -> TOP(up(take(x0, x1))) TOP(up(activate(n__length(x0)))) -> TOP(up(length(x0))) TOP(up(activate(x0))) -> TOP(up(x0)) TOP(up(n__s(x0))) -> TOP(n__s_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(n__inf(x0))) -> TOP(n__inf_flat(down(x0))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(down(x0), block(x1))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(block(x0), down(x1))) TOP(up(n__length(x0))) -> TOP(n__length_flat(down(x0))) The TRS R consists of the following rules: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) eq_flat(up(x_1), block(x_2)) -> up(eq(x_1, x_2)) eq_flat(block(x_1), up(x_2)) -> up(eq(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) inf_flat(up(x_1)) -> up(inf(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) s_flat(up(x_1)) -> up(s(x_1)) take_flat(up(x_1), block(x_2)) -> up(take(x_1, x_2)) take_flat(block(x_1), up(x_2)) -> up(take(x_1, x_2)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) n__length_flat(up(x_1)) -> up(n__length(x_1)) 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 7 less nodes. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(inf(x0))) -> TOP(up(cons(x0, n__inf(s(x0))))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(take(s(x0), cons(x1, x2)))) -> TOP(up(cons(activate(x1), n__take(activate(x0), activate(x2))))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(length(cons(x0, x1)))) -> TOP(up(s(n__length(activate(x1))))) TOP(up(s(x0))) -> TOP(up(n__s(x0))) TOP(up(n__s(x0))) -> TOP(n__s_flat(down(x0))) TOP(up(inf(x0))) -> TOP(up(n__inf(x0))) TOP(up(n__inf(x0))) -> TOP(n__inf_flat(down(x0))) TOP(up(take(x0, x1))) -> TOP(up(n__take(x0, x1))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(down(x0), block(x1))) TOP(up(length(x0))) -> TOP(up(n__length(x0))) TOP(up(n__length(x0))) -> TOP(n__length_flat(down(x0))) TOP(up(activate(n__s(x0)))) -> TOP(up(s(x0))) TOP(up(activate(n__inf(x0)))) -> TOP(up(inf(x0))) TOP(up(activate(n__take(x0, x1)))) -> TOP(up(take(x0, x1))) TOP(up(activate(n__length(x0)))) -> TOP(up(length(x0))) TOP(up(activate(x0))) -> TOP(up(x0)) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(block(x0), down(x1))) The TRS R consists of the following rules: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) eq_flat(up(x_1), block(x_2)) -> up(eq(x_1, x_2)) eq_flat(block(x_1), up(x_2)) -> up(eq(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) inf_flat(up(x_1)) -> up(inf(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) s_flat(up(x_1)) -> up(s(x_1)) take_flat(up(x_1), block(x_2)) -> up(take(x_1, x_2)) take_flat(block(x_1), up(x_2)) -> up(take(x_1, x_2)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) n__length_flat(up(x_1)) -> up(n__length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(inf(x0))) -> TOP(up(cons(x0, n__inf(s(x0))))) TOP(up(take(s(x0), cons(x1, x2)))) -> TOP(up(cons(activate(x1), n__take(activate(x0), activate(x2))))) TOP(up(length(cons(x0, x1)))) -> TOP(up(s(n__length(activate(x1))))) TOP(up(inf(x0))) -> TOP(up(n__inf(x0))) TOP(up(take(x0, x1))) -> TOP(up(n__take(x0, x1))) TOP(up(length(x0))) -> TOP(up(n__length(x0))) TOP(up(activate(n__s(x0)))) -> TOP(up(s(x0))) TOP(up(activate(x0))) -> TOP(up(x0)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(TOP(x_1)) = x_1 POL(activate(x_1)) = 1 + x_1 POL(block(x_1)) = 0 POL(cons(x_1, x_2)) = 0 POL(cons_flat(x_1, x_2)) = 0 POL(down(x_1)) = 0 POL(eq(x_1, x_2)) = 0 POL(false) = 1 POL(inf(x_1)) = 1 POL(length(x_1)) = 1 POL(n__0) = 0 POL(n__inf(x_1)) = 0 POL(n__inf_flat(x_1)) = 0 POL(n__length(x_1)) = 0 POL(n__length_flat(x_1)) = 0 POL(n__s(x_1)) = 0 POL(n__s_flat(x_1)) = 0 POL(n__take(x_1, x_2)) = 0 POL(n__take_flat(x_1, x_2)) = 0 POL(nil) = 0 POL(s(x_1)) = 0 POL(take(x_1, x_2)) = 1 POL(true) = 1 POL(up(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__length_flat(up(x_1)) -> up(n__length(x_1)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(up(n__s(x0))) TOP(up(n__s(x0))) -> TOP(n__s_flat(down(x0))) TOP(up(n__inf(x0))) -> TOP(n__inf_flat(down(x0))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(down(x0), block(x1))) TOP(up(n__length(x0))) -> TOP(n__length_flat(down(x0))) TOP(up(activate(n__inf(x0)))) -> TOP(up(inf(x0))) TOP(up(activate(n__take(x0, x1)))) -> TOP(up(take(x0, x1))) TOP(up(activate(n__length(x0)))) -> TOP(up(length(x0))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(block(x0), down(x1))) The TRS R consists of the following rules: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) eq_flat(up(x_1), block(x_2)) -> up(eq(x_1, x_2)) eq_flat(block(x_1), up(x_2)) -> up(eq(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) inf_flat(up(x_1)) -> up(inf(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) s_flat(up(x_1)) -> up(s(x_1)) take_flat(up(x_1), block(x_2)) -> up(take(x_1, x_2)) take_flat(block(x_1), up(x_2)) -> up(take(x_1, x_2)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) n__length_flat(up(x_1)) -> up(n__length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(s(x0))) -> TOP(up(n__s(x0))) TOP(up(n__s(x0))) -> TOP(n__s_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(n__inf(x0))) -> TOP(n__inf_flat(down(x0))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(down(x0), block(x1))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(block(x0), down(x1))) TOP(up(n__length(x0))) -> TOP(n__length_flat(down(x0))) The TRS R consists of the following rules: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) eq_flat(up(x_1), block(x_2)) -> up(eq(x_1, x_2)) eq_flat(block(x_1), up(x_2)) -> up(eq(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) inf_flat(up(x_1)) -> up(inf(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) s_flat(up(x_1)) -> up(s(x_1)) take_flat(up(x_1), block(x_2)) -> up(take(x_1, x_2)) take_flat(block(x_1), up(x_2)) -> up(take(x_1, x_2)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) n__length_flat(up(x_1)) -> up(n__length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(s(x0))) -> TOP(up(n__s(x0))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(TOP(x_1)) = x_1 POL(activate(x_1)) = 0 POL(block(x_1)) = 0 POL(cons(x_1, x_2)) = 0 POL(cons_flat(x_1, x_2)) = 0 POL(down(x_1)) = 0 POL(eq(x_1, x_2)) = 0 POL(false) = 1 POL(inf(x_1)) = x_1 POL(length(x_1)) = 0 POL(n__0) = 0 POL(n__inf(x_1)) = 0 POL(n__inf_flat(x_1)) = 0 POL(n__length(x_1)) = 0 POL(n__length_flat(x_1)) = 0 POL(n__s(x_1)) = 0 POL(n__s_flat(x_1)) = 0 POL(n__take(x_1, x_2)) = 0 POL(n__take_flat(x_1, x_2)) = 0 POL(nil) = 0 POL(s(x_1)) = 1 POL(take(x_1, x_2)) = 0 POL(true) = 1 POL(up(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: n__s_flat(up(x_1)) -> up(n__s(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) n__length_flat(up(x_1)) -> up(n__length(x_1)) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(n__s(x0))) -> TOP(n__s_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(n__inf(x0))) -> TOP(n__inf_flat(down(x0))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(down(x0), block(x1))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(block(x0), down(x1))) TOP(up(n__length(x0))) -> TOP(n__length_flat(down(x0))) The TRS R consists of the following rules: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) eq_flat(up(x_1), block(x_2)) -> up(eq(x_1, x_2)) eq_flat(block(x_1), up(x_2)) -> up(eq(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) inf_flat(up(x_1)) -> up(inf(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) s_flat(up(x_1)) -> up(s(x_1)) take_flat(up(x_1), block(x_2)) -> up(take(x_1, x_2)) take_flat(block(x_1), up(x_2)) -> up(take(x_1, x_2)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) n__length_flat(up(x_1)) -> up(n__length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(n__s(x0))) -> TOP(n__s_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(n__inf(x0))) -> TOP(n__inf_flat(down(x0))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(down(x0), block(x1))) TOP(up(n__take(x0, x1))) -> TOP(n__take_flat(block(x0), down(x1))) TOP(up(n__length(x0))) -> TOP(n__length_flat(down(x0))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( n__length_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( true ) = [[0], [0]] >>> <<< M( n__inf_1(x_1) ) = [[2], [0]] + [[1, 2], [0, 1]] * x_1 >>> <<< M( n__take_2(x_1, x_2) ) = [[2], [1]] + [[1, 1], [0, 1]] * x_1 + [[2, 0], [0, 1]] * x_2 >>> <<< M( n__take_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [2, 1]] * x_1 + [[0, 0], [2, 1]] * x_2 >>> <<< M( n__length_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 >>> <<< M( n__inf_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( block_1(x_1) ) = [[1], [0]] + [[0, 0], [0, 2]] * x_1 >>> <<< M( n__0 ) = [[1], [0]] >>> <<< M( inf_1(x_1) ) = [[0], [3]] + [[0, 0], [1, 3]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [2, 2]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< M( activate_1(x_1) ) = [[0], [2]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( n__s_1(x_1) ) = [[1], [0]] + [[1, 2], [0, 1]] * x_1 >>> <<< M( false ) = [[0], [0]] >>> <<< M( nil ) = [[0], [2]] >>> <<< M( s_1(x_1) ) = [[3], [1]] + [[1, 0], [1, 1]] * x_1 >>> <<< M( n__s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( eq_2(x_1, x_2) ) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [1, 0]] * x_2 >>> <<< M( length_1(x_1) ) = [[0], [1]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( take_2(x_1, x_2) ) = [[0], [3]] + [[0, 0], [1, 1]] * x_1 + [[0, 0], [1, 1]] * x_2 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 2]] * x_1 >>> <<< M( 0 ) = [[1], [2]] >>> <<< M( up_1(x_1) ) = [[0], [2]] + [[0, 0], [0, 2]] * x_1 >>> <<< M( cons_2(x_1, x_2) ) = [[3], [1]] + [[2, 0], [0, 2]] * x_1 + [[2, 0], [0, 1]] * x_2 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) n__s_flat(up(x_1)) -> up(n__s(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) n__length_flat(up(x_1)) -> up(n__length(x_1)) ---------------------------------------- (24) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: down(eq(n__0, n__0)) -> up(true) down(eq(n__s(X), n__s(Y))) -> up(eq(activate(X), activate(Y))) down(eq(X, Y)) -> up(false) down(inf(X)) -> up(cons(X, n__inf(s(X)))) down(take(0, X)) -> up(nil) down(take(s(X), cons(Y, L))) -> up(cons(activate(Y), n__take(activate(X), activate(L)))) down(length(nil)) -> up(0) down(length(cons(X, L))) -> up(s(n__length(activate(L)))) down(0) -> up(n__0) down(s(X)) -> up(n__s(X)) down(inf(X)) -> up(n__inf(X)) down(take(X1, X2)) -> up(n__take(X1, X2)) down(length(X)) -> up(n__length(X)) down(activate(n__0)) -> up(0) down(activate(n__s(X))) -> up(s(X)) down(activate(n__inf(X))) -> up(inf(X)) down(activate(n__take(X1, X2))) -> up(take(X1, X2)) down(activate(n__length(X))) -> up(length(X)) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(n__s(y2)) -> n__s_flat(down(y2)) down(cons(y5, y6)) -> cons_flat(down(y5), block(y6)) down(cons(y5, y6)) -> cons_flat(block(y5), down(y6)) down(n__inf(y7)) -> n__inf_flat(down(y7)) down(n__take(y11, y12)) -> n__take_flat(down(y11), block(y12)) down(n__take(y11, y12)) -> n__take_flat(block(y11), down(y12)) down(n__length(y14)) -> n__length_flat(down(y14)) eq_flat(up(x_1), block(x_2)) -> up(eq(x_1, x_2)) eq_flat(block(x_1), up(x_2)) -> up(eq(x_1, x_2)) n__s_flat(up(x_1)) -> up(n__s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) inf_flat(up(x_1)) -> up(inf(x_1)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__inf_flat(up(x_1)) -> up(n__inf(x_1)) s_flat(up(x_1)) -> up(s(x_1)) take_flat(up(x_1), block(x_2)) -> up(take(x_1, x_2)) take_flat(block(x_1), up(x_2)) -> up(take(x_1, x_2)) n__take_flat(up(x_1), block(x_2)) -> up(n__take(x_1, x_2)) n__take_flat(block(x_1), up(x_2)) -> up(n__take(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) n__length_flat(up(x_1)) -> up(n__length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (26) YES