YES(?,POLY) * Step 1: FromIts WORST_CASE(?,POLY) + Considered Problem: Rules: 0. start(A,B,C,D) -> stop1(A,B,C,D) [A + -1*D >= 0 (?,1) && D >= 0 && C + D >= 0 && B + D >= 0 && A + D >= 0 && C >= 0 && B + C >= 0 && A + C >= 0 && B >= 0 && A + B >= 0 && A >= 0 && D = 0] 1. start(A,B,C,D) -> cont1(A,B,C,D) [A + -1*D >= 0 (?,1) && D >= 0 && C + D >= 0 && B + D >= 0 && A + D >= 0 && C >= 0 && B + C >= 0 && A + C >= 0 && B >= 0 && A + B >= 0 && A >= 0 && D >= 1 && A >= D] 2. cont1(A,B,C,D) -> stop2(A,B,1,-1 + D) [A + -1*D >= 0 (?,1) && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && D >= 1 && A >= D && C = 0] 3. cont1(A,B,C,D) -> a(A,B,-1 + C,D) [A + -1*D >= 0 (?,1) && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && C >= 1 && D >= 1 && A >= D] 4. a(A,B,C,D) -> b(A,B,E,-1 + D) [A + -1*D >= 0 (?,1) && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && A >= D && D >= 1] 5. b(A,B,C,D) -> start(A,B,C,D) [-1 + A + -1*D >= 0 (?,1) && D >= 0 && B + D >= 0 && -1 + A + D >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && C >= 0 && A >= 1 + D] 6. b(A,B,C,D) -> stop3(A,B,C,D) [-1 + A + -1*D >= 0 (?,1) && D >= 0 && B + D >= 0 && -1 + A + D >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && 0 >= 1 + C && A >= 1 + D] 7. start0(A,B,C,D) -> start(A,B,B,A) [A >= 0 && B >= 0] (1,1) Signature: {(a,4);(b,4);(cont1,4);(start,4);(start0,4);(stop1,4);(stop2,4);(stop3,4)} Flow Graph: [0->{},1->{2,3},2->{},3->{4},4->{5,6},5->{0,1},6->{},7->{0,1}] + Applied Processor: FromIts + Details: () * Step 2: AddSinks WORST_CASE(?,POLY) + Considered Problem: Rules: start(A,B,C,D) -> stop1(A,B,C,D) [A + -1*D >= 0 && D >= 0 && C + D >= 0 && B + D >= 0 && A + D >= 0 && C >= 0 && B + C >= 0 && A + C >= 0 && B >= 0 && A + B >= 0 && A >= 0 && D = 0] start(A,B,C,D) -> cont1(A,B,C,D) [A + -1*D >= 0 && D >= 0 && C + D >= 0 && B + D >= 0 && A + D >= 0 && C >= 0 && B + C >= 0 && A + C >= 0 && B >= 0 && A + B >= 0 && A >= 0 && D >= 1 && A >= D] cont1(A,B,C,D) -> stop2(A,B,1,-1 + D) [A + -1*D >= 0 && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && D >= 1 && A >= D && C = 0] cont1(A,B,C,D) -> a(A,B,-1 + C,D) [A + -1*D >= 0 && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && C >= 1 && D >= 1 && A >= D] a(A,B,C,D) -> b(A,B,E,-1 + D) [A + -1*D >= 0 && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && A >= D && D >= 1] b(A,B,C,D) -> start(A,B,C,D) [-1 + A + -1*D >= 0 && D >= 0 && B + D >= 0 && -1 + A + D >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && C >= 0 && A >= 1 + D] b(A,B,C,D) -> stop3(A,B,C,D) [-1 + A + -1*D >= 0 && D >= 0 && B + D >= 0 && -1 + A + D >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && 0 >= 1 + C && A >= 1 + D] start0(A,B,C,D) -> start(A,B,B,A) [A >= 0 && B >= 0] Signature: {(a,4);(b,4);(cont1,4);(start,4);(start0,4);(stop1,4);(stop2,4);(stop3,4)} Rule Graph: [0->{},1->{2,3},2->{},3->{4},4->{5,6},5->{0,1},6->{},7->{0,1}] + Applied Processor: AddSinks + Details: () * Step 3: Decompose WORST_CASE(?,POLY) + Considered Problem: Rules: start(A,B,C,D) -> stop1(A,B,C,D) [A + -1*D >= 0 && D >= 0 && C + D >= 0 && B + D >= 0 && A + D >= 0 && C >= 0 && B + C >= 0 && A + C >= 0 && B >= 0 && A + B >= 0 && A >= 0 && D = 0] start(A,B,C,D) -> cont1(A,B,C,D) [A + -1*D >= 0 && D >= 0 && C + D >= 0 && B + D >= 0 && A + D >= 0 && C >= 0 && B + C >= 0 && A + C >= 0 && B >= 0 && A + B >= 0 && A >= 0 && D >= 1 && A >= D] cont1(A,B,C,D) -> stop2(A,B,1,-1 + D) [A + -1*D >= 0 && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && D >= 1 && A >= D && C = 0] cont1(A,B,C,D) -> a(A,B,-1 + C,D) [A + -1*D >= 0 && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && C >= 1 && D >= 1 && A >= D] a(A,B,C,D) -> b(A,B,E,-1 + D) [A + -1*D >= 0 && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && A >= D && D >= 1] b(A,B,C,D) -> start(A,B,C,D) [-1 + A + -1*D >= 0 && D >= 0 && B + D >= 0 && -1 + A + D >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && C >= 0 && A >= 1 + D] b(A,B,C,D) -> stop3(A,B,C,D) [-1 + A + -1*D >= 0 && D >= 0 && B + D >= 0 && -1 + A + D >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && 0 >= 1 + C && A >= 1 + D] start0(A,B,C,D) -> start(A,B,B,A) [A >= 0 && B >= 0] stop3(A,B,C,D) -> exitus616(A,B,C,D) True stop2(A,B,C,D) -> exitus616(A,B,C,D) True stop1(A,B,C,D) -> exitus616(A,B,C,D) True Signature: {(a,4);(b,4);(cont1,4);(exitus616,4);(start,4);(start0,4);(stop1,4);(stop2,4);(stop3,4)} Rule Graph: [0->{10},1->{2,3},2->{9},3->{4},4->{5,6},5->{0,1},6->{8},7->{0,1}] + Applied Processor: Decompose Greedy + Details: We construct a looptree: P: [0,1,2,3,4,5,6,7,8,9,10] | `- p:[1,5,4,3] c: [1,3,4,5] * Step 4: AbstractSize WORST_CASE(?,POLY) + Considered Problem: (Rules: start(A,B,C,D) -> stop1(A,B,C,D) [A + -1*D >= 0 && D >= 0 && C + D >= 0 && B + D >= 0 && A + D >= 0 && C >= 0 && B + C >= 0 && A + C >= 0 && B >= 0 && A + B >= 0 && A >= 0 && D = 0] start(A,B,C,D) -> cont1(A,B,C,D) [A + -1*D >= 0 && D >= 0 && C + D >= 0 && B + D >= 0 && A + D >= 0 && C >= 0 && B + C >= 0 && A + C >= 0 && B >= 0 && A + B >= 0 && A >= 0 && D >= 1 && A >= D] cont1(A,B,C,D) -> stop2(A,B,1,-1 + D) [A + -1*D >= 0 && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && D >= 1 && A >= D && C = 0] cont1(A,B,C,D) -> a(A,B,-1 + C,D) [A + -1*D >= 0 && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && C >= 1 && D >= 1 && A >= D] a(A,B,C,D) -> b(A,B,E,-1 + D) [A + -1*D >= 0 && -1 + D >= 0 && -1 + C + D >= 0 && -1 + B + D >= 0 && -2 + A + D >= 0 && C >= 0 && B + C >= 0 && -1 + A + C >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && A >= D && D >= 1] b(A,B,C,D) -> start(A,B,C,D) [-1 + A + -1*D >= 0 && D >= 0 && B + D >= 0 && -1 + A + D >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && C >= 0 && A >= 1 + D] b(A,B,C,D) -> stop3(A,B,C,D) [-1 + A + -1*D >= 0 && D >= 0 && B + D >= 0 && -1 + A + D >= 0 && B >= 0 && -1 + A + B >= 0 && -1 + A >= 0 && 0 >= 1 + C && A >= 1 + D] start0(A,B,C,D) -> start(A,B,B,A) [A >= 0 && B >= 0] stop3(A,B,C,D) -> exitus616(A,B,C,D) True stop2(A,B,C,D) -> exitus616(A,B,C,D) True stop1(A,B,C,D) -> exitus616(A,B,C,D) True Signature: {(a,4);(b,4);(cont1,4);(exitus616,4);(start,4);(start0,4);(stop1,4);(stop2,4);(stop3,4)} Rule Graph: [0->{10},1->{2,3},2->{9},3->{4},4->{5,6},5->{0,1},6->{8},7->{0,1}] ,We construct a looptree: P: [0,1,2,3,4,5,6,7,8,9,10] | `- p:[1,5,4,3] c: [1,3,4,5]) + Applied Processor: AbstractSize Minimize + Details: () * Step 5: AbstractFlow WORST_CASE(?,POLY) + Considered Problem: Program: Domain: [A,B,C,D,0.0] start ~> stop1 [A <= A, B <= B, C <= C, D <= D] start ~> cont1 [A <= A, B <= B, C <= C, D <= D] cont1 ~> stop2 [A <= A, B <= B, C <= K, D <= D] cont1 ~> a [A <= A, B <= B, C <= C, D <= D] a ~> b [A <= A, B <= B, C <= unknown, D <= D] b ~> start [A <= A, B <= B, C <= C, D <= D] b ~> stop3 [A <= A, B <= B, C <= C, D <= D] start0 ~> start [A <= A, B <= B, C <= B, D <= A] stop3 ~> exitus616 [A <= A, B <= B, C <= C, D <= D] stop2 ~> exitus616 [A <= A, B <= B, C <= C, D <= D] stop1 ~> exitus616 [A <= A, B <= B, C <= C, D <= D] + Loop: [0.0 <= K + D] start ~> cont1 [A <= A, B <= B, C <= C, D <= D] b ~> start [A <= A, B <= B, C <= C, D <= D] a ~> b [A <= A, B <= B, C <= unknown, D <= D] cont1 ~> a [A <= A, B <= B, C <= C, D <= D] + Applied Processor: AbstractFlow + Details: () * Step 6: Lare WORST_CASE(?,POLY) + Considered Problem: Program: Domain: [tick,huge,K,A,B,C,D,0.0] start ~> stop1 [] start ~> cont1 [] cont1 ~> stop2 [K ~=> C] cont1 ~> a [] a ~> b [huge ~=> C] b ~> start [] b ~> stop3 [] start0 ~> start [A ~=> D,B ~=> C] stop3 ~> exitus616 [] stop2 ~> exitus616 [] stop1 ~> exitus616 [] + Loop: [D ~+> 0.0,K ~+> 0.0] start ~> cont1 [] b ~> start [] a ~> b [huge ~=> C] cont1 ~> a [] + Applied Processor: Lare + Details: start0 ~> exitus616 [A ~=> D ,B ~=> C ,K ~=> C ,huge ~=> C ,A ~+> 0.0 ,A ~+> tick ,tick ~+> tick ,K ~+> 0.0 ,K ~+> tick ,A ~*> tick ,K ~*> tick] + b> [huge ~=> C,D ~+> 0.0,D ~+> tick,tick ~+> tick,K ~+> 0.0,K ~+> tick] cont1> [huge ~=> C,D ~+> 0.0,D ~+> tick,tick ~+> tick,K ~+> 0.0,K ~+> tick] start> [huge ~=> C,D ~+> 0.0,D ~+> tick,tick ~+> tick,K ~+> 0.0,K ~+> tick] YES(?,POLY)