/export/starexec/sandbox2/solver/bin/starexec_run_tct_rc /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1),?) * Step 1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: +(x,+(y,z)) -> +(+(x,y),z) +(x,0()) -> x +(0(),x) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(I(x),O(y)) -> I(+(x,y)) +(O(x),I(y)) -> I(+(x,y)) +(O(x),O(y)) -> O(+(x,y)) -(x,0()) -> x -(0(),x) -> 0() -(I(x),I(y)) -> O(-(x,y)) -(I(x),O(y)) -> I(-(x,y)) -(O(x),I(y)) -> I(-(-(x,y),I(1()))) -(O(x),O(y)) -> O(-(x,y)) BS(L(x)) -> true() BS(N(x,l(),r())) -> and(and(ge(x,Max(l())),ge(Min(r()),x)),and(BS(l()),BS(r()))) Log(x) -> -(Log'(x),I(0())) Log'(0()) -> 0() Log'(I(x)) -> +(Log'(x),I(0())) Log'(O(x)) -> if(ge(x,I(0())),+(Log'(x),I(0())),0()) Max(L(x)) -> x Max(N(x,l(),r())) -> Max(r()) Min(L(x)) -> x Min(N(x,l(),r())) -> Min(l()) O(0()) -> 0() Size(L(x)) -> I(0()) Size(N(x,l(),r())) -> +(+(Size(l()),Size(r())),I(1())) Val(L(x)) -> x Val(N(x,l(),r())) -> x WB(L(x)) -> true() WB(N(x,l(),r())) -> and(if(ge(Size(l()),Size(r())) ,ge(I(0()),-(Size(l()),Size(r()))) ,ge(I(0()),-(Size(r()),Size(l())))) ,and(WB(l()),WB(r()))) and(x,false()) -> false() and(x,true()) -> x ge(x,0()) -> true() ge(0(),I(x)) -> false() ge(0(),O(x)) -> ge(0(),x) ge(I(x),I(y)) -> ge(x,y) ge(I(x),O(y)) -> ge(x,y) ge(O(x),I(y)) -> not(ge(y,x)) ge(O(x),O(y)) -> ge(x,y) if(false(),x,y) -> y if(true(),x,y) -> x not(false()) -> true() not(true()) -> false() - Signature: {+/2,-/2,BS/1,Log/1,Log'/1,Max/1,Min/1,O/1,Size/1,Val/1,WB/1,and/2,ge/2,if/3,not/1} / {0/0,1/0,I/1,L/1,N/3 ,false/0,l/0,r/0,true/0} - Obligation: runtime complexity wrt. defined symbols {+,-,BS,Log,Log',Max,Min,O,Size,Val,WB,and,ge,if ,not} and constructors {0,1,I,L,N,false,l,r,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: +(x,+(y,z)) -> +(+(x,y),z) +(x,0()) -> x +(0(),x) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(I(x),O(y)) -> I(+(x,y)) +(O(x),I(y)) -> I(+(x,y)) +(O(x),O(y)) -> O(+(x,y)) -(x,0()) -> x -(0(),x) -> 0() -(I(x),I(y)) -> O(-(x,y)) -(I(x),O(y)) -> I(-(x,y)) -(O(x),I(y)) -> I(-(-(x,y),I(1()))) -(O(x),O(y)) -> O(-(x,y)) BS(L(x)) -> true() BS(N(x,l(),r())) -> and(and(ge(x,Max(l())),ge(Min(r()),x)),and(BS(l()),BS(r()))) Log(x) -> -(Log'(x),I(0())) Log'(0()) -> 0() Log'(I(x)) -> +(Log'(x),I(0())) Log'(O(x)) -> if(ge(x,I(0())),+(Log'(x),I(0())),0()) Max(L(x)) -> x Max(N(x,l(),r())) -> Max(r()) Min(L(x)) -> x Min(N(x,l(),r())) -> Min(l()) O(0()) -> 0() Size(L(x)) -> I(0()) Size(N(x,l(),r())) -> +(+(Size(l()),Size(r())),I(1())) Val(L(x)) -> x Val(N(x,l(),r())) -> x WB(L(x)) -> true() WB(N(x,l(),r())) -> and(if(ge(Size(l()),Size(r())) ,ge(I(0()),-(Size(l()),Size(r()))) ,ge(I(0()),-(Size(r()),Size(l())))) ,and(WB(l()),WB(r()))) and(x,false()) -> false() and(x,true()) -> x ge(x,0()) -> true() ge(0(),I(x)) -> false() ge(0(),O(x)) -> ge(0(),x) ge(I(x),I(y)) -> ge(x,y) ge(I(x),O(y)) -> ge(x,y) ge(O(x),I(y)) -> not(ge(y,x)) ge(O(x),O(y)) -> ge(x,y) if(false(),x,y) -> y if(true(),x,y) -> x not(false()) -> true() not(true()) -> false() - Signature: {+/2,-/2,BS/1,Log/1,Log'/1,Max/1,Min/1,O/1,Size/1,Val/1,WB/1,and/2,ge/2,if/3,not/1} / {0/0,1/0,I/1,L/1,N/3 ,false/0,l/0,r/0,true/0} - Obligation: runtime complexity wrt. defined symbols {+,-,BS,Log,Log',Max,Min,O,Size,Val,WB,and,ge,if ,not} and constructors {0,1,I,L,N,false,l,r,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 3: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: +(x,+(y,z)) -> +(+(x,y),z) +(x,0()) -> x +(0(),x) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(I(x),O(y)) -> I(+(x,y)) +(O(x),I(y)) -> I(+(x,y)) +(O(x),O(y)) -> O(+(x,y)) -(x,0()) -> x -(0(),x) -> 0() -(I(x),I(y)) -> O(-(x,y)) -(I(x),O(y)) -> I(-(x,y)) -(O(x),I(y)) -> I(-(-(x,y),I(1()))) -(O(x),O(y)) -> O(-(x,y)) BS(L(x)) -> true() BS(N(x,l(),r())) -> and(and(ge(x,Max(l())),ge(Min(r()),x)),and(BS(l()),BS(r()))) Log(x) -> -(Log'(x),I(0())) Log'(0()) -> 0() Log'(I(x)) -> +(Log'(x),I(0())) Log'(O(x)) -> if(ge(x,I(0())),+(Log'(x),I(0())),0()) Max(L(x)) -> x Max(N(x,l(),r())) -> Max(r()) Min(L(x)) -> x Min(N(x,l(),r())) -> Min(l()) O(0()) -> 0() Size(L(x)) -> I(0()) Size(N(x,l(),r())) -> +(+(Size(l()),Size(r())),I(1())) Val(L(x)) -> x Val(N(x,l(),r())) -> x WB(L(x)) -> true() WB(N(x,l(),r())) -> and(if(ge(Size(l()),Size(r())) ,ge(I(0()),-(Size(l()),Size(r()))) ,ge(I(0()),-(Size(r()),Size(l())))) ,and(WB(l()),WB(r()))) and(x,false()) -> false() and(x,true()) -> x ge(x,0()) -> true() ge(0(),I(x)) -> false() ge(0(),O(x)) -> ge(0(),x) ge(I(x),I(y)) -> ge(x,y) ge(I(x),O(y)) -> ge(x,y) ge(O(x),I(y)) -> not(ge(y,x)) ge(O(x),O(y)) -> ge(x,y) if(false(),x,y) -> y if(true(),x,y) -> x not(false()) -> true() not(true()) -> false() - Signature: {+/2,-/2,BS/1,Log/1,Log'/1,Max/1,Min/1,O/1,Size/1,Val/1,WB/1,and/2,ge/2,if/3,not/1} / {0/0,1/0,I/1,L/1,N/3 ,false/0,l/0,r/0,true/0} - Obligation: runtime complexity wrt. defined symbols {+,-,BS,Log,Log',Max,Min,O,Size,Val,WB,and,ge,if ,not} and constructors {0,1,I,L,N,false,l,r,true} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: +(x,y){x -> I(x),y -> I(y)} = +(I(x),I(y)) ->^+ O(+(+(x,y),I(0()))) = C[+(x,y) = +(x,y){}] WORST_CASE(Omega(n^1),?)