/export/starexec/sandbox/solver/bin/starexec_run_its /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(n^1)) Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [f17/6] 1. non_recursive : [exit_location/1] 2. recursive : [f27/6] 3. recursive : [f37/6] 4. recursive : [f45/6] 5. recursive : [f55/6] 6. recursive : [f65/6] 7. recursive : [f75/6] 8. recursive : [f83/4] 9. non_recursive : [f93/11] 10. non_recursive : [f83_loop_cont/12] 11. non_recursive : [f75_loop_cont/12] 12. non_recursive : [f65_loop_cont/12] 13. non_recursive : [f55_loop_cont/12] 14. non_recursive : [f45_loop_cont/12] 15. non_recursive : [f37_loop_cont/12] 16. non_recursive : [f27_loop_cont/12] 17. non_recursive : [f17_loop_cont/12] 18. non_recursive : [f0/11] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into f17/6 1. SCC is completely evaluated into other SCCs 2. SCC is partially evaluated into f27/6 3. SCC is partially evaluated into f37/6 4. SCC is partially evaluated into f45/6 5. SCC is partially evaluated into f55/6 6. SCC is partially evaluated into f65/6 7. SCC is partially evaluated into f75/6 8. SCC is partially evaluated into f83/4 9. SCC is completely evaluated into other SCCs 10. SCC is partially evaluated into f83_loop_cont/12 11. SCC is partially evaluated into f75_loop_cont/12 12. SCC is partially evaluated into f65_loop_cont/12 13. SCC is partially evaluated into f55_loop_cont/12 14. SCC is partially evaluated into f45_loop_cont/12 15. SCC is partially evaluated into f37_loop_cont/12 16. SCC is partially evaluated into f27_loop_cont/12 17. SCC is partially evaluated into f17_loop_cont/12 18. SCC is partially evaluated into f0/11 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations f17/6 * CE 3 is refined into CE [42] * CE 4 is refined into CE [43] * CE 2 is refined into CE [44] ### Cost equations --> "Loop" of f17/6 * CEs [44] --> Loop 42 * CEs [42] --> Loop 43 * CEs [43] --> Loop 44 ### Ranking functions of CR f17(D,E,F,M,N,O) * RF of phase [42]: [-D+E] #### Partial ranking functions of CR f17(D,E,F,M,N,O) * Partial RF of phase [42]: - RF of loop [42:1]: -D+E ### Specialization of cost equations f27/6 * CE 8 is refined into CE [45] * CE 9 is refined into CE [46] * CE 7 is refined into CE [47] ### Cost equations --> "Loop" of f27/6 * CEs [47] --> Loop 45 * CEs [45] --> Loop 46 * CEs [46] --> Loop 47 ### Ranking functions of CR f27(E,F,G,M,N,O) * RF of phase [45]: [E-F] #### Partial ranking functions of CR f27(E,F,G,M,N,O) * Partial RF of phase [45]: - RF of loop [45:1]: E-F ### Specialization of cost equations f37/6 * CE 13 is refined into CE [48] * CE 14 is refined into CE [49] * CE 12 is refined into CE [50] ### Cost equations --> "Loop" of f37/6 * CEs [50] --> Loop 48 * CEs [48] --> Loop 49 * CEs [49] --> Loop 50 ### Ranking functions of CR f37(A,E,G,M,N,O) * RF of phase [48]: [E-G] #### Partial ranking functions of CR f37(A,E,G,M,N,O) * Partial RF of phase [48]: - RF of loop [48:1]: E-G ### Specialization of cost equations f45/6 * CE 18 is refined into CE [51] * CE 19 is refined into CE [52] * CE 17 is refined into CE [53] ### Cost equations --> "Loop" of f45/6 * CEs [53] --> Loop 51 * CEs [51] --> Loop 52 * CEs [52] --> Loop 53 ### Ranking functions of CR f45(A,E,H,M,N,O) * RF of phase [51]: [-A+E] #### Partial ranking functions of CR f45(A,E,H,M,N,O) * Partial RF of phase [51]: - RF of loop [51:1]: -A+E ### Specialization of cost equations f55/6 * CE 23 is refined into CE [54] * CE 24 is refined into CE [55] * CE 22 is refined into CE [56] ### Cost equations --> "Loop" of f55/6 * CEs [56] --> Loop 54 * CEs [54] --> Loop 55 * CEs [55] --> Loop 56 ### Ranking functions of CR f55(E,H,I,M,N,O) * RF of phase [54]: [E-H] #### Partial ranking functions of CR f55(E,H,I,M,N,O) * Partial RF of phase [54]: - RF of loop [54:1]: E-H ### Specialization of cost equations f65/6 * CE 28 is refined into CE [57] * CE 29 is refined into CE [58] * CE 27 is refined into CE [59] ### Cost equations --> "Loop" of f65/6 * CEs [59] --> Loop 57 * CEs [57] --> Loop 58 * CEs [58] --> Loop 59 ### Ranking functions of CR f65(E,I,J,M,N,O) * RF of phase [57]: [E-I] #### Partial ranking functions of CR f65(E,I,J,M,N,O) * Partial RF of phase [57]: - RF of loop [57:1]: E-I ### Specialization of cost equations f75/6 * CE 33 is refined into CE [60] * CE 34 is refined into CE [61] * CE 32 is refined into CE [62] ### Cost equations --> "Loop" of f75/6 * CEs [62] --> Loop 60 * CEs [60] --> Loop 61 * CEs [61] --> Loop 62 ### Ranking functions of CR f75(A,E,J,M,N,O) * RF of phase [60]: [E-J] #### Partial ranking functions of CR f75(A,E,J,M,N,O) * Partial RF of phase [60]: - RF of loop [60:1]: E-J ### Specialization of cost equations f83/4 * CE 39 is refined into CE [63] * CE 38 is refined into CE [64] * CE 37 is refined into CE [65] ### Cost equations --> "Loop" of f83/4 * CEs [65] --> Loop 63 * CEs [63] --> Loop 64 * CEs [64] --> Loop 65 ### Ranking functions of CR f83(A,E,M,N) * RF of phase [63]: [-A+E] #### Partial ranking functions of CR f83(A,E,M,N) * Partial RF of phase [63]: - RF of loop [63:1]: -A+E ### Specialization of cost equations f83_loop_cont/12 * CE 41 is refined into CE [66] * CE 40 is refined into CE [67] ### Cost equations --> "Loop" of f83_loop_cont/12 * CEs [66] --> Loop 66 * CEs [67] --> Loop 67 ### Ranking functions of CR f83_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) #### Partial ranking functions of CR f83_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) ### Specialization of cost equations f75_loop_cont/12 * CE 36 is refined into CE [68,69,70,71] * CE 35 is refined into CE [72] ### Cost equations --> "Loop" of f75_loop_cont/12 * CEs [68] --> Loop 68 * CEs [69,71] --> Loop 69 * CEs [70] --> Loop 70 * CEs [72] --> Loop 71 ### Ranking functions of CR f75_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) #### Partial ranking functions of CR f75_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) ### Specialization of cost equations f65_loop_cont/12 * CE 31 is refined into CE [73,74,75,76,77,78,79,80] * CE 30 is refined into CE [81] ### Cost equations --> "Loop" of f65_loop_cont/12 * CEs [74,75] --> Loop 72 * CEs [78] --> Loop 73 * CEs [76] --> Loop 74 * CEs [79] --> Loop 75 * CEs [77] --> Loop 76 * CEs [80] --> Loop 77 * CEs [73] --> Loop 78 * CEs [81] --> Loop 79 ### Ranking functions of CR f65_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) #### Partial ranking functions of CR f65_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) ### Specialization of cost equations f55_loop_cont/12 * CE 26 is refined into CE [82,83,84,85,86,87,88,89,90,91,92,93] * CE 25 is refined into CE [94] ### Cost equations --> "Loop" of f55_loop_cont/12 * CEs [83,84] --> Loop 80 * CEs [89] --> Loop 81 * CEs [86,88] --> Loop 82 * CEs [91,93] --> Loop 83 * CEs [85,87] --> Loop 84 * CEs [90,92] --> Loop 85 * CEs [82] --> Loop 86 * CEs [94] --> Loop 87 ### Ranking functions of CR f55_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) #### Partial ranking functions of CR f55_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) ### Specialization of cost equations f45_loop_cont/12 * CE 21 is refined into CE [95,96,97,98,99,100,101,102,103,104,105,106] * CE 20 is refined into CE [107] ### Cost equations --> "Loop" of f45_loop_cont/12 * CEs [96,97] --> Loop 88 * CEs [102] --> Loop 89 * CEs [99,101] --> Loop 90 * CEs [104,106] --> Loop 91 * CEs [98,100] --> Loop 92 * CEs [103,105] --> Loop 93 * CEs [95] --> Loop 94 * CEs [107] --> Loop 95 ### Ranking functions of CR f45_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) #### Partial ranking functions of CR f45_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) ### Specialization of cost equations f37_loop_cont/12 * CE 16 is refined into CE [108,109,110,111,112,113,114,115,116,117,118,119] * CE 15 is refined into CE [120] ### Cost equations --> "Loop" of f37_loop_cont/12 * CEs [110] --> Loop 96 * CEs [109,115] --> Loop 97 * CEs [112,114] --> Loop 98 * CEs [117,119] --> Loop 99 * CEs [111,113] --> Loop 100 * CEs [116,118] --> Loop 101 * CEs [108] --> Loop 102 * CEs [120] --> Loop 103 ### Ranking functions of CR f37_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) #### Partial ranking functions of CR f37_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) ### Specialization of cost equations f27_loop_cont/12 * CE 11 is refined into CE [121,122,123,124,125,126,127,128,129,130,131,132] * CE 10 is refined into CE [133] ### Cost equations --> "Loop" of f27_loop_cont/12 * CEs [122,123] --> Loop 104 * CEs [128] --> Loop 105 * CEs [125,126] --> Loop 106 * CEs [130,131] --> Loop 107 * CEs [124,127] --> Loop 108 * CEs [129,132] --> Loop 109 * CEs [121] --> Loop 110 * CEs [133] --> Loop 111 ### Ranking functions of CR f27_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) #### Partial ranking functions of CR f27_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) ### Specialization of cost equations f17_loop_cont/12 * CE 6 is refined into CE [134,135,136,137,138,139,140,141,142,143,144,145] * CE 5 is refined into CE [146] ### Cost equations --> "Loop" of f17_loop_cont/12 * CEs [135,136] --> Loop 112 * CEs [141] --> Loop 113 * CEs [138,140] --> Loop 114 * CEs [143,145] --> Loop 115 * CEs [137,139] --> Loop 116 * CEs [142,144] --> Loop 117 * CEs [134] --> Loop 118 * CEs [146] --> Loop 119 ### Ranking functions of CR f17_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) #### Partial ranking functions of CR f17_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) ### Specialization of cost equations f0/11 * CE 1 is refined into CE [147,148,149,150,151,152,153,154] ### Cost equations --> "Loop" of f0/11 * CEs [148,152,153,154] --> Loop 120 * CEs [149,150,151] --> Loop 121 * CEs [147] --> Loop 122 ### Ranking functions of CR f0(A,B,C,D,E,F,G,H,I,J,M) #### Partial ranking functions of CR f0(A,B,C,D,E,F,G,H,I,J,M) Computing Bounds ===================================== #### Cost of chains of f17(D,E,F,M,N,O): * Chain [[42],44]: 1*it(42)+0 Such that:it(42) =< -D+E with precondition: [M=3,D>=0,E>=D+1] * Chain [[42],43]: 1*it(42)+0 Such that:it(42) =< -D+N with precondition: [M=10,O=0,E=N,D>=0,E>=D+1] * Chain [44]: 0 with precondition: [M=3,D>=0] * Chain [43]: 0 with precondition: [M=10,O=0,D=N,D>=0,D>=E] #### Cost of chains of f27(E,F,G,M,N,O): * Chain [[45],47]: 1*it(45)+0 Such that:it(45) =< E-F with precondition: [M=3,E>=F+1] * Chain [[45],46]: 1*it(45)+0 Such that:it(45) =< E-F with precondition: [M=9,O=0,E=N,E>=F+1] * Chain [47]: 0 with precondition: [M=3] * Chain [46]: 0 with precondition: [M=9,O=0,F=N,F>=E] #### Cost of chains of f37(A,E,G,M,N,O): * Chain [[48],50]: 1*it(48)+0 Such that:it(48) =< E-G with precondition: [A=0,M=3,E>=G+1] * Chain [[48],49]: 1*it(48)+0 Such that:it(48) =< E-G with precondition: [A=0,M=8,N=0,E=O,E>=G+1] * Chain [50]: 0 with precondition: [A=0,M=3] * Chain [49]: 0 with precondition: [A=0,M=8,N=0,G=O,G>=E] #### Cost of chains of f45(A,E,H,M,N,O): * Chain [[51],53]: 1*it(51)+0 Such that:it(51) =< -A+E with precondition: [M=3,E>=A+1] * Chain [[51],52]: 1*it(51)+0 Such that:it(51) =< -A+N with precondition: [M=7,O=0,E=N,E>=A+1] * Chain [53]: 0 with precondition: [M=3] * Chain [52]: 0 with precondition: [M=7,O=0,A=N,A>=E] #### Cost of chains of f55(E,H,I,M,N,O): * Chain [[54],56]: 1*it(54)+0 Such that:it(54) =< E-H with precondition: [M=3,E>=H+1] * Chain [[54],55]: 1*it(54)+0 Such that:it(54) =< E-H with precondition: [M=6,O=0,E=N,E>=H+1] * Chain [56]: 0 with precondition: [M=3] * Chain [55]: 0 with precondition: [M=6,O=0,H=N,H>=E] #### Cost of chains of f65(E,I,J,M,N,O): * Chain [[57],59]: 1*it(57)+0 Such that:it(57) =< E-I with precondition: [M=3,E>=I+1] * Chain [[57],58]: 1*it(57)+0 Such that:it(57) =< E-I with precondition: [M=5,O=0,E=N,E>=I+1] * Chain [59]: 0 with precondition: [M=3] * Chain [58]: 0 with precondition: [M=5,O=0,I=N,I>=E] #### Cost of chains of f75(A,E,J,M,N,O): * Chain [[60],62]: 1*it(60)+0 Such that:it(60) =< E-J with precondition: [M=3,E>=J+1] * Chain [[60],61]: 1*it(60)+0 Such that:it(60) =< E-J with precondition: [M=4,N=0,E=O,E>=J+1] * Chain [62]: 0 with precondition: [M=3] * Chain [61]: 0 with precondition: [M=4,N=0,J=O,J>=E] #### Cost of chains of f83(A,E,M,N): * Chain [[63],65]: 1*it(63)+0 Such that:it(63) =< -A+N with precondition: [M=2,E=N,E>=A+1] * Chain [[63],64]: 1*it(63)+0 Such that:it(63) =< -A+E with precondition: [M=3,E>=A+1] * Chain [65]: 0 with precondition: [M=2,A=N,A>=E] * Chain [64]: 0 with precondition: [M=3] #### Cost of chains of f83_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): * Chain [67]: 0 with precondition: [A=2] * Chain [66]: 0 with precondition: [A=3] #### Cost of chains of f75_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): * Chain [71]: 0 with precondition: [A=3] * Chain [70]: 0 with precondition: [A=4] * Chain [69]: 2*s(1)+0 Such that:aux(1) =< -B+F s(1) =< aux(1) with precondition: [A=4,F>=B+1] * Chain [68]: 0 with precondition: [A=4,B>=F] #### Cost of chains of f65_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): * Chain [79]: 0 with precondition: [A=3] * Chain [78]: 0 with precondition: [A=5] * Chain [77]: 0 with precondition: [A=5,0>=F,K>=F] * Chain [76]: 1*s(3)+0 Such that:s(3) =< F-K with precondition: [A=5,0>=F,F>=K+1] * Chain [75]: 2*s(5)+0 Such that:s(4) =< F s(5) =< s(4) with precondition: [A=5,F>=1,K>=F] * Chain [74]: 1*s(6)+2*s(8)+0 Such that:s(7) =< F s(6) =< F-K s(8) =< s(7) with precondition: [A=5,F>=1,F>=K+1] * Chain [73]: 0 with precondition: [A=5,K>=F] * Chain [72]: 2*s(9)+0 Such that:aux(2) =< F-K s(9) =< aux(2) with precondition: [A=5,F>=K+1] #### Cost of chains of f55_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): * Chain [87]: 0 with precondition: [A=3] * Chain [86]: 0 with precondition: [A=6] * Chain [85]: 0 with precondition: [A=6,0>=F,J>=F] * Chain [84]: 2*s(11)+0 Such that:aux(3) =< F-J s(11) =< aux(3) with precondition: [A=6,0>=F,F>=J+1] * Chain [83]: 5*s(14)+0 Such that:aux(5) =< F s(14) =< aux(5) with precondition: [A=6,F>=1,J>=F] * Chain [82]: 2*s(18)+5*s(20)+0 Such that:aux(7) =< F aux(8) =< F-J s(18) =< aux(8) s(20) =< aux(7) with precondition: [A=6,F>=1,F>=J+1] * Chain [81]: 0 with precondition: [A=6,J>=F] * Chain [80]: 2*s(25)+0 Such that:aux(9) =< F-J s(25) =< aux(9) with precondition: [A=6,F>=J+1] #### Cost of chains of f45_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): * Chain [95]: 0 with precondition: [A=3] * Chain [94]: 0 with precondition: [A=7] * Chain [93]: 0 with precondition: [A=7,0>=F,I>=F] * Chain [92]: 2*s(27)+0 Such that:aux(10) =< F-I s(27) =< aux(10) with precondition: [A=7,0>=F,F>=I+1] * Chain [91]: 9*s(31)+0 Such that:aux(12) =< F s(31) =< aux(12) with precondition: [A=7,F>=1,I>=F] * Chain [90]: 2*s(35)+9*s(38)+0 Such that:aux(14) =< F aux(15) =< F-I s(35) =< aux(15) s(38) =< aux(14) with precondition: [A=7,F>=1,F>=I+1] * Chain [89]: 0 with precondition: [A=7,I>=F] * Chain [88]: 2*s(43)+0 Such that:aux(16) =< F-I s(43) =< aux(16) with precondition: [A=7,F>=I+1] #### Cost of chains of f37_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): * Chain [103]: 0 with precondition: [A=3] * Chain [102]: 0 with precondition: [A=8] * Chain [101]: 2*s(45)+0 Such that:aux(17) =< -B+F s(45) =< aux(17) with precondition: [A=8,0>=F,F>=B+1] * Chain [100]: 0 with precondition: [A=8,0>=F,B>=F] * Chain [99]: 2*s(47)+13*s(50)+0 Such that:aux(19) =< -B+F aux(20) =< F s(47) =< aux(19) s(50) =< aux(20) with precondition: [A=8,F>=1,F>=B+1] * Chain [98]: 13*s(57)+0 Such that:aux(22) =< F s(57) =< aux(22) with precondition: [A=8,F>=1,B>=F] * Chain [97]: 2*s(61)+0 Such that:aux(23) =< -B+F s(61) =< aux(23) with precondition: [A=8,F>=B+1] * Chain [96]: 0 with precondition: [A=8,B>=F] #### Cost of chains of f27_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): * Chain [111]: 0 with precondition: [A=3,B=0] * Chain [110]: 0 with precondition: [A=9,B=0] * Chain [109]: 0 with precondition: [A=9,B=0,0>=F,H>=F] * Chain [108]: 2*s(63)+0 Such that:aux(24) =< F-H s(63) =< aux(24) with precondition: [A=9,B=0,0>=F,F>=H+1] * Chain [107]: 17*s(67)+0 Such that:aux(26) =< F s(67) =< aux(26) with precondition: [A=9,B=0,F>=1,H>=F] * Chain [106]: 2*s(71)+17*s(74)+0 Such that:aux(28) =< F aux(29) =< F-H s(71) =< aux(29) s(74) =< aux(28) with precondition: [A=9,B=0,F>=1,F>=H+1] * Chain [105]: 0 with precondition: [A=9,B=0,H>=F] * Chain [104]: 2*s(79)+0 Such that:aux(30) =< F-H s(79) =< aux(30) with precondition: [A=9,B=0,F>=H+1] #### Cost of chains of f17_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): * Chain [119]: 0 with precondition: [A=3,B=0] * Chain [118]: 0 with precondition: [A=10,B=0] * Chain [117]: 0 with precondition: [A=10,B=0,0>=F,G>=F] * Chain [116]: 2*s(81)+0 Such that:aux(31) =< F-G s(81) =< aux(31) with precondition: [A=10,B=0,0>=F,F>=G+1] * Chain [115]: 21*s(85)+0 Such that:aux(33) =< F s(85) =< aux(33) with precondition: [A=10,B=0,F>=1,G>=F] * Chain [114]: 2*s(89)+21*s(92)+0 Such that:aux(35) =< F aux(36) =< F-G s(89) =< aux(36) s(92) =< aux(35) with precondition: [A=10,B=0,F>=1,F>=G+1] * Chain [113]: 0 with precondition: [A=10,B=0,G>=F] * Chain [112]: 2*s(97)+0 Such that:aux(37) =< F-G s(97) =< aux(37) with precondition: [A=10,B=0,F>=G+1] #### Cost of chains of f0(A,B,C,D,E,F,G,H,I,J,M): * Chain [122]: 0 with precondition: [] * Chain [121]: 0 with precondition: [0>=E] * Chain [120]: 29*s(99)+0 Such that:aux(40) =< E s(99) =< aux(40) with precondition: [E>=1] Closed-form bounds of f0(A,B,C,D,E,F,G,H,I,J,M): ------------------------------------- * Chain [122] with precondition: [] - Upper bound: 0 - Complexity: constant * Chain [121] with precondition: [0>=E] - Upper bound: 0 - Complexity: constant * Chain [120] with precondition: [E>=1] - Upper bound: 29*E - Complexity: n ### Maximum cost of f0(A,B,C,D,E,F,G,H,I,J,M): nat(E)*29 Asymptotic class: n * Total analysis performed in 1030 ms.