/export/starexec/sandbox2/solver/bin/starexec_run_its /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [f13/19] 1. recursive : [f23/8] 2. recursive : [f33/13] 3. recursive : [f46/17] 4. recursive : [f60/18] 5. recursive : [f17/37,f23_loop_cont/38,f33_loop_cont/38,f46_loop_cont/38,f60_loop_cont/38] 6. non_recursive : [exit_location/1] 7. non_recursive : [f17_loop_cont/20] 8. non_recursive : [f0/19] #### Obtained direct recursion through partial evaluation 0. SCC is completely evaluated into other SCCs 1. SCC is partially evaluated into f23/8 2. SCC is partially evaluated into f33/13 3. SCC is partially evaluated into f46/17 4. SCC is partially evaluated into f60/18 5. SCC is partially evaluated into f17/37 6. SCC is completely evaluated into other SCCs 7. SCC is partially evaluated into f17_loop_cont/20 8. SCC is partially evaluated into f0/19 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations f23/8 * CE 16 is refined into CE [30] * CE 15 is refined into CE [31] * CE 18 is refined into CE [32] * CE 17 is refined into CE [33] * CE 14 is refined into CE [34] ### Cost equations --> "Loop" of f23/8 * CEs [34] --> Loop 27 * CEs [30] --> Loop 28 * CEs [31] --> Loop 29 * CEs [32] --> Loop 30 * CEs [33] --> Loop 31 ### Ranking functions of CR f23(B,D,E,F,W,X,Y,Z) * RF of phase [27]: [B-F+1] #### Partial ranking functions of CR f23(B,D,E,F,W,X,Y,Z) * Partial RF of phase [27]: - RF of loop [27:1]: B-F+1 ### Specialization of cost equations f33/13 * CE 21 is refined into CE [35] * CE 22 is refined into CE [36] * CE 20 is refined into CE [37] * CE 23 is refined into CE [38] * CE 19 is refined into CE [39] ### Cost equations --> "Loop" of f33/13 * CEs [39] --> Loop 32 * CEs [35] --> Loop 33 * CEs [36] --> Loop 34 * CEs [37] --> Loop 35 * CEs [38] --> Loop 36 ### Ranking functions of CR f33(A,B,C,F,G,H,I,W,X,Y,Z,A1,B1) * RF of phase [32]: [A-F+1,B-F+1,C-F] #### Partial ranking functions of CR f33(A,B,C,F,G,H,I,W,X,Y,Z,A1,B1) * Partial RF of phase [32]: - RF of loop [32:1]: A-F+1 B-F+1 C-F ### Specialization of cost equations f46/17 * CE 25 is refined into CE [40] * CE 26 is refined into CE [41] * CE 24 is refined into CE [42] ### Cost equations --> "Loop" of f46/17 * CEs [42] --> Loop 37 * CEs [40] --> Loop 38 * CEs [41] --> Loop 39 ### Ranking functions of CR f46(B,F,G,H,I,J,K,Q,R,W,X,Y,Z,A1,B1,C1,D1) * RF of phase [37]: [B-F+1] #### Partial ranking functions of CR f46(B,F,G,H,I,J,K,Q,R,W,X,Y,Z,A1,B1,C1,D1) * Partial RF of phase [37]: - RF of loop [37:1]: B-F+1 ### Specialization of cost equations f60/18 * CE 29 is refined into CE [43] * CE 28 is refined into CE [44] * CE 27 is refined into CE [45] ### Cost equations --> "Loop" of f60/18 * CEs [45] --> Loop 40 * CEs [43] --> Loop 41 * CEs [44] --> Loop 42 ### Ranking functions of CR f60(B,F,J,K,L,M,N,O,P,W,X,Y,Z,A1,B1,C1,D1,E1) * RF of phase [40]: [-F+J+1] #### Partial ranking functions of CR f60(B,F,J,K,L,M,N,O,P,W,X,Y,Z,A1,B1,C1,D1,E1) * Partial RF of phase [40]: - RF of loop [40:1]: -F+J+1 ### Specialization of cost equations f17/37 * CE 8 is refined into CE [46,47,48,49,50,51] * CE 10 is refined into CE [52] * CE 4 is refined into CE [53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70] * CE 6 is refined into CE [71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94] * CE 7 is refined into CE [95,96,97,98,99,100,101,102,103] * CE 9 is refined into CE [104,105] * CE 11 is refined into CE [106] * CE 5 is refined into CE [107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130] ### Cost equations --> "Loop" of f17/37 * CEs [122] --> Loop 43 * CEs [118] --> Loop 44 * CEs [130] --> Loop 45 * CEs [126] --> Loop 46 * CEs [120] --> Loop 47 * CEs [116] --> Loop 48 * CEs [128] --> Loop 49 * CEs [124] --> Loop 50 * CEs [129] --> Loop 51 * CEs [125] --> Loop 52 * CEs [121] --> Loop 53 * CEs [117] --> Loop 54 * CEs [127] --> Loop 55 * CEs [123] --> Loop 56 * CEs [119] --> Loop 57 * CEs [115] --> Loop 58 * CEs [110] --> Loop 59 * CEs [114] --> Loop 60 * CEs [108] --> Loop 61 * CEs [112] --> Loop 62 * CEs [113] --> Loop 63 * CEs [109] --> Loop 64 * CEs [111] --> Loop 65 * CEs [107] --> Loop 66 * CEs [52] --> Loop 67 * CEs [51] --> Loop 68 * CEs [50] --> Loop 69 * CEs [49] --> Loop 70 * CEs [48] --> Loop 71 * CEs [47] --> Loop 72 * CEs [46] --> Loop 73 * CEs [104] --> Loop 74 * CEs [57,58,65,66,69,70,77,78,89,90,93,94] --> Loop 75 * CEs [96,97,100,101,102,103,105] --> Loop 76 * CEs [54,60,62,73,74,81,82,85,86] --> Loop 77 * CEs [95,98,99] --> Loop 78 * CEs [55,56,63,64,67,68,75,76,87,88,91,92] --> Loop 79 * CEs [53,59,61,71,72,79,80,83,84] --> Loop 80 * CEs [106] --> Loop 81 ### Ranking functions of CR f17(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1,O1) * RF of phase [45,46,51,52,60,63]: [A-B-1] #### Partial ranking functions of CR f17(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1,O1) * Partial RF of phase [45,46,51,52,60,63]: - RF of loop [45:1,46:1,51:1,52:1,60:1,63:1]: A-B-1 ### Specialization of cost equations f17_loop_cont/20 * CE 12 is refined into CE [131] * CE 13 is refined into CE [132] ### Cost equations --> "Loop" of f17_loop_cont/20 * CEs [131] --> Loop 82 * CEs [132] --> Loop 83 ### Ranking functions of CR f17_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T) #### Partial ranking functions of CR f17_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T) ### Specialization of cost equations f0/19 * CE 3 is refined into CE [133,134,135,136,137,138,139,140,141,142] * CE 2 is refined into CE [143,144] * CE 1 is refined into CE [145] ### Cost equations --> "Loop" of f0/19 * CEs [136] --> Loop 84 * CEs [135,138,141,142] --> Loop 85 * CEs [133,134] --> Loop 86 * CEs [143,144] --> Loop 87 * CEs [137,139,140] --> Loop 88 * CEs [145] --> Loop 89 ### Ranking functions of CR f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,W) #### Partial ranking functions of CR f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,W) Computing Bounds ===================================== #### Cost of chains of f23(B,D,E,F,W,X,Y,Z): * Chain [[27],31]: 1*it(27)+0 Such that:it(27) =< B-F+1 with precondition: [W=7,Y=0,Z=1,F>=1,B>=F] * Chain [[27],30]: 1*it(27)+0 Such that:it(27) =< B-F+1 with precondition: [W=3,F>=1,B>=F] * Chain [[27],29]: 1*it(27)+0 Such that:it(27) =< B-F+1 with precondition: [W=7,Z=1,0>=Y+1,F>=1,B>=F] * Chain [[27],28]: 1*it(27)+0 Such that:it(27) =< B-F+1 with precondition: [W=7,Z=1,F>=1,Y>=1,B>=F] * Chain [31]: 0 with precondition: [E=0,W=7,Y=0,Z=1,X=D,F>=1,F>=B+1] * Chain [30]: 0 with precondition: [W=3,F>=1] * Chain [29]: 0 with precondition: [W=7,Z=1,X=D,E=Y,0>=E+1,F>=1,F>=B+1] * Chain [28]: 0 with precondition: [W=7,Z=1,X=D,E=Y,E>=1,F>=1,F>=B+1] #### Cost of chains of f33(A,B,C,F,G,H,I,W,X,Y,Z,A1,B1): * Chain [[32],36]: 1*it(32)+0 Such that:it(32) =< C-F with precondition: [W=3,C=B+1,A+1>=C,C>=F+1] * Chain [[32],35]: 1*it(32)+0 Such that:it(32) =< A-F with precondition: [W=5,A=B+1,A=C,A=X,A=Y,G=Z,H=A1,I=B1,A>=F+1] * Chain [[32],34]: 1*it(32)+0 Such that:it(32) =< A-F+1 with precondition: [W=6,Y=1,A=B,A+1=C,A+1=X,A>=F] * Chain [[32],33]: 1*it(32)+0 Such that:it(32) =< -F+X with precondition: [W=6,Y=1,B+1=C,B+1=X,A>=B+2,B>=F] * Chain [36]: 0 with precondition: [W=3,C=B+1,A+1>=C] * Chain [35]: 0 with precondition: [W=5,B+1=A,B+1=C,Z=G,A1=H,B1=I,B+1=X,F=Y,F>=B+1] * Chain [34]: 0 with precondition: [W=6,Y=1,B=A,B+1=C,B+1=X,F>=B+1] * Chain [33]: 0 with precondition: [W=6,Y=1,B+1=C,B+1=X,A>=B+2,F>=B+1] #### Cost of chains of f46(B,F,G,H,I,J,K,Q,R,W,X,Y,Z,A1,B1,C1,D1): * Chain [[37],39]: 1*it(37)+0 Such that:it(37) =< B-F+1 with precondition: [W=3,B>=F] * Chain [[37],38]: 1*it(37)+0 Such that:it(37) =< B-F+1 with precondition: [W=4,X=1,B>=F] * Chain [39]: 0 with precondition: [W=3] * Chain [38]: 0 with precondition: [W=4,X=1,Y=G,Z=H,A1=I,F>=B+1] #### Cost of chains of f60(B,F,J,K,L,M,N,O,P,W,X,Y,Z,A1,B1,C1,D1,E1): * Chain [[40],42]: 1*it(40)+0 Such that:it(40) =< -F+Y with precondition: [W=2,B+1=X,J+1=Y,F+K=J+Z+1,F+K=J+E1,J>=F,B>=K] * Chain [[40],41]: 1*it(40)+0 Such that:it(40) =< -F+J+1 with precondition: [W=3,J>=F,B>=K] * Chain [42]: 0 with precondition: [W=2,A1=L,B1=M,C1=N,D1=O,E1=P,B+1=X,F=Y,K=Z,F>=J+1,B>=K] * Chain [41]: 0 with precondition: [W=3,B>=K] #### Cost of chains of f17(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1,O1): * Chain [[45,46,51,52,60,63],81]: 6*it(45)+3*s(37)+3*s(38)+12*s(40)+3*s(50)+0 Such that:aux(7) =< A aux(18) =< A-B it(45) =< aux(18) aux(15) =< aux(7)-1 aux(9) =< aux(7) s(39) =< it(45)*aux(7) s(51) =< it(45)*aux(15) s(42) =< it(45)*aux(9) s(50) =< s(51) s(40) =< s(42) s(37) =< s(39) with precondition: [W=3,B>=1,A>=B+2] * Chain [[45,46,51,52,60,63],76]: 6*it(45)+3*s(37)+3*s(38)+12*s(40)+3*s(50)+10*s(52)+0 Such that:aux(23) =< A aux(24) =< A-B s(52) =< aux(23) it(45) =< aux(24) aux(15) =< aux(23)-1 aux(9) =< aux(23) s(39) =< it(45)*aux(23) s(51) =< it(45)*aux(15) s(42) =< it(45)*aux(9) s(50) =< s(51) s(40) =< s(42) s(37) =< s(39) with precondition: [W=3,B>=1,A>=B+2] * Chain [[45,46,51,52,60,63],75]: 6*it(45)+3*s(37)+6*s(38)+12*s(40)+3*s(50)+33*s(62)+0 Such that:aux(38) =< A aux(39) =< A-B s(62) =< aux(38) it(45) =< aux(39) aux(15) =< aux(38)-1 aux(9) =< aux(38) s(39) =< it(45)*aux(38) s(51) =< it(45)*aux(15) s(42) =< it(45)*aux(9) s(50) =< s(51) s(40) =< s(42) s(37) =< s(39) with precondition: [W=3,B>=1,A>=B+3] * Chain [[45,46,51,52,60,63],74]: 6*it(45)+3*s(37)+3*s(38)+12*s(40)+3*s(50)+0 Such that:aux(7) =< A aux(40) =< A-B it(45) =< aux(40) aux(15) =< aux(7)-1 aux(9) =< aux(7) s(39) =< it(45)*aux(7) s(51) =< it(45)*aux(15) s(42) =< it(45)*aux(9) s(50) =< s(51) s(40) =< s(42) s(37) =< s(39) with precondition: [W=3,B>=1,A>=B+2] * Chain [[45,46,51,52,60,63],72]: 6*it(45)+3*s(37)+3*s(38)+12*s(40)+3*s(50)+2*s(98)+0 Such that:aux(17) =< -B+Y aux(16) =< -B+Y+1 aux(41) =< Y aux(7) =< Y+1 s(98) =< aux(41) it(45) =< aux(16) it(45) =< aux(17) aux(15) =< aux(7)-1 aux(9) =< aux(7) s(39) =< it(45)*aux(7) s(51) =< it(45)*aux(15) s(42) =< it(45)*aux(9) s(50) =< s(51) s(40) =< s(42) s(37) =< s(39) with precondition: [W=5,B1=0,A=X,A=Y+1,A=Z,A=C1,B>=1,A>=B+2,A>=H1+2,A>=G1+H1+2] * Chain [[45,46,51,52,60,63],69]: 6*it(45)+3*s(37)+3*s(38)+12*s(40)+3*s(50)+2*s(100)+0 Such that:aux(43) =< -B+X aux(44) =< X s(100) =< aux(44) it(45) =< aux(43) aux(15) =< aux(44)-1 aux(9) =< aux(44) s(39) =< it(45)*aux(44) s(51) =< it(45)*aux(15) s(42) =< it(45)*aux(9) s(50) =< s(51) s(40) =< s(42) s(37) =< s(39) with precondition: [W=5,A=X,A=Y+1,A=Z,A=C1,0>=B1+1,B>=1,A>=B+2,A>=H1+2,A>=G1+H1+2] * Chain [[45,46,51,52,60,63],68]: 6*it(45)+3*s(37)+3*s(38)+12*s(40)+3*s(50)+2*s(102)+0 Such that:aux(17) =< -B+Y aux(16) =< -B+Y+1 aux(45) =< Y aux(7) =< Y+1 s(102) =< aux(45) it(45) =< aux(16) it(45) =< aux(17) aux(15) =< aux(7)-1 aux(9) =< aux(7) s(39) =< it(45)*aux(7) s(51) =< it(45)*aux(15) s(42) =< it(45)*aux(9) s(50) =< s(51) s(40) =< s(42) s(37) =< s(39) with precondition: [W=5,A=X,A=Y+1,A=Z,A=C1,B>=1,B1>=1,A>=B+2,A>=H1+2,A>=G1+H1+2] * Chain [81]: 0 with precondition: [W=3,B>=1] * Chain [79]: 1*aux(59)+0 with precondition: [A=1,B=1,W=3] * Chain [76]: 10*s(52)+0 Such that:aux(22) =< B s(52) =< aux(22) with precondition: [W=3,B>=1,A>=B] * Chain [75]: 33*s(62)+3*s(80)+0 Such that:aux(37) =< B s(62) =< aux(37) with precondition: [W=3,B>=1,A>=B+2] * Chain [74]: 0 with precondition: [W=3,B>=1,A>=B] * Chain [72]: 2*s(98)+0 Such that:aux(41) =< B s(98) =< aux(41) with precondition: [W=5,B1=0,B+1=A,D1=G,E1=H,F1=I,G1=J,H1=K,I1=L,J1=M,K1=N,L1=O,M1=P,N1=Q,O1=R,B+1=X,B=Y,B+1=Z,B+1=C1,B>=1] * Chain [69]: 2*s(100)+0 Such that:aux(42) =< B s(100) =< aux(42) with precondition: [W=5,B+1=A,D1=G,E1=H,F1=I,G1=J,H1=K,I1=L,J1=M,K1=N,L1=O,M1=P,N1=Q,O1=R,B+1=X,B=Y,B+1=Z,B+1=C1,0>=B1+1,B>=1] * Chain [68]: 2*s(102)+0 Such that:aux(45) =< B s(102) =< aux(45) with precondition: [W=5,B+1=A,D1=G,E1=H,F1=I,G1=J,H1=K,I1=L,J1=M,K1=N,L1=O,M1=P,N1=Q,O1=R,B+1=X,B=Y,B+1=Z,B+1=C1,B>=1,B1>=1] * Chain [67]: 0 with precondition: [W=5,Z=C,A1=D,B1=E,C1=F,D1=G,E1=H,F1=I,G1=J,H1=K,I1=L,J1=M,K1=N,L1=O,M1=P,N1=Q,O1=R,A=X,B=Y,2>=B,B>=1,B>=A+1] * Chain [65,81]: 3*s(140)+1 Such that:aux(60) =< 1 s(140) =< aux(60) with precondition: [A=1,B=1,W=3] * Chain [65,67]: 3*s(140)+1 Such that:aux(60) =< 1 s(140) =< aux(60) with precondition: [A=1,B=1,W=5,X=1,Y=2,Z=2,B1=0,C1=1,H1=1,L=I1,M=J1,N=K1,O=L1,P=M1,0>=G1] * Chain [62,81]: 3*s(143)+1*s(146)+1 Such that:aux(61) =< 1 s(143) =< aux(61) with precondition: [A=1,B=1,W=3] * Chain [62,67]: 3*s(143)+1*s(146)+1 Such that:aux(61) =< 1 s(146) =< -M1+2 s(143) =< aux(61) with precondition: [A=1,B=1,W=5,X=1,Y=2,Z=2,B1=0,C1=G1+1,C1+H1=2,C1+M1=3,C1>=2] * Chain [56,81]: 3*s(147)+1 Such that:aux(62) =< 1 s(147) =< aux(62) with precondition: [A=1,B=1,W=3] * Chain [56,67]: 3*s(147)+1 Such that:aux(62) =< 1 s(147) =< aux(62) with precondition: [A=1,B=1,W=5,X=1,Y=2,Z=2,C1=1,H1=1,L=I1,M=J1,N=K1,O=L1,P=M1,0>=B1+1,0>=G1] * Chain [55,81]: 3*s(150)+1 Such that:aux(63) =< 1 s(150) =< aux(63) with precondition: [A=1,B=1,W=3] * Chain [55,67]: 3*s(150)+1 Such that:aux(63) =< 1 s(150) =< aux(63) with precondition: [A=1,B=1,W=5,X=1,Y=2,Z=2,C1=1,H1=1,L=I1,M=J1,N=K1,O=L1,P=M1,0>=G1,B1>=1] * Chain [50,81]: 3*s(153)+1*s(156)+1 Such that:aux(64) =< 1 s(153) =< aux(64) with precondition: [A=1,B=1,W=3] * Chain [50,67]: 3*s(153)+1*s(156)+1 Such that:aux(64) =< 1 s(156) =< -M1+2 s(153) =< aux(64) with precondition: [A=1,B=1,W=5,X=1,Y=2,Z=2,C1=G1+1,C1+H1=2,C1+M1=3,0>=B1+1,C1>=2] * Chain [49,81]: 3*s(157)+1*s(160)+1 Such that:aux(65) =< 1 s(157) =< aux(65) with precondition: [A=1,B=1,W=3] * Chain [49,67]: 3*s(157)+1*s(160)+1 Such that:aux(65) =< 1 s(160) =< -M1+2 s(157) =< aux(65) with precondition: [A=1,B=1,W=5,X=1,Y=2,Z=2,C1=G1+1,C1+H1=2,C1+M1=3,B1>=1,C1>=2] #### Cost of chains of f17_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T): * Chain [83]: 0 with precondition: [A=3] * Chain [82]: 0 with precondition: [A=5] #### Cost of chains of f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,W): * Chain [89]: 0 with precondition: [A=1] * Chain [88]: 6 with precondition: [A=2] * Chain [87]: 0 with precondition: [0>=A] * Chain [86]: 10 with precondition: [A>=2] * Chain [85]: 52*s(230)+18*s(236)+72*s(237)+18*s(238)+33*s(240)+21*s(241)+0 Such that:s(227) =< 1 aux(75) =< A s(230) =< aux(75) s(231) =< aux(75)-1 s(232) =< aux(75) s(233) =< s(230)*aux(75) s(234) =< s(230)*s(231) s(235) =< s(230)*s(232) s(236) =< s(234) s(237) =< s(235) s(238) =< s(233) s(240) =< s(227) with precondition: [A>=3] * Chain [84]: 39*s(287)+3*s(294)+12*s(295)+3*s(296)+6*s(297)+0 Such that:aux(76) =< A s(287) =< aux(76) s(289) =< aux(76)-1 s(290) =< aux(76) s(291) =< s(287)*aux(76) s(292) =< s(287)*s(289) s(293) =< s(287)*s(290) s(294) =< s(292) s(295) =< s(293) s(296) =< s(291) with precondition: [A>=4] Closed-form bounds of f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,W): ------------------------------------- * Chain [89] with precondition: [A=1] - Upper bound: 0 - Complexity: constant * Chain [88] with precondition: [A=2] - Upper bound: 6 - Complexity: constant * Chain [87] with precondition: [0>=A] - Upper bound: 0 - Complexity: constant * Chain [86] with precondition: [A>=2] - Upper bound: 10 - Complexity: constant * Chain [85] with precondition: [A>=3] - Upper bound: inf - Complexity: infinity * Chain [84] with precondition: [A>=4] - Upper bound: inf - Complexity: infinity ### Maximum cost of f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,W): inf Asymptotic class: infinity * Total analysis performed in 6444 ms.