/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 Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 24 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) QDPOrderProof [EQUIVALENT, 227 ms] (6) QDP (7) QDPOrderProof [EQUIVALENT, 246 ms] (8) QDP (9) DependencyGraphProof [EQUIVALENT, 0 ms] (10) QDP (11) QDPOrderProof [EQUIVALENT, 213 ms] (12) QDP (13) DependencyGraphProof [EQUIVALENT, 0 ms] (14) QDP (15) QDPOrderProof [EQUIVALENT, 196 ms] (16) QDP (17) QDPOrderProof [EQUIVALENT, 46 ms] (18) QDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) QDP (21) QDPOrderProof [EQUIVALENT, 219 ms] (22) QDP (23) QDPOrderProof [EQUIVALENT, 215 ms] (24) QDP (25) DependencyGraphProof [EQUIVALENT, 0 ms] (26) QDP (27) QDPOrderProof [EQUIVALENT, 211 ms] (28) QDP (29) DependencyGraphProof [EQUIVALENT, 0 ms] (30) QDP (31) QDPOrderProof [EQUIVALENT, 221 ms] (32) QDP (33) QDPOrderProof [EQUIVALENT, 199 ms] (34) QDP (35) QDPOrderProof [EQUIVALENT, 158 ms] (36) QDP (37) QDPOrderProof [EQUIVALENT, 76 ms] (38) QDP (39) DependencyGraphProof [EQUIVALENT, 0 ms] (40) QDP (41) QDPSizeChangeProof [EQUIVALENT, 0 ms] (42) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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: A__PRIMES -> A__SIEVE(a__from(s(s(0)))) A__PRIMES -> A__FROM(s(s(0))) A__FROM(X) -> MARK(X) A__HEAD(cons(X, Y)) -> MARK(X) A__TAIL(cons(X, Y)) -> MARK(Y) A__IF(true, X, Y) -> MARK(X) A__IF(false, X, Y) -> MARK(Y) A__FILTER(s(s(X)), cons(Y, Z)) -> A__IF(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__SIEVE(cons(X, Y)) -> MARK(X) MARK(primes) -> A__PRIMES MARK(sieve(X)) -> A__SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) MARK(from(X)) -> MARK(X) MARK(head(X)) -> A__HEAD(mark(X)) MARK(head(X)) -> MARK(X) MARK(tail(X)) -> A__TAIL(mark(X)) MARK(tail(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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 1 SCC with 1 less node. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: A__SIEVE(cons(X, Y)) -> MARK(X) MARK(primes) -> A__PRIMES A__PRIMES -> A__SIEVE(a__from(s(s(0)))) A__PRIMES -> A__FROM(s(s(0))) A__FROM(X) -> MARK(X) MARK(sieve(X)) -> A__SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) MARK(from(X)) -> MARK(X) MARK(head(X)) -> A__HEAD(mark(X)) A__HEAD(cons(X, Y)) -> MARK(X) MARK(head(X)) -> MARK(X) MARK(tail(X)) -> A__TAIL(mark(X)) A__TAIL(cons(X, Y)) -> MARK(Y) MARK(tail(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(head(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(A__SIEVE(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(primes) = [[0A]] >>> <<< POL(A__PRIMES) = [[0A]] >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(0) = [[0A]] >>> <<< POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(head(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(A__HEAD(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__TAIL(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(a__primes) = [[0A]] >>> <<< POL(a__sieve(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: a__from(X) -> cons(mark(X), from(s(X))) a__from(X) -> from(X) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: A__SIEVE(cons(X, Y)) -> MARK(X) MARK(primes) -> A__PRIMES A__PRIMES -> A__SIEVE(a__from(s(s(0)))) A__PRIMES -> A__FROM(s(s(0))) A__FROM(X) -> MARK(X) MARK(sieve(X)) -> A__SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) MARK(from(X)) -> MARK(X) MARK(head(X)) -> A__HEAD(mark(X)) A__HEAD(cons(X, Y)) -> MARK(X) MARK(tail(X)) -> A__TAIL(mark(X)) A__TAIL(cons(X, Y)) -> MARK(Y) MARK(tail(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(head(X)) -> A__HEAD(mark(X)) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(A__SIEVE(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(primes) = [[0A]] >>> <<< POL(A__PRIMES) = [[1A]] >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(0) = [[0A]] >>> <<< POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(sieve(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(head(x_1)) = [[-I]] + [[2A]] * x_1 >>> <<< POL(A__HEAD(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(tail(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(A__TAIL(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[1A]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(a__primes) = [[0A]] >>> <<< POL(a__sieve(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[-I]] + [[2A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: a__from(X) -> cons(mark(X), from(s(X))) a__from(X) -> from(X) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: A__SIEVE(cons(X, Y)) -> MARK(X) MARK(primes) -> A__PRIMES A__PRIMES -> A__SIEVE(a__from(s(s(0)))) A__PRIMES -> A__FROM(s(s(0))) A__FROM(X) -> MARK(X) MARK(sieve(X)) -> A__SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) MARK(from(X)) -> MARK(X) A__HEAD(cons(X, Y)) -> MARK(X) MARK(tail(X)) -> A__TAIL(mark(X)) A__TAIL(cons(X, Y)) -> MARK(Y) MARK(tail(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(primes) -> A__PRIMES A__PRIMES -> A__SIEVE(a__from(s(s(0)))) A__SIEVE(cons(X, Y)) -> MARK(X) MARK(sieve(X)) -> A__SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(from(X)) -> MARK(X) MARK(tail(X)) -> A__TAIL(mark(X)) A__TAIL(cons(X, Y)) -> MARK(Y) MARK(tail(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) A__PRIMES -> A__FROM(s(s(0))) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(primes) -> A__PRIMES The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(primes) = [[1A]] >>> <<< POL(A__PRIMES) = [[0A]] >>> <<< POL(A__SIEVE(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(0) = [[0A]] >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(A__TAIL(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(a__primes) = [[1A]] >>> <<< POL(a__sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(head(x_1)) = [[-I]] + [[1A]] * x_1 >>> <<< POL(a__head(x_1)) = [[-I]] + [[1A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: a__from(X) -> cons(mark(X), from(s(X))) a__from(X) -> from(X) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: A__PRIMES -> A__SIEVE(a__from(s(s(0)))) A__SIEVE(cons(X, Y)) -> MARK(X) MARK(sieve(X)) -> A__SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(from(X)) -> MARK(X) MARK(tail(X)) -> A__TAIL(mark(X)) A__TAIL(cons(X, Y)) -> MARK(Y) MARK(tail(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) A__PRIMES -> A__FROM(s(s(0))) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(sieve(X)) -> A__SIEVE(mark(X)) A__SIEVE(cons(X, Y)) -> MARK(X) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(from(X)) -> MARK(X) MARK(tail(X)) -> A__TAIL(mark(X)) A__TAIL(cons(X, Y)) -> MARK(Y) MARK(tail(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(tail(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__SIEVE(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[3A]] + [[3A]] * x_1 >>> <<< POL(A__TAIL(x_1)) = [[3A]] + [[0A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(primes) = [[0A]] >>> <<< POL(a__primes) = [[0A]] >>> <<< POL(a__sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(head(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[3A]] + [[3A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> from(X) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(sieve(X)) -> A__SIEVE(mark(X)) A__SIEVE(cons(X, Y)) -> MARK(X) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(from(X)) -> MARK(X) MARK(tail(X)) -> A__TAIL(mark(X)) A__TAIL(cons(X, Y)) -> MARK(Y) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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. MARK(tail(X)) -> A__TAIL(mark(X)) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__SIEVE(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(A__TAIL(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(divides(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(primes) = [[0A]] >>> <<< POL(a__primes) = [[0A]] >>> <<< POL(a__sieve(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(head(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> from(X) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(sieve(X)) -> A__SIEVE(mark(X)) A__SIEVE(cons(X, Y)) -> MARK(X) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(from(X)) -> MARK(X) A__TAIL(cons(X, Y)) -> MARK(Y) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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 1 less node. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: A__SIEVE(cons(X, Y)) -> MARK(X) MARK(sieve(X)) -> A__SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(from(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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. MARK(from(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(A__SIEVE(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(primes) = [[1A]] >>> <<< POL(a__primes) = [[1A]] >>> <<< POL(a__sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(head(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> from(X) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: A__SIEVE(cons(X, Y)) -> MARK(X) MARK(sieve(X)) -> A__SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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. MARK(from(X)) -> A__FROM(mark(X)) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(A__SIEVE(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(false) = [[1A]] >>> <<< POL(primes) = [[2A]] >>> <<< POL(a__primes) = [[2A]] >>> <<< POL(a__sieve(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(head(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> from(X) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: A__SIEVE(cons(X, Y)) -> MARK(X) MARK(sieve(X)) -> A__SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) A__FROM(X) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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: MARK(sieve(X)) -> A__SIEVE(mark(X)) A__SIEVE(cons(X, Y)) -> MARK(X) MARK(sieve(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__SIEVE(cons(X, Y)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(sieve(x_1)) = [[3A]] + [[0A]] * x_1 >>> <<< POL(A__SIEVE(x_1)) = [[4A]] + [[1A]] * x_1 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[2A]] + [[-I]] * x_1 + [[1A]] * x_2 + [[1A]] * x_3 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[3A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[2A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(primes) = [[3A]] >>> <<< POL(a__primes) = [[3A]] >>> <<< POL(a__sieve(x_1)) = [[3A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(head(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[3A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> from(X) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(sieve(X)) -> A__SIEVE(mark(X)) MARK(sieve(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(sieve(X)) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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(sieve(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(true) = [[0A]] >>> <<< POL(sieve(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(primes) = [[2A]] >>> <<< POL(a__primes) = [[2A]] >>> <<< POL(a__sieve(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(head(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> from(X) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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. MARK(cons(X1, X2)) -> MARK(X1) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[2A]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(mark(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[3A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(primes) = [[3A]] >>> <<< POL(a__primes) = [[3A]] >>> <<< POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__sieve(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[3A]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[3A]] + [[1A]] * x_1 >>> <<< POL(head(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[2A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> from(X) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(divides(X1, X2)) -> MARK(X1) MARK(divides(X1, X2)) -> MARK(X2) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(divides(X1, X2)) -> MARK(X2) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[1A]] + [[0A]] * x_1 + [[1A]] * x_2 + [[1A]] * x_3 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[0A]] + [[1A]] * x_1 + [[1A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(divides(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(primes) = [[1A]] >>> <<< POL(a__primes) = [[1A]] >>> <<< POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(head(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> from(X) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(divides(X1, X2)) -> MARK(X1) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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. A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) MARK(filter(X1, X2)) -> MARK(X1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(A__IF(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(true) = [[0A]] >>> <<< POL(filter(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__FILTER(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[-I]] * x_2 >>> <<< POL(false) = [[0A]] >>> <<< POL(primes) = [[1A]] >>> <<< POL(a__primes) = [[1A]] >>> <<< POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__sieve(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(head(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__head(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 >>> <<< POL(a__filter(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) a__head(cons(X, Y)) -> mark(X) mark(tail(X)) -> a__tail(mark(X)) a__tail(cons(X, Y)) -> mark(Y) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__primes -> primes a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> from(X) a__sieve(X) -> sieve(X) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(divides(X1, X2)) -> MARK(X1) A__IF(false, X, Y) -> MARK(Y) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) 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: A__IF(true, X, Y) -> MARK(X) MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) A__IF(false, X, Y) -> MARK(Y) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(filter(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(divides(X1, X2)) -> MARK(X1) The TRS R consists of the following rules: a__primes -> a__sieve(a__from(s(s(0)))) a__from(X) -> cons(mark(X), from(s(X))) a__head(cons(X, Y)) -> mark(X) a__tail(cons(X, Y)) -> mark(Y) a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) mark(primes) -> a__primes mark(sieve(X)) -> a__sieve(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(head(X)) -> a__head(mark(X)) mark(tail(X)) -> a__tail(mark(X)) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(true) -> true mark(false) -> false mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) a__primes -> primes a__sieve(X) -> sieve(X) a__from(X) -> from(X) a__head(X) -> head(X) a__tail(X) -> tail(X) a__if(X1, X2, X3) -> if(X1, X2, X3) a__filter(X1, X2) -> filter(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) 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(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) The graph contains the following edges 1 > 2, 1 > 3 *MARK(if(X1, X2, X3)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(filter(X1, X2)) -> MARK(X2) The graph contains the following edges 1 > 1 *MARK(s(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(divides(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *A__IF(true, X, Y) -> MARK(X) The graph contains the following edges 2 >= 1 *A__IF(false, X, Y) -> MARK(Y) The graph contains the following edges 3 >= 1 ---------------------------------------- (42) YES