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