Runti Compl Inner Rewri 22807 pair #381904261

details

property	value
status	timeout (wallclock)
benchmark	aprove10.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)	294.544651985 seconds
cpu usage	1180.17659081
max memory	5.9575296E9

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() -> c()
            a() -> d()
            append(cons(n,l1),l2) -> cons(n,append(l1,l2))
            append(nil(),l2) -> l2
            if(false(),false(),l,t,n) -> lessE(l,t,s(n))
            if(false(),true(),l,t,n) -> t
            if(true(),b,l,t,n) -> l
            le(0(),m) -> true()
            le(s(n),0()) -> false()
            le(s(n),s(m)) -> le(n,m)
            length(cons(n,l)) -> s(length(l))
            length(nil()) -> 0()
            lessE(l,t,n) -> if(le(length(l),n),le(length(toList(t)),n),l,t,n)
            lessElements(l,t) -> lessE(l,t,0())
            toList(leaf()) -> nil()
            toList(node(t1,n,t2)) -> append(toList(t1),cons(n,toList(t2)))
        - Signature:
            {a/0,append/2,if/5,le/2,length/1,lessE/3,lessElements/2,toList/1} / {0/0,c/0,cons/2,d/0,false/0,leaf/0,nil/0
            ,node/3,s/1,true/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {a,append,if,le,length,lessE,lessElements
            ,toList} and constructors {0,c,cons,d,false,leaf,nil,node,s,true}
    + Applied Processor:
        Sum {left = someStrategy, right = someStrategy}
    + Details:
        ()
* Step 2: DecreasingLoops WORST_CASE(Omega(n^1),?)
    + Considered Problem:
        - Strict TRS:
            a() -> c()
            a() -> d()
            append(cons(n,l1),l2) -> cons(n,append(l1,l2))
            append(nil(),l2) -> l2
            if(false(),false(),l,t,n) -> lessE(l,t,s(n))
            if(false(),true(),l,t,n) -> t
            if(true(),b,l,t,n) -> l
            le(0(),m) -> true()
            le(s(n),0()) -> false()
            le(s(n),s(m)) -> le(n,m)
            length(cons(n,l)) -> s(length(l))
            length(nil()) -> 0()
            lessE(l,t,n) -> if(le(length(l),n),le(length(toList(t)),n),l,t,n)
            lessElements(l,t) -> lessE(l,t,0())
            toList(leaf()) -> nil()
            toList(node(t1,n,t2)) -> append(toList(t1),cons(n,toList(t2)))
        - Signature:
            {a/0,append/2,if/5,le/2,length/1,lessE/3,lessElements/2,toList/1} / {0/0,c/0,cons/2,d/0,false/0,leaf/0,nil/0
            ,node/3,s/1,true/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {a,append,if,le,length,lessE,lessElements
            ,toList} and constructors {0,c,cons,d,false,leaf,nil,node,s,true}
    + Applied Processor:
        DecreasingLoops {bound = AnyLoop, narrow = 10}
    + Details:
        The system has following decreasing Loops:
          append(y,z){y -> cons(x,y)} =
            append(cons(x,y),z) ->^+ cons(x,append(y,z))
              = C[append(y,z) = append(y,z){}]

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 Inner Rewri 22807