Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Runti Compl Inner Rewri 22807 pair #381904717
details
property
value
status
complete
benchmark
bubblesort.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n054.star.cs.uiowa.edu
space
Frederiksen_Others
run statistics
property
value
solver
tct 2018-07-13
configuration
tct_rci
runtime (wallclock)
6.94814705849 seconds
cpu usage
21.874617698
max memory
1.07565056E8
stage attributes
key
value
output-size
68128
starexec-result
WORST_CASE(Omega(n^1),O(n^2))
output
/export/starexec/sandbox/solver/bin/starexec_run_tct_rci /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1),O(n^2)) * Step 1: Sum WORST_CASE(Omega(n^1),O(n^2)) + Considered Problem: - Strict TRS: bsort(0(),xs) -> xs bsort(S(x'),Cons(x,xs)) -> bsort(x',bubble(x,xs)) bubble(x,Nil()) -> Cons(x,Nil()) bubble(x',Cons(x,xs)) -> bubble[Ite][False][Ite](<(x',x),x',Cons(x,xs)) bubblesort(xs) -> bsort(len(xs),xs) len(Cons(x,xs)) -> +(S(0()),len(xs)) len(Nil()) -> 0() - Weak TRS: +(x,S(0())) -> S(x) +(S(0()),y) -> S(y) <(x,0()) -> False() <(0(),S(y)) -> True() <(S(x),S(y)) -> <(x,y) bubble[Ite][False][Ite](False(),x',Cons(x,xs)) -> Cons(x,bubble(x',xs)) bubble[Ite][False][Ite](True(),x',Cons(x,xs)) -> Cons(x',bubble(x,xs)) - Signature: {+/2,</2,bsort/2,bubble/2,bubble[Ite][False][Ite]/3,bubblesort/1,len/1} / {0/0,Cons/2,False/0,Nil/0,S/1 ,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {+,<,bsort,bubble,bubble[Ite][False][Ite],bubblesort ,len} and constructors {0,Cons,False,Nil,S,True} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: bsort(0(),xs) -> xs bsort(S(x'),Cons(x,xs)) -> bsort(x',bubble(x,xs)) bubble(x,Nil()) -> Cons(x,Nil()) bubble(x',Cons(x,xs)) -> bubble[Ite][False][Ite](<(x',x),x',Cons(x,xs)) bubblesort(xs) -> bsort(len(xs),xs) len(Cons(x,xs)) -> +(S(0()),len(xs)) len(Nil()) -> 0() - Weak TRS: +(x,S(0())) -> S(x) +(S(0()),y) -> S(y) <(x,0()) -> False() <(0(),S(y)) -> True() <(S(x),S(y)) -> <(x,y) bubble[Ite][False][Ite](False(),x',Cons(x,xs)) -> Cons(x,bubble(x',xs)) bubble[Ite][False][Ite](True(),x',Cons(x,xs)) -> Cons(x',bubble(x,xs)) - Signature: {+/2,</2,bsort/2,bubble/2,bubble[Ite][False][Ite]/3,bubblesort/1,len/1} / {0/0,Cons/2,False/0,Nil/0,S/1 ,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {+,<,bsort,bubble,bubble[Ite][False][Ite],bubblesort ,len} and constructors {0,Cons,False,Nil,S,True} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: len(y){y -> Cons(x,y)} = len(Cons(x,y)) ->^+ +(S(0()),len(y)) = C[len(y) = len(y){}] ** Step 1.b:1: DependencyPairs WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: bsort(0(),xs) -> xs bsort(S(x'),Cons(x,xs)) -> bsort(x',bubble(x,xs)) bubble(x,Nil()) -> Cons(x,Nil()) bubble(x',Cons(x,xs)) -> bubble[Ite][False][Ite](<(x',x),x',Cons(x,xs)) bubblesort(xs) -> bsort(len(xs),xs) len(Cons(x,xs)) -> +(S(0()),len(xs)) len(Nil()) -> 0() - Weak TRS: +(x,S(0())) -> S(x) +(S(0()),y) -> S(y) <(x,0()) -> False() <(0(),S(y)) -> True() <(S(x),S(y)) -> <(x,y) bubble[Ite][False][Ite](False(),x',Cons(x,xs)) -> Cons(x,bubble(x',xs)) bubble[Ite][False][Ite](True(),x',Cons(x,xs)) -> Cons(x',bubble(x,xs)) - Signature: {+/2,</2,bsort/2,bubble/2,bubble[Ite][False][Ite]/3,bubblesort/1,len/1} / {0/0,Cons/2,False/0,Nil/0,S/1 ,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {+,<,bsort,bubble,bubble[Ite][False][Ite],bubblesort ,len} and constructors {0,Cons,False,Nil,S,True} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs bsort#(0(),xs) -> c_1() bsort#(S(x'),Cons(x,xs)) -> c_2(bsort#(x',bubble(x,xs)),bubble#(x,xs)) bubble#(x,Nil()) -> c_3()
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Runti Compl Inner Rewri 22807