details

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

run statistics

property	value
solver	Ctrl
configuration	Itrs
runtime (wallclock)	0.718225002289 seconds
cpu usage	0.751714321
max memory	1.0108928E7

stage attributes

key	value
output-size	4677
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 = if_3#(pair(yl, yh), x, ys) -> app#(qsort(yl), cons(x, qsort(yh))) if_3#(pair(yl, yh), x, ys) -> qsort#(yl) if_3#(pair(yl, yh), x, ys) -> qsort#(yh) qsort#(ins(I0, B0)) -> if_3#(split(I0, B0), I0, B0) qsort#(ins(I0, B0)) -> split#(I0, B0) split#(I2, ins(I3, B1)) -> if_2#(split(I2, B1), I2, I3, B1) [I3 >= I2] split#(I2, ins(I3, B1)) -> split#(I2, B1) [I3 >= I2] split#(I6, ins(I7, B5)) -> if_1#(split(I6, B5), I6, I7, B5) [I6 > I7] split#(I6, ins(I7, B5)) -> split#(I6, B5) [I6 > I7] app#(cons(I9, B6), B7) -> app#(B6, B7) R = if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) qsort(ins(I0, B0)) -> if_3(split(I0, B0), I0, B0) qsort(e) -> nil if_2(pair(zl, zh), I1, y, zs) -> pair(zl, ins(y, zh)) [y >= I1] split(I2, ins(I3, B1)) -> if_2(split(I2, B1), I2, I3, B1) [I3 >= I2] if_1(pair(B2, B3), I4, I5, B4) -> pair(ins(I5, B2), B3) [I4 > I5] split(I6, ins(I7, B5)) -> if_1(split(I6, B5), I6, I7, B5) [I6 > I7] split(I8, e) -> pair(e, e) app(cons(I9, B6), B7) -> cons(I9, app(B6, B7)) app(nil, B8) -> B8 The dependency graph for this problem is: 0 -> 9 1 -> 3, 4 2 -> 3, 4 3 -> 0, 1, 2 4 -> 5, 6, 7, 8 5 -> 6 -> 5, 6, 7, 8 7 -> 8 -> 5, 6, 7, 8 9 -> 9 Where: 0) if_3#(pair(yl, yh), x, ys) -> app#(qsort(yl), cons(x, qsort(yh))) 1) if_3#(pair(yl, yh), x, ys) -> qsort#(yl) 2) if_3#(pair(yl, yh), x, ys) -> qsort#(yh) 3) qsort#(ins(I0, B0)) -> if_3#(split(I0, B0), I0, B0) 4) qsort#(ins(I0, B0)) -> split#(I0, B0) 5) split#(I2, ins(I3, B1)) -> if_2#(split(I2, B1), I2, I3, B1) [I3 >= I2] 6) split#(I2, ins(I3, B1)) -> split#(I2, B1) [I3 >= I2] 7) split#(I6, ins(I7, B5)) -> if_1#(split(I6, B5), I6, I7, B5) [I6 > I7] 8) split#(I6, ins(I7, B5)) -> split#(I6, B5) [I6 > I7] 9) app#(cons(I9, B6), B7) -> app#(B6, B7) We have the following SCCs. { 1, 2, 3 } { 6, 8 } { 9 } DP problem for innermost termination. P = app#(cons(I9, B6), B7) -> app#(B6, B7) R = if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) qsort(ins(I0, B0)) -> if_3(split(I0, B0), I0, B0) qsort(e) -> nil if_2(pair(zl, zh), I1, y, zs) -> pair(zl, ins(y, zh)) [y >= I1] split(I2, ins(I3, B1)) -> if_2(split(I2, B1), I2, I3, B1) [I3 >= I2] if_1(pair(B2, B3), I4, I5, B4) -> pair(ins(I5, B2), B3) [I4 > I5] split(I6, ins(I7, B5)) -> if_1(split(I6, B5), I6, I7, B5) [I6 > I7] split(I8, e) -> pair(e, e) app(cons(I9, B6), B7) -> cons(I9, app(B6, B7)) app(nil, B8) -> B8 We use the subterm criterion with the projection function NU: NU[app#(x0,x1)] = x0 This gives the following inequalities: cons(I9, B6) |> B6 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed. DP problem for innermost termination. P = split#(I2, ins(I3, B1)) -> split#(I2, B1) [I3 >= I2] split#(I6, ins(I7, B5)) -> split#(I6, B5) [I6 > I7] R = if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) qsort(ins(I0, B0)) -> if_3(split(I0, B0), I0, B0) qsort(e) -> nil if_2(pair(zl, zh), I1, y, zs) -> pair(zl, ins(y, zh)) [y >= I1] split(I2, ins(I3, B1)) -> if_2(split(I2, B1), I2, I3, B1) [I3 >= I2] if_1(pair(B2, B3), I4, I5, B4) -> pair(ins(I5, B2), B3) [I4 > I5] split(I6, ins(I7, B5)) -> if_1(split(I6, B5), I6, I7, B5) [I6 > I7] split(I8, e) -> pair(e, e) app(cons(I9, B6), B7) -> cons(I9, app(B6, B7)) app(nil, B8) -> B8 We use the subterm criterion with the projection function NU: popout

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

job log

popout

actions

all output return to Integer TRS Innermost