details

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

run statistics

property	value
solver	tct 2018-07-13
configuration	tct_rci
runtime (wallclock)	27.1487381458 seconds
cpu usage	106.131696566
max memory	2.49966592E8

stage attributes

key	value
output-size	834507
starexec-result	WORST_CASE(?,O(n^4))

output

/export/starexec/sandbox2/solver/bin/starexec_run_tct_rci /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(n^4)) * Step 1: Sum WORST_CASE(?,O(n^4)) + Considered Problem: - Strict TRS: *(@x,@y) -> #mult(@x,@y) +(@x,@y) -> #add(@x,@y) appendreverse(@toreverse,@sofar) -> appendreverse#1(@toreverse,@sofar) appendreverse#1(::(@a,@as),@sofar) -> appendreverse(@as,::(@a,@sofar)) appendreverse#1(nil(),@sofar) -> @sofar bftMult(@t,@acc) -> bftMult'(tuple#2(::(@t,nil()),nil()),@acc) bftMult'(@queue,@acc) -> bftMult'#1(bftMult'#2(@queue),@acc) bftMult'#1(tuple#2(@elem,@queue),@acc) -> bftMult'#3(@elem,@acc,@queue) bftMult'#2(tuple#2(@dequeue@1,@dequeue@2)) -> dequeue(@dequeue@1,@dequeue@2) bftMult'#3(::(@t,@_@3),@acc,@queue) -> bftMult'#4(@t,@acc,@queue) bftMult'#3(nil(),@acc,@queue) -> @acc bftMult'#4(leaf(),@acc,@queue) -> bftMult'(@queue,@acc) bftMult'#4(node(@y,@t1,@t2),@acc,@queue) -> bftMult'#5(enqueue(@t2,enqueue(@t1,@queue)),@acc,@y) bftMult'#5(@queue',@acc,@y) -> bftMult'(@queue',matrixMult(@acc,@y)) computeLine(@line,@m,@acc) -> computeLine#1(@line,@acc,@m) computeLine#1(::(@x,@xs),@acc,@m) -> computeLine#2(@m,@acc,@x,@xs) computeLine#1(nil(),@acc,@m) -> @acc computeLine#2(::(@l,@ls),@acc,@x,@xs) -> computeLine(@xs,@ls,lineMult(@x,@l,@acc)) computeLine#2(nil(),@acc,@x,@xs) -> nil() dequeue(@outq,@inq) -> dequeue#1(@outq,@inq) dequeue#1(::(@t,@ts),@inq) -> tuple#2(::(@t,nil()),tuple#2(@ts,@inq)) dequeue#1(nil(),@inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t,@ts)) -> tuple#2(::(@t,nil()),tuple#2(@ts,nil())) dequeue#2(nil()) -> tuple#2(nil(),tuple#2(nil(),nil())) enqueue(@t,@queue) -> enqueue#1(@queue,@t) enqueue#1(tuple#2(@outq,@inq),@t) -> tuple#2(@outq,::(@t,@inq)) lineMult(@n,@l1,@l2) -> lineMult#1(@l1,@l2,@n) lineMult#1(::(@x,@xs),@l2,@n) -> lineMult#2(@l2,@n,@x,@xs) lineMult#1(nil(),@l2,@n) -> nil() lineMult#2(::(@y,@ys),@n,@x,@xs) -> ::(+(*(@x,@n),@y),lineMult(@n,@xs,@ys)) lineMult#2(nil(),@n,@x,@xs) -> ::(*(@x,@n),lineMult(@n,@xs,nil())) matrixMult(@m1,@m2) -> matrixMult#1(@m1,@m2) matrixMult#1(::(@l,@ls),@m2) -> ::(computeLine(@l,@m2,nil()),matrixMult(@ls,@m2)) matrixMult#1(nil(),@m2) -> nil() reverse(@xs) -> appendreverse(@xs,nil()) - Weak TRS: #add(#0(),@y) -> @y #add(#neg(#s(#0())),@y) -> #pred(@y) #add(#neg(#s(#s(@x))),@y) -> #pred(#add(#pos(#s(@x)),@y)) #add(#pos(#s(#0())),@y) -> #succ(@y) #add(#pos(#s(#s(@x))),@y) -> #succ(#add(#pos(#s(@x)),@y)) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(@y)) -> #0() #mult(#0(),#pos(@y)) -> #0() #mult(#neg(@x),#0()) -> #0() #mult(#neg(@x),#neg(@y)) -> #pos(#natmult(@x,@y)) #mult(#neg(@x),#pos(@y)) -> #neg(#natmult(@x,@y)) #mult(#pos(@x),#0()) -> #0() #mult(#pos(@x),#neg(@y)) -> #neg(#natmult(@x,@y)) #mult(#pos(@x),#pos(@y)) -> #pos(#natmult(@x,@y)) #natmult(#0(),@y) -> #0() #natmult(#s(@x),@y) -> #add(#pos(@y),#natmult(@x,@y)) #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) #pred(#pos(#s(#0()))) -> #0() #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) - Signature: {#add/2,#mult/2,#natmult/2,#pred/1,#succ/1,*/2,+/2,appendreverse/2,appendreverse#1/2,bftMult/2,bftMult'/2 ,bftMult'#1/2,bftMult'#2/1,bftMult'#3/3,bftMult'#4/3,bftMult'#5/3,computeLine/3,computeLine#1/3 ,computeLine#2/4,dequeue/2,dequeue#1/2,dequeue#2/1,enqueue/2,enqueue#1/2,lineMult/3,lineMult#1/3 ,lineMult#2/4,matrixMult/2,matrixMult#1/2,reverse/1} / {#0/0,#neg/1,#pos/1,#s/1,::/2,leaf/0,nil/0,node/3 ,tuple#2/2} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natmult,#pred,#succ,*,+,appendreverse ,appendreverse#1,bftMult,bftMult',bftMult'#1,bftMult'#2,bftMult'#3,bftMult'#4,bftMult'#5,computeLine ,computeLine#1,computeLine#2,dequeue,dequeue#1,dequeue#2,enqueue,enqueue#1,lineMult,lineMult#1,lineMult#2 ,matrixMult,matrixMult#1,reverse} and constructors {#0,#neg,#pos,#s,::,leaf,nil,node,tuple#2} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: DependencyPairs WORST_CASE(?,O(n^4)) + Considered Problem: - Strict TRS: *(@x,@y) -> #mult(@x,@y) +(@x,@y) -> #add(@x,@y) appendreverse(@toreverse,@sofar) -> appendreverse#1(@toreverse,@sofar) appendreverse#1(::(@a,@as),@sofar) -> appendreverse(@as,::(@a,@sofar)) appendreverse#1(nil(),@sofar) -> @sofar bftMult(@t,@acc) -> bftMult'(tuple#2(::(@t,nil()),nil()),@acc) bftMult'(@queue,@acc) -> bftMult'#1(bftMult'#2(@queue),@acc) bftMult'#1(tuple#2(@elem,@queue),@acc) -> bftMult'#3(@elem,@acc,@queue) bftMult'#2(tuple#2(@dequeue@1,@dequeue@2)) -> dequeue(@dequeue@1,@dequeue@2) bftMult'#3(::(@t,@_@3),@acc,@queue) -> bftMult'#4(@t,@acc,@queue) bftMult'#3(nil(),@acc,@queue) -> @acc bftMult'#4(leaf(),@acc,@queue) -> bftMult'(@queue,@acc) popout

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

job log

popout

actions

all output return to Runti Compl Inner Rewri 22807