Runti Compl Full Rewri 10127 pair #381903256

details

property	value
status	timeout (wallclock)
benchmark	thiemann08.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
space	AProVE_07

run statistics

property	value
solver	tct 2018-07-13
configuration	tct_rc
runtime (wallclock)	295.163388968 seconds
cpu usage	632.035242707
max memory	2.0010135552E10

stage attributes

unavailable

output

/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:
            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: 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),?)

popout

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

job log

popout

actions all output return to Runti Compl Full Rewri 10127