Runti Compl Inner Rewri 22807 pair #381905200

details

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

run statistics

property	value
solver	tct 2018-07-13
configuration	tct_rci
runtime (wallclock)	294.202412844 seconds
cpu usage	1001.79681863
max memory	3.328008192E9

stage attributes

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

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__app(X1,X2) -> app(X1,X2)
            a__app(cons(X,XS),YS) -> cons(mark(X),app(XS,YS))
            a__app(nil(),YS) -> mark(YS)
            a__from(X) -> cons(mark(X),from(s(X)))
            a__from(X) -> from(X)
            a__prefix(L) -> cons(nil(),zWadr(L,prefix(L)))
            a__prefix(X) -> prefix(X)
            a__zWadr(X1,X2) -> zWadr(X1,X2)
            a__zWadr(XS,nil()) -> nil()
            a__zWadr(cons(X,XS),cons(Y,YS)) -> cons(a__app(mark(Y),cons(mark(X),nil())),zWadr(XS,YS))
            a__zWadr(nil(),YS) -> nil()
            mark(app(X1,X2)) -> a__app(mark(X1),mark(X2))
            mark(cons(X1,X2)) -> cons(mark(X1),X2)
            mark(from(X)) -> a__from(mark(X))
            mark(nil()) -> nil()
            mark(prefix(X)) -> a__prefix(mark(X))
            mark(s(X)) -> s(mark(X))
            mark(zWadr(X1,X2)) -> a__zWadr(mark(X1),mark(X2))
        - Signature:
            {a__app/2,a__from/1,a__prefix/1,a__zWadr/2,mark/1} / {app/2,cons/2,from/1,nil/0,prefix/1,s/1,zWadr/2}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {a__app,a__from,a__prefix,a__zWadr
            ,mark} and constructors {app,cons,from,nil,prefix,s,zWadr}
    + Applied Processor:
        Sum {left = someStrategy, right = someStrategy}
    + Details:
        ()
* Step 2: DecreasingLoops WORST_CASE(Omega(n^1),?)
    + Considered Problem:
        - Strict TRS:
            a__app(X1,X2) -> app(X1,X2)
            a__app(cons(X,XS),YS) -> cons(mark(X),app(XS,YS))
            a__app(nil(),YS) -> mark(YS)
            a__from(X) -> cons(mark(X),from(s(X)))
            a__from(X) -> from(X)
            a__prefix(L) -> cons(nil(),zWadr(L,prefix(L)))
            a__prefix(X) -> prefix(X)
            a__zWadr(X1,X2) -> zWadr(X1,X2)
            a__zWadr(XS,nil()) -> nil()
            a__zWadr(cons(X,XS),cons(Y,YS)) -> cons(a__app(mark(Y),cons(mark(X),nil())),zWadr(XS,YS))
            a__zWadr(nil(),YS) -> nil()
            mark(app(X1,X2)) -> a__app(mark(X1),mark(X2))
            mark(cons(X1,X2)) -> cons(mark(X1),X2)
            mark(from(X)) -> a__from(mark(X))
            mark(nil()) -> nil()
            mark(prefix(X)) -> a__prefix(mark(X))
            mark(s(X)) -> s(mark(X))
            mark(zWadr(X1,X2)) -> a__zWadr(mark(X1),mark(X2))
        - Signature:
            {a__app/2,a__from/1,a__prefix/1,a__zWadr/2,mark/1} / {app/2,cons/2,from/1,nil/0,prefix/1,s/1,zWadr/2}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {a__app,a__from,a__prefix,a__zWadr
            ,mark} and constructors {app,cons,from,nil,prefix,s,zWadr}
    + Applied Processor:
        DecreasingLoops {bound = AnyLoop, narrow = 10}
    + Details:
        The system has following decreasing Loops:
          mark(x){x -> app(x,y)} =
            mark(app(x,y)) ->^+ a__app(mark(x),mark(y))
              = C[mark(x) = mark(x){}]

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