details

property	value
status	complete
benchmark	eratosthenes_small.itrs
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n099.star.cs.uiowa.edu
space	Mixed_ITRS_2014

run statistics

property	value
solver	Ctrl
configuration	Itrs
runtime (wallclock)	0.458148956299 seconds
cpu usage	0.473967121
max memory	1.03424E7

stage attributes

key	value
output-size	6406
starexec-result	MAYBE

output

/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))) popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to Integ TRS Inner 43557