Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Runti Compl Inner Rewri 22807 pair #381905025
details
property
value
status
complete
benchmark
shuffle.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n071.star.cs.uiowa.edu
space
Frederiksen_Glenstrup
run statistics
property
value
solver
tct 2018-07-13
configuration
tct_rci
runtime (wallclock)
3.57258892059 seconds
cpu usage
16.436786382
max memory
1.06430464E8
stage attributes
key
value
output-size
32630
starexec-result
WORST_CASE(Omega(n^1),O(n^3))
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),O(n^3)) * Step 1: Sum WORST_CASE(Omega(n^1),O(n^3)) + Considered Problem: - Strict TRS: append(Cons(x,xs),ys) -> Cons(x,append(xs,ys)) append(Nil(),ys) -> ys goal(xs) -> shuffle(xs) reverse(Cons(x,xs)) -> append(reverse(xs),Cons(x,Nil())) reverse(Nil()) -> Nil() shuffle(Cons(x,xs)) -> Cons(x,shuffle(reverse(xs))) shuffle(Nil()) -> Nil() - Signature: {append/2,goal/1,reverse/1,shuffle/1} / {Cons/2,Nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {append,goal,reverse,shuffle} and constructors {Cons,Nil} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: append(Cons(x,xs),ys) -> Cons(x,append(xs,ys)) append(Nil(),ys) -> ys goal(xs) -> shuffle(xs) reverse(Cons(x,xs)) -> append(reverse(xs),Cons(x,Nil())) reverse(Nil()) -> Nil() shuffle(Cons(x,xs)) -> Cons(x,shuffle(reverse(xs))) shuffle(Nil()) -> Nil() - Signature: {append/2,goal/1,reverse/1,shuffle/1} / {Cons/2,Nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {append,goal,reverse,shuffle} and constructors {Cons,Nil} + 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){}] ** Step 1.b:1: DependencyPairs WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: append(Cons(x,xs),ys) -> Cons(x,append(xs,ys)) append(Nil(),ys) -> ys goal(xs) -> shuffle(xs) reverse(Cons(x,xs)) -> append(reverse(xs),Cons(x,Nil())) reverse(Nil()) -> Nil() shuffle(Cons(x,xs)) -> Cons(x,shuffle(reverse(xs))) shuffle(Nil()) -> Nil() - Signature: {append/2,goal/1,reverse/1,shuffle/1} / {Cons/2,Nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {append,goal,reverse,shuffle} and constructors {Cons,Nil} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs append#(Cons(x,xs),ys) -> c_1(append#(xs,ys)) append#(Nil(),ys) -> c_2() goal#(xs) -> c_3(shuffle#(xs)) reverse#(Cons(x,xs)) -> c_4(append#(reverse(xs),Cons(x,Nil())),reverse#(xs)) reverse#(Nil()) -> c_5() shuffle#(Cons(x,xs)) -> c_6(shuffle#(reverse(xs)),reverse#(xs)) shuffle#(Nil()) -> c_7() Weak DPs and mark the set of starting terms. ** Step 1.b:2: PredecessorEstimation WORST_CASE(?,O(n^3)) + Considered Problem: - Strict DPs: append#(Cons(x,xs),ys) -> c_1(append#(xs,ys)) append#(Nil(),ys) -> c_2() goal#(xs) -> c_3(shuffle#(xs)) reverse#(Cons(x,xs)) -> c_4(append#(reverse(xs),Cons(x,Nil())),reverse#(xs)) reverse#(Nil()) -> c_5() shuffle#(Cons(x,xs)) -> c_6(shuffle#(reverse(xs)),reverse#(xs)) shuffle#(Nil()) -> c_7() - Weak TRS: append(Cons(x,xs),ys) -> Cons(x,append(xs,ys)) append(Nil(),ys) -> ys goal(xs) -> shuffle(xs) reverse(Cons(x,xs)) -> append(reverse(xs),Cons(x,Nil())) reverse(Nil()) -> Nil() shuffle(Cons(x,xs)) -> Cons(x,shuffle(reverse(xs))) shuffle(Nil()) -> Nil() - Signature: {append/2,goal/1,reverse/1,shuffle/1,append#/2,goal#/1,reverse#/1,shuffle#/1} / {Cons/2,Nil/0,c_1/1,c_2/0 ,c_3/1,c_4/2,c_5/0,c_6/2,c_7/0} - Obligation:
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Runti Compl Inner Rewri 22807