90.51/25.36 YES 90.64/25.39 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 90.64/25.39 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 90.64/25.39 90.64/25.39 90.64/25.39 Termination w.r.t. Q of the given QTRS could be proven: 90.64/25.39 90.64/25.39 (0) QTRS 90.64/25.39 (1) DependencyPairsProof [EQUIVALENT, 60 ms] 90.64/25.39 (2) QDP 90.64/25.39 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 90.64/25.39 (4) QDP 90.64/25.39 (5) QDPOrderProof [EQUIVALENT, 292 ms] 90.64/25.39 (6) QDP 90.64/25.39 (7) QDPOrderProof [EQUIVALENT, 280 ms] 90.64/25.39 (8) QDP 90.64/25.39 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 90.64/25.39 (10) QDP 90.64/25.39 (11) QDPOrderProof [EQUIVALENT, 224 ms] 90.64/25.39 (12) QDP 90.64/25.39 (13) DependencyGraphProof [EQUIVALENT, 0 ms] 90.64/25.39 (14) QDP 90.64/25.39 (15) QDPOrderProof [EQUIVALENT, 175 ms] 90.64/25.39 (16) QDP 90.64/25.39 (17) QDPOrderProof [EQUIVALENT, 214 ms] 90.64/25.39 (18) QDP 90.64/25.39 (19) DependencyGraphProof [EQUIVALENT, 0 ms] 90.64/25.39 (20) QDP 90.64/25.39 (21) QDPOrderProof [EQUIVALENT, 207 ms] 90.64/25.39 (22) QDP 90.64/25.39 (23) QDPOrderProof [EQUIVALENT, 188 ms] 90.64/25.39 (24) QDP 90.64/25.39 (25) DependencyGraphProof [EQUIVALENT, 0 ms] 90.64/25.39 (26) QDP 90.64/25.39 (27) QDPOrderProof [EQUIVALENT, 153 ms] 90.64/25.39 (28) QDP 90.64/25.39 (29) DependencyGraphProof [EQUIVALENT, 0 ms] 90.64/25.39 (30) QDP 90.64/25.39 (31) QDPOrderProof [EQUIVALENT, 151 ms] 90.64/25.39 (32) QDP 90.64/25.39 (33) QDPOrderProof [EQUIVALENT, 220 ms] 90.64/25.39 (34) QDP 90.64/25.39 (35) QDPOrderProof [EQUIVALENT, 156 ms] 90.64/25.39 (36) QDP 90.64/25.39 (37) QDPOrderProof [EQUIVALENT, 129 ms] 90.64/25.39 (38) QDP 90.64/25.39 (39) DependencyGraphProof [EQUIVALENT, 0 ms] 90.64/25.39 (40) QDP 90.64/25.39 (41) QDPSizeChangeProof [EQUIVALENT, 0 ms] 90.64/25.39 (42) YES 90.64/25.39 90.64/25.39 90.64/25.39 ---------------------------------------- 90.64/25.39 90.64/25.39 (0) 90.64/25.39 Obligation: 90.64/25.39 Q restricted rewrite system: 90.64/25.39 The TRS R consists of the following rules: 90.64/25.39 90.64/25.39 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.39 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.39 a__head(cons(X, Y)) -> mark(X) 90.64/25.39 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.39 a__if(true, X, Y) -> mark(X) 90.64/25.39 a__if(false, X, Y) -> mark(Y) 90.64/25.39 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)))) 90.64/25.39 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.39 mark(primes) -> a__primes 90.64/25.39 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.39 mark(from(X)) -> a__from(mark(X)) 90.64/25.39 mark(head(X)) -> a__head(mark(X)) 90.64/25.39 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.39 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.39 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.39 mark(s(X)) -> s(mark(X)) 90.64/25.39 mark(0) -> 0 90.64/25.39 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.39 mark(true) -> true 90.64/25.39 mark(false) -> false 90.64/25.39 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.39 a__primes -> primes 90.64/25.39 a__sieve(X) -> sieve(X) 90.64/25.39 a__from(X) -> from(X) 90.64/25.39 a__head(X) -> head(X) 90.64/25.39 a__tail(X) -> tail(X) 90.64/25.39 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.39 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.39 90.64/25.39 The set Q consists of the following terms: 90.64/25.39 90.64/25.39 a__primes 90.64/25.39 a__from(x0) 90.64/25.39 mark(primes) 90.64/25.39 mark(sieve(x0)) 90.64/25.39 mark(from(x0)) 90.64/25.39 mark(head(x0)) 90.64/25.39 mark(tail(x0)) 90.64/25.39 mark(if(x0, x1, x2)) 90.64/25.39 mark(filter(x0, x1)) 90.64/25.39 mark(s(x0)) 90.64/25.39 mark(0) 90.64/25.39 mark(cons(x0, x1)) 90.64/25.39 mark(true) 90.64/25.39 mark(false) 90.64/25.39 mark(divides(x0, x1)) 90.64/25.39 a__sieve(x0) 90.64/25.39 a__head(x0) 90.64/25.39 a__tail(x0) 90.64/25.39 a__if(x0, x1, x2) 90.64/25.39 a__filter(x0, x1) 90.64/25.39 90.64/25.39 90.64/25.39 ---------------------------------------- 90.64/25.39 90.64/25.39 (1) DependencyPairsProof (EQUIVALENT) 90.64/25.39 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 90.64/25.39 ---------------------------------------- 90.64/25.39 90.64/25.39 (2) 90.64/25.39 Obligation: 90.64/25.39 Q DP problem: 90.64/25.39 The TRS P consists of the following rules: 90.64/25.39 90.64/25.39 A__PRIMES -> A__SIEVE(a__from(s(s(0)))) 90.64/25.39 A__PRIMES -> A__FROM(s(s(0))) 90.64/25.39 A__FROM(X) -> MARK(X) 90.64/25.39 A__HEAD(cons(X, Y)) -> MARK(X) 90.64/25.39 A__TAIL(cons(X, Y)) -> MARK(Y) 90.64/25.39 A__IF(true, X, Y) -> MARK(X) 90.64/25.39 A__IF(false, X, Y) -> MARK(Y) 90.64/25.39 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)))) 90.64/25.39 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.39 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.39 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.39 MARK(primes) -> A__PRIMES 90.64/25.39 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.39 MARK(sieve(X)) -> MARK(X) 90.64/25.39 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.39 MARK(from(X)) -> MARK(X) 90.64/25.39 MARK(head(X)) -> A__HEAD(mark(X)) 90.64/25.39 MARK(head(X)) -> MARK(X) 90.64/25.39 MARK(tail(X)) -> A__TAIL(mark(X)) 90.64/25.39 MARK(tail(X)) -> MARK(X) 90.64/25.39 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.39 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.39 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.39 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.39 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.39 MARK(s(X)) -> MARK(X) 90.64/25.39 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.39 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.39 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.39 90.64/25.39 The TRS R consists of the following rules: 90.64/25.39 90.64/25.39 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.39 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.39 a__head(cons(X, Y)) -> mark(X) 90.64/25.39 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.39 a__if(true, X, Y) -> mark(X) 90.64/25.39 a__if(false, X, Y) -> mark(Y) 90.64/25.39 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)))) 90.64/25.39 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.39 mark(primes) -> a__primes 90.64/25.39 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.39 mark(from(X)) -> a__from(mark(X)) 90.64/25.39 mark(head(X)) -> a__head(mark(X)) 90.64/25.39 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.39 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.39 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.39 mark(s(X)) -> s(mark(X)) 90.64/25.39 mark(0) -> 0 90.64/25.39 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.40 mark(true) -> true 90.64/25.40 mark(false) -> false 90.64/25.40 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.40 a__primes -> primes 90.64/25.40 a__sieve(X) -> sieve(X) 90.64/25.40 a__from(X) -> from(X) 90.64/25.40 a__head(X) -> head(X) 90.64/25.40 a__tail(X) -> tail(X) 90.64/25.40 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.40 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.40 90.64/25.40 The set Q consists of the following terms: 90.64/25.40 90.64/25.40 a__primes 90.64/25.40 a__from(x0) 90.64/25.40 mark(primes) 90.64/25.40 mark(sieve(x0)) 90.64/25.40 mark(from(x0)) 90.64/25.40 mark(head(x0)) 90.64/25.40 mark(tail(x0)) 90.64/25.40 mark(if(x0, x1, x2)) 90.64/25.40 mark(filter(x0, x1)) 90.64/25.40 mark(s(x0)) 90.64/25.40 mark(0) 90.64/25.40 mark(cons(x0, x1)) 90.64/25.40 mark(true) 90.64/25.40 mark(false) 90.64/25.40 mark(divides(x0, x1)) 90.64/25.40 a__sieve(x0) 90.64/25.40 a__head(x0) 90.64/25.40 a__tail(x0) 90.64/25.40 a__if(x0, x1, x2) 90.64/25.40 a__filter(x0, x1) 90.64/25.40 90.64/25.40 We have to consider all minimal (P,Q,R)-chains. 90.64/25.40 ---------------------------------------- 90.64/25.40 90.64/25.40 (3) DependencyGraphProof (EQUIVALENT) 90.64/25.40 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 90.64/25.40 ---------------------------------------- 90.64/25.40 90.64/25.40 (4) 90.64/25.40 Obligation: 90.64/25.40 Q DP problem: 90.64/25.40 The TRS P consists of the following rules: 90.64/25.40 90.64/25.40 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.40 MARK(primes) -> A__PRIMES 90.64/25.40 A__PRIMES -> A__SIEVE(a__from(s(s(0)))) 90.64/25.40 A__PRIMES -> A__FROM(s(s(0))) 90.64/25.40 A__FROM(X) -> MARK(X) 90.64/25.40 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.40 MARK(sieve(X)) -> MARK(X) 90.64/25.40 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.40 MARK(from(X)) -> MARK(X) 90.64/25.40 MARK(head(X)) -> A__HEAD(mark(X)) 90.64/25.40 A__HEAD(cons(X, Y)) -> MARK(X) 90.64/25.40 MARK(head(X)) -> MARK(X) 90.64/25.40 MARK(tail(X)) -> A__TAIL(mark(X)) 90.64/25.40 A__TAIL(cons(X, Y)) -> MARK(Y) 90.64/25.40 MARK(tail(X)) -> MARK(X) 90.64/25.40 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.40 A__IF(true, X, Y) -> MARK(X) 90.64/25.40 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.40 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.40 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.40 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.40 MARK(s(X)) -> MARK(X) 90.64/25.40 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.40 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.40 A__IF(false, X, Y) -> MARK(Y) 90.64/25.40 90.64/25.40 The TRS R consists of the following rules: 90.64/25.40 90.64/25.40 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.40 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.40 a__head(cons(X, Y)) -> mark(X) 90.64/25.40 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.40 a__if(true, X, Y) -> mark(X) 90.64/25.40 a__if(false, X, Y) -> mark(Y) 90.64/25.40 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)))) 90.64/25.40 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.40 mark(primes) -> a__primes 90.64/25.40 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.40 mark(from(X)) -> a__from(mark(X)) 90.64/25.40 mark(head(X)) -> a__head(mark(X)) 90.64/25.40 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.40 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.40 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.40 mark(s(X)) -> s(mark(X)) 90.64/25.40 mark(0) -> 0 90.64/25.40 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.40 mark(true) -> true 90.64/25.40 mark(false) -> false 90.64/25.40 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.40 a__primes -> primes 90.64/25.40 a__sieve(X) -> sieve(X) 90.64/25.40 a__from(X) -> from(X) 90.64/25.40 a__head(X) -> head(X) 90.64/25.40 a__tail(X) -> tail(X) 90.64/25.40 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.40 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.40 90.64/25.40 The set Q consists of the following terms: 90.64/25.40 90.64/25.40 a__primes 90.64/25.40 a__from(x0) 90.64/25.40 mark(primes) 90.64/25.40 mark(sieve(x0)) 90.64/25.40 mark(from(x0)) 90.64/25.40 mark(head(x0)) 90.64/25.40 mark(tail(x0)) 90.64/25.40 mark(if(x0, x1, x2)) 90.64/25.40 mark(filter(x0, x1)) 90.64/25.40 mark(s(x0)) 90.64/25.40 mark(0) 90.64/25.40 mark(cons(x0, x1)) 90.64/25.40 mark(true) 90.64/25.40 mark(false) 90.64/25.40 mark(divides(x0, x1)) 90.64/25.40 a__sieve(x0) 90.64/25.40 a__head(x0) 90.64/25.40 a__tail(x0) 90.64/25.40 a__if(x0, x1, x2) 90.64/25.40 a__filter(x0, x1) 90.64/25.40 90.64/25.40 We have to consider all minimal (P,Q,R)-chains. 90.64/25.40 ---------------------------------------- 90.64/25.40 90.64/25.40 (5) QDPOrderProof (EQUIVALENT) 90.64/25.40 We use the reduction pair processor [LPAR04,JAR06]. 90.64/25.40 90.64/25.40 90.64/25.40 The following pairs can be oriented strictly and are deleted. 90.64/25.40 90.64/25.40 MARK(head(X)) -> MARK(X) 90.64/25.40 The remaining pairs can at least be oriented weakly. 90.64/25.40 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__SIEVE(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(primes) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__PRIMES) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(0) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(from(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(head(x_1)) = [[1A]] + [[1A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__HEAD(x_1)) = [[1A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(tail(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__TAIL(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__IF(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(true) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__FILTER(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(false) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__primes) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__sieve(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__head(x_1)) = [[1A]] + [[1A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__filter(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.40 >>> 90.64/25.40 90.64/25.40 90.64/25.40 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.64/25.40 90.64/25.40 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.40 a__from(X) -> from(X) 90.64/25.40 mark(primes) -> a__primes 90.64/25.40 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.40 mark(from(X)) -> a__from(mark(X)) 90.64/25.40 mark(head(X)) -> a__head(mark(X)) 90.64/25.40 a__head(cons(X, Y)) -> mark(X) 90.64/25.40 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.40 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.40 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.40 a__if(true, X, Y) -> mark(X) 90.64/25.40 a__if(false, X, Y) -> mark(Y) 90.64/25.40 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.40 mark(s(X)) -> s(mark(X)) 90.64/25.40 mark(0) -> 0 90.64/25.40 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.40 mark(true) -> true 90.64/25.40 mark(false) -> false 90.64/25.40 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.40 a__primes -> primes 90.64/25.40 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.40 a__sieve(X) -> sieve(X) 90.64/25.40 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.40 a__head(X) -> head(X) 90.64/25.40 a__tail(X) -> tail(X) 90.64/25.40 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.40 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.40 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)))) 90.64/25.40 90.64/25.40 90.64/25.40 ---------------------------------------- 90.64/25.40 90.64/25.40 (6) 90.64/25.40 Obligation: 90.64/25.40 Q DP problem: 90.64/25.40 The TRS P consists of the following rules: 90.64/25.40 90.64/25.40 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.40 MARK(primes) -> A__PRIMES 90.64/25.40 A__PRIMES -> A__SIEVE(a__from(s(s(0)))) 90.64/25.40 A__PRIMES -> A__FROM(s(s(0))) 90.64/25.40 A__FROM(X) -> MARK(X) 90.64/25.40 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.40 MARK(sieve(X)) -> MARK(X) 90.64/25.40 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.40 MARK(from(X)) -> MARK(X) 90.64/25.40 MARK(head(X)) -> A__HEAD(mark(X)) 90.64/25.40 A__HEAD(cons(X, Y)) -> MARK(X) 90.64/25.40 MARK(tail(X)) -> A__TAIL(mark(X)) 90.64/25.40 A__TAIL(cons(X, Y)) -> MARK(Y) 90.64/25.40 MARK(tail(X)) -> MARK(X) 90.64/25.40 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.40 A__IF(true, X, Y) -> MARK(X) 90.64/25.40 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.40 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.40 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.40 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.40 MARK(s(X)) -> MARK(X) 90.64/25.40 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.40 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.40 A__IF(false, X, Y) -> MARK(Y) 90.64/25.40 90.64/25.40 The TRS R consists of the following rules: 90.64/25.40 90.64/25.40 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.40 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.40 a__head(cons(X, Y)) -> mark(X) 90.64/25.40 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.40 a__if(true, X, Y) -> mark(X) 90.64/25.40 a__if(false, X, Y) -> mark(Y) 90.64/25.40 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)))) 90.64/25.40 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.40 mark(primes) -> a__primes 90.64/25.40 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.40 mark(from(X)) -> a__from(mark(X)) 90.64/25.40 mark(head(X)) -> a__head(mark(X)) 90.64/25.40 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.40 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.40 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.40 mark(s(X)) -> s(mark(X)) 90.64/25.40 mark(0) -> 0 90.64/25.40 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.40 mark(true) -> true 90.64/25.40 mark(false) -> false 90.64/25.40 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.40 a__primes -> primes 90.64/25.40 a__sieve(X) -> sieve(X) 90.64/25.40 a__from(X) -> from(X) 90.64/25.40 a__head(X) -> head(X) 90.64/25.40 a__tail(X) -> tail(X) 90.64/25.40 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.40 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.40 90.64/25.40 The set Q consists of the following terms: 90.64/25.40 90.64/25.40 a__primes 90.64/25.40 a__from(x0) 90.64/25.40 mark(primes) 90.64/25.40 mark(sieve(x0)) 90.64/25.40 mark(from(x0)) 90.64/25.40 mark(head(x0)) 90.64/25.40 mark(tail(x0)) 90.64/25.40 mark(if(x0, x1, x2)) 90.64/25.40 mark(filter(x0, x1)) 90.64/25.40 mark(s(x0)) 90.64/25.40 mark(0) 90.64/25.40 mark(cons(x0, x1)) 90.64/25.40 mark(true) 90.64/25.40 mark(false) 90.64/25.40 mark(divides(x0, x1)) 90.64/25.40 a__sieve(x0) 90.64/25.40 a__head(x0) 90.64/25.40 a__tail(x0) 90.64/25.40 a__if(x0, x1, x2) 90.64/25.40 a__filter(x0, x1) 90.64/25.40 90.64/25.40 We have to consider all minimal (P,Q,R)-chains. 90.64/25.40 ---------------------------------------- 90.64/25.40 90.64/25.40 (7) QDPOrderProof (EQUIVALENT) 90.64/25.40 We use the reduction pair processor [LPAR04,JAR06]. 90.64/25.40 90.64/25.40 90.64/25.40 The following pairs can be oriented strictly and are deleted. 90.64/25.40 90.64/25.40 MARK(head(X)) -> A__HEAD(mark(X)) 90.64/25.40 The remaining pairs can at least be oriented weakly. 90.64/25.40 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__SIEVE(x_1)) = [[1A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(cons(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(primes) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__PRIMES) = [[1A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(0) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(sieve(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(from(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(head(x_1)) = [[-I]] + [[2A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__HEAD(x_1)) = [[0A]] + [[1A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(tail(x_1)) = [[0A]] + [[1A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__TAIL(x_1)) = [[1A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__IF(x_1, x_2, x_3)) = [[1A]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(true) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__FILTER(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(false) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__primes) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__sieve(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__head(x_1)) = [[-I]] + [[2A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__tail(x_1)) = [[0A]] + [[1A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.40 >>> 90.64/25.40 90.64/25.40 90.64/25.40 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.64/25.40 90.64/25.40 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.40 a__from(X) -> from(X) 90.64/25.40 mark(primes) -> a__primes 90.64/25.40 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.40 mark(from(X)) -> a__from(mark(X)) 90.64/25.40 mark(head(X)) -> a__head(mark(X)) 90.64/25.40 a__head(cons(X, Y)) -> mark(X) 90.64/25.40 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.40 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.40 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.40 a__if(true, X, Y) -> mark(X) 90.64/25.40 a__if(false, X, Y) -> mark(Y) 90.64/25.40 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.40 mark(s(X)) -> s(mark(X)) 90.64/25.40 mark(0) -> 0 90.64/25.40 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.40 mark(true) -> true 90.64/25.40 mark(false) -> false 90.64/25.40 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.40 a__primes -> primes 90.64/25.40 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.40 a__sieve(X) -> sieve(X) 90.64/25.40 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.40 a__head(X) -> head(X) 90.64/25.40 a__tail(X) -> tail(X) 90.64/25.40 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.40 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.40 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)))) 90.64/25.40 90.64/25.40 90.64/25.40 ---------------------------------------- 90.64/25.40 90.64/25.40 (8) 90.64/25.40 Obligation: 90.64/25.40 Q DP problem: 90.64/25.40 The TRS P consists of the following rules: 90.64/25.40 90.64/25.40 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.40 MARK(primes) -> A__PRIMES 90.64/25.40 A__PRIMES -> A__SIEVE(a__from(s(s(0)))) 90.64/25.40 A__PRIMES -> A__FROM(s(s(0))) 90.64/25.40 A__FROM(X) -> MARK(X) 90.64/25.40 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.40 MARK(sieve(X)) -> MARK(X) 90.64/25.40 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.40 MARK(from(X)) -> MARK(X) 90.64/25.40 A__HEAD(cons(X, Y)) -> MARK(X) 90.64/25.40 MARK(tail(X)) -> A__TAIL(mark(X)) 90.64/25.40 A__TAIL(cons(X, Y)) -> MARK(Y) 90.64/25.40 MARK(tail(X)) -> MARK(X) 90.64/25.40 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.40 A__IF(true, X, Y) -> MARK(X) 90.64/25.40 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.40 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.40 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.40 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.40 MARK(s(X)) -> MARK(X) 90.64/25.40 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.40 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.40 A__IF(false, X, Y) -> MARK(Y) 90.64/25.40 90.64/25.40 The TRS R consists of the following rules: 90.64/25.40 90.64/25.40 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.40 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.40 a__head(cons(X, Y)) -> mark(X) 90.64/25.40 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.40 a__if(true, X, Y) -> mark(X) 90.64/25.40 a__if(false, X, Y) -> mark(Y) 90.64/25.40 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)))) 90.64/25.40 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.40 mark(primes) -> a__primes 90.64/25.40 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.40 mark(from(X)) -> a__from(mark(X)) 90.64/25.40 mark(head(X)) -> a__head(mark(X)) 90.64/25.40 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.40 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.40 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.40 mark(s(X)) -> s(mark(X)) 90.64/25.40 mark(0) -> 0 90.64/25.40 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.40 mark(true) -> true 90.64/25.40 mark(false) -> false 90.64/25.40 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.40 a__primes -> primes 90.64/25.40 a__sieve(X) -> sieve(X) 90.64/25.40 a__from(X) -> from(X) 90.64/25.40 a__head(X) -> head(X) 90.64/25.40 a__tail(X) -> tail(X) 90.64/25.40 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.40 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.40 90.64/25.40 The set Q consists of the following terms: 90.64/25.40 90.64/25.40 a__primes 90.64/25.40 a__from(x0) 90.64/25.40 mark(primes) 90.64/25.40 mark(sieve(x0)) 90.64/25.40 mark(from(x0)) 90.64/25.40 mark(head(x0)) 90.64/25.40 mark(tail(x0)) 90.64/25.40 mark(if(x0, x1, x2)) 90.64/25.40 mark(filter(x0, x1)) 90.64/25.40 mark(s(x0)) 90.64/25.40 mark(0) 90.64/25.40 mark(cons(x0, x1)) 90.64/25.40 mark(true) 90.64/25.40 mark(false) 90.64/25.40 mark(divides(x0, x1)) 90.64/25.40 a__sieve(x0) 90.64/25.40 a__head(x0) 90.64/25.40 a__tail(x0) 90.64/25.40 a__if(x0, x1, x2) 90.64/25.40 a__filter(x0, x1) 90.64/25.40 90.64/25.40 We have to consider all minimal (P,Q,R)-chains. 90.64/25.40 ---------------------------------------- 90.64/25.40 90.64/25.40 (9) DependencyGraphProof (EQUIVALENT) 90.64/25.40 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 90.64/25.40 ---------------------------------------- 90.64/25.40 90.64/25.40 (10) 90.64/25.40 Obligation: 90.64/25.40 Q DP problem: 90.64/25.40 The TRS P consists of the following rules: 90.64/25.40 90.64/25.40 MARK(primes) -> A__PRIMES 90.64/25.40 A__PRIMES -> A__SIEVE(a__from(s(s(0)))) 90.64/25.40 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.40 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.40 MARK(sieve(X)) -> MARK(X) 90.64/25.40 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.40 A__FROM(X) -> MARK(X) 90.64/25.40 MARK(from(X)) -> MARK(X) 90.64/25.40 MARK(tail(X)) -> A__TAIL(mark(X)) 90.64/25.40 A__TAIL(cons(X, Y)) -> MARK(Y) 90.64/25.40 MARK(tail(X)) -> MARK(X) 90.64/25.40 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.40 A__IF(true, X, Y) -> MARK(X) 90.64/25.40 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.40 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.40 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.40 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.40 MARK(s(X)) -> MARK(X) 90.64/25.40 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.40 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.40 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.40 A__IF(false, X, Y) -> MARK(Y) 90.64/25.40 A__PRIMES -> A__FROM(s(s(0))) 90.64/25.40 90.64/25.40 The TRS R consists of the following rules: 90.64/25.40 90.64/25.40 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.40 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.40 a__head(cons(X, Y)) -> mark(X) 90.64/25.40 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.40 a__if(true, X, Y) -> mark(X) 90.64/25.40 a__if(false, X, Y) -> mark(Y) 90.64/25.40 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)))) 90.64/25.40 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.40 mark(primes) -> a__primes 90.64/25.40 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.40 mark(from(X)) -> a__from(mark(X)) 90.64/25.40 mark(head(X)) -> a__head(mark(X)) 90.64/25.40 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.40 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.40 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.40 mark(s(X)) -> s(mark(X)) 90.64/25.40 mark(0) -> 0 90.64/25.40 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.40 mark(true) -> true 90.64/25.40 mark(false) -> false 90.64/25.40 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.40 a__primes -> primes 90.64/25.40 a__sieve(X) -> sieve(X) 90.64/25.40 a__from(X) -> from(X) 90.64/25.40 a__head(X) -> head(X) 90.64/25.40 a__tail(X) -> tail(X) 90.64/25.40 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.40 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.40 90.64/25.40 The set Q consists of the following terms: 90.64/25.40 90.64/25.40 a__primes 90.64/25.40 a__from(x0) 90.64/25.40 mark(primes) 90.64/25.40 mark(sieve(x0)) 90.64/25.40 mark(from(x0)) 90.64/25.40 mark(head(x0)) 90.64/25.40 mark(tail(x0)) 90.64/25.40 mark(if(x0, x1, x2)) 90.64/25.40 mark(filter(x0, x1)) 90.64/25.40 mark(s(x0)) 90.64/25.40 mark(0) 90.64/25.40 mark(cons(x0, x1)) 90.64/25.40 mark(true) 90.64/25.40 mark(false) 90.64/25.40 mark(divides(x0, x1)) 90.64/25.40 a__sieve(x0) 90.64/25.40 a__head(x0) 90.64/25.40 a__tail(x0) 90.64/25.40 a__if(x0, x1, x2) 90.64/25.40 a__filter(x0, x1) 90.64/25.40 90.64/25.40 We have to consider all minimal (P,Q,R)-chains. 90.64/25.40 ---------------------------------------- 90.64/25.40 90.64/25.40 (11) QDPOrderProof (EQUIVALENT) 90.64/25.40 We use the reduction pair processor [LPAR04,JAR06]. 90.64/25.40 90.64/25.40 90.64/25.40 The following pairs can be oriented strictly and are deleted. 90.64/25.40 90.64/25.40 MARK(primes) -> A__PRIMES 90.64/25.40 The remaining pairs can at least be oriented weakly. 90.64/25.40 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(primes) = [[1A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__PRIMES) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(A__SIEVE(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(a__from(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(0) = [[0A]] 90.64/25.40 >>> 90.64/25.40 90.64/25.40 <<< 90.64/25.40 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(from(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__TAIL(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__IF(x_1, x_2, x_3)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(true) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__FILTER(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(false) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__primes) = [[1A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(head(x_1)) = [[-I]] + [[1A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__head(x_1)) = [[-I]] + [[1A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 90.64/25.42 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.64/25.42 90.64/25.42 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.42 a__from(X) -> from(X) 90.64/25.42 mark(primes) -> a__primes 90.64/25.42 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.42 mark(from(X)) -> a__from(mark(X)) 90.64/25.42 mark(head(X)) -> a__head(mark(X)) 90.64/25.42 a__head(cons(X, Y)) -> mark(X) 90.64/25.42 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.42 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.42 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.42 a__if(true, X, Y) -> mark(X) 90.64/25.42 a__if(false, X, Y) -> mark(Y) 90.64/25.42 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.42 mark(s(X)) -> s(mark(X)) 90.64/25.42 mark(0) -> 0 90.64/25.42 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.42 mark(true) -> true 90.64/25.42 mark(false) -> false 90.64/25.42 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.42 a__primes -> primes 90.64/25.42 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.42 a__sieve(X) -> sieve(X) 90.64/25.42 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.42 a__head(X) -> head(X) 90.64/25.42 a__tail(X) -> tail(X) 90.64/25.42 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.42 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.42 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)))) 90.64/25.42 90.64/25.42 90.64/25.42 ---------------------------------------- 90.64/25.42 90.64/25.42 (12) 90.64/25.42 Obligation: 90.64/25.42 Q DP problem: 90.64/25.42 The TRS P consists of the following rules: 90.64/25.42 90.64/25.42 A__PRIMES -> A__SIEVE(a__from(s(s(0)))) 90.64/25.42 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.42 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.42 MARK(sieve(X)) -> MARK(X) 90.64/25.42 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.42 A__FROM(X) -> MARK(X) 90.64/25.42 MARK(from(X)) -> MARK(X) 90.64/25.42 MARK(tail(X)) -> A__TAIL(mark(X)) 90.64/25.42 A__TAIL(cons(X, Y)) -> MARK(Y) 90.64/25.42 MARK(tail(X)) -> MARK(X) 90.64/25.42 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.42 A__IF(true, X, Y) -> MARK(X) 90.64/25.42 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.42 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.42 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.42 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.42 MARK(s(X)) -> MARK(X) 90.64/25.42 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.42 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.42 A__IF(false, X, Y) -> MARK(Y) 90.64/25.42 A__PRIMES -> A__FROM(s(s(0))) 90.64/25.42 90.64/25.42 The TRS R consists of the following rules: 90.64/25.42 90.64/25.42 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.42 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.42 a__head(cons(X, Y)) -> mark(X) 90.64/25.42 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.42 a__if(true, X, Y) -> mark(X) 90.64/25.42 a__if(false, X, Y) -> mark(Y) 90.64/25.42 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)))) 90.64/25.42 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.42 mark(primes) -> a__primes 90.64/25.42 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.42 mark(from(X)) -> a__from(mark(X)) 90.64/25.42 mark(head(X)) -> a__head(mark(X)) 90.64/25.42 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.42 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.42 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.42 mark(s(X)) -> s(mark(X)) 90.64/25.42 mark(0) -> 0 90.64/25.42 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.42 mark(true) -> true 90.64/25.42 mark(false) -> false 90.64/25.42 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.42 a__primes -> primes 90.64/25.42 a__sieve(X) -> sieve(X) 90.64/25.42 a__from(X) -> from(X) 90.64/25.42 a__head(X) -> head(X) 90.64/25.42 a__tail(X) -> tail(X) 90.64/25.42 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.42 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.42 90.64/25.42 The set Q consists of the following terms: 90.64/25.42 90.64/25.42 a__primes 90.64/25.42 a__from(x0) 90.64/25.42 mark(primes) 90.64/25.42 mark(sieve(x0)) 90.64/25.42 mark(from(x0)) 90.64/25.42 mark(head(x0)) 90.64/25.42 mark(tail(x0)) 90.64/25.42 mark(if(x0, x1, x2)) 90.64/25.42 mark(filter(x0, x1)) 90.64/25.42 mark(s(x0)) 90.64/25.42 mark(0) 90.64/25.42 mark(cons(x0, x1)) 90.64/25.42 mark(true) 90.64/25.42 mark(false) 90.64/25.42 mark(divides(x0, x1)) 90.64/25.42 a__sieve(x0) 90.64/25.42 a__head(x0) 90.64/25.42 a__tail(x0) 90.64/25.42 a__if(x0, x1, x2) 90.64/25.42 a__filter(x0, x1) 90.64/25.42 90.64/25.42 We have to consider all minimal (P,Q,R)-chains. 90.64/25.42 ---------------------------------------- 90.64/25.42 90.64/25.42 (13) DependencyGraphProof (EQUIVALENT) 90.64/25.42 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 90.64/25.42 ---------------------------------------- 90.64/25.42 90.64/25.42 (14) 90.64/25.42 Obligation: 90.64/25.42 Q DP problem: 90.64/25.42 The TRS P consists of the following rules: 90.64/25.42 90.64/25.42 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.42 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.42 MARK(sieve(X)) -> MARK(X) 90.64/25.42 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.42 A__FROM(X) -> MARK(X) 90.64/25.42 MARK(from(X)) -> MARK(X) 90.64/25.42 MARK(tail(X)) -> A__TAIL(mark(X)) 90.64/25.42 A__TAIL(cons(X, Y)) -> MARK(Y) 90.64/25.42 MARK(tail(X)) -> MARK(X) 90.64/25.42 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.42 A__IF(true, X, Y) -> MARK(X) 90.64/25.42 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.42 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.42 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.42 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.42 MARK(s(X)) -> MARK(X) 90.64/25.42 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.42 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.42 A__IF(false, X, Y) -> MARK(Y) 90.64/25.42 90.64/25.42 The TRS R consists of the following rules: 90.64/25.42 90.64/25.42 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.42 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.42 a__head(cons(X, Y)) -> mark(X) 90.64/25.42 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.42 a__if(true, X, Y) -> mark(X) 90.64/25.42 a__if(false, X, Y) -> mark(Y) 90.64/25.42 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)))) 90.64/25.42 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.42 mark(primes) -> a__primes 90.64/25.42 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.42 mark(from(X)) -> a__from(mark(X)) 90.64/25.42 mark(head(X)) -> a__head(mark(X)) 90.64/25.42 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.42 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.42 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.42 mark(s(X)) -> s(mark(X)) 90.64/25.42 mark(0) -> 0 90.64/25.42 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.42 mark(true) -> true 90.64/25.42 mark(false) -> false 90.64/25.42 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.42 a__primes -> primes 90.64/25.42 a__sieve(X) -> sieve(X) 90.64/25.42 a__from(X) -> from(X) 90.64/25.42 a__head(X) -> head(X) 90.64/25.42 a__tail(X) -> tail(X) 90.64/25.42 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.42 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.42 90.64/25.42 The set Q consists of the following terms: 90.64/25.42 90.64/25.42 a__primes 90.64/25.42 a__from(x0) 90.64/25.42 mark(primes) 90.64/25.42 mark(sieve(x0)) 90.64/25.42 mark(from(x0)) 90.64/25.42 mark(head(x0)) 90.64/25.42 mark(tail(x0)) 90.64/25.42 mark(if(x0, x1, x2)) 90.64/25.42 mark(filter(x0, x1)) 90.64/25.42 mark(s(x0)) 90.64/25.42 mark(0) 90.64/25.42 mark(cons(x0, x1)) 90.64/25.42 mark(true) 90.64/25.42 mark(false) 90.64/25.42 mark(divides(x0, x1)) 90.64/25.42 a__sieve(x0) 90.64/25.42 a__head(x0) 90.64/25.42 a__tail(x0) 90.64/25.42 a__if(x0, x1, x2) 90.64/25.42 a__filter(x0, x1) 90.64/25.42 90.64/25.42 We have to consider all minimal (P,Q,R)-chains. 90.64/25.42 ---------------------------------------- 90.64/25.42 90.64/25.42 (15) QDPOrderProof (EQUIVALENT) 90.64/25.42 We use the reduction pair processor [LPAR04,JAR06]. 90.64/25.42 90.64/25.42 90.64/25.42 The following pairs can be oriented strictly and are deleted. 90.64/25.42 90.64/25.42 MARK(tail(X)) -> MARK(X) 90.64/25.42 The remaining pairs can at least be oriented weakly. 90.64/25.42 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__SIEVE(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(from(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(tail(x_1)) = [[3A]] + [[3A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__TAIL(x_1)) = [[3A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__IF(x_1, x_2, x_3)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(true) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__FILTER(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(false) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(primes) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__primes) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(head(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__head(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__tail(x_1)) = [[3A]] + [[3A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(0) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 90.64/25.42 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.64/25.42 90.64/25.42 mark(primes) -> a__primes 90.64/25.42 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.42 mark(from(X)) -> a__from(mark(X)) 90.64/25.42 mark(head(X)) -> a__head(mark(X)) 90.64/25.42 a__head(cons(X, Y)) -> mark(X) 90.64/25.42 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.42 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.42 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.42 a__if(true, X, Y) -> mark(X) 90.64/25.42 a__if(false, X, Y) -> mark(Y) 90.64/25.42 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.42 mark(s(X)) -> s(mark(X)) 90.64/25.42 mark(0) -> 0 90.64/25.42 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.42 mark(true) -> true 90.64/25.42 mark(false) -> false 90.64/25.42 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.42 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.42 a__primes -> primes 90.64/25.42 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.42 a__from(X) -> from(X) 90.64/25.42 a__sieve(X) -> sieve(X) 90.64/25.42 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.42 a__head(X) -> head(X) 90.64/25.42 a__tail(X) -> tail(X) 90.64/25.42 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.42 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.42 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)))) 90.64/25.42 90.64/25.42 90.64/25.42 ---------------------------------------- 90.64/25.42 90.64/25.42 (16) 90.64/25.42 Obligation: 90.64/25.42 Q DP problem: 90.64/25.42 The TRS P consists of the following rules: 90.64/25.42 90.64/25.42 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.42 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.42 MARK(sieve(X)) -> MARK(X) 90.64/25.42 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.42 A__FROM(X) -> MARK(X) 90.64/25.42 MARK(from(X)) -> MARK(X) 90.64/25.42 MARK(tail(X)) -> A__TAIL(mark(X)) 90.64/25.42 A__TAIL(cons(X, Y)) -> MARK(Y) 90.64/25.42 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.42 A__IF(true, X, Y) -> MARK(X) 90.64/25.42 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.42 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.42 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.42 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.42 MARK(s(X)) -> MARK(X) 90.64/25.42 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.42 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.42 A__IF(false, X, Y) -> MARK(Y) 90.64/25.42 90.64/25.42 The TRS R consists of the following rules: 90.64/25.42 90.64/25.42 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.42 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.42 a__head(cons(X, Y)) -> mark(X) 90.64/25.42 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.42 a__if(true, X, Y) -> mark(X) 90.64/25.42 a__if(false, X, Y) -> mark(Y) 90.64/25.42 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)))) 90.64/25.42 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.42 mark(primes) -> a__primes 90.64/25.42 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.42 mark(from(X)) -> a__from(mark(X)) 90.64/25.42 mark(head(X)) -> a__head(mark(X)) 90.64/25.42 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.42 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.42 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.42 mark(s(X)) -> s(mark(X)) 90.64/25.42 mark(0) -> 0 90.64/25.42 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.42 mark(true) -> true 90.64/25.42 mark(false) -> false 90.64/25.42 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.42 a__primes -> primes 90.64/25.42 a__sieve(X) -> sieve(X) 90.64/25.42 a__from(X) -> from(X) 90.64/25.42 a__head(X) -> head(X) 90.64/25.42 a__tail(X) -> tail(X) 90.64/25.42 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.42 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.42 90.64/25.42 The set Q consists of the following terms: 90.64/25.42 90.64/25.42 a__primes 90.64/25.42 a__from(x0) 90.64/25.42 mark(primes) 90.64/25.42 mark(sieve(x0)) 90.64/25.42 mark(from(x0)) 90.64/25.42 mark(head(x0)) 90.64/25.42 mark(tail(x0)) 90.64/25.42 mark(if(x0, x1, x2)) 90.64/25.42 mark(filter(x0, x1)) 90.64/25.42 mark(s(x0)) 90.64/25.42 mark(0) 90.64/25.42 mark(cons(x0, x1)) 90.64/25.42 mark(true) 90.64/25.42 mark(false) 90.64/25.42 mark(divides(x0, x1)) 90.64/25.42 a__sieve(x0) 90.64/25.42 a__head(x0) 90.64/25.42 a__tail(x0) 90.64/25.42 a__if(x0, x1, x2) 90.64/25.42 a__filter(x0, x1) 90.64/25.42 90.64/25.42 We have to consider all minimal (P,Q,R)-chains. 90.64/25.42 ---------------------------------------- 90.64/25.42 90.64/25.42 (17) QDPOrderProof (EQUIVALENT) 90.64/25.42 We use the reduction pair processor [LPAR04,JAR06]. 90.64/25.42 90.64/25.42 90.64/25.42 The following pairs can be oriented strictly and are deleted. 90.64/25.42 90.64/25.42 MARK(tail(X)) -> A__TAIL(mark(X)) 90.64/25.42 The remaining pairs can at least be oriented weakly. 90.64/25.42 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__SIEVE(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(from(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(tail(x_1)) = [[1A]] + [[1A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__TAIL(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__IF(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(true) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__FILTER(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(s(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(divides(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(false) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(primes) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__primes) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__sieve(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(head(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__head(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__tail(x_1)) = [[1A]] + [[1A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(0) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 90.64/25.42 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.64/25.42 90.64/25.42 mark(primes) -> a__primes 90.64/25.42 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.42 mark(from(X)) -> a__from(mark(X)) 90.64/25.42 mark(head(X)) -> a__head(mark(X)) 90.64/25.42 a__head(cons(X, Y)) -> mark(X) 90.64/25.42 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.42 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.42 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.42 a__if(true, X, Y) -> mark(X) 90.64/25.42 a__if(false, X, Y) -> mark(Y) 90.64/25.42 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.42 mark(s(X)) -> s(mark(X)) 90.64/25.42 mark(0) -> 0 90.64/25.42 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.42 mark(true) -> true 90.64/25.42 mark(false) -> false 90.64/25.42 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.42 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.42 a__primes -> primes 90.64/25.42 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.42 a__from(X) -> from(X) 90.64/25.42 a__sieve(X) -> sieve(X) 90.64/25.42 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.42 a__head(X) -> head(X) 90.64/25.42 a__tail(X) -> tail(X) 90.64/25.42 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.42 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.42 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)))) 90.64/25.42 90.64/25.42 90.64/25.42 ---------------------------------------- 90.64/25.42 90.64/25.42 (18) 90.64/25.42 Obligation: 90.64/25.42 Q DP problem: 90.64/25.42 The TRS P consists of the following rules: 90.64/25.42 90.64/25.42 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.42 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.42 MARK(sieve(X)) -> MARK(X) 90.64/25.42 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.42 A__FROM(X) -> MARK(X) 90.64/25.42 MARK(from(X)) -> MARK(X) 90.64/25.42 A__TAIL(cons(X, Y)) -> MARK(Y) 90.64/25.42 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.42 A__IF(true, X, Y) -> MARK(X) 90.64/25.42 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.42 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.42 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.42 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.42 MARK(s(X)) -> MARK(X) 90.64/25.42 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.42 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.42 A__IF(false, X, Y) -> MARK(Y) 90.64/25.42 90.64/25.42 The TRS R consists of the following rules: 90.64/25.42 90.64/25.42 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.42 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.42 a__head(cons(X, Y)) -> mark(X) 90.64/25.42 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.42 a__if(true, X, Y) -> mark(X) 90.64/25.42 a__if(false, X, Y) -> mark(Y) 90.64/25.42 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)))) 90.64/25.42 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.42 mark(primes) -> a__primes 90.64/25.42 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.42 mark(from(X)) -> a__from(mark(X)) 90.64/25.42 mark(head(X)) -> a__head(mark(X)) 90.64/25.42 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.42 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.42 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.42 mark(s(X)) -> s(mark(X)) 90.64/25.42 mark(0) -> 0 90.64/25.42 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.42 mark(true) -> true 90.64/25.42 mark(false) -> false 90.64/25.42 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.42 a__primes -> primes 90.64/25.42 a__sieve(X) -> sieve(X) 90.64/25.42 a__from(X) -> from(X) 90.64/25.42 a__head(X) -> head(X) 90.64/25.42 a__tail(X) -> tail(X) 90.64/25.42 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.42 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.42 90.64/25.42 The set Q consists of the following terms: 90.64/25.42 90.64/25.42 a__primes 90.64/25.42 a__from(x0) 90.64/25.42 mark(primes) 90.64/25.42 mark(sieve(x0)) 90.64/25.42 mark(from(x0)) 90.64/25.42 mark(head(x0)) 90.64/25.42 mark(tail(x0)) 90.64/25.42 mark(if(x0, x1, x2)) 90.64/25.42 mark(filter(x0, x1)) 90.64/25.42 mark(s(x0)) 90.64/25.42 mark(0) 90.64/25.42 mark(cons(x0, x1)) 90.64/25.42 mark(true) 90.64/25.42 mark(false) 90.64/25.42 mark(divides(x0, x1)) 90.64/25.42 a__sieve(x0) 90.64/25.42 a__head(x0) 90.64/25.42 a__tail(x0) 90.64/25.42 a__if(x0, x1, x2) 90.64/25.42 a__filter(x0, x1) 90.64/25.42 90.64/25.42 We have to consider all minimal (P,Q,R)-chains. 90.64/25.42 ---------------------------------------- 90.64/25.42 90.64/25.42 (19) DependencyGraphProof (EQUIVALENT) 90.64/25.42 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 90.64/25.42 ---------------------------------------- 90.64/25.42 90.64/25.42 (20) 90.64/25.42 Obligation: 90.64/25.42 Q DP problem: 90.64/25.42 The TRS P consists of the following rules: 90.64/25.42 90.64/25.42 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.42 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.42 MARK(sieve(X)) -> MARK(X) 90.64/25.42 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.42 A__FROM(X) -> MARK(X) 90.64/25.42 MARK(from(X)) -> MARK(X) 90.64/25.42 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.42 A__IF(true, X, Y) -> MARK(X) 90.64/25.42 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.42 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.42 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.42 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.42 MARK(s(X)) -> MARK(X) 90.64/25.42 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.42 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.42 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.42 A__IF(false, X, Y) -> MARK(Y) 90.64/25.42 90.64/25.42 The TRS R consists of the following rules: 90.64/25.42 90.64/25.42 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.42 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.42 a__head(cons(X, Y)) -> mark(X) 90.64/25.42 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.42 a__if(true, X, Y) -> mark(X) 90.64/25.42 a__if(false, X, Y) -> mark(Y) 90.64/25.42 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)))) 90.64/25.42 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.42 mark(primes) -> a__primes 90.64/25.42 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.42 mark(from(X)) -> a__from(mark(X)) 90.64/25.42 mark(head(X)) -> a__head(mark(X)) 90.64/25.42 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.42 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.42 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.42 mark(s(X)) -> s(mark(X)) 90.64/25.42 mark(0) -> 0 90.64/25.42 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.42 mark(true) -> true 90.64/25.42 mark(false) -> false 90.64/25.42 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.42 a__primes -> primes 90.64/25.42 a__sieve(X) -> sieve(X) 90.64/25.42 a__from(X) -> from(X) 90.64/25.42 a__head(X) -> head(X) 90.64/25.42 a__tail(X) -> tail(X) 90.64/25.42 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.42 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.42 90.64/25.42 The set Q consists of the following terms: 90.64/25.42 90.64/25.42 a__primes 90.64/25.42 a__from(x0) 90.64/25.42 mark(primes) 90.64/25.42 mark(sieve(x0)) 90.64/25.42 mark(from(x0)) 90.64/25.42 mark(head(x0)) 90.64/25.42 mark(tail(x0)) 90.64/25.42 mark(if(x0, x1, x2)) 90.64/25.42 mark(filter(x0, x1)) 90.64/25.42 mark(s(x0)) 90.64/25.42 mark(0) 90.64/25.42 mark(cons(x0, x1)) 90.64/25.42 mark(true) 90.64/25.42 mark(false) 90.64/25.42 mark(divides(x0, x1)) 90.64/25.42 a__sieve(x0) 90.64/25.42 a__head(x0) 90.64/25.42 a__tail(x0) 90.64/25.42 a__if(x0, x1, x2) 90.64/25.42 a__filter(x0, x1) 90.64/25.42 90.64/25.42 We have to consider all minimal (P,Q,R)-chains. 90.64/25.42 ---------------------------------------- 90.64/25.42 90.64/25.42 (21) QDPOrderProof (EQUIVALENT) 90.64/25.42 We use the reduction pair processor [LPAR04,JAR06]. 90.64/25.42 90.64/25.42 90.64/25.42 The following pairs can be oriented strictly and are deleted. 90.64/25.42 90.64/25.42 MARK(from(X)) -> MARK(X) 90.64/25.42 The remaining pairs can at least be oriented weakly. 90.64/25.42 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__SIEVE(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(cons(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(from(x_1)) = [[1A]] + [[1A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__IF(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(true) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(A__FILTER(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(s(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(false) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(primes) = [[1A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__primes) = [[1A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(head(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__head(x_1)) = [[0A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(tail(x_1)) = [[4A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__tail(x_1)) = [[4A]] + [[0A]] * x_1 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.64/25.42 >>> 90.64/25.42 90.64/25.42 <<< 90.64/25.42 POL(0) = [[0A]] 90.64/25.42 >>> 90.64/25.42 90.64/25.42 90.64/25.42 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.64/25.42 90.64/25.42 mark(primes) -> a__primes 90.64/25.42 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.42 mark(from(X)) -> a__from(mark(X)) 90.64/25.42 mark(head(X)) -> a__head(mark(X)) 90.64/25.42 a__head(cons(X, Y)) -> mark(X) 90.64/25.42 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.44 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.44 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.44 a__if(true, X, Y) -> mark(X) 90.64/25.44 a__if(false, X, Y) -> mark(Y) 90.64/25.44 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.44 mark(s(X)) -> s(mark(X)) 90.64/25.44 mark(0) -> 0 90.64/25.44 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.44 mark(true) -> true 90.64/25.44 mark(false) -> false 90.64/25.44 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.44 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.44 a__primes -> primes 90.64/25.44 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.44 a__from(X) -> from(X) 90.64/25.44 a__sieve(X) -> sieve(X) 90.64/25.44 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.44 a__head(X) -> head(X) 90.64/25.44 a__tail(X) -> tail(X) 90.64/25.44 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.44 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.44 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)))) 90.64/25.44 90.64/25.44 90.64/25.44 ---------------------------------------- 90.64/25.44 90.64/25.44 (22) 90.64/25.44 Obligation: 90.64/25.44 Q DP problem: 90.64/25.44 The TRS P consists of the following rules: 90.64/25.44 90.64/25.44 A__SIEVE(cons(X, Y)) -> MARK(X) 90.64/25.44 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.64/25.44 MARK(sieve(X)) -> MARK(X) 90.64/25.44 MARK(from(X)) -> A__FROM(mark(X)) 90.64/25.44 A__FROM(X) -> MARK(X) 90.64/25.44 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.64/25.44 A__IF(true, X, Y) -> MARK(X) 90.64/25.44 MARK(if(X1, X2, X3)) -> MARK(X1) 90.64/25.44 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.64/25.44 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.64/25.44 MARK(filter(X1, X2)) -> MARK(X1) 90.64/25.44 MARK(filter(X1, X2)) -> MARK(X2) 90.64/25.44 MARK(s(X)) -> MARK(X) 90.64/25.44 MARK(cons(X1, X2)) -> MARK(X1) 90.64/25.44 MARK(divides(X1, X2)) -> MARK(X1) 90.64/25.44 MARK(divides(X1, X2)) -> MARK(X2) 90.64/25.44 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.64/25.44 A__IF(false, X, Y) -> MARK(Y) 90.64/25.44 90.64/25.44 The TRS R consists of the following rules: 90.64/25.44 90.64/25.44 a__primes -> a__sieve(a__from(s(s(0)))) 90.64/25.44 a__from(X) -> cons(mark(X), from(s(X))) 90.64/25.44 a__head(cons(X, Y)) -> mark(X) 90.64/25.44 a__tail(cons(X, Y)) -> mark(Y) 90.64/25.44 a__if(true, X, Y) -> mark(X) 90.64/25.44 a__if(false, X, Y) -> mark(Y) 90.64/25.44 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)))) 90.64/25.44 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.64/25.44 mark(primes) -> a__primes 90.64/25.44 mark(sieve(X)) -> a__sieve(mark(X)) 90.64/25.44 mark(from(X)) -> a__from(mark(X)) 90.64/25.44 mark(head(X)) -> a__head(mark(X)) 90.64/25.44 mark(tail(X)) -> a__tail(mark(X)) 90.64/25.44 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.64/25.44 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.64/25.44 mark(s(X)) -> s(mark(X)) 90.64/25.44 mark(0) -> 0 90.64/25.44 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.64/25.44 mark(true) -> true 90.64/25.44 mark(false) -> false 90.64/25.44 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.64/25.44 a__primes -> primes 90.64/25.44 a__sieve(X) -> sieve(X) 90.64/25.44 a__from(X) -> from(X) 90.64/25.44 a__head(X) -> head(X) 90.64/25.44 a__tail(X) -> tail(X) 90.64/25.44 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.64/25.44 a__filter(X1, X2) -> filter(X1, X2) 90.64/25.44 90.64/25.44 The set Q consists of the following terms: 90.64/25.44 90.64/25.44 a__primes 90.64/25.44 a__from(x0) 90.64/25.44 mark(primes) 90.64/25.44 mark(sieve(x0)) 90.64/25.44 mark(from(x0)) 90.64/25.44 mark(head(x0)) 90.64/25.44 mark(tail(x0)) 90.64/25.44 mark(if(x0, x1, x2)) 90.64/25.44 mark(filter(x0, x1)) 90.64/25.44 mark(s(x0)) 90.64/25.44 mark(0) 90.64/25.44 mark(cons(x0, x1)) 90.87/25.44 mark(true) 90.87/25.44 mark(false) 90.87/25.44 mark(divides(x0, x1)) 90.87/25.44 a__sieve(x0) 90.87/25.44 a__head(x0) 90.87/25.44 a__tail(x0) 90.87/25.44 a__if(x0, x1, x2) 90.87/25.44 a__filter(x0, x1) 90.87/25.44 90.87/25.44 We have to consider all minimal (P,Q,R)-chains. 90.87/25.44 ---------------------------------------- 90.87/25.44 90.87/25.44 (23) QDPOrderProof (EQUIVALENT) 90.87/25.44 We use the reduction pair processor [LPAR04,JAR06]. 90.87/25.44 90.87/25.44 90.87/25.44 The following pairs can be oriented strictly and are deleted. 90.87/25.44 90.87/25.44 MARK(from(X)) -> A__FROM(mark(X)) 90.87/25.44 The remaining pairs can at least be oriented weakly. 90.87/25.44 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(A__SIEVE(x_1)) = [[1A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(from(x_1)) = [[2A]] + [[1A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(A__IF(x_1, x_2, x_3)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(true) = [[0A]] 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(A__FILTER(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(false) = [[1A]] 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(primes) = [[2A]] 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__primes) = [[2A]] 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__sieve(x_1)) = [[0A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__from(x_1)) = [[2A]] + [[1A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(head(x_1)) = [[0A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__head(x_1)) = [[0A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__filter(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(0) = [[0A]] 90.87/25.44 >>> 90.87/25.44 90.87/25.44 90.87/25.44 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.87/25.44 90.87/25.44 mark(primes) -> a__primes 90.87/25.44 mark(sieve(X)) -> a__sieve(mark(X)) 90.87/25.44 mark(from(X)) -> a__from(mark(X)) 90.87/25.44 mark(head(X)) -> a__head(mark(X)) 90.87/25.44 a__head(cons(X, Y)) -> mark(X) 90.87/25.44 mark(tail(X)) -> a__tail(mark(X)) 90.87/25.44 a__tail(cons(X, Y)) -> mark(Y) 90.87/25.44 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.87/25.44 a__if(true, X, Y) -> mark(X) 90.87/25.44 a__if(false, X, Y) -> mark(Y) 90.87/25.44 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.87/25.44 mark(s(X)) -> s(mark(X)) 90.87/25.44 mark(0) -> 0 90.87/25.44 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.87/25.44 mark(true) -> true 90.87/25.44 mark(false) -> false 90.87/25.44 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.87/25.44 a__from(X) -> cons(mark(X), from(s(X))) 90.87/25.44 a__primes -> primes 90.87/25.44 a__primes -> a__sieve(a__from(s(s(0)))) 90.87/25.44 a__from(X) -> from(X) 90.87/25.44 a__sieve(X) -> sieve(X) 90.87/25.44 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.87/25.44 a__head(X) -> head(X) 90.87/25.44 a__tail(X) -> tail(X) 90.87/25.44 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.87/25.44 a__filter(X1, X2) -> filter(X1, X2) 90.87/25.44 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)))) 90.87/25.44 90.87/25.44 90.87/25.44 ---------------------------------------- 90.87/25.44 90.87/25.44 (24) 90.87/25.44 Obligation: 90.87/25.44 Q DP problem: 90.87/25.44 The TRS P consists of the following rules: 90.87/25.44 90.87/25.44 A__SIEVE(cons(X, Y)) -> MARK(X) 90.87/25.44 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.87/25.44 MARK(sieve(X)) -> MARK(X) 90.87/25.44 A__FROM(X) -> MARK(X) 90.87/25.44 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.87/25.44 A__IF(true, X, Y) -> MARK(X) 90.87/25.44 MARK(if(X1, X2, X3)) -> MARK(X1) 90.87/25.44 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.87/25.44 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.87/25.44 MARK(filter(X1, X2)) -> MARK(X1) 90.87/25.44 MARK(filter(X1, X2)) -> MARK(X2) 90.87/25.44 MARK(s(X)) -> MARK(X) 90.87/25.44 MARK(cons(X1, X2)) -> MARK(X1) 90.87/25.44 MARK(divides(X1, X2)) -> MARK(X1) 90.87/25.44 MARK(divides(X1, X2)) -> MARK(X2) 90.87/25.44 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.87/25.44 A__IF(false, X, Y) -> MARK(Y) 90.87/25.44 90.87/25.44 The TRS R consists of the following rules: 90.87/25.44 90.87/25.44 a__primes -> a__sieve(a__from(s(s(0)))) 90.87/25.44 a__from(X) -> cons(mark(X), from(s(X))) 90.87/25.44 a__head(cons(X, Y)) -> mark(X) 90.87/25.44 a__tail(cons(X, Y)) -> mark(Y) 90.87/25.44 a__if(true, X, Y) -> mark(X) 90.87/25.44 a__if(false, X, Y) -> mark(Y) 90.87/25.44 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)))) 90.87/25.44 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.87/25.44 mark(primes) -> a__primes 90.87/25.44 mark(sieve(X)) -> a__sieve(mark(X)) 90.87/25.44 mark(from(X)) -> a__from(mark(X)) 90.87/25.44 mark(head(X)) -> a__head(mark(X)) 90.87/25.44 mark(tail(X)) -> a__tail(mark(X)) 90.87/25.44 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.87/25.44 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.87/25.44 mark(s(X)) -> s(mark(X)) 90.87/25.44 mark(0) -> 0 90.87/25.44 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.87/25.44 mark(true) -> true 90.87/25.44 mark(false) -> false 90.87/25.44 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.87/25.44 a__primes -> primes 90.87/25.44 a__sieve(X) -> sieve(X) 90.87/25.44 a__from(X) -> from(X) 90.87/25.44 a__head(X) -> head(X) 90.87/25.44 a__tail(X) -> tail(X) 90.87/25.44 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.87/25.44 a__filter(X1, X2) -> filter(X1, X2) 90.87/25.44 90.87/25.44 The set Q consists of the following terms: 90.87/25.44 90.87/25.44 a__primes 90.87/25.44 a__from(x0) 90.87/25.44 mark(primes) 90.87/25.44 mark(sieve(x0)) 90.87/25.44 mark(from(x0)) 90.87/25.44 mark(head(x0)) 90.87/25.44 mark(tail(x0)) 90.87/25.44 mark(if(x0, x1, x2)) 90.87/25.44 mark(filter(x0, x1)) 90.87/25.44 mark(s(x0)) 90.87/25.44 mark(0) 90.87/25.44 mark(cons(x0, x1)) 90.87/25.44 mark(true) 90.87/25.44 mark(false) 90.87/25.44 mark(divides(x0, x1)) 90.87/25.44 a__sieve(x0) 90.87/25.44 a__head(x0) 90.87/25.44 a__tail(x0) 90.87/25.44 a__if(x0, x1, x2) 90.87/25.44 a__filter(x0, x1) 90.87/25.44 90.87/25.44 We have to consider all minimal (P,Q,R)-chains. 90.87/25.44 ---------------------------------------- 90.87/25.44 90.87/25.44 (25) DependencyGraphProof (EQUIVALENT) 90.87/25.44 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 90.87/25.44 ---------------------------------------- 90.87/25.44 90.87/25.44 (26) 90.87/25.44 Obligation: 90.87/25.44 Q DP problem: 90.87/25.44 The TRS P consists of the following rules: 90.87/25.44 90.87/25.44 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.87/25.44 A__SIEVE(cons(X, Y)) -> MARK(X) 90.87/25.44 MARK(sieve(X)) -> MARK(X) 90.87/25.44 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.87/25.44 A__IF(true, X, Y) -> MARK(X) 90.87/25.44 MARK(if(X1, X2, X3)) -> MARK(X1) 90.87/25.44 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.87/25.44 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.87/25.44 MARK(filter(X1, X2)) -> MARK(X1) 90.87/25.44 MARK(filter(X1, X2)) -> MARK(X2) 90.87/25.44 MARK(s(X)) -> MARK(X) 90.87/25.44 MARK(cons(X1, X2)) -> MARK(X1) 90.87/25.44 MARK(divides(X1, X2)) -> MARK(X1) 90.87/25.44 MARK(divides(X1, X2)) -> MARK(X2) 90.87/25.44 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.87/25.44 A__IF(false, X, Y) -> MARK(Y) 90.87/25.44 90.87/25.44 The TRS R consists of the following rules: 90.87/25.44 90.87/25.44 a__primes -> a__sieve(a__from(s(s(0)))) 90.87/25.44 a__from(X) -> cons(mark(X), from(s(X))) 90.87/25.44 a__head(cons(X, Y)) -> mark(X) 90.87/25.44 a__tail(cons(X, Y)) -> mark(Y) 90.87/25.44 a__if(true, X, Y) -> mark(X) 90.87/25.44 a__if(false, X, Y) -> mark(Y) 90.87/25.44 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)))) 90.87/25.44 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.87/25.44 mark(primes) -> a__primes 90.87/25.44 mark(sieve(X)) -> a__sieve(mark(X)) 90.87/25.44 mark(from(X)) -> a__from(mark(X)) 90.87/25.44 mark(head(X)) -> a__head(mark(X)) 90.87/25.44 mark(tail(X)) -> a__tail(mark(X)) 90.87/25.44 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.87/25.44 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.87/25.44 mark(s(X)) -> s(mark(X)) 90.87/25.44 mark(0) -> 0 90.87/25.44 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.87/25.44 mark(true) -> true 90.87/25.44 mark(false) -> false 90.87/25.44 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.87/25.44 a__primes -> primes 90.87/25.44 a__sieve(X) -> sieve(X) 90.87/25.44 a__from(X) -> from(X) 90.87/25.44 a__head(X) -> head(X) 90.87/25.44 a__tail(X) -> tail(X) 90.87/25.44 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.87/25.44 a__filter(X1, X2) -> filter(X1, X2) 90.87/25.44 90.87/25.44 The set Q consists of the following terms: 90.87/25.44 90.87/25.44 a__primes 90.87/25.44 a__from(x0) 90.87/25.44 mark(primes) 90.87/25.44 mark(sieve(x0)) 90.87/25.44 mark(from(x0)) 90.87/25.44 mark(head(x0)) 90.87/25.44 mark(tail(x0)) 90.87/25.44 mark(if(x0, x1, x2)) 90.87/25.44 mark(filter(x0, x1)) 90.87/25.44 mark(s(x0)) 90.87/25.44 mark(0) 90.87/25.44 mark(cons(x0, x1)) 90.87/25.44 mark(true) 90.87/25.44 mark(false) 90.87/25.44 mark(divides(x0, x1)) 90.87/25.44 a__sieve(x0) 90.87/25.44 a__head(x0) 90.87/25.44 a__tail(x0) 90.87/25.44 a__if(x0, x1, x2) 90.87/25.44 a__filter(x0, x1) 90.87/25.44 90.87/25.44 We have to consider all minimal (P,Q,R)-chains. 90.87/25.44 ---------------------------------------- 90.87/25.44 90.87/25.44 (27) QDPOrderProof (EQUIVALENT) 90.87/25.44 We use the reduction pair processor [LPAR04,JAR06]. 90.87/25.44 90.87/25.44 90.87/25.44 The following pairs can be oriented strictly and are deleted. 90.87/25.44 90.87/25.44 A__SIEVE(cons(X, Y)) -> MARK(X) 90.87/25.44 The remaining pairs can at least be oriented weakly. 90.87/25.44 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(MARK(x_1)) = [[2A]] + [[1A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(sieve(x_1)) = [[3A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(A__SIEVE(x_1)) = [[4A]] + [[1A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(cons(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(A__IF(x_1, x_2, x_3)) = [[2A]] + [[-I]] * x_1 + [[1A]] * x_2 + [[1A]] * x_3 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(true) = [[0A]] 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(filter(x_1, x_2)) = [[3A]] + [[0A]] * x_1 + [[0A]] * x_2 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(A__FILTER(x_1, x_2)) = [[2A]] + [[1A]] * x_1 + [[0A]] * x_2 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(s(x_1)) = [[0A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(false) = [[0A]] 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(primes) = [[3A]] 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__primes) = [[3A]] 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__sieve(x_1)) = [[3A]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(from(x_1)) = [[1A]] + [[1A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(head(x_1)) = [[-I]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__head(x_1)) = [[-I]] + [[0A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(tail(x_1)) = [[1A]] + [[1A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__tail(x_1)) = [[1A]] + [[1A]] * x_1 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(a__filter(x_1, x_2)) = [[3A]] + [[0A]] * x_1 + [[0A]] * x_2 90.87/25.44 >>> 90.87/25.44 90.87/25.44 <<< 90.87/25.44 POL(0) = [[0A]] 90.87/25.44 >>> 90.87/25.44 90.87/25.44 90.87/25.44 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.87/25.44 90.87/25.44 mark(primes) -> a__primes 90.87/25.44 mark(sieve(X)) -> a__sieve(mark(X)) 90.87/25.44 mark(from(X)) -> a__from(mark(X)) 90.87/25.44 mark(head(X)) -> a__head(mark(X)) 90.87/25.44 a__head(cons(X, Y)) -> mark(X) 90.87/25.44 mark(tail(X)) -> a__tail(mark(X)) 90.87/25.44 a__tail(cons(X, Y)) -> mark(Y) 90.87/25.44 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.87/25.44 a__if(true, X, Y) -> mark(X) 90.87/25.44 a__if(false, X, Y) -> mark(Y) 90.87/25.44 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.87/25.44 mark(s(X)) -> s(mark(X)) 90.87/25.44 mark(0) -> 0 90.87/25.44 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.87/25.44 mark(true) -> true 90.87/25.44 mark(false) -> false 90.87/25.44 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.87/25.44 a__from(X) -> cons(mark(X), from(s(X))) 90.87/25.44 a__primes -> primes 90.87/25.44 a__primes -> a__sieve(a__from(s(s(0)))) 90.87/25.44 a__from(X) -> from(X) 90.87/25.44 a__sieve(X) -> sieve(X) 90.87/25.44 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.87/25.44 a__head(X) -> head(X) 90.87/25.44 a__tail(X) -> tail(X) 90.87/25.44 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.87/25.44 a__filter(X1, X2) -> filter(X1, X2) 90.87/25.44 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)))) 90.87/25.44 90.87/25.44 90.87/25.44 ---------------------------------------- 90.87/25.44 90.87/25.44 (28) 90.87/25.44 Obligation: 90.87/25.44 Q DP problem: 90.87/25.44 The TRS P consists of the following rules: 90.87/25.44 90.87/25.44 MARK(sieve(X)) -> A__SIEVE(mark(X)) 90.87/25.44 MARK(sieve(X)) -> MARK(X) 90.87/25.44 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.87/25.44 A__IF(true, X, Y) -> MARK(X) 90.87/25.44 MARK(if(X1, X2, X3)) -> MARK(X1) 90.87/25.44 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.87/25.44 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.87/25.44 MARK(filter(X1, X2)) -> MARK(X1) 90.87/25.44 MARK(filter(X1, X2)) -> MARK(X2) 90.87/25.44 MARK(s(X)) -> MARK(X) 90.87/25.44 MARK(cons(X1, X2)) -> MARK(X1) 90.87/25.44 MARK(divides(X1, X2)) -> MARK(X1) 90.87/25.44 MARK(divides(X1, X2)) -> MARK(X2) 90.87/25.44 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.87/25.44 A__IF(false, X, Y) -> MARK(Y) 90.87/25.44 90.87/25.44 The TRS R consists of the following rules: 90.87/25.44 90.87/25.44 a__primes -> a__sieve(a__from(s(s(0)))) 90.87/25.44 a__from(X) -> cons(mark(X), from(s(X))) 90.87/25.44 a__head(cons(X, Y)) -> mark(X) 90.87/25.44 a__tail(cons(X, Y)) -> mark(Y) 90.87/25.44 a__if(true, X, Y) -> mark(X) 90.87/25.44 a__if(false, X, Y) -> mark(Y) 90.87/25.44 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)))) 90.87/25.44 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.87/25.44 mark(primes) -> a__primes 90.87/25.44 mark(sieve(X)) -> a__sieve(mark(X)) 90.87/25.44 mark(from(X)) -> a__from(mark(X)) 90.87/25.44 mark(head(X)) -> a__head(mark(X)) 90.87/25.44 mark(tail(X)) -> a__tail(mark(X)) 90.87/25.44 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.87/25.44 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.87/25.44 mark(s(X)) -> s(mark(X)) 90.87/25.44 mark(0) -> 0 90.87/25.44 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.87/25.44 mark(true) -> true 90.87/25.44 mark(false) -> false 90.87/25.44 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.87/25.44 a__primes -> primes 90.87/25.44 a__sieve(X) -> sieve(X) 90.87/25.44 a__from(X) -> from(X) 90.87/25.44 a__head(X) -> head(X) 90.93/25.47 a__tail(X) -> tail(X) 90.93/25.47 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.47 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.47 90.93/25.47 The set Q consists of the following terms: 90.93/25.47 90.93/25.47 a__primes 90.93/25.47 a__from(x0) 90.93/25.47 mark(primes) 90.93/25.47 mark(sieve(x0)) 90.93/25.47 mark(from(x0)) 90.93/25.47 mark(head(x0)) 90.93/25.47 mark(tail(x0)) 90.93/25.47 mark(if(x0, x1, x2)) 90.93/25.47 mark(filter(x0, x1)) 90.93/25.47 mark(s(x0)) 90.93/25.47 mark(0) 90.93/25.47 mark(cons(x0, x1)) 90.93/25.47 mark(true) 90.93/25.47 mark(false) 90.93/25.47 mark(divides(x0, x1)) 90.93/25.47 a__sieve(x0) 90.93/25.47 a__head(x0) 90.93/25.47 a__tail(x0) 90.93/25.47 a__if(x0, x1, x2) 90.93/25.47 a__filter(x0, x1) 90.93/25.47 90.93/25.47 We have to consider all minimal (P,Q,R)-chains. 90.93/25.47 ---------------------------------------- 90.93/25.47 90.93/25.47 (29) DependencyGraphProof (EQUIVALENT) 90.93/25.47 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 90.93/25.47 ---------------------------------------- 90.93/25.47 90.93/25.47 (30) 90.93/25.47 Obligation: 90.93/25.47 Q DP problem: 90.93/25.47 The TRS P consists of the following rules: 90.93/25.47 90.93/25.47 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.93/25.47 A__IF(true, X, Y) -> MARK(X) 90.93/25.47 MARK(sieve(X)) -> MARK(X) 90.93/25.47 MARK(if(X1, X2, X3)) -> MARK(X1) 90.93/25.47 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.93/25.47 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.93/25.47 MARK(filter(X1, X2)) -> MARK(X1) 90.93/25.47 MARK(filter(X1, X2)) -> MARK(X2) 90.93/25.47 MARK(s(X)) -> MARK(X) 90.93/25.47 MARK(cons(X1, X2)) -> MARK(X1) 90.93/25.47 MARK(divides(X1, X2)) -> MARK(X1) 90.93/25.47 MARK(divides(X1, X2)) -> MARK(X2) 90.93/25.47 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.93/25.47 A__IF(false, X, Y) -> MARK(Y) 90.93/25.47 90.93/25.47 The TRS R consists of the following rules: 90.93/25.47 90.93/25.47 a__primes -> a__sieve(a__from(s(s(0)))) 90.93/25.47 a__from(X) -> cons(mark(X), from(s(X))) 90.93/25.47 a__head(cons(X, Y)) -> mark(X) 90.93/25.47 a__tail(cons(X, Y)) -> mark(Y) 90.93/25.47 a__if(true, X, Y) -> mark(X) 90.93/25.47 a__if(false, X, Y) -> mark(Y) 90.93/25.47 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)))) 90.93/25.47 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.93/25.47 mark(primes) -> a__primes 90.93/25.47 mark(sieve(X)) -> a__sieve(mark(X)) 90.93/25.47 mark(from(X)) -> a__from(mark(X)) 90.93/25.47 mark(head(X)) -> a__head(mark(X)) 90.93/25.47 mark(tail(X)) -> a__tail(mark(X)) 90.93/25.47 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.93/25.47 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.93/25.47 mark(s(X)) -> s(mark(X)) 90.93/25.47 mark(0) -> 0 90.93/25.47 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.93/25.47 mark(true) -> true 90.93/25.47 mark(false) -> false 90.93/25.47 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.93/25.47 a__primes -> primes 90.93/25.47 a__sieve(X) -> sieve(X) 90.93/25.47 a__from(X) -> from(X) 90.93/25.47 a__head(X) -> head(X) 90.93/25.47 a__tail(X) -> tail(X) 90.93/25.47 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.47 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.47 90.93/25.47 The set Q consists of the following terms: 90.93/25.47 90.93/25.47 a__primes 90.93/25.47 a__from(x0) 90.93/25.47 mark(primes) 90.93/25.47 mark(sieve(x0)) 90.93/25.47 mark(from(x0)) 90.93/25.47 mark(head(x0)) 90.93/25.47 mark(tail(x0)) 90.93/25.47 mark(if(x0, x1, x2)) 90.93/25.47 mark(filter(x0, x1)) 90.93/25.47 mark(s(x0)) 90.93/25.47 mark(0) 90.93/25.47 mark(cons(x0, x1)) 90.93/25.47 mark(true) 90.93/25.47 mark(false) 90.93/25.47 mark(divides(x0, x1)) 90.93/25.47 a__sieve(x0) 90.93/25.47 a__head(x0) 90.93/25.47 a__tail(x0) 90.93/25.47 a__if(x0, x1, x2) 90.93/25.47 a__filter(x0, x1) 90.93/25.47 90.93/25.47 We have to consider all minimal (P,Q,R)-chains. 90.93/25.47 ---------------------------------------- 90.93/25.47 90.93/25.47 (31) QDPOrderProof (EQUIVALENT) 90.93/25.47 We use the reduction pair processor [LPAR04,JAR06]. 90.93/25.47 90.93/25.47 90.93/25.47 The following pairs can be oriented strictly and are deleted. 90.93/25.47 90.93/25.47 MARK(sieve(X)) -> MARK(X) 90.93/25.47 The remaining pairs can at least be oriented weakly. 90.93/25.47 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(A__IF(x_1, x_2, x_3)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(true) = [[0A]] 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(sieve(x_1)) = [[1A]] + [[1A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(filter(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(A__FILTER(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(s(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(cons(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(false) = [[0A]] 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(primes) = [[2A]] 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(a__primes) = [[2A]] 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(a__sieve(x_1)) = [[1A]] + [[1A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(from(x_1)) = [[1A]] + [[1A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(head(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(a__head(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(a__if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(a__filter(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 90.93/25.47 >>> 90.93/25.47 90.93/25.47 <<< 90.93/25.47 POL(0) = [[0A]] 90.93/25.47 >>> 90.93/25.47 90.93/25.47 90.93/25.47 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.93/25.47 90.93/25.47 mark(primes) -> a__primes 90.93/25.47 mark(sieve(X)) -> a__sieve(mark(X)) 90.93/25.47 mark(from(X)) -> a__from(mark(X)) 90.93/25.47 mark(head(X)) -> a__head(mark(X)) 90.93/25.47 a__head(cons(X, Y)) -> mark(X) 90.93/25.47 mark(tail(X)) -> a__tail(mark(X)) 90.93/25.47 a__tail(cons(X, Y)) -> mark(Y) 90.93/25.47 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.93/25.47 a__if(true, X, Y) -> mark(X) 90.93/25.47 a__if(false, X, Y) -> mark(Y) 90.93/25.47 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.93/25.47 mark(s(X)) -> s(mark(X)) 90.93/25.47 mark(0) -> 0 90.93/25.47 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.93/25.47 mark(true) -> true 90.93/25.47 mark(false) -> false 90.93/25.47 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.93/25.47 a__from(X) -> cons(mark(X), from(s(X))) 90.93/25.47 a__primes -> primes 90.93/25.47 a__primes -> a__sieve(a__from(s(s(0)))) 90.93/25.47 a__from(X) -> from(X) 90.93/25.47 a__sieve(X) -> sieve(X) 90.93/25.47 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.93/25.47 a__head(X) -> head(X) 90.93/25.47 a__tail(X) -> tail(X) 90.93/25.47 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.47 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.47 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)))) 90.93/25.47 90.93/25.47 90.93/25.47 ---------------------------------------- 90.93/25.47 90.93/25.47 (32) 90.93/25.47 Obligation: 90.93/25.47 Q DP problem: 90.93/25.47 The TRS P consists of the following rules: 90.93/25.47 90.93/25.47 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.93/25.47 A__IF(true, X, Y) -> MARK(X) 90.93/25.47 MARK(if(X1, X2, X3)) -> MARK(X1) 90.93/25.47 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.93/25.47 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.93/25.47 MARK(filter(X1, X2)) -> MARK(X1) 90.93/25.47 MARK(filter(X1, X2)) -> MARK(X2) 90.93/25.47 MARK(s(X)) -> MARK(X) 90.93/25.47 MARK(cons(X1, X2)) -> MARK(X1) 90.93/25.47 MARK(divides(X1, X2)) -> MARK(X1) 90.93/25.47 MARK(divides(X1, X2)) -> MARK(X2) 90.93/25.47 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.93/25.47 A__IF(false, X, Y) -> MARK(Y) 90.93/25.47 90.93/25.47 The TRS R consists of the following rules: 90.93/25.47 90.93/25.47 a__primes -> a__sieve(a__from(s(s(0)))) 90.93/25.47 a__from(X) -> cons(mark(X), from(s(X))) 90.93/25.47 a__head(cons(X, Y)) -> mark(X) 90.93/25.47 a__tail(cons(X, Y)) -> mark(Y) 90.93/25.47 a__if(true, X, Y) -> mark(X) 90.93/25.47 a__if(false, X, Y) -> mark(Y) 90.93/25.47 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)))) 90.93/25.47 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.93/25.47 mark(primes) -> a__primes 90.93/25.47 mark(sieve(X)) -> a__sieve(mark(X)) 90.93/25.47 mark(from(X)) -> a__from(mark(X)) 90.93/25.47 mark(head(X)) -> a__head(mark(X)) 90.93/25.47 mark(tail(X)) -> a__tail(mark(X)) 90.93/25.47 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.93/25.47 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.93/25.47 mark(s(X)) -> s(mark(X)) 90.93/25.47 mark(0) -> 0 90.93/25.47 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.93/25.47 mark(true) -> true 90.93/25.47 mark(false) -> false 90.93/25.47 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.93/25.47 a__primes -> primes 90.93/25.47 a__sieve(X) -> sieve(X) 90.93/25.47 a__from(X) -> from(X) 90.93/25.47 a__head(X) -> head(X) 90.93/25.47 a__tail(X) -> tail(X) 90.93/25.47 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.47 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.47 90.93/25.47 The set Q consists of the following terms: 90.93/25.47 90.93/25.47 a__primes 90.93/25.47 a__from(x0) 90.93/25.47 mark(primes) 90.93/25.47 mark(sieve(x0)) 90.93/25.47 mark(from(x0)) 90.93/25.47 mark(head(x0)) 90.93/25.47 mark(tail(x0)) 90.93/25.47 mark(if(x0, x1, x2)) 90.93/25.47 mark(filter(x0, x1)) 90.93/25.47 mark(s(x0)) 90.93/25.47 mark(0) 90.93/25.47 mark(cons(x0, x1)) 90.93/25.47 mark(true) 90.93/25.48 mark(false) 90.93/25.48 mark(divides(x0, x1)) 90.93/25.48 a__sieve(x0) 90.93/25.48 a__head(x0) 90.93/25.48 a__tail(x0) 90.93/25.48 a__if(x0, x1, x2) 90.93/25.48 a__filter(x0, x1) 90.93/25.48 90.93/25.48 We have to consider all minimal (P,Q,R)-chains. 90.93/25.48 ---------------------------------------- 90.93/25.48 90.93/25.48 (33) QDPOrderProof (EQUIVALENT) 90.93/25.48 We use the reduction pair processor [LPAR04,JAR06]. 90.93/25.48 90.93/25.48 90.93/25.48 The following pairs can be oriented strictly and are deleted. 90.93/25.48 90.93/25.48 MARK(cons(X1, X2)) -> MARK(X1) 90.93/25.48 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(Y) 90.93/25.48 The remaining pairs can at least be oriented weakly. 90.93/25.48 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(MARK(x_1)) = [[2A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(A__IF(x_1, x_2, x_3)) = [[2A]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(mark(x_1)) = [[2A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(true) = [[0A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(A__FILTER(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(cons(x_1, x_2)) = [[3A]] + [[1A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(false) = [[0A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(primes) = [[3A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__primes) = [[3A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__sieve(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(from(x_1)) = [[3A]] + [[1A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__from(x_1)) = [[3A]] + [[1A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(head(x_1)) = [[4A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__head(x_1)) = [[4A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__if(x_1, x_2, x_3)) = [[2A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(0) = [[0A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 90.93/25.48 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.93/25.48 90.93/25.48 mark(primes) -> a__primes 90.93/25.48 mark(sieve(X)) -> a__sieve(mark(X)) 90.93/25.48 mark(from(X)) -> a__from(mark(X)) 90.93/25.48 mark(head(X)) -> a__head(mark(X)) 90.93/25.48 a__head(cons(X, Y)) -> mark(X) 90.93/25.48 mark(tail(X)) -> a__tail(mark(X)) 90.93/25.48 a__tail(cons(X, Y)) -> mark(Y) 90.93/25.48 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.93/25.48 a__if(true, X, Y) -> mark(X) 90.93/25.48 a__if(false, X, Y) -> mark(Y) 90.93/25.48 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.93/25.48 mark(s(X)) -> s(mark(X)) 90.93/25.48 mark(0) -> 0 90.93/25.48 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.93/25.48 mark(true) -> true 90.93/25.48 mark(false) -> false 90.93/25.48 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.93/25.48 a__from(X) -> cons(mark(X), from(s(X))) 90.93/25.48 a__primes -> primes 90.93/25.48 a__primes -> a__sieve(a__from(s(s(0)))) 90.93/25.48 a__from(X) -> from(X) 90.93/25.48 a__sieve(X) -> sieve(X) 90.93/25.48 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.93/25.48 a__head(X) -> head(X) 90.93/25.48 a__tail(X) -> tail(X) 90.93/25.48 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.48 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.48 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)))) 90.93/25.48 90.93/25.48 90.93/25.48 ---------------------------------------- 90.93/25.48 90.93/25.48 (34) 90.93/25.48 Obligation: 90.93/25.48 Q DP problem: 90.93/25.48 The TRS P consists of the following rules: 90.93/25.48 90.93/25.48 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.93/25.48 A__IF(true, X, Y) -> MARK(X) 90.93/25.48 MARK(if(X1, X2, X3)) -> MARK(X1) 90.93/25.48 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.93/25.48 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.93/25.48 MARK(filter(X1, X2)) -> MARK(X1) 90.93/25.48 MARK(filter(X1, X2)) -> MARK(X2) 90.93/25.48 MARK(s(X)) -> MARK(X) 90.93/25.48 MARK(divides(X1, X2)) -> MARK(X1) 90.93/25.48 MARK(divides(X1, X2)) -> MARK(X2) 90.93/25.48 A__IF(false, X, Y) -> MARK(Y) 90.93/25.48 90.93/25.48 The TRS R consists of the following rules: 90.93/25.48 90.93/25.48 a__primes -> a__sieve(a__from(s(s(0)))) 90.93/25.48 a__from(X) -> cons(mark(X), from(s(X))) 90.93/25.48 a__head(cons(X, Y)) -> mark(X) 90.93/25.48 a__tail(cons(X, Y)) -> mark(Y) 90.93/25.48 a__if(true, X, Y) -> mark(X) 90.93/25.48 a__if(false, X, Y) -> mark(Y) 90.93/25.48 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)))) 90.93/25.48 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.93/25.48 mark(primes) -> a__primes 90.93/25.48 mark(sieve(X)) -> a__sieve(mark(X)) 90.93/25.48 mark(from(X)) -> a__from(mark(X)) 90.93/25.48 mark(head(X)) -> a__head(mark(X)) 90.93/25.48 mark(tail(X)) -> a__tail(mark(X)) 90.93/25.48 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.93/25.48 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.93/25.48 mark(s(X)) -> s(mark(X)) 90.93/25.48 mark(0) -> 0 90.93/25.48 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.93/25.48 mark(true) -> true 90.93/25.48 mark(false) -> false 90.93/25.48 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.93/25.48 a__primes -> primes 90.93/25.48 a__sieve(X) -> sieve(X) 90.93/25.48 a__from(X) -> from(X) 90.93/25.48 a__head(X) -> head(X) 90.93/25.48 a__tail(X) -> tail(X) 90.93/25.48 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.48 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.48 90.93/25.48 The set Q consists of the following terms: 90.93/25.48 90.93/25.48 a__primes 90.93/25.48 a__from(x0) 90.93/25.48 mark(primes) 90.93/25.48 mark(sieve(x0)) 90.93/25.48 mark(from(x0)) 90.93/25.48 mark(head(x0)) 90.93/25.48 mark(tail(x0)) 90.93/25.48 mark(if(x0, x1, x2)) 90.93/25.48 mark(filter(x0, x1)) 90.93/25.48 mark(s(x0)) 90.93/25.48 mark(0) 90.93/25.48 mark(cons(x0, x1)) 90.93/25.48 mark(true) 90.93/25.48 mark(false) 90.93/25.48 mark(divides(x0, x1)) 90.93/25.48 a__sieve(x0) 90.93/25.48 a__head(x0) 90.93/25.48 a__tail(x0) 90.93/25.48 a__if(x0, x1, x2) 90.93/25.48 a__filter(x0, x1) 90.93/25.48 90.93/25.48 We have to consider all minimal (P,Q,R)-chains. 90.93/25.48 ---------------------------------------- 90.93/25.48 90.93/25.48 (35) QDPOrderProof (EQUIVALENT) 90.93/25.48 We use the reduction pair processor [LPAR04,JAR06]. 90.93/25.48 90.93/25.48 90.93/25.48 The following pairs can be oriented strictly and are deleted. 90.93/25.48 90.93/25.48 MARK(divides(X1, X2)) -> MARK(X2) 90.93/25.48 The remaining pairs can at least be oriented weakly. 90.93/25.48 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(MARK(x_1)) = [[1A]] + [[1A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(A__IF(x_1, x_2, x_3)) = [[1A]] + [[0A]] * x_1 + [[1A]] * x_2 + [[1A]] * x_3 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(true) = [[0A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(filter(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(A__FILTER(x_1, x_2)) = [[0A]] + [[1A]] * x_1 + [[1A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(cons(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(divides(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[1A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(false) = [[0A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(primes) = [[1A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__primes) = [[1A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(from(x_1)) = [[1A]] + [[1A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(head(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__head(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__if(x_1, x_2, x_3)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__filter(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(0) = [[0A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 90.93/25.48 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.93/25.48 90.93/25.48 mark(primes) -> a__primes 90.93/25.48 mark(sieve(X)) -> a__sieve(mark(X)) 90.93/25.48 mark(from(X)) -> a__from(mark(X)) 90.93/25.48 mark(head(X)) -> a__head(mark(X)) 90.93/25.48 a__head(cons(X, Y)) -> mark(X) 90.93/25.48 mark(tail(X)) -> a__tail(mark(X)) 90.93/25.48 a__tail(cons(X, Y)) -> mark(Y) 90.93/25.48 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.93/25.48 a__if(true, X, Y) -> mark(X) 90.93/25.48 a__if(false, X, Y) -> mark(Y) 90.93/25.48 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.93/25.48 mark(s(X)) -> s(mark(X)) 90.93/25.48 mark(0) -> 0 90.93/25.48 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.93/25.48 mark(true) -> true 90.93/25.48 mark(false) -> false 90.93/25.48 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.93/25.48 a__from(X) -> cons(mark(X), from(s(X))) 90.93/25.48 a__primes -> primes 90.93/25.48 a__primes -> a__sieve(a__from(s(s(0)))) 90.93/25.48 a__from(X) -> from(X) 90.93/25.48 a__sieve(X) -> sieve(X) 90.93/25.48 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.93/25.48 a__head(X) -> head(X) 90.93/25.48 a__tail(X) -> tail(X) 90.93/25.48 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.48 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.48 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)))) 90.93/25.48 90.93/25.48 90.93/25.48 ---------------------------------------- 90.93/25.48 90.93/25.48 (36) 90.93/25.48 Obligation: 90.93/25.48 Q DP problem: 90.93/25.48 The TRS P consists of the following rules: 90.93/25.48 90.93/25.48 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.93/25.48 A__IF(true, X, Y) -> MARK(X) 90.93/25.48 MARK(if(X1, X2, X3)) -> MARK(X1) 90.93/25.48 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.93/25.48 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.93/25.48 MARK(filter(X1, X2)) -> MARK(X1) 90.93/25.48 MARK(filter(X1, X2)) -> MARK(X2) 90.93/25.48 MARK(s(X)) -> MARK(X) 90.93/25.48 MARK(divides(X1, X2)) -> MARK(X1) 90.93/25.48 A__IF(false, X, Y) -> MARK(Y) 90.93/25.48 90.93/25.48 The TRS R consists of the following rules: 90.93/25.48 90.93/25.48 a__primes -> a__sieve(a__from(s(s(0)))) 90.93/25.48 a__from(X) -> cons(mark(X), from(s(X))) 90.93/25.48 a__head(cons(X, Y)) -> mark(X) 90.93/25.48 a__tail(cons(X, Y)) -> mark(Y) 90.93/25.48 a__if(true, X, Y) -> mark(X) 90.93/25.48 a__if(false, X, Y) -> mark(Y) 90.93/25.48 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)))) 90.93/25.48 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.93/25.48 mark(primes) -> a__primes 90.93/25.48 mark(sieve(X)) -> a__sieve(mark(X)) 90.93/25.48 mark(from(X)) -> a__from(mark(X)) 90.93/25.48 mark(head(X)) -> a__head(mark(X)) 90.93/25.48 mark(tail(X)) -> a__tail(mark(X)) 90.93/25.48 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.93/25.48 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.93/25.48 mark(s(X)) -> s(mark(X)) 90.93/25.48 mark(0) -> 0 90.93/25.48 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.93/25.48 mark(true) -> true 90.93/25.48 mark(false) -> false 90.93/25.48 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.93/25.48 a__primes -> primes 90.93/25.48 a__sieve(X) -> sieve(X) 90.93/25.48 a__from(X) -> from(X) 90.93/25.48 a__head(X) -> head(X) 90.93/25.48 a__tail(X) -> tail(X) 90.93/25.48 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.48 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.48 90.93/25.48 The set Q consists of the following terms: 90.93/25.48 90.93/25.48 a__primes 90.93/25.48 a__from(x0) 90.93/25.48 mark(primes) 90.93/25.48 mark(sieve(x0)) 90.93/25.48 mark(from(x0)) 90.93/25.48 mark(head(x0)) 90.93/25.48 mark(tail(x0)) 90.93/25.48 mark(if(x0, x1, x2)) 90.93/25.48 mark(filter(x0, x1)) 90.93/25.48 mark(s(x0)) 90.93/25.48 mark(0) 90.93/25.48 mark(cons(x0, x1)) 90.93/25.48 mark(true) 90.93/25.48 mark(false) 90.93/25.48 mark(divides(x0, x1)) 90.93/25.48 a__sieve(x0) 90.93/25.48 a__head(x0) 90.93/25.48 a__tail(x0) 90.93/25.48 a__if(x0, x1, x2) 90.93/25.48 a__filter(x0, x1) 90.93/25.48 90.93/25.48 We have to consider all minimal (P,Q,R)-chains. 90.93/25.48 ---------------------------------------- 90.93/25.48 90.93/25.48 (37) QDPOrderProof (EQUIVALENT) 90.93/25.48 We use the reduction pair processor [LPAR04,JAR06]. 90.93/25.48 90.93/25.48 90.93/25.48 The following pairs can be oriented strictly and are deleted. 90.93/25.48 90.93/25.48 A__FILTER(s(s(X)), cons(Y, Z)) -> MARK(X) 90.93/25.48 MARK(filter(X1, X2)) -> MARK(X1) 90.93/25.48 The remaining pairs can at least be oriented weakly. 90.93/25.48 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(A__IF(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(true) = [[0A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(filter(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(A__FILTER(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(cons(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(divides(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[-I]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(false) = [[0A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(primes) = [[1A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__primes) = [[1A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__sieve(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(from(x_1)) = [[0A]] + [[1A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__from(x_1)) = [[0A]] + [[1A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(head(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__head(x_1)) = [[-I]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(tail(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__tail(x_1)) = [[0A]] + [[0A]] * x_1 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__if(x_1, x_2, x_3)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(a__filter(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 90.93/25.48 >>> 90.93/25.48 90.93/25.48 <<< 90.93/25.48 POL(0) = [[0A]] 90.93/25.48 >>> 90.93/25.48 90.93/25.48 90.93/25.48 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 90.93/25.48 90.93/25.48 mark(primes) -> a__primes 90.93/25.48 mark(sieve(X)) -> a__sieve(mark(X)) 90.93/25.48 mark(from(X)) -> a__from(mark(X)) 90.93/25.48 mark(head(X)) -> a__head(mark(X)) 90.93/25.48 a__head(cons(X, Y)) -> mark(X) 90.93/25.48 mark(tail(X)) -> a__tail(mark(X)) 90.93/25.48 a__tail(cons(X, Y)) -> mark(Y) 90.93/25.48 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.93/25.48 a__if(true, X, Y) -> mark(X) 90.93/25.48 a__if(false, X, Y) -> mark(Y) 90.93/25.48 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.93/25.48 mark(s(X)) -> s(mark(X)) 90.93/25.48 mark(0) -> 0 90.93/25.48 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.93/25.48 mark(true) -> true 90.93/25.48 mark(false) -> false 90.93/25.48 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.93/25.48 a__from(X) -> cons(mark(X), from(s(X))) 90.93/25.48 a__primes -> primes 90.93/25.48 a__primes -> a__sieve(a__from(s(s(0)))) 90.93/25.48 a__from(X) -> from(X) 90.93/25.48 a__sieve(X) -> sieve(X) 90.93/25.48 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.93/25.48 a__head(X) -> head(X) 90.93/25.48 a__tail(X) -> tail(X) 90.93/25.48 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.48 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.48 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)))) 90.93/25.48 90.93/25.48 90.93/25.48 ---------------------------------------- 90.93/25.48 90.93/25.48 (38) 90.93/25.48 Obligation: 90.93/25.48 Q DP problem: 90.93/25.48 The TRS P consists of the following rules: 90.93/25.48 90.93/25.48 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.93/25.48 A__IF(true, X, Y) -> MARK(X) 90.93/25.48 MARK(if(X1, X2, X3)) -> MARK(X1) 90.93/25.48 MARK(filter(X1, X2)) -> A__FILTER(mark(X1), mark(X2)) 90.93/25.48 MARK(filter(X1, X2)) -> MARK(X2) 90.93/25.48 MARK(s(X)) -> MARK(X) 90.93/25.48 MARK(divides(X1, X2)) -> MARK(X1) 90.93/25.48 A__IF(false, X, Y) -> MARK(Y) 90.93/25.48 90.93/25.48 The TRS R consists of the following rules: 90.93/25.48 90.93/25.48 a__primes -> a__sieve(a__from(s(s(0)))) 90.93/25.48 a__from(X) -> cons(mark(X), from(s(X))) 90.93/25.48 a__head(cons(X, Y)) -> mark(X) 90.93/25.48 a__tail(cons(X, Y)) -> mark(Y) 90.93/25.48 a__if(true, X, Y) -> mark(X) 90.93/25.48 a__if(false, X, Y) -> mark(Y) 90.93/25.48 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)))) 90.93/25.48 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.93/25.48 mark(primes) -> a__primes 90.93/25.48 mark(sieve(X)) -> a__sieve(mark(X)) 90.93/25.48 mark(from(X)) -> a__from(mark(X)) 90.93/25.48 mark(head(X)) -> a__head(mark(X)) 90.93/25.48 mark(tail(X)) -> a__tail(mark(X)) 90.93/25.48 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.93/25.48 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.93/25.48 mark(s(X)) -> s(mark(X)) 90.93/25.48 mark(0) -> 0 90.93/25.48 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.93/25.48 mark(true) -> true 90.93/25.48 mark(false) -> false 90.93/25.48 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.93/25.48 a__primes -> primes 90.93/25.48 a__sieve(X) -> sieve(X) 90.93/25.48 a__from(X) -> from(X) 90.93/25.48 a__head(X) -> head(X) 90.93/25.48 a__tail(X) -> tail(X) 90.93/25.48 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.48 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.48 90.93/25.48 The set Q consists of the following terms: 90.93/25.48 90.93/25.48 a__primes 90.93/25.48 a__from(x0) 90.93/25.48 mark(primes) 90.93/25.48 mark(sieve(x0)) 90.93/25.48 mark(from(x0)) 90.93/25.48 mark(head(x0)) 90.93/25.48 mark(tail(x0)) 90.93/25.48 mark(if(x0, x1, x2)) 90.93/25.48 mark(filter(x0, x1)) 90.93/25.48 mark(s(x0)) 90.93/25.48 mark(0) 90.93/25.48 mark(cons(x0, x1)) 90.93/25.48 mark(true) 90.93/25.48 mark(false) 90.93/25.48 mark(divides(x0, x1)) 90.93/25.48 a__sieve(x0) 90.93/25.48 a__head(x0) 90.93/25.48 a__tail(x0) 90.93/25.48 a__if(x0, x1, x2) 90.93/25.48 a__filter(x0, x1) 90.93/25.48 90.93/25.48 We have to consider all minimal (P,Q,R)-chains. 90.93/25.48 ---------------------------------------- 90.93/25.48 90.93/25.48 (39) DependencyGraphProof (EQUIVALENT) 90.93/25.48 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 90.93/25.48 ---------------------------------------- 90.93/25.48 90.93/25.48 (40) 90.93/25.48 Obligation: 90.93/25.48 Q DP problem: 90.93/25.48 The TRS P consists of the following rules: 90.93/25.48 90.93/25.48 A__IF(true, X, Y) -> MARK(X) 90.93/25.49 MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.93/25.49 A__IF(false, X, Y) -> MARK(Y) 90.93/25.49 MARK(if(X1, X2, X3)) -> MARK(X1) 90.93/25.49 MARK(filter(X1, X2)) -> MARK(X2) 90.93/25.49 MARK(s(X)) -> MARK(X) 90.93/25.49 MARK(divides(X1, X2)) -> MARK(X1) 90.93/25.49 90.93/25.49 The TRS R consists of the following rules: 90.93/25.49 90.93/25.49 a__primes -> a__sieve(a__from(s(s(0)))) 90.93/25.49 a__from(X) -> cons(mark(X), from(s(X))) 90.93/25.49 a__head(cons(X, Y)) -> mark(X) 90.93/25.49 a__tail(cons(X, Y)) -> mark(Y) 90.93/25.49 a__if(true, X, Y) -> mark(X) 90.93/25.49 a__if(false, X, Y) -> mark(Y) 90.93/25.49 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)))) 90.93/25.49 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 90.93/25.49 mark(primes) -> a__primes 90.93/25.49 mark(sieve(X)) -> a__sieve(mark(X)) 90.93/25.49 mark(from(X)) -> a__from(mark(X)) 90.93/25.49 mark(head(X)) -> a__head(mark(X)) 90.93/25.49 mark(tail(X)) -> a__tail(mark(X)) 90.93/25.49 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 90.93/25.49 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 90.93/25.49 mark(s(X)) -> s(mark(X)) 90.93/25.49 mark(0) -> 0 90.93/25.49 mark(cons(X1, X2)) -> cons(mark(X1), X2) 90.93/25.49 mark(true) -> true 90.93/25.49 mark(false) -> false 90.93/25.49 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 90.93/25.49 a__primes -> primes 90.93/25.49 a__sieve(X) -> sieve(X) 90.93/25.49 a__from(X) -> from(X) 90.93/25.49 a__head(X) -> head(X) 90.93/25.49 a__tail(X) -> tail(X) 90.93/25.49 a__if(X1, X2, X3) -> if(X1, X2, X3) 90.93/25.49 a__filter(X1, X2) -> filter(X1, X2) 90.93/25.49 90.93/25.49 The set Q consists of the following terms: 90.93/25.49 90.93/25.49 a__primes 90.93/25.49 a__from(x0) 90.93/25.49 mark(primes) 90.93/25.49 mark(sieve(x0)) 90.93/25.49 mark(from(x0)) 90.93/25.49 mark(head(x0)) 90.93/25.49 mark(tail(x0)) 90.93/25.49 mark(if(x0, x1, x2)) 90.93/25.49 mark(filter(x0, x1)) 90.93/25.49 mark(s(x0)) 90.93/25.49 mark(0) 90.93/25.49 mark(cons(x0, x1)) 90.93/25.49 mark(true) 90.93/25.49 mark(false) 90.93/25.49 mark(divides(x0, x1)) 90.93/25.49 a__sieve(x0) 90.93/25.49 a__head(x0) 90.93/25.49 a__tail(x0) 90.93/25.49 a__if(x0, x1, x2) 90.93/25.49 a__filter(x0, x1) 90.93/25.49 90.93/25.49 We have to consider all minimal (P,Q,R)-chains. 90.93/25.49 ---------------------------------------- 90.93/25.49 90.93/25.49 (41) QDPSizeChangeProof (EQUIVALENT) 90.93/25.49 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. 90.93/25.49 90.93/25.49 From the DPs we obtained the following set of size-change graphs: 90.93/25.49 *MARK(if(X1, X2, X3)) -> A__IF(mark(X1), X2, X3) 90.93/25.49 The graph contains the following edges 1 > 2, 1 > 3 90.93/25.49 90.93/25.49 90.93/25.49 *MARK(if(X1, X2, X3)) -> MARK(X1) 90.93/25.49 The graph contains the following edges 1 > 1 90.93/25.49 90.93/25.49 90.93/25.49 *MARK(filter(X1, X2)) -> MARK(X2) 90.93/25.49 The graph contains the following edges 1 > 1 90.93/25.49 90.93/25.49 90.93/25.49 *MARK(s(X)) -> MARK(X) 90.93/25.49 The graph contains the following edges 1 > 1 90.93/25.49 90.93/25.49 90.93/25.49 *MARK(divides(X1, X2)) -> MARK(X1) 90.93/25.49 The graph contains the following edges 1 > 1 90.93/25.49 90.93/25.49 90.93/25.49 *A__IF(true, X, Y) -> MARK(X) 90.93/25.49 The graph contains the following edges 2 >= 1 90.93/25.49 90.93/25.49 90.93/25.49 *A__IF(false, X, Y) -> MARK(Y) 90.93/25.49 The graph contains the following edges 3 >= 1 90.93/25.49 90.93/25.49 90.93/25.49 ---------------------------------------- 90.93/25.49 90.93/25.49 (42) 90.93/25.49 YES 91.19/25.56 EOF