/export/starexec/sandbox/solver/bin/starexec_run_its /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(1)) Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [f16/6] 1. recursive : [f13/11,f16_loop_cont/12] 2. recursive : [f10/11,f13_loop_cont/12] 3. recursive : [f10_loop_cont/12,f7/11] 4. non_recursive : [exit_location/1] 5. non_recursive : [f31/6] 6. non_recursive : [f7_loop_cont/7] 7. non_recursive : [f0/6] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into f16/6 1. SCC is partially evaluated into f13/11 2. SCC is partially evaluated into f10/11 3. SCC is partially evaluated into f7/11 4. SCC is completely evaluated into other SCCs 5. SCC is completely evaluated into other SCCs 6. SCC is partially evaluated into f7_loop_cont/7 7. SCC is partially evaluated into f0/6 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations f16/6 * CE 22 is refined into CE [23] * CE 21 is refined into CE [24] * CE 20 is refined into CE [25] * CE 19 is refined into CE [26] ### Cost equations --> "Loop" of f16/6 * CEs [26] --> Loop 23 * CEs [23] --> Loop 24 * CEs [24] --> Loop 25 * CEs [25] --> Loop 26 ### Ranking functions of CR f16(A,D,E,G,H,I) * RF of phase [23]: [-E+5] #### Partial ranking functions of CR f16(A,D,E,G,H,I) * Partial RF of phase [23]: - RF of loop [23:1]: -E+5 ### Specialization of cost equations f13/11 * CE 17 is refined into CE [27] * CE 14 is refined into CE [28,29] * CE 18 is refined into CE [30] * CE 16 is refined into CE [31,32] * CE 15 is refined into CE [33] ### Cost equations --> "Loop" of f13/11 * CEs [33] --> Loop 27 * CEs [27] --> Loop 28 * CEs [28,29] --> Loop 29 * CEs [30] --> Loop 30 * CEs [32] --> Loop 31 * CEs [31] --> Loop 32 ### Ranking functions of CR f13(A,B,C,D,E,G,H,I,J,K,L) * RF of phase [27]: [-D+5] #### Partial ranking functions of CR f13(A,B,C,D,E,G,H,I,J,K,L) * Partial RF of phase [27]: - RF of loop [27:1]: -D+5 ### Specialization of cost equations f10/11 * CE 12 is refined into CE [34] * CE 10 is refined into CE [35,36,37] * CE 13 is refined into CE [38] * CE 9 is refined into CE [39,40,41,42] * CE 11 is refined into CE [43] ### Cost equations --> "Loop" of f10/11 * CEs [43] --> Loop 33 * CEs [34] --> Loop 34 * CEs [35,36,37] --> Loop 35 * CEs [38] --> Loop 36 * CEs [42] --> Loop 37 * CEs [40] --> Loop 38 * CEs [41] --> Loop 39 * CEs [39] --> Loop 40 ### Ranking functions of CR f10(A,B,C,D,E,G,H,I,J,K,L) * RF of phase [33]: [-C+5] #### Partial ranking functions of CR f10(A,B,C,D,E,G,H,I,J,K,L) * Partial RF of phase [33]: - RF of loop [33:1]: -C+5 ### Specialization of cost equations f7/11 * CE 3 is refined into CE [44,45,46] * CE 6 is refined into CE [47] * CE 2 is refined into CE [48,49,50,51,52,53,54,55] * CE 5 is refined into CE [56] * CE 4 is refined into CE [57] ### Cost equations --> "Loop" of f7/11 * CEs [57] --> Loop 41 * CEs [44,45,46] --> Loop 42 * CEs [47] --> Loop 43 * CEs [55] --> Loop 44 * CEs [56] --> Loop 45 * CEs [53] --> Loop 46 * CEs [51] --> Loop 47 * CEs [49] --> Loop 48 * CEs [54] --> Loop 49 * CEs [52] --> Loop 50 * CEs [50] --> Loop 51 * CEs [48] --> Loop 52 ### Ranking functions of CR f7(A,B,C,D,E,G,H,I,J,K,L) * RF of phase [41]: [-B+5] #### Partial ranking functions of CR f7(A,B,C,D,E,G,H,I,J,K,L) * Partial RF of phase [41]: - RF of loop [41:1]: -B+5 ### Specialization of cost equations f7_loop_cont/7 * CE 8 is refined into CE [58] * CE 7 is refined into CE [59] ### Cost equations --> "Loop" of f7_loop_cont/7 * CEs [58] --> Loop 53 * CEs [59] --> Loop 54 ### Ranking functions of CR f7_loop_cont(A,B,C,D,E,F,G) #### Partial ranking functions of CR f7_loop_cont(A,B,C,D,E,F,G) ### Specialization of cost equations f0/6 * CE 1 is refined into CE [60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79] ### Cost equations --> "Loop" of f0/6 * CEs [60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79] --> Loop 55 ### Ranking functions of CR f0(A,B,C,D,E,G) #### Partial ranking functions of CR f0(A,B,C,D,E,G) Computing Bounds ===================================== #### Cost of chains of f16(A,D,E,G,H,I): * Chain [[23],26]: 1*it(23)+0 Such that:it(23) =< -E+I with precondition: [G=2,D=H,4>=D,4>=I,E>=0,I>=E+1] * Chain [[23],25]: 1*it(23)+0 Such that:it(23) =< -E+5 with precondition: [G=3,I=5,D+1=H,4>=D,4>=E,E>=0] * Chain [[23],24]: 1*it(23)+0 Such that:it(23) =< -E+5 with precondition: [G=4,4>=D,4>=E,E>=0] * Chain [26]: 0 with precondition: [G=2,D=H,E=I,4>=D,4>=E,E>=0] * Chain [24]: 0 with precondition: [G=4,4>=D,E>=0] #### Cost of chains of f13(A,B,C,D,E,G,H,I,J,K,L): * Chain [[27],32]: 1*it(27)+1*s(3)+0 Such that:aux(2) =< -D+5 aux(3) =< -D+K aux(1) =< aux(2) it(27) =< aux(2) aux(1) =< aux(3) it(27) =< aux(3) s(3) =< aux(1)*5 with precondition: [G=2,L=0,A=H,B=I,C=J,4>=C,4>=K,D>=0,K>=D+1] * Chain [[27],31]: 1*it(27)+1*s(3)+1*s(4)+0 Such that:s(4) =< 4 aux(2) =< -D+5 aux(3) =< -D+K aux(1) =< aux(2) it(27) =< aux(2) aux(1) =< aux(3) it(27) =< aux(3) s(3) =< aux(1)*5 with precondition: [G=2,A=H,B=I,C=J,4>=C,4>=K,4>=L,D>=0,L>=1,K>=D+1] * Chain [[27],30]: 1*it(27)+1*s(3)+0 Such that:aux(4) =< -D+5 it(27) =< aux(4) s(3) =< aux(4)*5 with precondition: [G=4,4>=C,4>=D,D>=0] * Chain [[27],29]: 1*it(27)+1*s(3)+5 Such that:aux(3) =< -D+4 aux(2) =< -D+5 aux(1) =< aux(2) it(27) =< aux(2) aux(1) =< aux(3) it(27) =< aux(3) s(3) =< aux(1)*5 with precondition: [G=4,4>=C,3>=D,D>=0] * Chain [[27],28]: 1*it(27)+1*s(3)+0 Such that:aux(5) =< -D+5 it(27) =< aux(5) s(3) =< aux(5)*5 with precondition: [G=5,K=5,L=5,A=H,B=I,C+1=J,4>=C,4>=D] * Chain [32]: 0 with precondition: [G=2,L=0,H=A,I=B,C=J,D=K,4>=C,4>=D,D>=0] * Chain [31]: 1*s(4)+0 Such that:s(4) =< 4 with precondition: [G=2,H=A,I=B,C=J,D=K,4>=C,4>=D,4>=L,D>=0,L>=1] * Chain [30]: 0 with precondition: [G=4,4>=C,D>=0] * Chain [29]: 5 with precondition: [G=4,4>=C,4>=D,D>=0] #### Cost of chains of f10(A,B,C,D,E,G,H,I,J,K,L): * Chain [[33],40]: 1*it(33)+1*s(15)+1*s(16)+0 Such that:aux(7) =< -C+5 aux(8) =< -C+J aux(6) =< aux(7) it(33) =< aux(7) aux(6) =< aux(8) it(33) =< aux(8) s(17) =< aux(6)*5 s(15) =< s(17) s(16) =< s(17)*5 with precondition: [G=2,K=0,L=0,A=H,B=I,4>=B,4>=J,C>=0,J>=C+1] * Chain [[33],39]: 1*it(33)+1*s(15)+1*s(16)+1*s(18)+0 Such that:s(18) =< 4 aux(7) =< -C+5 aux(8) =< -C+J aux(6) =< aux(7) it(33) =< aux(7) aux(6) =< aux(8) it(33) =< aux(8) s(17) =< aux(6)*5 s(15) =< s(17) s(16) =< s(17)*5 with precondition: [G=2,K=0,A=H,B=I,4>=B,4>=J,4>=L,C>=0,L>=1,J>=C+1] * Chain [[33],38]: 1*it(33)+1*s(15)+1*s(16)+1*s(22)+1*s(23)+0 Such that:s(20) =< 4 s(19) =< 5 aux(7) =< -C+5 aux(8) =< -C+J s(21) =< s(19) s(22) =< s(19) s(21) =< s(20) s(22) =< s(20) s(23) =< s(21)*5 aux(6) =< aux(7) it(33) =< aux(7) aux(6) =< aux(8) it(33) =< aux(8) s(17) =< aux(6)*5 s(15) =< s(17) s(16) =< s(17)*5 with precondition: [G=2,L=0,A=H,B=I,4>=B,4>=J,4>=K,C>=0,K>=1,J>=C+1] * Chain [[33],37]: 1*it(33)+1*s(15)+1*s(16)+1*s(24)+1*s(28)+1*s(29)+0 Such that:aux(9) =< 4 s(25) =< 5 aux(7) =< -C+5 aux(8) =< -C+J s(24) =< aux(9) s(27) =< s(25) s(28) =< s(25) s(27) =< aux(9) s(28) =< aux(9) s(29) =< s(27)*5 aux(6) =< aux(7) it(33) =< aux(7) aux(6) =< aux(8) it(33) =< aux(8) s(17) =< aux(6)*5 s(15) =< s(17) s(16) =< s(17)*5 with precondition: [G=2,A=H,B=I,4>=B,4>=J,4>=K,4>=L,C>=0,K>=1,L>=1,J>=C+1] * Chain [[33],36]: 1*it(33)+1*s(15)+1*s(16)+0 Such that:aux(10) =< -C+5 it(33) =< aux(10) s(17) =< aux(10)*5 s(15) =< s(17) s(16) =< s(17)*5 with precondition: [G=4,4>=B,4>=C,C>=0] * Chain [[33],35]: 1*it(33)+1*s(15)+1*s(16)+65 Such that:aux(8) =< -C+4 aux(7) =< -C+5 aux(6) =< aux(7) it(33) =< aux(7) aux(6) =< aux(8) it(33) =< aux(8) s(17) =< aux(6)*5 s(15) =< s(17) s(16) =< s(17)*5 with precondition: [G=4,4>=B,3>=C,C>=0] * Chain [[33],34]: 1*it(33)+1*s(15)+1*s(16)+0 Such that:aux(12) =< -C+5 it(33) =< aux(12) s(17) =< aux(12)*5 s(15) =< s(17) s(16) =< s(17)*5 with precondition: [G=6,J=5,K=5,L=5,A=H,B+1=I,4>=B,4>=C] * Chain [40]: 0 with precondition: [G=2,K=0,L=0,H=A,B=I,C=J,4>=B,4>=C,C>=0] * Chain [39]: 1*s(18)+0 Such that:s(18) =< 4 with precondition: [G=2,K=0,H=A,B=I,C=J,4>=B,4>=C,4>=L,C>=0,L>=1] * Chain [38]: 1*s(22)+1*s(23)+0 Such that:s(20) =< 4 s(19) =< 5 s(21) =< s(19) s(22) =< s(19) s(21) =< s(20) s(22) =< s(20) s(23) =< s(21)*5 with precondition: [G=2,L=0,H=A,B=I,C=J,4>=B,4>=C,4>=K,C>=0,K>=1] * Chain [37]: 1*s(24)+1*s(28)+1*s(29)+0 Such that:s(25) =< 5 aux(9) =< 4 s(24) =< aux(9) s(27) =< s(25) s(28) =< s(25) s(27) =< aux(9) s(28) =< aux(9) s(29) =< s(27)*5 with precondition: [G=2,H=A,B=I,C=J,4>=B,4>=C,4>=K,4>=L,C>=0,K>=1,L>=1] * Chain [36]: 0 with precondition: [G=4,4>=B,C>=0] * Chain [35]: 65 with precondition: [G=4,4>=B,4>=C,C>=0] #### Cost of chains of f7(A,B,C,D,E,G,H,I,J,K,L): * Chain [[41],52]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+0 Such that:aux(14) =< -B+5 aux(15) =< -B+I aux(13) =< aux(14) it(41) =< aux(14) aux(13) =< aux(15) it(41) =< aux(15) s(57) =< aux(13)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=2,H=400,J=0,K=0,L=0,4>=I,B>=0,I>=B+1] * Chain [[41],51]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+1*s(58)+0 Such that:s(58) =< 4 aux(14) =< -B+5 aux(15) =< -B+I aux(13) =< aux(14) it(41) =< aux(14) aux(13) =< aux(15) it(41) =< aux(15) s(57) =< aux(13)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=2,H=400,J=0,K=0,4>=I,4>=L,B>=0,L>=1,I>=B+1] * Chain [[41],50]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+1*s(62)+1*s(63)+0 Such that:s(59) =< 4 s(60) =< 5 aux(14) =< -B+5 aux(15) =< -B+I s(61) =< s(60) s(62) =< s(60) s(61) =< s(59) s(62) =< s(59) s(63) =< s(61)*5 aux(13) =< aux(14) it(41) =< aux(14) aux(13) =< aux(15) it(41) =< aux(15) s(57) =< aux(13)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=2,H=400,J=0,L=0,4>=I,4>=K,B>=0,K>=1,I>=B+1] * Chain [[41],49]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+1*s(66)+1*s(68)+1*s(69)+0 Such that:s(65) =< 4 s(64) =< 5 aux(14) =< -B+5 aux(15) =< -B+I s(66) =< s(65) s(67) =< s(64) s(68) =< s(64) s(67) =< s(65) s(68) =< s(65) s(69) =< s(67)*5 aux(13) =< aux(14) it(41) =< aux(14) aux(13) =< aux(15) it(41) =< aux(15) s(57) =< aux(13)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=2,H=400,J=0,4>=I,4>=K,4>=L,B>=0,K>=1,L>=1,I>=B+1] * Chain [[41],48]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+1*s(73)+1*s(75)+1*s(76)+0 Such that:s(71) =< 4 s(70) =< 5 aux(14) =< -B+5 aux(15) =< -B+I s(72) =< s(70) s(73) =< s(70) s(72) =< s(71) s(73) =< s(71) s(74) =< s(72)*5 s(75) =< s(74) s(76) =< s(74)*5 aux(13) =< aux(14) it(41) =< aux(14) aux(13) =< aux(15) it(41) =< aux(15) s(57) =< aux(13)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=2,H=400,K=0,L=0,4>=I,4>=J,B>=0,J>=1,I>=B+1] * Chain [[41],47]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+1*s(77)+1*s(81)+1*s(83)+1*s(84)+0 Such that:aux(16) =< 4 s(78) =< 5 aux(14) =< -B+5 aux(15) =< -B+I s(77) =< aux(16) s(80) =< s(78) s(81) =< s(78) s(80) =< aux(16) s(81) =< aux(16) s(82) =< s(80)*5 s(83) =< s(82) s(84) =< s(82)*5 aux(13) =< aux(14) it(41) =< aux(14) aux(13) =< aux(15) it(41) =< aux(15) s(57) =< aux(13)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=2,H=400,K=0,4>=I,4>=J,4>=L,B>=0,J>=1,L>=1,I>=B+1] * Chain [[41],46]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+2*s(90)+1*s(91)+1*s(95)+1*s(96)+0 Such that:aux(17) =< 4 aux(18) =< 5 aux(14) =< -B+5 aux(15) =< -B+I s(89) =< aux(18) s(90) =< aux(18) s(89) =< aux(17) s(90) =< aux(17) s(91) =< s(89)*5 s(94) =< s(89)*5 s(95) =< s(94) s(96) =< s(94)*5 aux(13) =< aux(14) it(41) =< aux(14) aux(13) =< aux(15) it(41) =< aux(15) s(57) =< aux(13)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=2,H=400,L=0,4>=I,4>=J,4>=K,B>=0,J>=1,K>=1,I>=B+1] * Chain [[41],45]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+0 Such that:aux(19) =< -B+5 it(41) =< aux(19) s(57) =< aux(19)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=2,H=400,I=5,J=5,K=5,L=5,4>=B] * Chain [[41],44]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+1*s(101)+2*s(103)+1*s(104)+1*s(108)+1*s(109)+0 Such that:aux(20) =< 4 aux(21) =< 5 aux(14) =< -B+5 aux(15) =< -B+I s(101) =< aux(20) s(102) =< aux(21) s(103) =< aux(21) s(102) =< aux(20) s(103) =< aux(20) s(104) =< s(102)*5 s(107) =< s(102)*5 s(108) =< s(107) s(109) =< s(107)*5 aux(13) =< aux(14) it(41) =< aux(14) aux(13) =< aux(15) it(41) =< aux(15) s(57) =< aux(13)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=2,H=400,4>=I,4>=J,4>=K,4>=L,B>=0,J>=1,K>=1,L>=1,I>=B+1] * Chain [[41],43]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+0 Such that:aux(22) =< -B+5 it(41) =< aux(22) s(57) =< aux(22)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=4,4>=B,B>=0] * Chain [[41],42]: 1*it(41)+1*s(53)+1*s(54)+1*s(55)+375 Such that:aux(15) =< -B+4 aux(14) =< -B+5 aux(13) =< aux(14) it(41) =< aux(14) aux(13) =< aux(15) it(41) =< aux(15) s(57) =< aux(13)*5 s(53) =< s(57) s(56) =< s(57)*5 s(54) =< s(56) s(55) =< s(56)*5 with precondition: [A=400,G=4,3>=B,B>=0] * Chain [52]: 0 with precondition: [A=400,G=2,H=400,J=0,K=0,L=0,B=I,4>=B,B>=0] * Chain [51]: 1*s(58)+0 Such that:s(58) =< 4 with precondition: [A=400,G=2,H=400,J=0,K=0,B=I,4>=B,4>=L,B>=0,L>=1] * Chain [50]: 1*s(62)+1*s(63)+0 Such that:s(59) =< 4 s(60) =< 5 s(61) =< s(60) s(62) =< s(60) s(61) =< s(59) s(62) =< s(59) s(63) =< s(61)*5 with precondition: [A=400,G=2,H=400,J=0,L=0,B=I,4>=B,4>=K,B>=0,K>=1] * Chain [49]: 1*s(66)+1*s(68)+1*s(69)+0 Such that:s(65) =< 4 s(64) =< 5 s(66) =< s(65) s(67) =< s(64) s(68) =< s(64) s(67) =< s(65) s(68) =< s(65) s(69) =< s(67)*5 with precondition: [A=400,G=2,H=400,J=0,B=I,4>=B,4>=K,4>=L,B>=0,K>=1,L>=1] * Chain [48]: 1*s(73)+1*s(75)+1*s(76)+0 Such that:s(71) =< 4 s(70) =< 5 s(72) =< s(70) s(73) =< s(70) s(72) =< s(71) s(73) =< s(71) s(74) =< s(72)*5 s(75) =< s(74) s(76) =< s(74)*5 with precondition: [A=400,G=2,H=400,K=0,L=0,B=I,4>=B,4>=J,B>=0,J>=1] * Chain [47]: 1*s(77)+1*s(81)+1*s(83)+1*s(84)+0 Such that:s(78) =< 5 aux(16) =< 4 s(77) =< aux(16) s(80) =< s(78) s(81) =< s(78) s(80) =< aux(16) s(81) =< aux(16) s(82) =< s(80)*5 s(83) =< s(82) s(84) =< s(82)*5 with precondition: [A=400,G=2,H=400,K=0,B=I,4>=B,4>=J,4>=L,B>=0,J>=1,L>=1] * Chain [46]: 2*s(90)+1*s(91)+1*s(95)+1*s(96)+0 Such that:aux(17) =< 4 aux(18) =< 5 s(89) =< aux(18) s(90) =< aux(18) s(89) =< aux(17) s(90) =< aux(17) s(91) =< s(89)*5 s(94) =< s(89)*5 s(95) =< s(94) s(96) =< s(94)*5 with precondition: [A=400,G=2,H=400,L=0,B=I,4>=B,4>=J,4>=K,B>=0,J>=1,K>=1] * Chain [44]: 1*s(101)+2*s(103)+1*s(104)+1*s(108)+1*s(109)+0 Such that:aux(20) =< 4 aux(21) =< 5 s(101) =< aux(20) s(102) =< aux(21) s(103) =< aux(21) s(102) =< aux(20) s(103) =< aux(20) s(104) =< s(102)*5 s(107) =< s(102)*5 s(108) =< s(107) s(109) =< s(107)*5 with precondition: [A=400,G=2,H=400,B=I,4>=B,4>=J,4>=K,4>=L,B>=0,J>=1,K>=1,L>=1] * Chain [43]: 0 with precondition: [A=400,G=4,B>=0] * Chain [42]: 375 with precondition: [A=400,G=4,4>=B,B>=0] #### Cost of chains of f7_loop_cont(A,B,C,D,E,F,G): * Chain [54]: 0 with precondition: [A=2] * Chain [53]: 0 with precondition: [A=4] #### Cost of chains of f0(A,B,C,D,E,G): * Chain [55]: 10467 with precondition: [] Closed-form bounds of f0(A,B,C,D,E,G): ------------------------------------- * Chain [55] with precondition: [] - Upper bound: 10467 - Complexity: constant ### Maximum cost of f0(A,B,C,D,E,G): 10467 Asymptotic class: constant * Total analysis performed in 1081 ms.