/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:
  NU[split#(x0,x1)] = x1

This gives the following inequalities:
  ins(I3, B1) |> B1
  ins(I7, B5) |> B5

All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed.

DP problem for innermost termination.
P =
  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) 
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