Runti Compl Inner Rewri 22807 pair #381904489

details

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

run statistics

property	value
solver	tct 2018-07-13
configuration	tct_rci
runtime (wallclock)	295.171665907 seconds
cpu usage	1236.30290164
max memory	7.003869184E9

stage attributes

unavailable

output

/export/starexec/sandbox2/solver/bin/starexec_run_tct_rci /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:
            a() -> b()
            a() -> c()
            append(cons(n,x),y) -> cons(n,app(x,y))
            append(nil(),y) -> y
            averIter(x,y,z) -> ifIter(ge(x,y),x,y,z)
            average(x,y) -> if(ge(x,y),x,y)
            ge(x,0()) -> true()
            ge(0(),s(y)) -> false()
            ge(s(x),s(y)) -> ge(x,y)
            head(cons(n,x)) -> n
            head(nil()) -> error()
            high(n,cons(m,x)) -> if_high(ge(m,n),n,cons(m,x))
            high(n,nil()) -> nil()
            if(false(),x,y) -> averIter(x,y,x)
            if(true(),x,y) -> averIter(y,x,y)
            ifIter(false(),x,y,z) -> averIter(plus(x,s(s(s(0())))),plus(y,s(0())),plus(z,s(0())))
            ifIter(true(),x,y,z) -> z
            if_high(false(),n,cons(m,x)) -> high(n,x)
            if_high(true(),n,cons(m,x)) -> cons(average(m,m),high(n,x))
            if_low(false(),n,cons(m,x)) -> cons(m,low(n,x))
            if_low(true(),n,cons(m,x)) -> low(n,x)
            ifquick(false(),x) -> append(quicksort(low(head(x),tail(x))),cons(tail(x),quicksort(high(head(x),tail(x)))))
            ifquick(true(),x) -> nil()
            isempty(cons(n,x)) -> false()
            isempty(nil()) -> true()
            low(n,cons(m,x)) -> if_low(ge(m,n),n,cons(m,x))
            low(n,nil()) -> nil()
            plus(0(),y) -> y
            plus(s(x),y) -> s(plus(x,y))
            quicksort(x) -> ifquick(isempty(x),x)
            tail(cons(n,x)) -> x
            tail(nil()) -> nil()
        - Signature:
            {a/0,append/2,averIter/3,average/2,ge/2,head/1,high/2,if/3,ifIter/4,if_high/3,if_low/3,ifquick/2,isempty/1
            ,low/2,plus/2,quicksort/1,tail/1} / {0/0,app/2,b/0,c/0,cons/2,error/0,false/0,nil/0,s/1,true/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {a,append,averIter,average,ge,head,high,if,ifIter,if_high
            ,if_low,ifquick,isempty,low,plus,quicksort,tail} and constructors {0,app,b,c,cons,error,false,nil,s,true}
    + Applied Processor:
        Sum {left = someStrategy, right = someStrategy}
    + Details:
        ()
* Step 2: DecreasingLoops WORST_CASE(Omega(n^1),?)
    + Considered Problem:
        - Strict TRS:
            a() -> b()
            a() -> c()
            append(cons(n,x),y) -> cons(n,app(x,y))
            append(nil(),y) -> y
            averIter(x,y,z) -> ifIter(ge(x,y),x,y,z)
            average(x,y) -> if(ge(x,y),x,y)
            ge(x,0()) -> true()
            ge(0(),s(y)) -> false()
            ge(s(x),s(y)) -> ge(x,y)
            head(cons(n,x)) -> n
            head(nil()) -> error()
            high(n,cons(m,x)) -> if_high(ge(m,n),n,cons(m,x))
            high(n,nil()) -> nil()
            if(false(),x,y) -> averIter(x,y,x)
            if(true(),x,y) -> averIter(y,x,y)
            ifIter(false(),x,y,z) -> averIter(plus(x,s(s(s(0())))),plus(y,s(0())),plus(z,s(0())))
            ifIter(true(),x,y,z) -> z
            if_high(false(),n,cons(m,x)) -> high(n,x)
            if_high(true(),n,cons(m,x)) -> cons(average(m,m),high(n,x))
            if_low(false(),n,cons(m,x)) -> cons(m,low(n,x))
            if_low(true(),n,cons(m,x)) -> low(n,x)
            ifquick(false(),x) -> append(quicksort(low(head(x),tail(x))),cons(tail(x),quicksort(high(head(x),tail(x)))))
            ifquick(true(),x) -> nil()
            isempty(cons(n,x)) -> false()
            isempty(nil()) -> true()
            low(n,cons(m,x)) -> if_low(ge(m,n),n,cons(m,x))
            low(n,nil()) -> nil()
            plus(0(),y) -> y
            plus(s(x),y) -> s(plus(x,y))
            quicksort(x) -> ifquick(isempty(x),x)
            tail(cons(n,x)) -> x
            tail(nil()) -> nil()
        - Signature:
            {a/0,append/2,averIter/3,average/2,ge/2,head/1,high/2,if/3,ifIter/4,if_high/3,if_low/3,ifquick/2,isempty/1
            ,low/2,plus/2,quicksort/1,tail/1} / {0/0,app/2,b/0,c/0,cons/2,error/0,false/0,nil/0,s/1,true/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {a,append,averIter,average,ge,head,high,if,ifIter,if_high
            ,if_low,ifquick,isempty,low,plus,quicksort,tail} and constructors {0,app,b,c,cons,error,false,nil,s,true}
    + Applied Processor:
        DecreasingLoops {bound = AnyLoop, narrow = 10}
    + Details:
        The system has following decreasing Loops:
          ge(x,y){x -> s(x),y -> s(y)} =
            ge(s(x),s(y)) ->^+ ge(x,y)
              = C[ge(x,y) = ge(x,y){}]

popout

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

job log

popout

actions all output return to Runti Compl Inner Rewri 22807