/export/starexec/sandbox/solver/bin/starexec_run_Itrs /export/starexec/sandbox/benchmark/theBenchmark.itrs /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE DP problem for innermost termination. P = isdiv#(x, y) -> isdiv#(0 - x, y) [0 > x] isdiv#(I0, I1) -> isdiv#(I0, 0 - I1) [0 > I1] isdiv#(I2, I3) -> isdiv#(I2, 0 - I2 + I3) [I3 >= I2 && I2 > 0] if_2#(false, I7, I8, zs) -> filter#(I7, zs) filter#(I9, cons(I10, B0)) -> if_2#(isdiv(I9, I10), I9, I10, B0) filter#(I9, cons(I10, B0)) -> isdiv#(I9, I10) if_1#(true, I11, I12, B1) -> filter#(I11, B1) filter#(I13, cons(I14, B2)) -> if_1#(isdiv(I13, I14), I13, I14, B2) filter#(I13, cons(I14, B2)) -> isdiv#(I13, I14) sieve#(cons(I16, ys)) -> sieve#(filter(I16, ys)) sieve#(cons(I16, ys)) -> filter#(I16, ys) nats#(I17, I18) -> nats#(I17 + 1, I18) [I18 > I17] primes#(I23) -> sieve#(nats(2, I23)) primes#(I23) -> nats#(2, I23) mem#(I24, cons(I25, B3)) -> mem#(I24, B3) [I24 > I25] mem#(I26, cons(I27, B4)) -> mem#(I26, B4) [I27 > I26] isprime#(I31) -> mem#(I31, primes(I31)) isprime#(I31) -> primes#(I31) R = isdiv(x, y) -> isdiv(0 - x, y) [0 > x] isdiv(I0, I1) -> isdiv(I0, 0 - I1) [0 > I1] isdiv(I2, I3) -> isdiv(I2, 0 - I2 + I3) [I3 >= I2 && I2 > 0] isdiv(I4, I5) -> false [I4 > I5 && I5 > 0] isdiv(I6, 0) -> true [I6 > 0] if_2(false, I7, I8, zs) -> cons(I7, filter(I7, zs)) filter(I9, cons(I10, B0)) -> if_2(isdiv(I9, I10), I9, I10, B0) if_1(true, I11, I12, B1) -> filter(I11, B1) filter(I13, cons(I14, B2)) -> if_1(isdiv(I13, I14), I13, I14, B2) filter(I15, nil) -> nil sieve(cons(I16, ys)) -> cons(I16, sieve(filter(I16, ys))) sieve(nil) -> nil nats(I17, I18) -> cons(I17, nats(I17 + 1, I18)) [I18 > I17] nats(I19, I20) -> cons(I19, nil) [I19 = I20] nats(I21, I22) -> nil [I21 > I22] primes(I23) -> sieve(nats(2, I23)) mem(I24, cons(I25, B3)) -> mem(I24, B3) [I24 > I25] mem(I26, cons(I27, B4)) -> mem(I26, B4) [I27 > I26] mem(I28, cons(I29, B5)) -> true [I28 = I29] mem(I30, nil) -> false isprime(I31) -> mem(I31, primes(I31)) The dependency graph for this problem is: 0 -> 1, 2 1 -> 0, 2 2 -> 2 3 -> 4, 5, 7, 8 4 -> 3 5 -> 0, 1, 2 6 -> 4, 5, 7, 8 7 -> 6 8 -> 0, 1, 2 9 -> 9, 10 10 -> 4, 5, 7, 8 11 -> 11 12 -> 9, 10 13 -> 11 14 -> 14, 15 15 -> 14, 15 16 -> 14, 15 17 -> 12, 13 Where: 0) isdiv#(x, y) -> isdiv#(0 - x, y) [0 > x] 1) isdiv#(I0, I1) -> isdiv#(I0, 0 - I1) [0 > I1] 2) isdiv#(I2, I3) -> isdiv#(I2, 0 - I2 + I3) [I3 >= I2 && I2 > 0] 3) if_2#(false, I7, I8, zs) -> filter#(I7, zs) 4) filter#(I9, cons(I10, B0)) -> if_2#(isdiv(I9, I10), I9, I10, B0) 5) filter#(I9, cons(I10, B0)) -> isdiv#(I9, I10) 6) if_1#(true, I11, I12, B1) -> filter#(I11, B1) 7) filter#(I13, cons(I14, B2)) -> if_1#(isdiv(I13, I14), I13, I14, B2) 8) filter#(I13, cons(I14, B2)) -> isdiv#(I13, I14) 9) sieve#(cons(I16, ys)) -> sieve#(filter(I16, ys)) 10) sieve#(cons(I16, ys)) -> filter#(I16, ys) 11) nats#(I17, I18) -> nats#(I17 + 1, I18) [I18 > I17] 12) primes#(I23) -> sieve#(nats(2, I23)) 13) primes#(I23) -> nats#(2, I23) 14) mem#(I24, cons(I25, B3)) -> mem#(I24, B3) [I24 > I25] 15) mem#(I26, cons(I27, B4)) -> mem#(I26, B4) [I27 > I26] 16) isprime#(I31) -> mem#(I31, primes(I31)) 17) isprime#(I31) -> primes#(I31) We have the following SCCs. { 14, 15 } { 11 } { 9 } { 3, 4, 6, 7 } { 0, 1 } { 2 } DP problem for innermost termination. P = isdiv#(I2, I3) -> isdiv#(I2, 0 - I2 + I3) [I3 >= I2 && I2 > 0] R = isdiv(x, y) -> isdiv(0 - x, y) [0 > x] isdiv(I0, I1) -> isdiv(I0, 0 - I1) [0 > I1] isdiv(I2, I3) -> isdiv(I2, 0 - I2 + I3) [I3 >= I2 && I2 > 0] isdiv(I4, I5) -> false [I4 > I5 && I5 > 0] isdiv(I6, 0) -> true [I6 > 0] if_2(false, I7, I8, zs) -> cons(I7, filter(I7, zs)) filter(I9, cons(I10, B0)) -> if_2(isdiv(I9, I10), I9, I10, B0) if_1(true, I11, I12, B1) -> filter(I11, B1) filter(I13, cons(I14, B2)) -> if_1(isdiv(I13, I14), I13, I14, B2) filter(I15, nil) -> nil sieve(cons(I16, ys)) -> cons(I16, sieve(filter(I16, ys))) sieve(nil) -> nil nats(I17, I18) -> cons(I17, nats(I17 + 1, I18)) [I18 > I17] nats(I19, I20) -> cons(I19, nil) [I19 = I20] nats(I21, I22) -> nil [I21 > I22] primes(I23) -> sieve(nats(2, I23)) mem(I24, cons(I25, B3)) -> mem(I24, B3) [I24 > I25] mem(I26, cons(I27, B4)) -> mem(I26, B4) [I27 > I26] mem(I28, cons(I29, B5)) -> true [I28 = I29] mem(I30, nil) -> false isprime(I31) -> mem(I31, primes(I31)) We use the reverse value criterion with the projection function NU: NU[isdiv#(z1,z2)] = z2 + -1 * z1 This gives the following inequalities: I3 >= I2 && I2 > 0 ==> I3 + -1 * I2 > 0 - I2 + I3 + -1 * I2 with I3 + -1 * I2 >= 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#(0 - x, y) [0 > x] isdiv#(I0, I1) -> isdiv#(I0, 0 - I1) [0 > I1] R = isdiv(x, y) -> isdiv(0 - x, y) [0 > x] isdiv(I0, I1) -> isdiv(I0, 0 - I1) [0 > I1] isdiv(I2, I3) -> isdiv(I2, 0 - I2 + I3) [I3 >= I2 && I2 > 0] isdiv(I4, I5) -> false [I4 > I5 && I5 > 0] isdiv(I6, 0) -> true [I6 > 0] if_2(false, I7, I8, zs) -> cons(I7, filter(I7, zs)) filter(I9, cons(I10, B0)) -> if_2(isdiv(I9, I10), I9, I10, B0) if_1(true, I11, I12, B1) -> filter(I11, B1) filter(I13, cons(I14, B2)) -> if_1(isdiv(I13, I14), I13, I14, B2) filter(I15, nil) -> nil sieve(cons(I16, ys)) -> cons(I16, sieve(filter(I16, ys))) sieve(nil) -> nil nats(I17, I18) -> cons(I17, nats(I17 + 1, I18)) [I18 > I17] nats(I19, I20) -> cons(I19, nil) [I19 = I20] nats(I21, I22) -> nil [I21 > I22] primes(I23) -> sieve(nats(2, I23)) mem(I24, cons(I25, B3)) -> mem(I24, B3) [I24 > I25] mem(I26, cons(I27, B4)) -> mem(I26, B4) [I27 > I26] mem(I28, cons(I29, B5)) -> true [I28 = I29] mem(I30, nil) -> false isprime(I31) -> mem(I31, primes(I31)) We use the reverse value criterion with the projection function NU: NU[isdiv#(z1,z2)] = 0 + -1 * z1 This gives the following inequalities: 0 > x ==> 0 + -1 * x > 0 + -1 * (0 - x) with 0 + -1 * x >= 0 0 > I1 ==> 0 + -1 * I0 >= 0 + -1 * I0 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = isdiv#(I0, I1) -> isdiv#(I0, 0 - I1) [0 > I1] R = isdiv(x, y) -> isdiv(0 - x, y) [0 > x] isdiv(I0, I1) -> isdiv(I0, 0 - I1) [0 > I1] isdiv(I2, I3) -> isdiv(I2, 0 - I2 + I3) [I3 >= I2 && I2 > 0] isdiv(I4, I5) -> false [I4 > I5 && I5 > 0] isdiv(I6, 0) -> true [I6 > 0] if_2(false, I7, I8, zs) -> cons(I7, filter(I7, zs)) filter(I9, cons(I10, B0)) -> if_2(isdiv(I9, I10), I9, I10, B0) if_1(true, I11, I12, B1) -> filter(I11, B1) filter(I13, cons(I14, B2)) -> if_1(isdiv(I13, I14), I13, I14, B2) filter(I15, nil) -> nil sieve(cons(I16, ys)) -> cons(I16, sieve(filter(I16, ys))) sieve(nil) -> nil nats(I17, I18) -> cons(I17, nats(I17 + 1, I18)) [I18 > I17] nats(I19, I20) -> cons(I19, nil) [I19 = I20] nats(I21, I22) -> nil [I21 > I22] primes(I23) -> sieve(nats(2, I23)) mem(I24, cons(I25, B3)) -> mem(I24, B3) [I24 > I25] mem(I26, cons(I27, B4)) -> mem(I26, B4) [I27 > I26] mem(I28, cons(I29, B5)) -> true [I28 = I29] mem(I30, nil) -> false isprime(I31) -> mem(I31, primes(I31)) The dependency graph for this problem is: 1 -> Where: 1) isdiv#(I0, I1) -> isdiv#(I0, 0 - I1) [0 > I1] We have the following SCCs. DP problem for innermost termination. P = if_2#(false, I7, I8, zs) -> filter#(I7, zs) filter#(I9, cons(I10, B0)) -> if_2#(isdiv(I9, I10), I9, I10, B0) if_1#(true, I11, I12, B1) -> filter#(I11, B1) filter#(I13, cons(I14, B2)) -> if_1#(isdiv(I13, I14), I13, I14, B2) R = isdiv(x, y) -> isdiv(0 - x, y) [0 > x] isdiv(I0, I1) -> isdiv(I0, 0 - I1) [0 > I1] isdiv(I2, I3) -> isdiv(I2, 0 - I2 + I3) [I3 >= I2 && I2 > 0] isdiv(I4, I5) -> false [I4 > I5 && I5 > 0] isdiv(I6, 0) -> true [I6 > 0] if_2(false, I7, I8, zs) -> cons(I7, filter(I7, zs)) filter(I9, cons(I10, B0)) -> if_2(isdiv(I9, I10), I9, I10, B0) if_1(true, I11, I12, B1) -> filter(I11, B1) filter(I13, cons(I14, B2)) -> if_1(isdiv(I13, I14), I13, I14, B2) filter(I15, nil) -> nil sieve(cons(I16, ys)) -> cons(I16, sieve(filter(I16, ys))) sieve(nil) -> nil nats(I17, I18) -> cons(I17, nats(I17 + 1, I18)) [I18 > I17] nats(I19, I20) -> cons(I19, nil) [I19 = I20] nats(I21, I22) -> nil [I21 > I22] primes(I23) -> sieve(nats(2, I23)) mem(I24, cons(I25, B3)) -> mem(I24, B3) [I24 > I25] mem(I26, cons(I27, B4)) -> mem(I26, B4) [I27 > I26] mem(I28, cons(I29, B5)) -> true [I28 = I29] mem(I30, nil) -> false isprime(I31) -> mem(I31, primes(I31)) We use the subterm criterion with the projection function NU: NU[if_2#(x0,x1,x2,x3)] = x3 NU[filter#(x0,x1)] = x1 NU[if_1#(x0,x1,x2,x3)] = x3 This gives the following inequalities: zs = zs cons(I10, B0) |> B0 B1 = B1 cons(I14, B2) |> B2 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = if_2#(false, I7, I8, zs) -> filter#(I7, zs) if_1#(true, I11, I12, B1) -> filter#(I11, B1) R = isdiv(x, y) -> isdiv(0 - x, y) [0 > x] isdiv(I0, I1) -> isdiv(I0, 0 - I1) [0 > I1] isdiv(I2, I3) -> isdiv(I2, 0 - I2 + I3) [I3 >= I2 && I2 > 0] isdiv(I4, I5) -> false [I4 > I5 && I5 > 0] isdiv(I6, 0) -> true [I6 > 0] if_2(false, I7, I8, zs) -> cons(I7, filter(I7, zs)) filter(I9, cons(I10, B0)) -> if_2(isdiv(I9, I10), I9, I10, B0) if_1(true, I11, I12, B1) -> filter(I11, B1) filter(I13, cons(I14, B2)) -> if_1(isdiv(I13, I14), I13, I14, B2) filter(I15, nil) -> nil sieve(cons(I16, ys)) -> cons(I16, sieve(filter(I16, ys))) sieve(nil) -> nil nats(I17, I18) -> cons(I17, nats(I17 + 1, I18)) [I18 > I17] nats(I19, I20) -> cons(I19, nil) [I19 = I20] nats(I21, I22) -> nil [I21 > I22] primes(I23) -> sieve(nats(2, I23)) mem(I24, cons(I25, B3)) -> mem(I24, B3) [I24 > I25] mem(I26, cons(I27, B4)) -> mem(I26, B4) [I27 > I26] mem(I28, cons(I29, B5)) -> true [I28 = I29] mem(I30, nil) -> false isprime(I31) -> mem(I31, primes(I31)) The dependency graph for this problem is: 3 -> 6 -> Where: 3) if_2#(false, I7, I8, zs) -> filter#(I7, zs) 6) if_1#(true, I11, I12, B1) -> filter#(I11, B1) We have the following SCCs. DP problem for innermost termination. P = sieve#(cons(I16, ys)) -> sieve#(filter(I16, ys)) R = isdiv(x, y) -> isdiv(0 - x, y) [0 > x] isdiv(I0, I1) -> isdiv(I0, 0 - I1) [0 > I1] isdiv(I2, I3) -> isdiv(I2, 0 - I2 + I3) [I3 >= I2 && I2 > 0] isdiv(I4, I5) -> false [I4 > I5 && I5 > 0] isdiv(I6, 0) -> true [I6 > 0] if_2(false, I7, I8, zs) -> cons(I7, filter(I7, zs)) filter(I9, cons(I10, B0)) -> if_2(isdiv(I9, I10), I9, I10, B0) if_1(true, I11, I12, B1) -> filter(I11, B1) filter(I13, cons(I14, B2)) -> if_1(isdiv(I13, I14), I13, I14, B2) filter(I15, nil) -> nil sieve(cons(I16, ys)) -> cons(I16, sieve(filter(I16, ys))) sieve(nil) -> nil nats(I17, I18) -> cons(I17, nats(I17 + 1, I18)) [I18 > I17] nats(I19, I20) -> cons(I19, nil) [I19 = I20] nats(I21, I22) -> nil [I21 > I22] primes(I23) -> sieve(nats(2, I23)) mem(I24, cons(I25, B3)) -> mem(I24, B3) [I24 > I25] mem(I26, cons(I27, B4)) -> mem(I26, B4) [I27 > I26] mem(I28, cons(I29, B5)) -> true [I28 = I29] mem(I30, nil) -> false isprime(I31) -> mem(I31, primes(I31))