MAYBE
* Step 1: Failure MAYBE
  + Considered Problem:
      - Strict TRS:
          concat(cons(x,xs),ys) -> cons(x,concat(xs,ys))
          concat(nil(),ys) -> ys
          goal(xs) -> qs(xs)
          high(x,cons(y,ys)) -> ifHigh(leq(x,y),x,cons(y,ys))
          high(x,nil()) -> nil()
          ifHigh(false(),x,cons(y,ys)) -> high(x,ys)
          ifHigh(true(),x,cons(y,ys)) -> cons(y,high(x,ys))
          ifLow(false(),x,cons(y,ys)) -> cons(y,low(x,ys))
          ifLow(true(),x,cons(y,ys)) -> low(x,ys)
          leq(0(),x) -> true()
          leq(s(x),0()) -> false()
          leq(s(x),s(y)) -> leq(x,y)
          low(x,cons(y,ys)) -> ifLow(leq(x,y),x,cons(y,ys))
          low(x,nil()) -> nil()
          qs(cons(x,xs)) -> concat(qs(low(x,xs)),cons(x,qs(high(x,xs))))
          qs(nil()) -> nil()
      - Signature:
          {concat/2,goal/1,high/2,ifHigh/3,ifLow/3,leq/2,low/2,qs/1} / {0/0,cons/2,false/0,nil/0,s/1,true/0}
      - Obligation:
          innermost runtime complexity wrt. defined symbols {concat,goal,high,ifHigh,ifLow,leq,low
          ,qs} and constructors {0,cons,false,nil,s,true}
  + Applied Processor:
      EmptyProcessor
  + Details:
      The problem is still open.
MAYBE