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


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


WORST_CASE(Omega(n^1),?)
* Step 1: Sum.  WORST_CASE(Omega(n^1),?)
    + Considered Problem:
        - Strict TRS:
            empty(cons(x,l)) -> false()
            empty(nil()) -> true()
            head(cons(x,l)) -> x
            if(false(),x,l) -> last(head(l),tail(l))
            if(true(),x,l) -> x
            last(x,l) -> if(empty(l),x,l)
            rev(cons(x,l)) -> cons(rev1(x,l),rev2(x,l))
            rev(nil()) -> nil()
            rev2(x,cons(y,l)) -> rev(cons(x,rev2(y,l)))
            rev2(x,nil()) -> nil()
            tail(cons(x,l)) -> l
            tail(nil()) -> nil()
        - Signature:
            {empty/1,head/1,if/3,last/2,rev/1,rev2/2,tail/1} / {cons/2,false/0,nil/0,rev1/2,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {empty,head,if,last,rev,rev2,tail} and constructors {cons,false,nil
            ,rev1,true}
    + Applied Processor:
        Sum {left = someStrategy, right = someStrategy}
    + Details:
        ()
* Step 2: Sum.  WORST_CASE(Omega(n^1),?)
    + Considered Problem:
        - Strict TRS:
            empty(cons(x,l)) -> false()
            empty(nil()) -> true()
            head(cons(x,l)) -> x
            if(false(),x,l) -> last(head(l),tail(l))
            if(true(),x,l) -> x
            last(x,l) -> if(empty(l),x,l)
            rev(cons(x,l)) -> cons(rev1(x,l),rev2(x,l))
            rev(nil()) -> nil()
            rev2(x,cons(y,l)) -> rev(cons(x,rev2(y,l)))
            rev2(x,nil()) -> nil()
            tail(cons(x,l)) -> l
            tail(nil()) -> nil()
        - Signature:
            {empty/1,head/1,if/3,last/2,rev/1,rev2/2,tail/1} / {cons/2,false/0,nil/0,rev1/2,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {empty,head,if,last,rev,rev2,tail} and constructors {cons,false,nil
            ,rev1,true}
    + Applied Processor:
        Sum {left = someStrategy, right = someStrategy}
    + Details:
        ()
* Step 3: DecreasingLoops.  WORST_CASE(Omega(n^1),?)
    + Considered Problem:
        - Strict TRS:
            empty(cons(x,l)) -> false()
            empty(nil()) -> true()
            head(cons(x,l)) -> x
            if(false(),x,l) -> last(head(l),tail(l))
            if(true(),x,l) -> x
            last(x,l) -> if(empty(l),x,l)
            rev(cons(x,l)) -> cons(rev1(x,l),rev2(x,l))
            rev(nil()) -> nil()
            rev2(x,cons(y,l)) -> rev(cons(x,rev2(y,l)))
            rev2(x,nil()) -> nil()
            tail(cons(x,l)) -> l
            tail(nil()) -> nil()
        - Signature:
            {empty/1,head/1,if/3,last/2,rev/1,rev2/2,tail/1} / {cons/2,false/0,nil/0,rev1/2,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {empty,head,if,last,rev,rev2,tail} and constructors {cons,false,nil
            ,rev1,true}
    + Applied Processor:
        DecreasingLoops {bound = AnyLoop, narrow = 10}
    + Details:
        The system has following decreasing Loops:
          rev2(x,z){z -> cons(y,z)} =
            rev2(x,cons(y,z)) ->^+ rev(cons(x,rev2(y,z)))
              = C[rev2(y,z) = rev2(x,z){x -> y}]

WORST_CASE(Omega(n^1),?)