YES(?,POLY) * Step 1: FromIts WORST_CASE(?,POLY) + Considered Problem: Rules: 0. f0(A,B,C,D,E,F,G,H,I,J) -> f17(0,K,L,0,E,F,G,H,I,J) True (1,1) 1. f17(A,B,C,D,E,F,G,H,I,J) -> f17(A,B,C,1 + D,E,F,G,H,I,J) [E >= 1 + D] (?,1) 2. f27(A,B,C,D,E,F,G,H,I,J) -> f27(A,B,C,D,E,-1 + F,G,H,I,J) [F >= 0] (?,1) 3. f37(A,B,C,D,E,F,G,H,I,J) -> f37(A,B,C,D,E,F,1 + G,H,I,J) [E >= 1 + G] (?,1) 4. f45(A,B,C,D,E,F,G,H,I,J) -> f45(1 + A,B,C,D,E,F,G,H,I,J) [E >= 1 + A] (?,1) 5. f55(A,B,C,D,E,F,G,H,I,J) -> f55(A,B,C,D,E,F,G,1 + H,I,J) [E >= 1 + H] (?,1) 6. f65(A,B,C,D,E,F,G,H,I,J) -> f65(A,B,C,D,E,F,G,H,-1 + I,J) [I >= 0] (?,1) 7. f75(A,B,C,D,E,F,G,H,I,J) -> f75(A,B,C,D,E,F,G,H,I,1 + J) [E >= 1 + J] (?,1) 8. f83(A,B,C,D,E,F,G,H,I,J) -> f83(-1 + A,B,C,D,E,F,G,H,I,J) [A >= 0] (?,1) 9. f83(A,B,C,D,E,F,G,H,I,J) -> f93(A,B,C,D,E,F,G,H,I,J) [0 >= 1 + A] (?,1) 10. f75(A,B,C,D,E,F,G,H,I,J) -> f83(-1 + E,B,C,D,E,F,G,H,I,J) [J >= E] (?,1) 11. f65(A,B,C,D,E,F,G,H,I,J) -> f75(A,B,C,D,E,F,G,H,I,0) [0 >= 1 + I] (?,1) 12. f55(A,B,C,D,E,F,G,H,I,J) -> f65(A,B,C,D,E,F,G,H,-1 + E,J) [H >= E] (?,1) 13. f45(A,B,C,D,E,F,G,H,I,J) -> f55(A,B,C,D,E,F,G,0,I,J) [A >= E] (?,1) 14. f37(A,B,C,D,E,F,G,H,I,J) -> f45(0,B,C,D,E,F,G,H,I,J) [G >= E] (?,1) 15. f27(A,B,C,D,E,F,G,H,I,J) -> f37(A,B,C,D,E,F,0,H,I,J) [0 >= 1 + F] (?,1) 16. f17(A,B,C,D,E,F,G,H,I,J) -> f27(A,B,C,D,E,-1 + E,G,H,I,J) [D >= E] (?,1) Signature: {(f0,10);(f17,10);(f27,10);(f37,10);(f45,10);(f55,10);(f65,10);(f75,10);(f83,10);(f93,10)} Flow Graph: [0->{1,16},1->{1,16},2->{2,15},3->{3,14},4->{4,13},5->{5,12},6->{6,11},7->{7,10},8->{8,9},9->{},10->{8,9} ,11->{7,10},12->{6,11},13->{5,12},14->{4,13},15->{3,14},16->{2,15}] + Applied Processor: FromIts + Details: () * Step 2: AddSinks WORST_CASE(?,POLY) + Considered Problem: Rules: f0(A,B,C,D,E,F,G,H,I,J) -> f17(0,K,L,0,E,F,G,H,I,J) True f17(A,B,C,D,E,F,G,H,I,J) -> f17(A,B,C,1 + D,E,F,G,H,I,J) [E >= 1 + D] f27(A,B,C,D,E,F,G,H,I,J) -> f27(A,B,C,D,E,-1 + F,G,H,I,J) [F >= 0] f37(A,B,C,D,E,F,G,H,I,J) -> f37(A,B,C,D,E,F,1 + G,H,I,J) [E >= 1 + G] f45(A,B,C,D,E,F,G,H,I,J) -> f45(1 + A,B,C,D,E,F,G,H,I,J) [E >= 1 + A] f55(A,B,C,D,E,F,G,H,I,J) -> f55(A,B,C,D,E,F,G,1 + H,I,J) [E >= 1 + H] f65(A,B,C,D,E,F,G,H,I,J) -> f65(A,B,C,D,E,F,G,H,-1 + I,J) [I >= 0] f75(A,B,C,D,E,F,G,H,I,J) -> f75(A,B,C,D,E,F,G,H,I,1 + J) [E >= 1 + J] f83(A,B,C,D,E,F,G,H,I,J) -> f83(-1 + A,B,C,D,E,F,G,H,I,J) [A >= 0] f83(A,B,C,D,E,F,G,H,I,J) -> f93(A,B,C,D,E,F,G,H,I,J) [0 >= 1 + A] f75(A,B,C,D,E,F,G,H,I,J) -> f83(-1 + E,B,C,D,E,F,G,H,I,J) [J >= E] f65(A,B,C,D,E,F,G,H,I,J) -> f75(A,B,C,D,E,F,G,H,I,0) [0 >= 1 + I] f55(A,B,C,D,E,F,G,H,I,J) -> f65(A,B,C,D,E,F,G,H,-1 + E,J) [H >= E] f45(A,B,C,D,E,F,G,H,I,J) -> f55(A,B,C,D,E,F,G,0,I,J) [A >= E] f37(A,B,C,D,E,F,G,H,I,J) -> f45(0,B,C,D,E,F,G,H,I,J) [G >= E] f27(A,B,C,D,E,F,G,H,I,J) -> f37(A,B,C,D,E,F,0,H,I,J) [0 >= 1 + F] f17(A,B,C,D,E,F,G,H,I,J) -> f27(A,B,C,D,E,-1 + E,G,H,I,J) [D >= E] Signature: {(f0,10);(f17,10);(f27,10);(f37,10);(f45,10);(f55,10);(f65,10);(f75,10);(f83,10);(f93,10)} Rule Graph: [0->{1,16},1->{1,16},2->{2,15},3->{3,14},4->{4,13},5->{5,12},6->{6,11},7->{7,10},8->{8,9},9->{},10->{8,9} ,11->{7,10},12->{6,11},13->{5,12},14->{4,13},15->{3,14},16->{2,15}] + Applied Processor: AddSinks + Details: () * Step 3: Decompose WORST_CASE(?,POLY) + Considered Problem: Rules: f0(A,B,C,D,E,F,G,H,I,J) -> f17(0,K,L,0,E,F,G,H,I,J) True f17(A,B,C,D,E,F,G,H,I,J) -> f17(A,B,C,1 + D,E,F,G,H,I,J) [E >= 1 + D] f27(A,B,C,D,E,F,G,H,I,J) -> f27(A,B,C,D,E,-1 + F,G,H,I,J) [F >= 0] f37(A,B,C,D,E,F,G,H,I,J) -> f37(A,B,C,D,E,F,1 + G,H,I,J) [E >= 1 + G] f45(A,B,C,D,E,F,G,H,I,J) -> f45(1 + A,B,C,D,E,F,G,H,I,J) [E >= 1 + A] f55(A,B,C,D,E,F,G,H,I,J) -> f55(A,B,C,D,E,F,G,1 + H,I,J) [E >= 1 + H] f65(A,B,C,D,E,F,G,H,I,J) -> f65(A,B,C,D,E,F,G,H,-1 + I,J) [I >= 0] f75(A,B,C,D,E,F,G,H,I,J) -> f75(A,B,C,D,E,F,G,H,I,1 + J) [E >= 1 + J] f83(A,B,C,D,E,F,G,H,I,J) -> f83(-1 + A,B,C,D,E,F,G,H,I,J) [A >= 0] f83(A,B,C,D,E,F,G,H,I,J) -> f93(A,B,C,D,E,F,G,H,I,J) [0 >= 1 + A] f75(A,B,C,D,E,F,G,H,I,J) -> f83(-1 + E,B,C,D,E,F,G,H,I,J) [J >= E] f65(A,B,C,D,E,F,G,H,I,J) -> f75(A,B,C,D,E,F,G,H,I,0) [0 >= 1 + I] f55(A,B,C,D,E,F,G,H,I,J) -> f65(A,B,C,D,E,F,G,H,-1 + E,J) [H >= E] f45(A,B,C,D,E,F,G,H,I,J) -> f55(A,B,C,D,E,F,G,0,I,J) [A >= E] f37(A,B,C,D,E,F,G,H,I,J) -> f45(0,B,C,D,E,F,G,H,I,J) [G >= E] f27(A,B,C,D,E,F,G,H,I,J) -> f37(A,B,C,D,E,F,0,H,I,J) [0 >= 1 + F] f17(A,B,C,D,E,F,G,H,I,J) -> f27(A,B,C,D,E,-1 + E,G,H,I,J) [D >= E] f93(A,B,C,D,E,F,G,H,I,J) -> exitus616(A,B,C,D,E,F,G,H,I,J) True Signature: {(exitus616,10);(f0,10);(f17,10);(f27,10);(f37,10);(f45,10);(f55,10);(f65,10);(f75,10);(f83,10);(f93,10)} Rule Graph: [0->{1,16},1->{1,16},2->{2,15},3->{3,14},4->{4,13},5->{5,12},6->{6,11},7->{7,10},8->{8,9},9->{17},10->{8 ,9},11->{7,10},12->{6,11},13->{5,12},14->{4,13},15->{3,14},16->{2,15}] + Applied Processor: Decompose Greedy + Details: We construct a looptree: P: [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17] | +- p:[1] c: [1] | +- p:[2] c: [2] | +- p:[3] c: [3] | +- p:[4] c: [4] | +- p:[5] c: [5] | +- p:[6] c: [6] | +- p:[7] c: [7] | `- p:[8] c: [8] * Step 4: AbstractSize WORST_CASE(?,POLY) + Considered Problem: (Rules: f0(A,B,C,D,E,F,G,H,I,J) -> f17(0,K,L,0,E,F,G,H,I,J) True f17(A,B,C,D,E,F,G,H,I,J) -> f17(A,B,C,1 + D,E,F,G,H,I,J) [E >= 1 + D] f27(A,B,C,D,E,F,G,H,I,J) -> f27(A,B,C,D,E,-1 + F,G,H,I,J) [F >= 0] f37(A,B,C,D,E,F,G,H,I,J) -> f37(A,B,C,D,E,F,1 + G,H,I,J) [E >= 1 + G] f45(A,B,C,D,E,F,G,H,I,J) -> f45(1 + A,B,C,D,E,F,G,H,I,J) [E >= 1 + A] f55(A,B,C,D,E,F,G,H,I,J) -> f55(A,B,C,D,E,F,G,1 + H,I,J) [E >= 1 + H] f65(A,B,C,D,E,F,G,H,I,J) -> f65(A,B,C,D,E,F,G,H,-1 + I,J) [I >= 0] f75(A,B,C,D,E,F,G,H,I,J) -> f75(A,B,C,D,E,F,G,H,I,1 + J) [E >= 1 + J] f83(A,B,C,D,E,F,G,H,I,J) -> f83(-1 + A,B,C,D,E,F,G,H,I,J) [A >= 0] f83(A,B,C,D,E,F,G,H,I,J) -> f93(A,B,C,D,E,F,G,H,I,J) [0 >= 1 + A] f75(A,B,C,D,E,F,G,H,I,J) -> f83(-1 + E,B,C,D,E,F,G,H,I,J) [J >= E] f65(A,B,C,D,E,F,G,H,I,J) -> f75(A,B,C,D,E,F,G,H,I,0) [0 >= 1 + I] f55(A,B,C,D,E,F,G,H,I,J) -> f65(A,B,C,D,E,F,G,H,-1 + E,J) [H >= E] f45(A,B,C,D,E,F,G,H,I,J) -> f55(A,B,C,D,E,F,G,0,I,J) [A >= E] f37(A,B,C,D,E,F,G,H,I,J) -> f45(0,B,C,D,E,F,G,H,I,J) [G >= E] f27(A,B,C,D,E,F,G,H,I,J) -> f37(A,B,C,D,E,F,0,H,I,J) [0 >= 1 + F] f17(A,B,C,D,E,F,G,H,I,J) -> f27(A,B,C,D,E,-1 + E,G,H,I,J) [D >= E] f93(A,B,C,D,E,F,G,H,I,J) -> exitus616(A,B,C,D,E,F,G,H,I,J) True Signature: {(exitus616,10);(f0,10);(f17,10);(f27,10);(f37,10);(f45,10);(f55,10);(f65,10);(f75,10);(f83,10);(f93,10)} Rule Graph: [0->{1,16},1->{1,16},2->{2,15},3->{3,14},4->{4,13},5->{5,12},6->{6,11},7->{7,10},8->{8,9},9->{17},10->{8 ,9},11->{7,10},12->{6,11},13->{5,12},14->{4,13},15->{3,14},16->{2,15}] ,We construct a looptree: P: [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17] | +- p:[1] c: [1] | +- p:[2] c: [2] | +- p:[3] c: [3] | +- p:[4] c: [4] | +- p:[5] c: [5] | +- p:[6] c: [6] | +- p:[7] c: [7] | `- p:[8] c: [8]) + Applied Processor: AbstractSize Minimize + Details: () * Step 5: AbstractFlow WORST_CASE(?,POLY) + Considered Problem: Program: Domain: [A,B,C,D,E,F,G,H,I,J,0.0,0.1,0.2,0.3,0.4,0.5,0.6,0.7] f0 ~> f17 [A <= 0*K, B <= unknown, C <= unknown, D <= 0*K, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] f17 ~> f17 [A <= A, B <= B, C <= C, D <= D + E, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] f27 ~> f27 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= K + F, G <= G, H <= H, I <= I, J <= J] f37 ~> f37 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= E + G, H <= H, I <= I, J <= J] f45 ~> f45 [A <= A + E, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] f55 ~> f55 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= E + H, I <= I, J <= J] f65 ~> f65 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= K + I, J <= J] f75 ~> f75 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= E + J] f83 ~> f83 [A <= K + A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] f83 ~> f93 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] f75 ~> f83 [A <= K + E, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] f65 ~> f75 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= 0*K] f55 ~> f65 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= K + E, J <= J] f45 ~> f55 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= 0*K, I <= I, J <= J] f37 ~> f45 [A <= 0*K, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] f27 ~> f37 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= 0*K, H <= H, I <= I, J <= J] f17 ~> f27 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= K + E, G <= G, H <= H, I <= I, J <= J] f93 ~> exitus616 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] + Loop: [0.0 <= K + D + E] f17 ~> f17 [A <= A, B <= B, C <= C, D <= D + E, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] + Loop: [0.1 <= F] f27 ~> f27 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= K + F, G <= G, H <= H, I <= I, J <= J] + Loop: [0.2 <= K + E + G] f37 ~> f37 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= E + G, H <= H, I <= I, J <= J] + Loop: [0.3 <= K + A + E] f45 ~> f45 [A <= A + E, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] + Loop: [0.4 <= K + E + H] f55 ~> f55 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= E + H, I <= I, J <= J] + Loop: [0.5 <= I] f65 ~> f65 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= K + I, J <= J] + Loop: [0.6 <= K + E + J] f75 ~> f75 [A <= A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= E + J] + Loop: [0.7 <= A] f83 ~> f83 [A <= K + A, B <= B, C <= C, D <= D, E <= E, F <= F, G <= G, H <= H, I <= I, J <= J] + Applied Processor: AbstractFlow + Details: () * Step 6: Lare WORST_CASE(?,POLY) + Considered Problem: Program: Domain: [tick,huge,K,A,B,C,D,E,F,G,H,I,J,0.0,0.1,0.2,0.3,0.4,0.5,0.6,0.7] f0 ~> f17 [K ~=> A,K ~=> D,huge ~=> B,huge ~=> C] f17 ~> f17 [D ~+> D,E ~+> D] f27 ~> f27 [F ~+> F,K ~+> F] f37 ~> f37 [E ~+> G,G ~+> G] f45 ~> f45 [A ~+> A,E ~+> A] f55 ~> f55 [E ~+> H,H ~+> H] f65 ~> f65 [I ~+> I,K ~+> I] f75 ~> f75 [E ~+> J,J ~+> J] f83 ~> f83 [A ~+> A,K ~+> A] f83 ~> f93 [] f75 ~> f83 [E ~+> A,K ~+> A] f65 ~> f75 [K ~=> J] f55 ~> f65 [E ~+> I,K ~+> I] f45 ~> f55 [K ~=> H] f37 ~> f45 [K ~=> A] f27 ~> f37 [K ~=> G] f17 ~> f27 [E ~+> F,K ~+> F] f93 ~> exitus616 [] + Loop: [D ~+> 0.0,E ~+> 0.0,K ~+> 0.0] f17 ~> f17 [D ~+> D,E ~+> D] + Loop: [F ~=> 0.1] f27 ~> f27 [F ~+> F,K ~+> F] + Loop: [E ~+> 0.2,G ~+> 0.2,K ~+> 0.2] f37 ~> f37 [E ~+> G,G ~+> G] + Loop: [A ~+> 0.3,E ~+> 0.3,K ~+> 0.3] f45 ~> f45 [A ~+> A,E ~+> A] + Loop: [E ~+> 0.4,H ~+> 0.4,K ~+> 0.4] f55 ~> f55 [E ~+> H,H ~+> H] + Loop: [I ~=> 0.5] f65 ~> f65 [I ~+> I,K ~+> I] + Loop: [E ~+> 0.6,J ~+> 0.6,K ~+> 0.6] f75 ~> f75 [E ~+> J,J ~+> J] + Loop: [A ~=> 0.7] f83 ~> f83 [A ~+> A,K ~+> A] + Applied Processor: Lare + Details: f0 ~> exitus616 [K ~=> D ,K ~=> G ,K ~=> H ,K ~=> J ,huge ~=> B ,huge ~=> C ,E ~+> A ,E ~+> D ,E ~+> F ,E ~+> G ,E ~+> H ,E ~+> I ,E ~+> J ,E ~+> 0.0 ,E ~+> 0.1 ,E ~+> 0.2 ,E ~+> 0.3 ,E ~+> 0.4 ,E ~+> 0.5 ,E ~+> 0.6 ,E ~+> 0.7 ,E ~+> tick ,tick ~+> tick ,K ~+> A ,K ~+> D ,K ~+> F ,K ~+> G ,K ~+> H ,K ~+> I ,K ~+> J ,K ~+> 0.0 ,K ~+> 0.1 ,K ~+> 0.2 ,K ~+> 0.3 ,K ~+> 0.4 ,K ~+> 0.5 ,K ~+> 0.6 ,K ~+> 0.7 ,K ~+> tick ,E ~*> A ,E ~*> D ,E ~*> F ,E ~*> G ,E ~*> H ,E ~*> I ,E ~*> J ,E ~*> tick ,K ~*> A ,K ~*> D ,K ~*> F ,K ~*> G ,K ~*> H ,K ~*> I ,K ~*> J ,K ~*> 0.0 ,K ~*> 0.2 ,K ~*> 0.3 ,K ~*> 0.4 ,K ~*> 0.6 ,K ~*> tick] + f17> [D ~+> D ,D ~+> 0.0 ,D ~+> tick ,E ~+> D ,E ~+> 0.0 ,E ~+> tick ,tick ~+> tick ,K ~+> 0.0 ,K ~+> tick ,D ~*> D ,E ~*> D ,K ~*> D] + f27> [F ~=> 0.1,F ~+> F,F ~+> tick,tick ~+> tick,K ~+> F,F ~*> F,K ~*> F] + f37> [E ~+> G ,E ~+> 0.2 ,E ~+> tick ,G ~+> G ,G ~+> 0.2 ,G ~+> tick ,tick ~+> tick ,K ~+> 0.2 ,K ~+> tick ,E ~*> G ,G ~*> G ,K ~*> G] + f45> [A ~+> A ,A ~+> 0.3 ,A ~+> tick ,E ~+> A ,E ~+> 0.3 ,E ~+> tick ,tick ~+> tick ,K ~+> 0.3 ,K ~+> tick ,A ~*> A ,E ~*> A ,K ~*> A] + f55> [E ~+> H ,E ~+> 0.4 ,E ~+> tick ,H ~+> H ,H ~+> 0.4 ,H ~+> tick ,tick ~+> tick ,K ~+> 0.4 ,K ~+> tick ,E ~*> H ,H ~*> H ,K ~*> H] + f65> [I ~=> 0.5,I ~+> I,I ~+> tick,tick ~+> tick,K ~+> I,I ~*> I,K ~*> I] + f75> [E ~+> J ,E ~+> 0.6 ,E ~+> tick ,J ~+> J ,J ~+> 0.6 ,J ~+> tick ,tick ~+> tick ,K ~+> 0.6 ,K ~+> tick ,E ~*> J ,J ~*> J ,K ~*> J] + f83> [A ~=> 0.7,A ~+> A,A ~+> tick,tick ~+> tick,K ~+> A,A ~*> A,K ~*> A] YES(?,POLY)