8.11/8.19 WORST_CASE(?,O(n^3)) 8.11/8.19 8.11/8.19 Preprocessing Cost Relations 8.11/8.19 ===================================== 8.11/8.19 8.11/8.19 #### Computed strongly connected components 8.11/8.19 0. recursive : [lbl101/10] 8.11/8.19 1. recursive : [lbl121/15,lbl123/15] 8.11/8.19 2. recursive : [lbl101_loop_cont/17,lbl121_loop_cont/17,lbl53/16,lbl71/16] 8.11/8.19 3. non_recursive : [exit_location/1] 8.11/8.19 4. non_recursive : [stop/17] 8.11/8.19 5. non_recursive : [lbl71_loop_cont/18] 8.11/8.19 6. non_recursive : [lbl21/17] 8.11/8.19 7. non_recursive : [start/17] 8.11/8.19 8. non_recursive : [start0/17] 8.11/8.19 8.11/8.19 #### Obtained direct recursion through partial evaluation 8.11/8.19 0. SCC is partially evaluated into lbl101/10 8.11/8.19 1. SCC is partially evaluated into lbl121/15 8.11/8.19 2. SCC is partially evaluated into lbl71/16 8.11/8.19 3. SCC is completely evaluated into other SCCs 8.11/8.19 4. SCC is completely evaluated into other SCCs 8.11/8.19 5. SCC is partially evaluated into lbl71_loop_cont/18 8.11/8.19 6. SCC is partially evaluated into lbl21/17 8.11/8.19 7. SCC is completely evaluated into other SCCs 8.11/8.19 8. SCC is partially evaluated into start0/17 8.11/8.19 8.11/8.19 Control-Flow Refinement of Cost Relations 8.11/8.19 ===================================== 8.11/8.19 8.11/8.19 ### Specialization of cost equations lbl101/10 8.11/8.19 * CE 18 is refined into CE [22] 8.11/8.19 * CE 17 is refined into CE [23] 8.11/8.19 * CE 16 is refined into CE [24] 8.11/8.19 8.11/8.19 8.11/8.19 ### Cost equations --> "Loop" of lbl101/10 8.11/8.19 * CEs [24] --> Loop 22 8.11/8.19 * CEs [22] --> Loop 23 8.11/8.19 * CEs [23] --> Loop 24 8.11/8.19 8.11/8.19 ### Ranking functions of CR lbl101(E,G,I,K,L,M,O,R,S,T) 8.11/8.19 * RF of phase [22]: [E,E-G+1] 8.11/8.19 8.11/8.19 #### Partial ranking functions of CR lbl101(E,G,I,K,L,M,O,R,S,T) 8.11/8.19 * Partial RF of phase [22]: 8.11/8.19 - RF of loop [22:1]: 8.11/8.19 E 8.11/8.19 E-G+1 8.11/8.19 8.11/8.19 8.11/8.19 ### Specialization of cost equations lbl121/15 8.11/8.19 * CE 19 is refined into CE [25] 8.11/8.19 * CE 21 is refined into CE [26] 8.11/8.19 * CE 20 is refined into CE [27] 8.11/8.19 8.11/8.19 8.11/8.19 ### Cost equations --> "Loop" of lbl121/15 8.11/8.19 * CEs [25] --> Loop 25 8.11/8.19 * CEs [26] --> Loop 26 8.11/8.19 * CEs [27] --> Loop 27 8.11/8.19 8.11/8.19 ### Ranking functions of CR lbl121(A,C,E,G,I,K,L,M,O,R,S,T,U,V,W) 8.11/8.19 8.11/8.19 #### Partial ranking functions of CR lbl121(A,C,E,G,I,K,L,M,O,R,S,T,U,V,W) 8.11/8.19 8.11/8.19 8.11/8.19 ### Specialization of cost equations lbl71/16 8.11/8.19 * CE 6 is refined into CE [28,29] 8.11/8.19 * CE 7 is refined into CE [30] 8.11/8.19 * CE 10 is refined into CE [31,32] 8.11/8.19 * CE 8 is refined into CE [33,34] 8.11/8.19 * CE 9 is refined into CE [35] 8.11/8.19 * CE 13 is refined into CE [36] 8.11/8.19 * CE 11 is refined into CE [37,38] 8.11/8.19 * CE 12 is refined into CE [39] 8.11/8.19 * CE 4 is refined into CE [40,41] 8.11/8.19 * CE 5 is refined into CE [42] 8.11/8.19 8.11/8.19 8.11/8.19 ### Cost equations --> "Loop" of lbl71/16 8.11/8.19 * CEs [38] --> Loop 28 8.11/8.19 * CEs [39] --> Loop 29 8.11/8.19 * CEs [37] --> Loop 30 8.11/8.19 * CEs [40,42] --> Loop 31 8.11/8.19 * CEs [41] --> Loop 32 8.11/8.19 * CEs [36] --> Loop 33 8.11/8.19 * CEs [31] --> Loop 34 8.11/8.19 * CEs [32] --> Loop 35 8.11/8.19 * CEs [33,35] --> Loop 36 8.11/8.19 * CEs [34] --> Loop 37 8.11/8.19 * CEs [28,30] --> Loop 38 8.11/8.19 * CEs [29] --> Loop 39 8.11/8.19 8.11/8.19 ### Ranking functions of CR lbl71(A,C,E,G,I,K,L,M,O,R,S,T,U,V,W,X) 8.11/8.19 8.11/8.19 #### Partial ranking functions of CR lbl71(A,C,E,G,I,K,L,M,O,R,S,T,U,V,W,X) 8.11/8.19 * Partial RF of phase [28,29,30,31,32]: 8.11/8.19 - RF of loop [28:1,29:1,30:1]: 8.11/8.19 -E+K-1 depends on loops [31:1,32:1] 8.11/8.19 -E+L-1 depends on loops [31:1,32:1] 8.11/8.19 -E+2*O depends on loops [31:1,32:1] 8.11/8.19 -I+K-1 depends on loops [31:1,32:1] 8.11/8.19 -I+L-1 depends on loops [31:1,32:1] 8.11/8.19 -I+2*O depends on loops [31:1,32:1] 8.11/8.19 - RF of loop [31:1]: 8.11/8.19 E-2*G+2 depends on loops [28:1,29:1,30:1] 8.11/8.19 E-2*G-K+2*O+2 depends on loops [28:1,29:1,30:1] 8.11/8.19 E-2*G-L+2*O+2 depends on loops [28:1,29:1,30:1] 8.11/8.19 E/3-2/3 depends on loops [28:1,29:1,30:1] 8.11/8.19 E/3-K/3+2/3 depends on loops [28:1,29:1,30:1] 8.11/8.19 E/3-L/3+2/3 depends on loops [28:1,29:1,30:1] 8.11/8.19 E/3-2/3*O+2/3 depends on loops [28:1,29:1,30:1] 8.11/8.19 -2*G+I+2 depends on loops [28:1,29:1,30:1] 8.11/8.19 -2*G+I-K+2*O+2 depends on loops [28:1,29:1,30:1] 8.11/8.19 -2*G+I-L+2*O+2 depends on loops [28:1,29:1,30:1] 8.11/8.19 I/3-2/3 depends on loops [28:1,29:1,30:1] 8.11/8.19 I/3-K/3+2/3 depends on loops [28:1,29:1,30:1] 8.11/8.19 I/3-L/3+2/3 depends on loops [28:1,29:1,30:1] 8.11/8.19 I/3-2/3*O+2/3 depends on loops [28:1,29:1,30:1] 8.11/8.19 - RF of loop [31:1,32:1]: 8.11/8.19 G-1 8.11/8.19 - RF of loop [32:1]: 8.11/8.19 E/2-G+1/2 depends on loops [28:1,29:1,30:1] 8.11/8.19 E/4-3/4 depends on loops [28:1,29:1,30:1] 8.11/8.19 E/4-K/4+1/2 depends on loops [28:1,29:1,30:1] 8.11/8.19 E/4-L/4+1/2 depends on loops [28:1,29:1,30:1] 8.11/8.19 E/4-O/2+1/2 depends on loops [28:1,29:1,30:1] 8.11/8.19 -G+I/2+1/2 depends on loops [28:1,29:1,30:1] 8.11/8.19 I/4-3/4 depends on loops [28:1,29:1,30:1] 8.11/8.19 I/4-K/4+1/2 depends on loops [28:1,29:1,30:1] 8.11/8.19 I/4-L/4+1/2 depends on loops [28:1,29:1,30:1] 8.11/8.19 I/4-O/2+1/2 depends on loops [28:1,29:1,30:1] 8.11/8.19 8.11/8.19 8.11/8.19 ### Specialization of cost equations lbl71_loop_cont/18 8.11/8.19 * CE 15 is refined into CE [43] 8.11/8.19 * CE 14 is refined into CE [44] 8.11/8.19 8.11/8.19 8.11/8.19 ### Cost equations --> "Loop" of lbl71_loop_cont/18 8.11/8.19 * CEs [43] --> Loop 40 8.11/8.19 * CEs [44] --> Loop 41 8.11/8.19 8.11/8.19 ### Ranking functions of CR lbl71_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) 8.11/8.19 8.11/8.19 #### Partial ranking functions of CR lbl71_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) 8.11/8.19 8.11/8.19 8.11/8.19 ### Specialization of cost equations lbl21/17 8.11/8.19 * CE 3 is refined into CE [45,46,47,48,49] 8.11/8.19 * CE 2 is refined into CE [50] 8.11/8.19 8.11/8.19 8.11/8.19 ### Cost equations --> "Loop" of lbl21/17 8.11/8.19 * CEs [46,48] --> Loop 42 8.11/8.19 * CEs [45,47,49] --> Loop 43 8.11/8.19 * CEs [50] --> Loop 44 8.11/8.19 8.11/8.19 ### Ranking functions of CR lbl21(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,R) 8.11/8.19 8.11/8.19 #### Partial ranking functions of CR lbl21(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,R) 8.11/8.19 8.11/8.19 8.11/8.19 ### Specialization of cost equations start0/17 8.11/8.19 * CE 1 is refined into CE [51,52,53] 8.11/8.19 8.11/8.19 8.11/8.19 ### Cost equations --> "Loop" of start0/17 8.11/8.19 * CEs [53] --> Loop 45 8.11/8.19 * CEs [52] --> Loop 46 8.11/8.19 * CEs [51] --> Loop 47 8.11/8.19 8.11/8.19 ### Ranking functions of CR start0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,R) 8.11/8.19 8.11/8.19 #### Partial ranking functions of CR start0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,R) 8.11/8.19 8.11/8.19 8.11/8.19 Computing Bounds 8.11/8.19 ===================================== 8.11/8.19 8.11/8.19 #### Cost of chains of lbl101(E,G,I,K,L,M,O,R,S,T): 8.11/8.19 * Chain [[22],24]: 1*it(22)+0 8.11/8.19 Such that:it(22) =< E-G+1 8.11/8.19 it(22) =< E-S 8.11/8.19 8.11/8.19 with precondition: [R=2,K=L,I+1=T,G>=1,S>=0,K>=2*O,K>=I+1,2*O+1>=K,I>=E+G,E>=G+S] 8.11/8.19 8.11/8.19 * Chain [[22],23]: 1*it(22)+0 8.11/8.19 Such that:it(22) =< E-G+1 8.11/8.19 8.11/8.19 with precondition: [R=3,K=L,G>=1,K>=2*O,E>=G,K>=I+1,2*O+1>=K,I>=E+G] 8.11/8.19 8.11/8.19 * Chain [24]: 0 8.11/8.19 with precondition: [R=2,L=K,E=S,I+1=T,E>=0,G>=1,L>=2*O,O>=G,L>=I+1,2*O+1>=L,I>=E+G] 8.11/8.19 8.11/8.19 * Chain [23]: 0 8.11/8.19 with precondition: [R=3,L=K,E>=0,G>=1,L>=2*O,O>=G,L>=I+1,2*O+1>=L,I>=E+G] 8.11/8.19 8.11/8.19 8.11/8.19 #### Cost of chains of lbl121(A,C,E,G,I,K,L,M,O,R,S,T,U,V,W): 8.11/8.19 * Chain [27]: 0 8.11/8.19 with precondition: [A=0,G=1,R=4,S=0,V=0,T=C,I=K,I=L,I=M+1,E=U,I=W,E>=0,O>=1,I>=2*O,I>=E+1,2*O+1>=I] 8.11/8.19 8.11/8.19 * Chain [26]: 0 8.11/8.19 with precondition: [R=3,I=K,I=L,I=M+1,E>=0,G>=1,I>=2*O,I>=E+1,O>=G,2*O+1>=I] 8.11/8.19 8.11/8.19 * Chain [25]: 0 8.11/8.19 with precondition: [R=5,U=0,W=0,I=K,I=L,I=M+1,A=S,A=V,A>=1,E>=0,G>=2*A,I>=2*O,I>=E+1,O>=G,2*A+1>=G,2*O+1>=I] 8.11/8.19 8.11/8.19 8.11/8.19 #### Cost of chains of lbl71(A,C,E,G,I,K,L,M,O,R,S,T,U,V,W,X): 8.11/8.19 * Chain [[28,29,30,31,32],39]: 3*it(28)+2*it(31)+1*s(1)+1*s(6)+1*s(7)+0 8.11/8.19 Such that:aux(223) =< G+W 8.11/8.19 aux(237) =< -E+2*O 8.11/8.19 aux(238) =< -E+W 8.11/8.19 aux(239) =< G 8.11/8.19 aux(240) =< W 8.11/8.19 s(1) =< aux(240) 8.11/8.19 it(31) =< aux(239) 8.11/8.19 aux(94) =< aux(223) 8.11/8.19 aux(162) =< aux(240) 8.11/8.19 aux(94) =< aux(240) 8.11/8.19 aux(126) =< aux(240) 8.11/8.19 aux(126) =< aux(94) 8.11/8.19 aux(183) =< aux(240) 8.11/8.19 aux(167) =< aux(94) 8.11/8.19 aux(162) =< aux(240)-3 8.11/8.19 aux(7) =< it(31)*aux(126) 8.11/8.19 aux(4) =< it(31)*aux(240) 8.11/8.19 aux(1) =< it(31)*aux(240) 8.11/8.19 aux(10) =< it(31)*aux(94) 8.11/8.19 aux(1) =< it(31)*aux(94) 8.11/8.19 aux(5) =< it(31)*aux(183) 8.11/8.19 aux(2) =< it(31)*aux(183) 8.11/8.19 aux(11) =< it(31)*aux(167) 8.11/8.19 aux(2) =< it(31)*aux(167) 8.11/8.19 s(7) =< it(31)*aux(162) 8.11/8.19 aux(13) =< aux(4) 8.11/8.19 aux(13) =< aux(10) 8.11/8.19 aux(14) =< aux(5) 8.11/8.19 aux(14) =< aux(11) 8.11/8.19 it(28) =< aux(11)+aux(10)+aux(238) 8.11/8.19 it(28) =< aux(7)+aux(7)+aux(237) 8.11/8.19 it(28) =< aux(5)+aux(4)+aux(238) 8.11/8.19 it(28) =< aux(2)+aux(1)+aux(238) 8.11/8.19 it(28) =< aux(7)+aux(7)+aux(238) 8.11/8.19 it(28) =< aux(14)+aux(13)+aux(238) 8.11/8.19 s(6) =< it(28)*aux(240) 8.11/8.19 8.11/8.19 with precondition: [R=4,E=I,K=L,K=W,E>=0,G>=1,K>=2*O,K>=E+1,K>=G+2,O>=G,2*O+1>=K,G+K>=E+3] 8.11/8.19 8.11/8.19 * Chain [[28,29,30,31,32],38]: 3*it(28)+2*it(31)+1*s(6)+1*s(7)+0 8.11/8.19 Such that:aux(223) =< G+W 8.11/8.19 aux(241) =< -E+2*O 8.11/8.19 aux(242) =< -E+W 8.11/8.19 aux(243) =< G 8.11/8.19 aux(244) =< W 8.11/8.19 it(31) =< aux(243) 8.11/8.19 aux(94) =< aux(223) 8.11/8.19 aux(162) =< aux(244) 8.11/8.19 aux(94) =< aux(244) 8.11/8.19 aux(126) =< aux(244) 8.11/8.19 aux(126) =< aux(94) 8.11/8.19 aux(183) =< aux(244) 8.11/8.19 aux(167) =< aux(94) 8.11/8.19 aux(162) =< aux(244)-3 8.11/8.19 aux(7) =< it(31)*aux(126) 8.11/8.19 aux(4) =< it(31)*aux(244) 8.11/8.19 aux(1) =< it(31)*aux(244) 8.11/8.19 aux(10) =< it(31)*aux(94) 8.11/8.19 aux(1) =< it(31)*aux(94) 8.11/8.19 aux(5) =< it(31)*aux(183) 8.11/8.19 aux(2) =< it(31)*aux(183) 8.11/8.19 aux(11) =< it(31)*aux(167) 8.11/8.19 aux(2) =< it(31)*aux(167) 8.11/8.19 s(7) =< it(31)*aux(162) 8.11/8.19 aux(13) =< aux(4) 8.11/8.19 aux(13) =< aux(10) 8.11/8.19 aux(14) =< aux(5) 8.11/8.19 aux(14) =< aux(11) 8.11/8.19 it(28) =< aux(11)+aux(10)+aux(242) 8.11/8.19 it(28) =< aux(7)+aux(7)+aux(241) 8.11/8.19 it(28) =< aux(5)+aux(4)+aux(242) 8.11/8.19 it(28) =< aux(2)+aux(1)+aux(242) 8.11/8.19 it(28) =< aux(7)+aux(7)+aux(242) 8.11/8.19 it(28) =< aux(14)+aux(13)+aux(242) 8.11/8.19 s(6) =< it(28)*aux(244) 8.11/8.19 8.11/8.19 with precondition: [R=4,E=I,K=L,K=W,E>=0,G>=1,K>=2*O,K>=E+1,O>=G,2*O+1>=K,G+K>=E+3] 8.11/8.19 8.11/8.19 * Chain [[28,29,30,31,32],37]: 3*it(28)+2*it(31)+1*s(6)+1*s(7)+1*s(8)+0 8.11/8.19 Such that:aux(223) =< G+L 8.11/8.19 aux(245) =< -E+L 8.11/8.19 aux(246) =< -E+2*O 8.11/8.19 aux(247) =< G 8.11/8.19 aux(248) =< L 8.11/8.19 s(8) =< aux(248) 8.11/8.19 it(31) =< aux(247) 8.11/8.19 aux(94) =< aux(223) 8.11/8.19 aux(162) =< aux(248) 8.11/8.19 aux(94) =< aux(248) 8.11/8.19 aux(126) =< aux(248) 8.11/8.19 aux(126) =< aux(94) 8.11/8.19 aux(183) =< aux(248) 8.11/8.19 aux(167) =< aux(94) 8.11/8.19 aux(162) =< aux(248)-3 8.11/8.19 aux(7) =< it(31)*aux(126) 8.11/8.19 aux(4) =< it(31)*aux(248) 8.11/8.19 aux(1) =< it(31)*aux(248) 8.11/8.19 aux(10) =< it(31)*aux(94) 8.11/8.19 aux(1) =< it(31)*aux(94) 8.11/8.19 aux(5) =< it(31)*aux(183) 8.11/8.19 aux(2) =< it(31)*aux(183) 8.11/8.19 aux(11) =< it(31)*aux(167) 8.11/8.19 aux(2) =< it(31)*aux(167) 8.11/8.19 s(7) =< it(31)*aux(162) 8.11/8.19 aux(13) =< aux(4) 8.11/8.19 aux(13) =< aux(10) 8.11/8.19 aux(14) =< aux(5) 8.11/8.19 aux(14) =< aux(11) 8.11/8.19 it(28) =< aux(11)+aux(10)+aux(245) 8.11/8.19 it(28) =< aux(7)+aux(7)+aux(246) 8.11/8.19 it(28) =< aux(5)+aux(4)+aux(245) 8.11/8.19 it(28) =< aux(2)+aux(1)+aux(245) 8.11/8.19 it(28) =< aux(7)+aux(7)+aux(245) 8.11/8.19 it(28) =< aux(14)+aux(13)+aux(245) 8.11/8.19 s(6) =< it(28)*aux(248) 8.11/8.19 8.11/8.19 with precondition: [R=3,E=I,K=L,E>=0,G>=1,K>=2*O,K>=E+1,K>=G+2,O>=G,2*O+1>=K,G+K>=E+3] 8.11/8.19 8.11/8.19 * Chain [[28,29,30,31,32],36]: 3*it(28)+2*it(31)+1*s(6)+1*s(7)+0 8.11/8.19 Such that:aux(223) =< G+L 8.11/8.19 aux(249) =< -E+L 8.11/8.19 aux(250) =< -E+2*O 8.11/8.19 aux(251) =< G 8.11/8.19 aux(252) =< L 8.11/8.19 it(31) =< aux(251) 8.11/8.19 aux(94) =< aux(223) 8.11/8.19 aux(162) =< aux(252) 8.11/8.19 aux(94) =< aux(252) 8.11/8.19 aux(126) =< aux(252) 8.11/8.19 aux(126) =< aux(94) 8.11/8.19 aux(183) =< aux(252) 8.11/8.19 aux(167) =< aux(94) 8.11/8.19 aux(162) =< aux(252)-3 8.11/8.19 aux(7) =< it(31)*aux(126) 8.11/8.19 aux(4) =< it(31)*aux(252) 8.11/8.19 aux(1) =< it(31)*aux(252) 8.11/8.19 aux(10) =< it(31)*aux(94) 8.11/8.19 aux(1) =< it(31)*aux(94) 8.11/8.19 aux(5) =< it(31)*aux(183) 8.11/8.19 aux(2) =< it(31)*aux(183) 8.11/8.19 aux(11) =< it(31)*aux(167) 8.11/8.19 aux(2) =< it(31)*aux(167) 8.11/8.19 s(7) =< it(31)*aux(162) 8.11/8.19 aux(13) =< aux(4) 8.11/8.19 aux(13) =< aux(10) 8.11/8.19 aux(14) =< aux(5) 8.11/8.19 aux(14) =< aux(11) 8.11/8.19 it(28) =< aux(11)+aux(10)+aux(249) 8.11/8.19 it(28) =< aux(7)+aux(7)+aux(250) 8.11/8.19 it(28) =< aux(5)+aux(4)+aux(249) 8.11/8.19 it(28) =< aux(2)+aux(1)+aux(249) 8.11/8.19 it(28) =< aux(7)+aux(7)+aux(249) 8.11/8.19 it(28) =< aux(14)+aux(13)+aux(249) 8.11/8.19 s(6) =< it(28)*aux(252) 8.11/8.19 8.11/8.19 with precondition: [R=3,E=I,K=L,E>=0,G>=1,K>=2*O,K>=E+1,O>=G,2*O+1>=K,G+K>=E+3] 8.11/8.19 8.11/8.19 * Chain [[28,29,30,31,32],35]: 3*it(28)+2*it(31)+1*s(6)+1*s(7)+1*s(9)+0 8.11/8.19 Such that:aux(223) =< G+K 8.11/8.19 aux(253) =< -E+K 8.11/8.19 aux(254) =< G 8.11/8.19 aux(255) =< -I+K 8.11/8.19 aux(256) =< -I+2*O 8.11/8.19 aux(257) =< K 8.11/8.19 aux(212) =< aux(253) 8.11/8.19 aux(212) =< aux(255) 8.11/8.19 s(9) =< aux(257) 8.11/8.19 it(31) =< aux(254) 8.11/8.19 aux(94) =< aux(223) 8.11/8.19 aux(162) =< aux(257) 8.11/8.19 aux(94) =< aux(257) 8.11/8.19 aux(126) =< aux(257) 8.11/8.19 aux(126) =< aux(94) 8.11/8.19 aux(183) =< aux(257) 8.11/8.19 aux(167) =< aux(94) 8.11/8.19 aux(162) =< aux(257)-3 8.11/8.19 aux(7) =< it(31)*aux(126) 8.11/8.19 aux(4) =< it(31)*aux(257) 8.11/8.19 aux(1) =< it(31)*aux(257) 8.11/8.19 aux(10) =< it(31)*aux(94) 8.11/8.19 aux(1) =< it(31)*aux(94) 8.11/8.19 aux(5) =< it(31)*aux(183) 8.11/8.19 aux(2) =< it(31)*aux(183) 8.11/8.19 aux(11) =< it(31)*aux(167) 8.11/8.19 aux(2) =< it(31)*aux(167) 8.11/8.19 s(7) =< it(31)*aux(162) 8.11/8.19 aux(13) =< aux(4) 8.11/8.19 aux(13) =< aux(10) 8.11/8.19 aux(14) =< aux(5) 8.11/8.19 aux(14) =< aux(11) 8.11/8.19 it(28) =< aux(11)+aux(10)+aux(255) 8.11/8.19 it(28) =< aux(7)+aux(7)+aux(256) 8.11/8.19 it(28) =< aux(5)+aux(4)+aux(255) 8.11/8.19 it(28) =< aux(2)+aux(1)+aux(255) 8.11/8.19 it(28) =< aux(7)+aux(7)+aux(212) 8.11/8.19 it(28) =< aux(14)+aux(13)+aux(212) 8.11/8.19 it(28) =< aux(14)+aux(13)+aux(255) 8.11/8.19 s(6) =< it(28)*aux(257) 8.11/8.19 8.11/8.19 with precondition: [R=3,E=I,K=L,E>=0,G>=1,K>=2*O,K>=E+1,O>=G,2*O+1>=K,G+K>=E+3] 8.11/8.19 8.11/8.19 * Chain [[28,29,30,31,32],34]: 3*it(28)+2*it(31)+1*s(6)+1*s(7)+0 8.11/8.19 Such that:aux(223) =< G+K 8.11/8.19 aux(258) =< -E+K 8.11/8.19 aux(259) =< G 8.11/8.19 aux(260) =< -I+K 8.11/8.19 aux(261) =< -I+L 8.11/8.19 aux(262) =< -I+2*O 8.11/8.19 aux(263) =< K 8.11/8.19 aux(212) =< aux(258) 8.11/8.19 aux(212) =< aux(261) 8.11/8.19 it(31) =< aux(259) 8.11/8.19 aux(94) =< aux(223) 8.11/8.19 aux(162) =< aux(263) 8.11/8.19 aux(94) =< aux(263) 8.11/8.19 aux(126) =< aux(263) 8.19/8.19 aux(126) =< aux(94) 8.19/8.19 aux(183) =< aux(263) 8.19/8.19 aux(167) =< aux(94) 8.19/8.19 aux(162) =< aux(263)-3 8.19/8.19 aux(7) =< it(31)*aux(126) 8.19/8.19 aux(4) =< it(31)*aux(263) 8.19/8.19 aux(1) =< it(31)*aux(263) 8.19/8.19 aux(10) =< it(31)*aux(94) 8.19/8.19 aux(1) =< it(31)*aux(94) 8.19/8.19 aux(5) =< it(31)*aux(183) 8.19/8.19 aux(2) =< it(31)*aux(183) 8.19/8.19 aux(11) =< it(31)*aux(167) 8.19/8.19 aux(2) =< it(31)*aux(167) 8.19/8.19 s(7) =< it(31)*aux(162) 8.19/8.19 aux(13) =< aux(4) 8.19/8.19 aux(13) =< aux(10) 8.19/8.19 aux(14) =< aux(5) 8.19/8.19 aux(14) =< aux(11) 8.19/8.19 it(28) =< aux(11)+aux(10)+aux(260) 8.19/8.19 it(28) =< aux(7)+aux(7)+aux(262) 8.19/8.19 it(28) =< aux(5)+aux(4)+aux(260) 8.19/8.19 it(28) =< aux(2)+aux(1)+aux(260) 8.19/8.19 it(28) =< aux(7)+aux(7)+aux(212) 8.19/8.19 it(28) =< aux(14)+aux(13)+aux(212) 8.19/8.19 it(28) =< aux(14)+aux(13)+aux(260) 8.19/8.19 s(6) =< it(28)*aux(263) 8.19/8.19 8.19/8.19 with precondition: [R=3,E=I,K=L,E>=0,G>=1,K>=2*O,K>=E+1,O>=G,2*O+1>=K,G+K>=E+3] 8.19/8.19 8.19/8.19 * Chain [[28,29,30,31,32],33]: 3*it(28)+2*it(31)+1*s(6)+1*s(7)+0 8.19/8.19 Such that:aux(223) =< G+K 8.19/8.19 aux(264) =< -E+K 8.19/8.19 aux(265) =< -E+2*O 8.19/8.19 aux(266) =< G 8.19/8.19 aux(267) =< -I+L 8.19/8.19 aux(268) =< K 8.19/8.19 aux(212) =< aux(264) 8.19/8.19 aux(212) =< aux(267) 8.19/8.19 it(31) =< aux(266) 8.19/8.19 aux(94) =< aux(223) 8.19/8.19 aux(162) =< aux(268) 8.19/8.19 aux(94) =< aux(268) 8.19/8.19 aux(126) =< aux(268) 8.19/8.19 aux(126) =< aux(94) 8.19/8.19 aux(183) =< aux(268) 8.19/8.19 aux(167) =< aux(94) 8.19/8.19 aux(162) =< aux(268)-3 8.19/8.19 aux(7) =< it(31)*aux(126) 8.19/8.19 aux(4) =< it(31)*aux(268) 8.19/8.19 aux(1) =< it(31)*aux(268) 8.19/8.19 aux(10) =< it(31)*aux(94) 8.19/8.19 aux(1) =< it(31)*aux(94) 8.19/8.19 aux(5) =< it(31)*aux(183) 8.19/8.19 aux(2) =< it(31)*aux(183) 8.19/8.19 aux(11) =< it(31)*aux(167) 8.19/8.19 aux(2) =< it(31)*aux(167) 8.19/8.19 s(7) =< it(31)*aux(162) 8.19/8.19 aux(13) =< aux(4) 8.19/8.19 aux(13) =< aux(10) 8.19/8.19 aux(14) =< aux(5) 8.19/8.19 aux(14) =< aux(11) 8.19/8.19 it(28) =< aux(11)+aux(10)+aux(264) 8.19/8.19 it(28) =< aux(7)+aux(7)+aux(265) 8.19/8.19 it(28) =< aux(5)+aux(4)+aux(264) 8.19/8.19 it(28) =< aux(2)+aux(1)+aux(264) 8.19/8.19 it(28) =< aux(7)+aux(7)+aux(212) 8.19/8.19 it(28) =< aux(14)+aux(13)+aux(212) 8.19/8.19 it(28) =< aux(14)+aux(13)+aux(264) 8.19/8.19 s(6) =< it(28)*aux(268) 8.19/8.19 8.19/8.19 with precondition: [R=3,E=I,K=L,E>=0,G>=1,K>=2*O,K>=E+1,O>=G,2*O+1>=K,G+K>=E+3] 8.19/8.19 8.19/8.19 * Chain [33]: 0 8.19/8.19 with precondition: [R=3,E=I,L=K,E>=0,G>=1,L>=2*O,O>=G,2*O+1>=L] 8.19/8.19 8.19/8.19 8.19/8.19 #### Cost of chains of lbl71_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R): 8.19/8.19 * Chain [41]: 0 8.19/8.19 with precondition: [A=3,L=K,O>=1,L>=2*O,2*O+1>=L] 8.19/8.19 8.19/8.19 * Chain [40]: 0 8.19/8.19 with precondition: [A=4,L=K,O>=1,L>=2*O,2*O+1>=L] 8.19/8.19 8.19/8.19 8.19/8.19 #### Cost of chains of lbl21(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,R): 8.19/8.19 * Chain [44]: 0 8.19/8.19 with precondition: [B=A,D=C,F=E,H=G,J=I,L=K,N=M,0>=O,L>=2*O,2*O+1>=L] 8.19/8.19 8.19/8.19 * Chain [43]: 10*s(122)+4*s(135)+12*s(138)+4*s(139)+1*s(143)+1*s(181)+3*s(184)+1*s(185)+0 8.19/8.19 Such that:aux(280) =< K 8.19/8.19 s(163) =< K+O 8.19/8.19 aux(277) =< L 8.19/8.19 aux(278) =< L+O 8.19/8.19 aux(281) =< O 8.19/8.19 aux(282) =< 2*O 8.19/8.19 s(122) =< aux(281) 8.19/8.19 s(169) =< s(163) 8.19/8.19 s(170) =< aux(280) 8.19/8.19 s(169) =< aux(280) 8.19/8.19 s(171) =< aux(280) 8.19/8.19 s(171) =< s(169) 8.19/8.19 s(172) =< aux(280) 8.19/8.19 s(173) =< s(169) 8.19/8.19 s(170) =< aux(280)-3 8.19/8.19 s(174) =< s(122)*s(171) 8.19/8.19 s(175) =< s(122)*aux(280) 8.19/8.19 s(176) =< s(122)*aux(280) 8.19/8.19 s(177) =< s(122)*s(169) 8.19/8.19 s(176) =< s(122)*s(169) 8.19/8.19 s(178) =< s(122)*s(172) 8.19/8.19 s(179) =< s(122)*s(172) 8.19/8.19 s(180) =< s(122)*s(173) 8.19/8.19 s(179) =< s(122)*s(173) 8.19/8.19 s(181) =< s(122)*s(170) 8.19/8.19 s(182) =< s(175) 8.19/8.19 s(182) =< s(177) 8.19/8.19 s(183) =< s(178) 8.19/8.19 s(183) =< s(180) 8.19/8.19 s(184) =< s(180)+s(177)+aux(280) 8.19/8.19 s(184) =< s(174)+s(174)+aux(282) 8.19/8.19 s(184) =< s(178)+s(175)+aux(280) 8.19/8.19 s(184) =< s(179)+s(176)+aux(280) 8.19/8.19 s(184) =< s(174)+s(174)+aux(280) 8.19/8.19 s(184) =< s(183)+s(182)+aux(280) 8.19/8.19 s(185) =< s(184)*aux(280) 8.19/8.19 s(123) =< aux(278) 8.19/8.19 s(124) =< aux(277) 8.19/8.19 s(123) =< aux(277) 8.19/8.19 s(125) =< aux(277) 8.19/8.19 s(125) =< s(123) 8.19/8.19 s(126) =< aux(277) 8.19/8.19 s(127) =< s(123) 8.19/8.19 s(124) =< aux(277)-3 8.19/8.19 s(128) =< s(122)*s(125) 8.19/8.19 s(129) =< s(122)*aux(277) 8.19/8.19 s(130) =< s(122)*aux(277) 8.19/8.19 s(131) =< s(122)*s(123) 8.19/8.19 s(130) =< s(122)*s(123) 8.19/8.19 s(132) =< s(122)*s(126) 8.19/8.19 s(133) =< s(122)*s(126) 8.19/8.19 s(134) =< s(122)*s(127) 8.19/8.19 s(133) =< s(122)*s(127) 8.19/8.19 s(135) =< s(122)*s(124) 8.19/8.19 s(136) =< s(129) 8.19/8.19 s(136) =< s(131) 8.19/8.19 s(137) =< s(132) 8.19/8.19 s(137) =< s(134) 8.19/8.19 s(138) =< s(134)+s(131)+aux(277) 8.19/8.19 s(138) =< s(128)+s(128)+aux(282) 8.19/8.19 s(138) =< s(132)+s(129)+aux(277) 8.19/8.19 s(138) =< s(133)+s(130)+aux(277) 8.19/8.19 s(138) =< s(128)+s(128)+aux(277) 8.19/8.19 s(138) =< s(137)+s(136)+aux(277) 8.19/8.19 s(139) =< s(138)*aux(277) 8.19/8.19 s(143) =< aux(277) 8.19/8.19 8.19/8.19 with precondition: [B=A,D=C,F=E,H=G,J=I,L=K,N=M,O>=1,L>=2*O,2*O+1>=L] 8.19/8.19 8.19/8.19 * Chain [42]: 2*s(191)+4*s(192)+2*s(205)+6*s(208)+2*s(209)+0 8.19/8.19 Such that:aux(285) =< K 8.19/8.19 aux(286) =< K+O 8.19/8.19 aux(287) =< O 8.19/8.19 aux(288) =< 2*O 8.19/8.19 s(191) =< aux(285) 8.19/8.19 s(192) =< aux(287) 8.19/8.19 s(193) =< aux(286) 8.19/8.19 s(194) =< aux(285) 8.19/8.19 s(193) =< aux(285) 8.19/8.19 s(195) =< aux(285) 8.19/8.19 s(195) =< s(193) 8.19/8.19 s(196) =< aux(285) 8.19/8.19 s(197) =< s(193) 8.19/8.19 s(194) =< aux(285)-3 8.19/8.19 s(198) =< s(192)*s(195) 8.19/8.19 s(199) =< s(192)*aux(285) 8.19/8.19 s(200) =< s(192)*aux(285) 8.19/8.19 s(201) =< s(192)*s(193) 8.19/8.19 s(200) =< s(192)*s(193) 8.19/8.19 s(202) =< s(192)*s(196) 8.19/8.19 s(203) =< s(192)*s(196) 8.19/8.19 s(204) =< s(192)*s(197) 8.19/8.19 s(203) =< s(192)*s(197) 8.19/8.19 s(205) =< s(192)*s(194) 8.19/8.19 s(206) =< s(199) 8.19/8.19 s(206) =< s(201) 8.19/8.19 s(207) =< s(202) 8.19/8.19 s(207) =< s(204) 8.19/8.19 s(208) =< s(204)+s(201)+aux(285) 8.19/8.19 s(208) =< s(198)+s(198)+aux(288) 8.19/8.19 s(208) =< s(202)+s(199)+aux(285) 8.19/8.19 s(208) =< s(203)+s(200)+aux(285) 8.19/8.19 s(208) =< s(198)+s(198)+aux(285) 8.19/8.19 s(208) =< s(207)+s(206)+aux(285) 8.19/8.19 s(209) =< s(208)*aux(285) 8.19/8.19 8.19/8.19 with precondition: [B=A,D=C,F=E,H=G,J=I,L=K,N=M,L>=2*O,2*O+1>=L,L>=O+2] 8.19/8.19 8.19/8.19 8.19/8.19 #### Cost of chains of start0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,R): 8.19/8.19 * Chain [47]: 0 8.19/8.19 with precondition: [1>=L] 8.19/8.19 8.19/8.19 * Chain [46]: 10*s(240)+5*s(253)+15*s(256)+5*s(257)+1*s(275)+0 8.19/8.19 Such that:s(238) =< L/2 8.19/8.19 aux(289) =< L 8.19/8.19 aux(290) =< 3/2*L 8.19/8.19 s(240) =< s(238) 8.19/8.19 s(241) =< aux(290) 8.19/8.19 s(242) =< aux(289) 8.19/8.19 s(241) =< aux(289) 8.19/8.19 s(243) =< aux(289) 8.19/8.19 s(243) =< s(241) 8.19/8.19 s(244) =< aux(289) 8.19/8.19 s(245) =< s(241) 8.19/8.19 s(242) =< aux(289)-3 8.19/8.19 s(246) =< s(240)*s(243) 8.19/8.19 s(247) =< s(240)*aux(289) 8.19/8.19 s(248) =< s(240)*aux(289) 8.19/8.19 s(249) =< s(240)*s(241) 8.19/8.19 s(248) =< s(240)*s(241) 8.19/8.19 s(250) =< s(240)*s(244) 8.19/8.19 s(251) =< s(240)*s(244) 8.19/8.19 s(252) =< s(240)*s(245) 8.19/8.19 s(251) =< s(240)*s(245) 8.19/8.19 s(253) =< s(240)*s(242) 8.19/8.19 s(254) =< s(247) 8.19/8.19 s(254) =< s(249) 8.19/8.19 s(255) =< s(250) 8.19/8.19 s(255) =< s(252) 8.19/8.19 s(256) =< s(252)+s(249)+aux(289) 8.19/8.19 s(256) =< s(246)+s(246)+aux(289) 8.19/8.19 s(256) =< s(250)+s(247)+aux(289) 8.19/8.19 s(256) =< s(251)+s(248)+aux(289) 8.19/8.19 s(256) =< s(255)+s(254)+aux(289) 8.19/8.19 s(257) =< s(256)*aux(289) 8.19/8.19 s(275) =< aux(289) 8.19/8.19 8.19/8.19 with precondition: [L>=2] 8.19/8.19 8.19/8.19 * Chain [45]: 2*s(280)+4*s(281)+2*s(294)+6*s(297)+2*s(298)+0 8.19/8.19 Such that:s(278) =< L/2 8.19/8.19 s(277) =< 3/2*L 8.19/8.19 aux(291) =< L 8.19/8.19 aux(292) =< 2*L 8.19/8.19 s(278) =< aux(291) 8.19/8.19 s(279) =< aux(291) 8.19/8.19 s(277) =< aux(292) 8.19/8.19 s(279) =< aux(292) 8.19/8.19 s(280) =< aux(291) 8.19/8.19 s(281) =< s(278) 8.19/8.19 s(282) =< s(277) 8.19/8.19 s(283) =< aux(291) 8.19/8.19 s(282) =< aux(291) 8.19/8.19 s(284) =< aux(291) 8.19/8.19 s(284) =< s(282) 8.19/8.19 s(285) =< aux(291) 8.19/8.19 s(286) =< s(282) 8.19/8.19 s(283) =< aux(291)-3 8.19/8.19 s(287) =< s(281)*s(284) 8.19/8.19 s(288) =< s(281)*aux(291) 8.19/8.19 s(289) =< s(281)*aux(291) 8.19/8.19 s(290) =< s(281)*s(282) 8.19/8.19 s(289) =< s(281)*s(282) 8.19/8.19 s(291) =< s(281)*s(285) 8.19/8.19 s(292) =< s(281)*s(285) 8.19/8.19 s(293) =< s(281)*s(286) 8.19/8.19 s(292) =< s(281)*s(286) 8.19/8.19 s(294) =< s(281)*s(283) 8.19/8.19 s(295) =< s(288) 8.19/8.19 s(295) =< s(290) 8.19/8.19 s(296) =< s(291) 8.19/8.19 s(296) =< s(293) 8.19/8.19 s(297) =< s(293)+s(290)+aux(291) 8.19/8.19 s(297) =< s(287)+s(287)+s(279) 8.19/8.19 s(297) =< s(291)+s(288)+aux(291) 8.19/8.19 s(297) =< s(292)+s(289)+aux(291) 8.19/8.19 s(297) =< s(287)+s(287)+aux(291) 8.19/8.19 s(297) =< s(296)+s(295)+aux(291) 8.19/8.19 s(298) =< s(297)*aux(291) 8.19/8.19 8.19/8.19 with precondition: [L>=3] 8.19/8.19 8.19/8.19 8.19/8.19 Closed-form bounds of start0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,R): 8.19/8.19 ------------------------------------- 8.19/8.19 * Chain [47] with precondition: [1>=L] 8.19/8.19 - Upper bound: 0 8.19/8.19 - Complexity: constant 8.19/8.19 * Chain [46] with precondition: [L>=2] 8.19/8.19 - Upper bound: 5*L*L+16*L+L/2*(3/2*L*(10*L))+L/2*(5*L)+L/2*(45*L)+5*L 8.19/8.19 - Complexity: n^3 8.19/8.19 * Chain [45] with precondition: [L>=3] 8.19/8.19 - Upper bound: 2*L*L+8*L+L/2*(3/2*L*(4*L))+L/2*(2*L)+L/2*(18*L)+2*L 8.19/8.19 - Complexity: n^3 8.19/8.19 8.19/8.19 ### Maximum cost of start0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,R): nat(L)*3*nat(L)+nat(L)*8+nat(L)*6*nat(3/2*L)*nat(L/2)+nat(L)*3*nat(L/2)+nat(3/2*L)*18*nat(L/2)+nat(L/2)*6+(nat(L)*2*nat(L)+nat(L)*8+nat(L)*4*nat(3/2*L)*nat(L/2)+nat(L)*2*nat(L/2)+nat(3/2*L)*12*nat(L/2)+nat(L/2)*4) 8.19/8.19 Asymptotic class: n^3 8.19/8.19 * Total analysis performed in 7717 ms. 8.19/8.19 8.19/8.29 EOF