/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: c69e44bd14796315568835c1ffa2502984884775 mhark 20210624 unpublished Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 67 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) QDPSizeChangeProof [EQUIVALENT, 0 ms] (9) YES (10) QDP (11) UsableRulesProof [EQUIVALENT, 0 ms] (12) QDP (13) QDPSizeChangeProof [EQUIVALENT, 0 ms] (14) YES (15) QDP (16) UsableRulesProof [EQUIVALENT, 0 ms] (17) QDP (18) QDPSizeChangeProof [EQUIVALENT, 0 ms] (19) YES (20) QDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) QDP (23) QDPSizeChangeProof [EQUIVALENT, 0 ms] (24) YES (25) QDP (26) UsableRulesProof [EQUIVALENT, 0 ms] (27) QDP (28) QDPSizeChangeProof [EQUIVALENT, 0 ms] (29) YES (30) QDP (31) QDPOrderProof [EQUIVALENT, 42 ms] (32) QDP (33) QDPOrderProof [EQUIVALENT, 54 ms] (34) QDP (35) DependencyGraphProof [EQUIVALENT, 0 ms] (36) QDP (37) QDPOrderProof [EQUIVALENT, 53 ms] (38) QDP (39) QDPOrderProof [EQUIVALENT, 0 ms] (40) QDP (41) QDPOrderProof [EQUIVALENT, 0 ms] (42) QDP (43) DependencyGraphProof [EQUIVALENT, 0 ms] (44) QDP (45) UsableRulesProof [EQUIVALENT, 0 ms] (46) QDP (47) QDPSizeChangeProof [EQUIVALENT, 0 ms] (48) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(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: ACTIVE(filter(cons(X, Y), 0, M)) -> MARK(cons(0, filter(Y, M, M))) ACTIVE(filter(cons(X, Y), 0, M)) -> CONS(0, filter(Y, M, M)) ACTIVE(filter(cons(X, Y), 0, M)) -> FILTER(Y, M, M) ACTIVE(filter(cons(X, Y), s(N), M)) -> MARK(cons(X, filter(Y, N, M))) ACTIVE(filter(cons(X, Y), s(N), M)) -> CONS(X, filter(Y, N, M)) ACTIVE(filter(cons(X, Y), s(N), M)) -> FILTER(Y, N, M) ACTIVE(sieve(cons(0, Y))) -> MARK(cons(0, sieve(Y))) ACTIVE(sieve(cons(0, Y))) -> CONS(0, sieve(Y)) ACTIVE(sieve(cons(0, Y))) -> SIEVE(Y) ACTIVE(sieve(cons(s(N), Y))) -> MARK(cons(s(N), sieve(filter(Y, N, N)))) ACTIVE(sieve(cons(s(N), Y))) -> CONS(s(N), sieve(filter(Y, N, N))) ACTIVE(sieve(cons(s(N), Y))) -> SIEVE(filter(Y, N, N)) ACTIVE(sieve(cons(s(N), Y))) -> FILTER(Y, N, N) ACTIVE(nats(N)) -> MARK(cons(N, nats(s(N)))) ACTIVE(nats(N)) -> CONS(N, nats(s(N))) ACTIVE(nats(N)) -> NATS(s(N)) ACTIVE(nats(N)) -> S(N) ACTIVE(zprimes) -> MARK(sieve(nats(s(s(0))))) ACTIVE(zprimes) -> SIEVE(nats(s(s(0)))) ACTIVE(zprimes) -> NATS(s(s(0))) ACTIVE(zprimes) -> S(s(0)) ACTIVE(zprimes) -> S(0) MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3))) MARK(filter(X1, X2, X3)) -> FILTER(mark(X1), mark(X2), mark(X3)) MARK(filter(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2, X3)) -> MARK(X2) MARK(filter(X1, X2, X3)) -> MARK(X3) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) MARK(cons(X1, X2)) -> CONS(mark(X1), X2) MARK(cons(X1, X2)) -> MARK(X1) MARK(0) -> ACTIVE(0) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> S(mark(X)) MARK(s(X)) -> MARK(X) MARK(sieve(X)) -> ACTIVE(sieve(mark(X))) MARK(sieve(X)) -> SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) MARK(nats(X)) -> ACTIVE(nats(mark(X))) MARK(nats(X)) -> NATS(mark(X)) MARK(nats(X)) -> MARK(X) MARK(zprimes) -> ACTIVE(zprimes) FILTER(mark(X1), X2, X3) -> FILTER(X1, X2, X3) FILTER(X1, mark(X2), X3) -> FILTER(X1, X2, X3) FILTER(X1, X2, mark(X3)) -> FILTER(X1, X2, X3) FILTER(active(X1), X2, X3) -> FILTER(X1, X2, X3) FILTER(X1, active(X2), X3) -> FILTER(X1, X2, X3) FILTER(X1, X2, active(X3)) -> FILTER(X1, X2, X3) CONS(mark(X1), X2) -> CONS(X1, X2) CONS(X1, mark(X2)) -> CONS(X1, X2) CONS(active(X1), X2) -> CONS(X1, X2) CONS(X1, active(X2)) -> CONS(X1, X2) S(mark(X)) -> S(X) S(active(X)) -> S(X) SIEVE(mark(X)) -> SIEVE(X) SIEVE(active(X)) -> SIEVE(X) NATS(mark(X)) -> NATS(X) NATS(active(X)) -> NATS(X) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(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 6 SCCs with 22 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: NATS(active(X)) -> NATS(X) NATS(mark(X)) -> NATS(X) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (6) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: NATS(active(X)) -> NATS(X) NATS(mark(X)) -> NATS(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *NATS(active(X)) -> NATS(X) The graph contains the following edges 1 > 1 *NATS(mark(X)) -> NATS(X) The graph contains the following edges 1 > 1 ---------------------------------------- (9) YES ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: SIEVE(active(X)) -> SIEVE(X) SIEVE(mark(X)) -> SIEVE(X) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) 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. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: SIEVE(active(X)) -> SIEVE(X) SIEVE(mark(X)) -> SIEVE(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) 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: *SIEVE(active(X)) -> SIEVE(X) The graph contains the following edges 1 > 1 *SIEVE(mark(X)) -> SIEVE(X) The graph contains the following edges 1 > 1 ---------------------------------------- (14) YES ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: S(active(X)) -> S(X) S(mark(X)) -> S(X) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(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: S(active(X)) -> S(X) S(mark(X)) -> S(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: *S(active(X)) -> S(X) The graph contains the following edges 1 > 1 *S(mark(X)) -> S(X) The graph contains the following edges 1 > 1 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: CONS(X1, mark(X2)) -> CONS(X1, X2) CONS(mark(X1), X2) -> CONS(X1, X2) CONS(active(X1), X2) -> CONS(X1, X2) CONS(X1, active(X2)) -> CONS(X1, X2) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: CONS(X1, mark(X2)) -> CONS(X1, X2) CONS(mark(X1), X2) -> CONS(X1, X2) CONS(active(X1), X2) -> CONS(X1, X2) CONS(X1, active(X2)) -> CONS(X1, X2) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) 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: *CONS(X1, mark(X2)) -> CONS(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 *CONS(mark(X1), X2) -> CONS(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *CONS(active(X1), X2) -> CONS(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *CONS(X1, active(X2)) -> CONS(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (24) YES ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: FILTER(X1, mark(X2), X3) -> FILTER(X1, X2, X3) FILTER(mark(X1), X2, X3) -> FILTER(X1, X2, X3) FILTER(X1, X2, mark(X3)) -> FILTER(X1, X2, X3) FILTER(active(X1), X2, X3) -> FILTER(X1, X2, X3) FILTER(X1, active(X2), X3) -> FILTER(X1, X2, X3) FILTER(X1, X2, active(X3)) -> FILTER(X1, X2, X3) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) 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. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: FILTER(X1, mark(X2), X3) -> FILTER(X1, X2, X3) FILTER(mark(X1), X2, X3) -> FILTER(X1, X2, X3) FILTER(X1, X2, mark(X3)) -> FILTER(X1, X2, X3) FILTER(active(X1), X2, X3) -> FILTER(X1, X2, X3) FILTER(X1, active(X2), X3) -> FILTER(X1, X2, X3) FILTER(X1, X2, active(X3)) -> FILTER(X1, X2, X3) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) 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: *FILTER(X1, mark(X2), X3) -> FILTER(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 *FILTER(mark(X1), X2, X3) -> FILTER(X1, X2, X3) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 *FILTER(X1, X2, mark(X3)) -> FILTER(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 *FILTER(active(X1), X2, X3) -> FILTER(X1, X2, X3) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 *FILTER(X1, active(X2), X3) -> FILTER(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 *FILTER(X1, X2, active(X3)) -> FILTER(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 ---------------------------------------- (29) YES ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3))) ACTIVE(filter(cons(X, Y), 0, M)) -> MARK(cons(0, filter(Y, M, M))) MARK(filter(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2, X3)) -> MARK(X2) MARK(filter(X1, X2, X3)) -> MARK(X3) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) ACTIVE(filter(cons(X, Y), s(N), M)) -> MARK(cons(X, filter(Y, N, M))) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> ACTIVE(s(mark(X))) ACTIVE(sieve(cons(0, Y))) -> MARK(cons(0, sieve(Y))) MARK(s(X)) -> MARK(X) MARK(sieve(X)) -> ACTIVE(sieve(mark(X))) ACTIVE(sieve(cons(s(N), Y))) -> MARK(cons(s(N), sieve(filter(Y, N, N)))) MARK(sieve(X)) -> MARK(X) MARK(nats(X)) -> ACTIVE(nats(mark(X))) ACTIVE(nats(N)) -> MARK(cons(N, nats(s(N)))) MARK(nats(X)) -> MARK(X) MARK(zprimes) -> ACTIVE(zprimes) ACTIVE(zprimes) -> MARK(sieve(nats(s(s(0))))) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) MARK(s(X)) -> ACTIVE(s(mark(X))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVE(x_1)) = x_1 POL(MARK(x_1)) = 1 POL(active(x_1)) = 0 POL(cons(x_1, x_2)) = 0 POL(filter(x_1, x_2, x_3)) = 1 POL(mark(x_1)) = 0 POL(nats(x_1)) = 1 POL(s(x_1)) = 0 POL(sieve(x_1)) = 1 POL(zprimes) = 1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(X1, mark(X2)) -> cons(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(active(X)) -> s(X) s(mark(X)) -> s(X) sieve(active(X)) -> sieve(X) sieve(mark(X)) -> sieve(X) nats(active(X)) -> nats(X) nats(mark(X)) -> nats(X) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3))) ACTIVE(filter(cons(X, Y), 0, M)) -> MARK(cons(0, filter(Y, M, M))) MARK(filter(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2, X3)) -> MARK(X2) MARK(filter(X1, X2, X3)) -> MARK(X3) ACTIVE(filter(cons(X, Y), s(N), M)) -> MARK(cons(X, filter(Y, N, M))) MARK(cons(X1, X2)) -> MARK(X1) ACTIVE(sieve(cons(0, Y))) -> MARK(cons(0, sieve(Y))) MARK(s(X)) -> MARK(X) MARK(sieve(X)) -> ACTIVE(sieve(mark(X))) ACTIVE(sieve(cons(s(N), Y))) -> MARK(cons(s(N), sieve(filter(Y, N, N)))) MARK(sieve(X)) -> MARK(X) MARK(nats(X)) -> ACTIVE(nats(mark(X))) ACTIVE(nats(N)) -> MARK(cons(N, nats(s(N)))) MARK(nats(X)) -> MARK(X) MARK(zprimes) -> ACTIVE(zprimes) ACTIVE(zprimes) -> MARK(sieve(nats(s(s(0))))) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(zprimes) -> MARK(sieve(nats(s(s(0))))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVE(x_1)) = x_1 POL(MARK(x_1)) = x_1 POL(active(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 POL(filter(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(mark(x_1)) = x_1 POL(nats(x_1)) = x_1 POL(s(x_1)) = x_1 POL(sieve(x_1)) = x_1 POL(zprimes) = 1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) mark(s(X)) -> active(s(mark(X))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) mark(sieve(X)) -> active(sieve(mark(X))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) mark(nats(X)) -> active(nats(mark(X))) active(nats(N)) -> mark(cons(N, nats(s(N)))) mark(zprimes) -> active(zprimes) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(0) -> active(0) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(X1, mark(X2)) -> cons(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) sieve(active(X)) -> sieve(X) sieve(mark(X)) -> sieve(X) s(active(X)) -> s(X) s(mark(X)) -> s(X) nats(active(X)) -> nats(X) nats(mark(X)) -> nats(X) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3))) ACTIVE(filter(cons(X, Y), 0, M)) -> MARK(cons(0, filter(Y, M, M))) MARK(filter(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2, X3)) -> MARK(X2) MARK(filter(X1, X2, X3)) -> MARK(X3) ACTIVE(filter(cons(X, Y), s(N), M)) -> MARK(cons(X, filter(Y, N, M))) MARK(cons(X1, X2)) -> MARK(X1) ACTIVE(sieve(cons(0, Y))) -> MARK(cons(0, sieve(Y))) MARK(s(X)) -> MARK(X) MARK(sieve(X)) -> ACTIVE(sieve(mark(X))) ACTIVE(sieve(cons(s(N), Y))) -> MARK(cons(s(N), sieve(filter(Y, N, N)))) MARK(sieve(X)) -> MARK(X) MARK(nats(X)) -> ACTIVE(nats(mark(X))) ACTIVE(nats(N)) -> MARK(cons(N, nats(s(N)))) MARK(nats(X)) -> MARK(X) MARK(zprimes) -> ACTIVE(zprimes) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(filter(cons(X, Y), 0, M)) -> MARK(cons(0, filter(Y, M, M))) MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3))) ACTIVE(filter(cons(X, Y), s(N), M)) -> MARK(cons(X, filter(Y, N, M))) MARK(filter(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2, X3)) -> MARK(X2) MARK(filter(X1, X2, X3)) -> MARK(X3) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(sieve(X)) -> ACTIVE(sieve(mark(X))) ACTIVE(sieve(cons(0, Y))) -> MARK(cons(0, sieve(Y))) MARK(sieve(X)) -> MARK(X) MARK(nats(X)) -> ACTIVE(nats(mark(X))) ACTIVE(sieve(cons(s(N), Y))) -> MARK(cons(s(N), sieve(filter(Y, N, N)))) MARK(nats(X)) -> MARK(X) ACTIVE(nats(N)) -> MARK(cons(N, nats(s(N)))) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(filter(cons(X, Y), 0, M)) -> MARK(cons(0, filter(Y, M, M))) ACTIVE(filter(cons(X, Y), s(N), M)) -> MARK(cons(X, filter(Y, N, M))) MARK(filter(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2, X3)) -> MARK(X2) MARK(filter(X1, X2, X3)) -> MARK(X3) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVE(x_1)) = x_1 POL(MARK(x_1)) = x_1 POL(active(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 POL(filter(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(mark(x_1)) = x_1 POL(nats(x_1)) = x_1 POL(s(x_1)) = x_1 POL(sieve(x_1)) = x_1 POL(zprimes) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(X1, mark(X2)) -> cons(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) mark(s(X)) -> active(s(mark(X))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) mark(sieve(X)) -> active(sieve(mark(X))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) mark(nats(X)) -> active(nats(mark(X))) active(nats(N)) -> mark(cons(N, nats(s(N)))) mark(zprimes) -> active(zprimes) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(0) -> active(0) sieve(active(X)) -> sieve(X) sieve(mark(X)) -> sieve(X) nats(active(X)) -> nats(X) nats(mark(X)) -> nats(X) s(active(X)) -> s(X) s(mark(X)) -> s(X) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3))) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(sieve(X)) -> ACTIVE(sieve(mark(X))) ACTIVE(sieve(cons(0, Y))) -> MARK(cons(0, sieve(Y))) MARK(sieve(X)) -> MARK(X) MARK(nats(X)) -> ACTIVE(nats(mark(X))) ACTIVE(sieve(cons(s(N), Y))) -> MARK(cons(s(N), sieve(filter(Y, N, N)))) MARK(nats(X)) -> MARK(X) ACTIVE(nats(N)) -> MARK(cons(N, nats(s(N)))) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(nats(X)) -> MARK(X) ACTIVE(nats(N)) -> MARK(cons(N, nats(s(N)))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MARK(x1) = x1 filter(x1, x2, x3) = x1 ACTIVE(x1) = x1 mark(x1) = x1 cons(x1, x2) = x1 s(x1) = x1 sieve(x1) = x1 0 = 0 nats(x1) = nats(x1) active(x1) = x1 zprimes = zprimes Knuth-Bendix order [KBO] with precedence:trivial and weight map: nats_1=1 0=1 zprimes=3 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) mark(s(X)) -> active(s(mark(X))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) mark(sieve(X)) -> active(sieve(mark(X))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) mark(nats(X)) -> active(nats(mark(X))) active(nats(N)) -> mark(cons(N, nats(s(N)))) mark(zprimes) -> active(zprimes) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(0) -> active(0) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) sieve(active(X)) -> sieve(X) sieve(mark(X)) -> sieve(X) cons(X1, mark(X2)) -> cons(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) nats(active(X)) -> nats(X) nats(mark(X)) -> nats(X) s(active(X)) -> s(X) s(mark(X)) -> s(X) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3))) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(sieve(X)) -> ACTIVE(sieve(mark(X))) ACTIVE(sieve(cons(0, Y))) -> MARK(cons(0, sieve(Y))) MARK(sieve(X)) -> MARK(X) MARK(nats(X)) -> ACTIVE(nats(mark(X))) ACTIVE(sieve(cons(s(N), Y))) -> MARK(cons(s(N), sieve(filter(Y, N, N)))) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(sieve(cons(0, Y))) -> MARK(cons(0, sieve(Y))) MARK(sieve(X)) -> MARK(X) ACTIVE(sieve(cons(s(N), Y))) -> MARK(cons(s(N), sieve(filter(Y, N, N)))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MARK(x1) = x1 filter(x1, x2, x3) = x1 ACTIVE(x1) = x1 mark(x1) = x1 cons(x1, x2) = x1 s(x1) = x1 sieve(x1) = sieve(x1) 0 = 0 nats(x1) = x1 active(x1) = x1 zprimes = zprimes Knuth-Bendix order [KBO] with precedence:trivial and weight map: 0=1 zprimes=3 sieve_1=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) mark(s(X)) -> active(s(mark(X))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) mark(sieve(X)) -> active(sieve(mark(X))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) mark(nats(X)) -> active(nats(mark(X))) active(nats(N)) -> mark(cons(N, nats(s(N)))) mark(zprimes) -> active(zprimes) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(0) -> active(0) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) sieve(active(X)) -> sieve(X) sieve(mark(X)) -> sieve(X) cons(X1, mark(X2)) -> cons(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) nats(active(X)) -> nats(X) nats(mark(X)) -> nats(X) s(active(X)) -> s(X) s(mark(X)) -> s(X) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3))) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(sieve(X)) -> ACTIVE(sieve(mark(X))) MARK(nats(X)) -> ACTIVE(nats(mark(X))) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) The TRS R consists of the following rules: active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M))) active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M))) active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y))) active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N)))) active(nats(N)) -> mark(cons(N, nats(s(N)))) active(zprimes) -> mark(sieve(nats(s(s(0))))) mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(sieve(X)) -> active(sieve(mark(X))) mark(nats(X)) -> active(nats(mark(X))) mark(zprimes) -> active(zprimes) filter(mark(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, mark(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, mark(X3)) -> filter(X1, X2, X3) filter(active(X1), X2, X3) -> filter(X1, X2, X3) filter(X1, active(X2), X3) -> filter(X1, X2, X3) filter(X1, X2, active(X3)) -> filter(X1, X2, X3) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) sieve(mark(X)) -> sieve(X) sieve(active(X)) -> sieve(X) nats(mark(X)) -> nats(X) nats(active(X)) -> nats(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) 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. ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) 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: *MARK(s(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(cons(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 ---------------------------------------- (48) YES