/export/starexec/sandbox/solver/bin/starexec_run_tct_rc /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^1),?)
* Step 1: Sum.  WORST_CASE(Omega(n^1),?)
    + Considered Problem:
        - Strict TRS:
            app(cons(N,L),Y) -> cons(N,app(L,Y))
            app(nil(),Y) -> Y
            high(N,cons(M,L)) -> ifhigh(le(M,N),N,cons(M,L))
            high(N,nil()) -> nil()
            ifhigh(false(),N,cons(M,L)) -> cons(M,high(N,L))
            ifhigh(true(),N,cons(M,L)) -> high(N,L)
            iflow(false(),N,cons(M,L)) -> low(N,L)
            iflow(true(),N,cons(M,L)) -> cons(M,low(N,L))
            le(0(),Y) -> true()
            le(s(X),0()) -> false()
            le(s(X),s(Y)) -> le(X,Y)
            low(N,cons(M,L)) -> iflow(le(M,N),N,cons(M,L))
            low(N,nil()) -> nil()
            quicksort(cons(N,L)) -> app(quicksort(low(N,L)),cons(N,quicksort(high(N,L))))
            quicksort(nil()) -> nil()
        - Signature:
            {app/2,high/2,ifhigh/3,iflow/3,le/2,low/2,quicksort/1} / {0/0,cons/2,false/0,nil/0,s/1,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {app,high,ifhigh,iflow,le,low,quicksort} and constructors {0,cons
            ,false,nil,s,true}
    + Applied Processor:
        Sum {left = someStrategy, right = someStrategy}
    + Details:
        ()
* Step 2: Sum.  WORST_CASE(Omega(n^1),?)
    + Considered Problem:
        - Strict TRS:
            app(cons(N,L),Y) -> cons(N,app(L,Y))
            app(nil(),Y) -> Y
            high(N,cons(M,L)) -> ifhigh(le(M,N),N,cons(M,L))
            high(N,nil()) -> nil()
            ifhigh(false(),N,cons(M,L)) -> cons(M,high(N,L))
            ifhigh(true(),N,cons(M,L)) -> high(N,L)
            iflow(false(),N,cons(M,L)) -> low(N,L)
            iflow(true(),N,cons(M,L)) -> cons(M,low(N,L))
            le(0(),Y) -> true()
            le(s(X),0()) -> false()
            le(s(X),s(Y)) -> le(X,Y)
            low(N,cons(M,L)) -> iflow(le(M,N),N,cons(M,L))
            low(N,nil()) -> nil()
            quicksort(cons(N,L)) -> app(quicksort(low(N,L)),cons(N,quicksort(high(N,L))))
            quicksort(nil()) -> nil()
        - Signature:
            {app/2,high/2,ifhigh/3,iflow/3,le/2,low/2,quicksort/1} / {0/0,cons/2,false/0,nil/0,s/1,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {app,high,ifhigh,iflow,le,low,quicksort} and constructors {0,cons
            ,false,nil,s,true}
    + Applied Processor:
        Sum {left = someStrategy, right = someStrategy}
    + Details:
        ()
* Step 3: DecreasingLoops.  WORST_CASE(Omega(n^1),?)
    + Considered Problem:
        - Strict TRS:
            app(cons(N,L),Y) -> cons(N,app(L,Y))
            app(nil(),Y) -> Y
            high(N,cons(M,L)) -> ifhigh(le(M,N),N,cons(M,L))
            high(N,nil()) -> nil()
            ifhigh(false(),N,cons(M,L)) -> cons(M,high(N,L))
            ifhigh(true(),N,cons(M,L)) -> high(N,L)
            iflow(false(),N,cons(M,L)) -> low(N,L)
            iflow(true(),N,cons(M,L)) -> cons(M,low(N,L))
            le(0(),Y) -> true()
            le(s(X),0()) -> false()
            le(s(X),s(Y)) -> le(X,Y)
            low(N,cons(M,L)) -> iflow(le(M,N),N,cons(M,L))
            low(N,nil()) -> nil()
            quicksort(cons(N,L)) -> app(quicksort(low(N,L)),cons(N,quicksort(high(N,L))))
            quicksort(nil()) -> nil()
        - Signature:
            {app/2,high/2,ifhigh/3,iflow/3,le/2,low/2,quicksort/1} / {0/0,cons/2,false/0,nil/0,s/1,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {app,high,ifhigh,iflow,le,low,quicksort} and constructors {0,cons
            ,false,nil,s,true}
    + Applied Processor:
        DecreasingLoops {bound = AnyLoop, narrow = 10}
    + Details:
        The system has following decreasing Loops:
          app(y,z){y -> cons(x,y)} =
            app(cons(x,y),z) ->^+ cons(x,app(y,z))
              = C[app(y,z) = app(y,z){}]

WORST_CASE(Omega(n^1),?)