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