0.00/0.51 MAYBE 0.00/0.51 0.00/0.51 DP problem for innermost termination. 0.00/0.51 P = 0.00/0.51 isdiv#(x, y) -> isdiv#(x, y - x) [y >= x && x > 0] 0.00/0.51 if#(false, I3, I4, zs) -> filter#(I3, zs) 0.00/0.51 if#(true, I5, I6, B0) -> filter#(I5, B0) 0.00/0.51 filter#(I7, cons(I8, B1)) -> if#(isdiv(I7, I8), I7, I8, B1) 0.00/0.51 filter#(I7, cons(I8, B1)) -> isdiv#(I7, I8) 0.00/0.51 sieve#(cons(I10, ys)) -> sieve#(filter(I10, ys)) 0.00/0.51 sieve#(cons(I10, ys)) -> filter#(I10, ys) 0.00/0.51 nats#(I11, I12) -> nats#(I11 + 1, I12) [I12 >= I11] 0.00/0.51 primes#(I15) -> sieve#(nats(2, I15)) 0.00/0.51 primes#(I15) -> nats#(2, I15) 0.00/0.51 R = 0.00/0.51 isdiv(x, y) -> isdiv(x, y - x) [y >= x && x > 0] 0.00/0.51 isdiv(I0, I1) -> false [I0 > I1 && I1 > 0] 0.00/0.51 isdiv(I2, 0) -> true [I2 > 0] 0.00/0.51 if(false, I3, I4, zs) -> cons(I4, filter(I3, zs)) 0.00/0.51 if(true, I5, I6, B0) -> filter(I5, B0) 0.00/0.51 filter(I7, cons(I8, B1)) -> if(isdiv(I7, I8), I7, I8, B1) 0.00/0.51 filter(I9, nil) -> nil 0.00/0.51 sieve(cons(I10, ys)) -> cons(I10, sieve(filter(I10, ys))) 0.00/0.51 sieve(nil) -> nil 0.00/0.51 nats(I11, I12) -> cons(I11, nats(I11 + 1, I12)) [I12 >= I11] 0.00/0.51 nats(I13, I14) -> nil [I13 > I14] 0.00/0.51 primes(I15) -> sieve(nats(2, I15)) 0.00/0.51 0.00/0.51 The dependency graph for this problem is: 0.00/0.51 0 -> 0 0.00/0.51 1 -> 3, 4 0.00/0.51 2 -> 3, 4 0.00/0.51 3 -> 1, 2 0.00/0.51 4 -> 0 0.00/0.51 5 -> 5, 6 0.00/0.51 6 -> 3, 4 0.00/0.51 7 -> 7 0.00/0.51 8 -> 5, 6 0.00/0.51 9 -> 7 0.00/0.51 Where: 0.00/0.51 0) isdiv#(x, y) -> isdiv#(x, y - x) [y >= x && x > 0] 0.00/0.51 1) if#(false, I3, I4, zs) -> filter#(I3, zs) 0.00/0.51 2) if#(true, I5, I6, B0) -> filter#(I5, B0) 0.00/0.51 3) filter#(I7, cons(I8, B1)) -> if#(isdiv(I7, I8), I7, I8, B1) 0.00/0.51 4) filter#(I7, cons(I8, B1)) -> isdiv#(I7, I8) 0.00/0.51 5) sieve#(cons(I10, ys)) -> sieve#(filter(I10, ys)) 0.00/0.51 6) sieve#(cons(I10, ys)) -> filter#(I10, ys) 0.00/0.51 7) nats#(I11, I12) -> nats#(I11 + 1, I12) [I12 >= I11] 0.00/0.51 8) primes#(I15) -> sieve#(nats(2, I15)) 0.00/0.51 9) primes#(I15) -> nats#(2, I15) 0.00/0.51 0.00/0.51 We have the following SCCs. 0.00/0.51 { 5 } 0.00/0.51 { 1, 2, 3 } 0.00/0.51 { 0 } 0.00/0.51 { 7 } 0.00/0.51 0.00/0.51 DP problem for innermost termination. 0.00/0.51 P = 0.00/0.51 nats#(I11, I12) -> nats#(I11 + 1, I12) [I12 >= I11] 0.00/0.51 R = 0.00/0.51 isdiv(x, y) -> isdiv(x, y - x) [y >= x && x > 0] 0.00/0.51 isdiv(I0, I1) -> false [I0 > I1 && I1 > 0] 0.00/0.51 isdiv(I2, 0) -> true [I2 > 0] 0.00/0.51 if(false, I3, I4, zs) -> cons(I4, filter(I3, zs)) 0.00/0.51 if(true, I5, I6, B0) -> filter(I5, B0) 0.00/0.51 filter(I7, cons(I8, B1)) -> if(isdiv(I7, I8), I7, I8, B1) 0.00/0.51 filter(I9, nil) -> nil 0.00/0.51 sieve(cons(I10, ys)) -> cons(I10, sieve(filter(I10, ys))) 0.00/0.51 sieve(nil) -> nil 0.00/0.51 nats(I11, I12) -> cons(I11, nats(I11 + 1, I12)) [I12 >= I11] 0.00/0.51 nats(I13, I14) -> nil [I13 > I14] 0.00/0.51 primes(I15) -> sieve(nats(2, I15)) 0.00/0.51 0.00/0.51 We use the reverse value criterion with the projection function NU: 0.00/0.51 NU[nats#(z1,z2)] = z2 + -1 * z1 0.00/0.51 0.00/0.51 This gives the following inequalities: 0.00/0.51 I12 >= I11 ==> I12 + -1 * I11 > I12 + -1 * (I11 + 1) with I12 + -1 * I11 >= 0 0.00/0.51 0.00/0.51 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed. 0.00/0.51 0.00/0.51 DP problem for innermost termination. 0.00/0.51 P = 0.00/0.51 isdiv#(x, y) -> isdiv#(x, y - x) [y >= x && x > 0] 0.00/0.51 R = 0.00/0.51 isdiv(x, y) -> isdiv(x, y - x) [y >= x && x > 0] 0.00/0.51 isdiv(I0, I1) -> false [I0 > I1 && I1 > 0] 0.00/0.51 isdiv(I2, 0) -> true [I2 > 0] 0.00/0.51 if(false, I3, I4, zs) -> cons(I4, filter(I3, zs)) 0.00/0.51 if(true, I5, I6, B0) -> filter(I5, B0) 0.00/0.51 filter(I7, cons(I8, B1)) -> if(isdiv(I7, I8), I7, I8, B1) 0.00/0.51 filter(I9, nil) -> nil 0.00/0.51 sieve(cons(I10, ys)) -> cons(I10, sieve(filter(I10, ys))) 0.00/0.51 sieve(nil) -> nil 0.00/0.51 nats(I11, I12) -> cons(I11, nats(I11 + 1, I12)) [I12 >= I11] 0.00/0.51 nats(I13, I14) -> nil [I13 > I14] 0.00/0.51 primes(I15) -> sieve(nats(2, I15)) 0.00/0.51 0.00/0.51 We use the reverse value criterion with the projection function NU: 0.00/0.51 NU[isdiv#(z1,z2)] = z2 + -1 * z1 0.00/0.51 0.00/0.51 This gives the following inequalities: 0.00/0.51 y >= x && x > 0 ==> y + -1 * x > y - x + -1 * x with y + -1 * x >= 0 0.00/0.51 0.00/0.51 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed. 0.00/0.51 0.00/0.51 DP problem for innermost termination. 0.00/0.51 P = 0.00/0.51 if#(false, I3, I4, zs) -> filter#(I3, zs) 0.00/0.51 if#(true, I5, I6, B0) -> filter#(I5, B0) 0.00/0.51 filter#(I7, cons(I8, B1)) -> if#(isdiv(I7, I8), I7, I8, B1) 0.00/0.51 R = 0.00/0.51 isdiv(x, y) -> isdiv(x, y - x) [y >= x && x > 0] 0.00/0.51 isdiv(I0, I1) -> false [I0 > I1 && I1 > 0] 0.00/0.51 isdiv(I2, 0) -> true [I2 > 0] 0.00/0.51 if(false, I3, I4, zs) -> cons(I4, filter(I3, zs)) 0.00/0.51 if(true, I5, I6, B0) -> filter(I5, B0) 0.00/0.51 filter(I7, cons(I8, B1)) -> if(isdiv(I7, I8), I7, I8, B1) 0.00/0.51 filter(I9, nil) -> nil 0.00/0.51 sieve(cons(I10, ys)) -> cons(I10, sieve(filter(I10, ys))) 0.00/0.51 sieve(nil) -> nil 0.00/0.51 nats(I11, I12) -> cons(I11, nats(I11 + 1, I12)) [I12 >= I11] 0.00/0.51 nats(I13, I14) -> nil [I13 > I14] 0.00/0.51 primes(I15) -> sieve(nats(2, I15)) 0.00/0.51 0.00/0.51 We use the subterm criterion with the projection function NU: 0.00/0.51 NU[if#(x0,x1,x2,x3)] = x3 0.00/0.51 NU[filter#(x0,x1)] = x1 0.00/0.51 0.00/0.51 This gives the following inequalities: 0.00/0.51 zs = zs 0.00/0.51 B0 = B0 0.00/0.51 cons(I8, B1) |> B1 0.00/0.51 0.00/0.51 We remove all the strictly oriented dependency pairs. 0.00/0.51 0.00/0.51 DP problem for innermost termination. 0.00/0.51 P = 0.00/0.51 if#(false, I3, I4, zs) -> filter#(I3, zs) 0.00/0.51 if#(true, I5, I6, B0) -> filter#(I5, B0) 0.00/0.51 R = 0.00/0.51 isdiv(x, y) -> isdiv(x, y - x) [y >= x && x > 0] 0.00/0.51 isdiv(I0, I1) -> false [I0 > I1 && I1 > 0] 0.00/0.51 isdiv(I2, 0) -> true [I2 > 0] 0.00/0.51 if(false, I3, I4, zs) -> cons(I4, filter(I3, zs)) 0.00/0.51 if(true, I5, I6, B0) -> filter(I5, B0) 0.00/0.51 filter(I7, cons(I8, B1)) -> if(isdiv(I7, I8), I7, I8, B1) 0.00/0.51 filter(I9, nil) -> nil 0.00/0.51 sieve(cons(I10, ys)) -> cons(I10, sieve(filter(I10, ys))) 0.00/0.51 sieve(nil) -> nil 0.00/0.51 nats(I11, I12) -> cons(I11, nats(I11 + 1, I12)) [I12 >= I11] 0.00/0.51 nats(I13, I14) -> nil [I13 > I14] 0.00/0.51 primes(I15) -> sieve(nats(2, I15)) 0.00/0.51 0.00/0.51 The dependency graph for this problem is: 0.00/0.51 1 -> 0.00/0.51 2 -> 0.00/0.51 Where: 0.00/0.51 1) if#(false, I3, I4, zs) -> filter#(I3, zs) 0.00/0.51 2) if#(true, I5, I6, B0) -> filter#(I5, B0) 0.00/0.51 0.00/0.51 We have the following SCCs. 0.00/0.51 0.00/0.51 0.00/0.51 DP problem for innermost termination. 0.00/0.51 P = 0.00/0.51 sieve#(cons(I10, ys)) -> sieve#(filter(I10, ys)) 0.00/0.51 R = 0.00/0.51 isdiv(x, y) -> isdiv(x, y - x) [y >= x && x > 0] 0.00/0.51 isdiv(I0, I1) -> false [I0 > I1 && I1 > 0] 0.00/0.51 isdiv(I2, 0) -> true [I2 > 0] 0.00/0.51 if(false, I3, I4, zs) -> cons(I4, filter(I3, zs)) 0.00/0.51 if(true, I5, I6, B0) -> filter(I5, B0) 0.00/0.51 filter(I7, cons(I8, B1)) -> if(isdiv(I7, I8), I7, I8, B1) 0.00/0.51 filter(I9, nil) -> nil 0.00/0.51 sieve(cons(I10, ys)) -> cons(I10, sieve(filter(I10, ys))) 0.00/0.51 sieve(nil) -> nil 0.00/0.51 nats(I11, I12) -> cons(I11, nats(I11 + 1, I12)) [I12 >= I11] 0.00/0.51 nats(I13, I14) -> nil [I13 > I14] 0.00/0.51 primes(I15) -> sieve(nats(2, I15)) 0.00/0.51 0.00/3.49 EOF