tct-trs: Prelude.head: empty list tct-trs: Prelude.head: empty list tct-trs: Prelude.head: empty list tct-trs: Prelude.head: empty list WORST_CASE(Omega(n^1),?) * Step 1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: ADD(0(),z0) -> c10() ADD(s(z0),z1) -> c11(ADD(z0,z1)) COND1(true(),z0,z1,z2) -> c(COND2(gr(z0,0()),z0,z1,z2),GR(z0,0())) COND2(false(),z0,z1,z2) -> c3(COND3(gr(z1,0()),z0,z1,z2),GR(z1,0())) COND2(true(),z0,z1,z2) -> c1(COND1(gr(add(z0,z1),z2),p(z0),z1,z2),GR(add(z0,z1),z2),ADD(z0,z1)) COND2(true(),z0,z1,z2) -> c2(COND1(gr(add(z0,z1),z2),p(z0),z1,z2),P(z0)) COND3(false(),z0,z1,z2) -> c6(COND1(gr(add(z0,z1),z2),z0,z1,z2),GR(add(z0,z1),z2),ADD(z0,z1)) COND3(true(),z0,z1,z2) -> c4(COND1(gr(add(z0,z1),z2),z0,p(z1),z2),GR(add(z0,z1),z2),ADD(z0,z1)) COND3(true(),z0,z1,z2) -> c5(COND1(gr(add(z0,z1),z2),z0,p(z1),z2),P(z1)) GR(0(),z0) -> c7() GR(s(z0),0()) -> c8() GR(s(z0),s(z1)) -> c9(GR(z0,z1)) P(0()) -> c12() P(s(z0)) -> c13() - Weak TRS: add(0(),z0) -> z0 add(s(z0),z1) -> s(add(z0,z1)) cond1(true(),z0,z1,z2) -> cond2(gr(z0,0()),z0,z1,z2) cond2(false(),z0,z1,z2) -> cond3(gr(z1,0()),z0,z1,z2) cond2(true(),z0,z1,z2) -> cond1(gr(add(z0,z1),z2),p(z0),z1,z2) cond3(false(),z0,z1,z2) -> cond1(gr(add(z0,z1),z2),z0,z1,z2) cond3(true(),z0,z1,z2) -> cond1(gr(add(z0,z1),z2),z0,p(z1),z2) gr(0(),z0) -> false() gr(s(z0),0()) -> true() gr(s(z0),s(z1)) -> gr(z0,z1) p(0()) -> 0() p(s(z0)) -> z0 - Signature: {ADD/2,COND1/4,COND2/4,COND3/4,GR/2,P/1,add/2,cond1/4,cond2/4,cond3/4,gr/2,p/1} / {0/0,c/2,c1/3,c10/0,c11/1 ,c12/0,c13/0,c2/2,c3/2,c4/3,c5/2,c6/3,c7/0,c8/0,c9/1,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {ADD,COND1,COND2,COND3,GR,P,add,cond1,cond2,cond3,gr ,p} and constructors {0,c,c1,c10,c11,c12,c13,c2,c3,c4,c5,c6,c7,c8,c9,false,s,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: ADD(0(),z0) -> c10() ADD(s(z0),z1) -> c11(ADD(z0,z1)) COND1(true(),z0,z1,z2) -> c(COND2(gr(z0,0()),z0,z1,z2),GR(z0,0())) COND2(false(),z0,z1,z2) -> c3(COND3(gr(z1,0()),z0,z1,z2),GR(z1,0())) COND2(true(),z0,z1,z2) -> c1(COND1(gr(add(z0,z1),z2),p(z0),z1,z2),GR(add(z0,z1),z2),ADD(z0,z1)) COND2(true(),z0,z1,z2) -> c2(COND1(gr(add(z0,z1),z2),p(z0),z1,z2),P(z0)) COND3(false(),z0,z1,z2) -> c6(COND1(gr(add(z0,z1),z2),z0,z1,z2),GR(add(z0,z1),z2),ADD(z0,z1)) COND3(true(),z0,z1,z2) -> c4(COND1(gr(add(z0,z1),z2),z0,p(z1),z2),GR(add(z0,z1),z2),ADD(z0,z1)) COND3(true(),z0,z1,z2) -> c5(COND1(gr(add(z0,z1),z2),z0,p(z1),z2),P(z1)) GR(0(),z0) -> c7() GR(s(z0),0()) -> c8() GR(s(z0),s(z1)) -> c9(GR(z0,z1)) P(0()) -> c12() P(s(z0)) -> c13() - Weak TRS: add(0(),z0) -> z0 add(s(z0),z1) -> s(add(z0,z1)) cond1(true(),z0,z1,z2) -> cond2(gr(z0,0()),z0,z1,z2) cond2(false(),z0,z1,z2) -> cond3(gr(z1,0()),z0,z1,z2) cond2(true(),z0,z1,z2) -> cond1(gr(add(z0,z1),z2),p(z0),z1,z2) cond3(false(),z0,z1,z2) -> cond1(gr(add(z0,z1),z2),z0,z1,z2) cond3(true(),z0,z1,z2) -> cond1(gr(add(z0,z1),z2),z0,p(z1),z2) gr(0(),z0) -> false() gr(s(z0),0()) -> true() gr(s(z0),s(z1)) -> gr(z0,z1) p(0()) -> 0() p(s(z0)) -> z0 - Signature: {ADD/2,COND1/4,COND2/4,COND3/4,GR/2,P/1,add/2,cond1/4,cond2/4,cond3/4,gr/2,p/1} / {0/0,c/2,c1/3,c10/0,c11/1 ,c12/0,c13/0,c2/2,c3/2,c4/3,c5/2,c6/3,c7/0,c8/0,c9/1,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {ADD,COND1,COND2,COND3,GR,P,add,cond1,cond2,cond3,gr ,p} and constructors {0,c,c1,c10,c11,c12,c13,c2,c3,c4,c5,c6,c7,c8,c9,false,s,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 3: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: ADD(0(),z0) -> c10() ADD(s(z0),z1) -> c11(ADD(z0,z1)) COND1(true(),z0,z1,z2) -> c(COND2(gr(z0,0()),z0,z1,z2),GR(z0,0())) COND2(false(),z0,z1,z2) -> c3(COND3(gr(z1,0()),z0,z1,z2),GR(z1,0())) COND2(true(),z0,z1,z2) -> c1(COND1(gr(add(z0,z1),z2),p(z0),z1,z2),GR(add(z0,z1),z2),ADD(z0,z1)) COND2(true(),z0,z1,z2) -> c2(COND1(gr(add(z0,z1),z2),p(z0),z1,z2),P(z0)) COND3(false(),z0,z1,z2) -> c6(COND1(gr(add(z0,z1),z2),z0,z1,z2),GR(add(z0,z1),z2),ADD(z0,z1)) COND3(true(),z0,z1,z2) -> c4(COND1(gr(add(z0,z1),z2),z0,p(z1),z2),GR(add(z0,z1),z2),ADD(z0,z1)) COND3(true(),z0,z1,z2) -> c5(COND1(gr(add(z0,z1),z2),z0,p(z1),z2),P(z1)) GR(0(),z0) -> c7() GR(s(z0),0()) -> c8() GR(s(z0),s(z1)) -> c9(GR(z0,z1)) P(0()) -> c12() P(s(z0)) -> c13() - Weak TRS: add(0(),z0) -> z0 add(s(z0),z1) -> s(add(z0,z1)) cond1(true(),z0,z1,z2) -> cond2(gr(z0,0()),z0,z1,z2) cond2(false(),z0,z1,z2) -> cond3(gr(z1,0()),z0,z1,z2) cond2(true(),z0,z1,z2) -> cond1(gr(add(z0,z1),z2),p(z0),z1,z2) cond3(false(),z0,z1,z2) -> cond1(gr(add(z0,z1),z2),z0,z1,z2) cond3(true(),z0,z1,z2) -> cond1(gr(add(z0,z1),z2),z0,p(z1),z2) gr(0(),z0) -> false() gr(s(z0),0()) -> true() gr(s(z0),s(z1)) -> gr(z0,z1) p(0()) -> 0() p(s(z0)) -> z0 - Signature: {ADD/2,COND1/4,COND2/4,COND3/4,GR/2,P/1,add/2,cond1/4,cond2/4,cond3/4,gr/2,p/1} / {0/0,c/2,c1/3,c10/0,c11/1 ,c12/0,c13/0,c2/2,c3/2,c4/3,c5/2,c6/3,c7/0,c8/0,c9/1,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {ADD,COND1,COND2,COND3,GR,P,add,cond1,cond2,cond3,gr ,p} and constructors {0,c,c1,c10,c11,c12,c13,c2,c3,c4,c5,c6,c7,c8,c9,false,s,true} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: ADD(x,y){x -> s(x)} = ADD(s(x),y) ->^+ c11(ADD(x,y)) = C[ADD(x,y) = ADD(x,y){}] WORST_CASE(Omega(n^1),?)