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