Runti Compl Full Rewri 10127 pair #381902699

details

property	value
status	complete
benchmark	aprove05.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n056.star.cs.uiowa.edu
space	Secret_07_TRS

run statistics

property	value
solver	tct 2018-07-13
configuration	tct_rc
runtime (wallclock)	295.312070131 seconds
cpu usage	548.359111496
max memory	2.117206016E9

stage attributes

key	value
output-size	3413
starexec-result	WORST_CASE(Omega(n^1),?)

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:
            a() -> b()
            a() -> c()
            ge(x,0()) -> true()
            ge(0(),s(y)) -> false()
            ge(s(x),s(y)) -> ge(x,y)
            head(cons(x,xs)) -> x
            head(nil()) -> error()
            ifProd(false(),xs,x) -> prodIter(tail(xs),times(x,head(xs)))
            ifProd(true(),xs,x) -> x
            ifTimes(false(),x,y,z,u) -> timesIter(x,y,plus(y,z),s(u))
            ifTimes(true(),x,y,z,u) -> z
            isempty(cons(x,xs)) -> false()
            isempty(nil()) -> true()
            plus(0(),y) -> y
            plus(s(x),y) -> s(plus(x,y))
            prod(xs) -> prodIter(xs,s(0()))
            prodIter(xs,x) -> ifProd(isempty(xs),xs,x)
            tail(cons(x,xs)) -> xs
            tail(nil()) -> nil()
            times(x,y) -> timesIter(x,y,0(),0())
            timesIter(x,y,z,u) -> ifTimes(ge(u,x),x,y,z,u)
        - Signature:
            {a/0,ge/2,head/1,ifProd/3,ifTimes/5,isempty/1,plus/2,prod/1,prodIter/2,tail/1,times/2,timesIter/4} / {0/0
            ,b/0,c/0,cons/2,error/0,false/0,nil/0,s/1,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {a,ge,head,ifProd,ifTimes,isempty,plus,prod,prodIter,tail,times
            ,timesIter} and constructors {0,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()
            ge(x,0()) -> true()
            ge(0(),s(y)) -> false()
            ge(s(x),s(y)) -> ge(x,y)
            head(cons(x,xs)) -> x
            head(nil()) -> error()
            ifProd(false(),xs,x) -> prodIter(tail(xs),times(x,head(xs)))
            ifProd(true(),xs,x) -> x
            ifTimes(false(),x,y,z,u) -> timesIter(x,y,plus(y,z),s(u))
            ifTimes(true(),x,y,z,u) -> z
            isempty(cons(x,xs)) -> false()
            isempty(nil()) -> true()
            plus(0(),y) -> y
            plus(s(x),y) -> s(plus(x,y))
            prod(xs) -> prodIter(xs,s(0()))
            prodIter(xs,x) -> ifProd(isempty(xs),xs,x)
            tail(cons(x,xs)) -> xs
            tail(nil()) -> nil()
            times(x,y) -> timesIter(x,y,0(),0())
            timesIter(x,y,z,u) -> ifTimes(ge(u,x),x,y,z,u)
        - Signature:
            {a/0,ge/2,head/1,ifProd/3,ifTimes/5,isempty/1,plus/2,prod/1,prodIter/2,tail/1,times/2,timesIter/4} / {0/0
            ,b/0,c/0,cons/2,error/0,false/0,nil/0,s/1,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {a,ge,head,ifProd,ifTimes,isempty,plus,prod,prodIter,tail,times
            ,timesIter} and constructors {0,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){}]

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