/export/starexec/sandbox/solver/bin/starexec_run_its /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(?,O(n^2))  

Preprocessing Cost Relations
=====================================

#### Computed strongly connected components 
0. recursive  : [lbl82/9]
1. recursive  : [lbl111/10,lbl82_loop_cont/11]
2. non_recursive  : [exit_location/1]
3. non_recursive  : [stop/9]
4. non_recursive  : [lbl16/9]
5. non_recursive  : [lbl111_loop_cont/10]
6. non_recursive  : [start/9]
7. non_recursive  : [start0/9]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into lbl82/9
1. SCC is partially evaluated into lbl111/10
2. SCC is completely evaluated into other SCCs
3. SCC is completely evaluated into other SCCs
4. SCC is completely evaluated into other SCCs
5. SCC is partially evaluated into lbl111_loop_cont/10
6. SCC is partially evaluated into start/9
7. SCC is partially evaluated into start0/9

Control-Flow Refinement of Cost Relations
=====================================

### Specialization of cost equations lbl82/9 
* CE 16 is refined into CE [17] 
* CE 15 is refined into CE [18] 
* CE 14 is refined into CE [19] 


### Cost equations --> "Loop" of lbl82/9 
* CEs [17] --> Loop 17 
* CEs [18] --> Loop 18 
* CEs [19] --> Loop 19 

### Ranking functions of CR lbl82(A,B,D,F,H,I,J,K,L) 

#### Partial ranking functions of CR lbl82(A,B,D,F,H,I,J,K,L) 


### Specialization of cost equations lbl111/10 
* CE 5 is refined into CE [20] 
* CE 11 is refined into CE [21] 
* CE 9 is discarded (unfeasible) 
* CE 4 is refined into CE [22] 
* CE 8 is refined into CE [23] 
* CE 7 is refined into CE [24] 
* CE 10 is refined into CE [25] 
* CE 6 is refined into CE [26] 


### Cost equations --> "Loop" of lbl111/10 
* CEs [24] --> Loop 20 
* CEs [25] --> Loop 21 
* CEs [26] --> Loop 22 
* CEs [20] --> Loop 23 
* CEs [21] --> Loop 24 
* CEs [22] --> Loop 25 
* CEs [23] --> Loop 26 

### Ranking functions of CR lbl111(A,B,D,F,H,I,J,K,L,M) 

#### Partial ranking functions of CR lbl111(A,B,D,F,H,I,J,K,L,M) 
* Partial RF of phase [20,21,22]:
  - RF of loop [20:1]:
    A/2-D depends on loops [21:1] 
    -D+H/2 depends on loops [21:1] 
    -D/2+F/2 depends on loops [21:1] 
  - RF of loop [20:1,22:1]:
    F-1
  - RF of loop [21:1]:
    D depends on loops [20:1,22:1] 
    D-F+1 depends on loops [20:1,22:1] 
  - RF of loop [22:1]:
    -D/2+1/2 depends on loops [21:1] 


### Specialization of cost equations lbl111_loop_cont/10 
* CE 12 is refined into CE [27] 
* CE 13 is refined into CE [28] 


### Cost equations --> "Loop" of lbl111_loop_cont/10 
* CEs [27] --> Loop 27 
* CEs [28] --> Loop 28 

### Ranking functions of CR lbl111_loop_cont(A,B,C,D,E,F,G,H,I,J) 

#### Partial ranking functions of CR lbl111_loop_cont(A,B,C,D,E,F,G,H,I,J) 


### Specialization of cost equations start/9 
* CE 3 is refined into CE [29,30,31,32,33] 
* CE 2 is refined into CE [34] 


### Cost equations --> "Loop" of start/9 
* CEs [32] --> Loop 29 
* CEs [30] --> Loop 30 
* CEs [31,33] --> Loop 31 
* CEs [34] --> Loop 32 
* CEs [29] --> Loop 33 

### Ranking functions of CR start(A,B,C,D,E,F,G,H,I) 

#### Partial ranking functions of CR start(A,B,C,D,E,F,G,H,I) 


### Specialization of cost equations start0/9 
* CE 1 is refined into CE [35,36,37,38,39] 


### Cost equations --> "Loop" of start0/9 
* CEs [39] --> Loop 34 
* CEs [38] --> Loop 35 
* CEs [37] --> Loop 36 
* CEs [36] --> Loop 37 
* CEs [35] --> Loop 38 

### Ranking functions of CR start0(A,B,C,D,E,F,G,H,I) 

#### Partial ranking functions of CR start0(A,B,C,D,E,F,G,H,I) 


Computing Bounds
=====================================

#### Cost of chains of lbl82(A,B,D,F,H,I,J,K,L):
* Chain [19]: 0
  with precondition: [F=0,I=2,L=0,D=A,D=H,B=J,D=K,D>=2,D>=B+1] 

* Chain [18]: 0
  with precondition: [I=3,D=A,D=H,B=J,F=L,D=F+K,F>=1,D>=B,D>=F+2] 

* Chain [17]: 0
  with precondition: [I=4,D=A,D=H,F>=0,D>=B,D>=F+2,D+F>=B+1] 


#### Cost of chains of lbl111(A,B,D,F,H,I,J,K,L,M):
* Chain [[20,21,22],26]: 2*it(20)+1*it(21)+0
  Such that:aux(24) =< -2*F+M+1
aux(167) =< D
aux(168) =< D-F+1
aux(169) =< F
aux(170) =< J
aux(24) =< aux(168)
aux(29) =< aux(170)
it(20) =< aux(169)
aux(75) =< aux(170)+2
aux(82) =< aux(170)+1
aux(29) =< aux(170)
aux(127) =< aux(29)+1
aux(75) =< aux(29)+2
aux(132) =< it(20)*aux(127)
aux(14) =< it(20)*aux(127)
aux(17) =< it(20)*aux(75)
aux(102) =< it(20)*aux(82)
aux(14) =< it(20)*aux(82)
aux(16) =< it(20)*aux(170)
aux(30) =< it(20)*aux(29)
aux(13) =< it(20)*aux(29)
aux(13) =< it(20)*aux(170)
aux(19) =< aux(30)
aux(19) =< aux(16)
aux(20) =< aux(132)
aux(20) =< aux(102)
it(21) =< aux(17)+aux(16)+aux(168)
it(21) =< aux(14)+aux(13)+aux(167)
it(21) =< aux(17)+aux(16)+aux(24)
it(21) =< aux(20)+aux(19)+aux(167)

  with precondition: [I=2,A=H,A=J,A=M,D>=0,F>=1,A>=B,A>=F+1,D+F>=2,A>=D+F] 

* Chain [[20,21,22],25]: 2*it(20)+1*it(21)+0
  Such that:aux(18) =< D-F+1
aux(24) =< 2*D
aux(171) =< D
aux(172) =< F
aux(173) =< H
aux(24) =< aux(171)
aux(29) =< aux(173)
it(20) =< aux(172)
aux(75) =< aux(173)+2
aux(82) =< aux(173)+1
aux(29) =< aux(173)
aux(127) =< aux(29)+1
aux(75) =< aux(29)+2
aux(132) =< it(20)*aux(127)
aux(14) =< it(20)*aux(127)
aux(17) =< it(20)*aux(75)
aux(102) =< it(20)*aux(82)
aux(14) =< it(20)*aux(82)
aux(16) =< it(20)*aux(173)
aux(30) =< it(20)*aux(29)
aux(13) =< it(20)*aux(29)
aux(13) =< it(20)*aux(173)
aux(19) =< aux(30)
aux(19) =< aux(16)
aux(20) =< aux(132)
aux(20) =< aux(102)
it(21) =< aux(17)+aux(16)+aux(18)
it(21) =< aux(14)+aux(13)+aux(171)
it(21) =< aux(17)+aux(16)+aux(24)
it(21) =< aux(20)+aux(19)+aux(171)

  with precondition: [I=4,A=H,D>=0,F>=1,A>=B,A>=F+1,D+F>=2,A>=D+F] 

* Chain [[20,21,22],24]: 2*it(20)+1*it(21)+0
  Such that:aux(18) =< D-F+1
aux(24) =< 2*D
aux(163) =< -F+H
aux(174) =< D
aux(175) =< F
aux(176) =< H
aux(24) =< aux(174)
aux(163) =< aux(174)
aux(29) =< aux(176)
it(20) =< aux(175)
aux(75) =< aux(176)+2
aux(82) =< aux(176)+1
aux(29) =< aux(176)
aux(127) =< aux(29)+1
aux(75) =< aux(29)+2
aux(132) =< it(20)*aux(127)
aux(14) =< it(20)*aux(127)
aux(17) =< it(20)*aux(75)
aux(102) =< it(20)*aux(82)
aux(14) =< it(20)*aux(82)
aux(16) =< it(20)*aux(176)
aux(30) =< it(20)*aux(29)
aux(13) =< it(20)*aux(29)
aux(13) =< it(20)*aux(176)
aux(19) =< aux(30)
aux(19) =< aux(16)
aux(20) =< aux(132)
aux(20) =< aux(102)
it(21) =< aux(17)+aux(16)+aux(18)
it(21) =< aux(14)+aux(13)+aux(174)
it(21) =< aux(17)+aux(16)+aux(24)
it(21) =< aux(20)+aux(19)+aux(163)

  with precondition: [I=4,A=H,D>=0,F>=1,A>=B,A>=F+1,D+F>=2,A>=D+F] 

* Chain [[20,21,22],23]: 2*it(20)+1*it(21)+0
  Such that:aux(18) =< D-F+1
aux(24) =< 2*D
aux(163) =< -F+H
aux(177) =< D
aux(178) =< F
aux(179) =< H
aux(24) =< aux(177)
aux(163) =< aux(177)
aux(29) =< aux(179)
it(20) =< aux(178)
aux(75) =< aux(179)+2
aux(82) =< aux(179)+1
aux(29) =< aux(179)
aux(127) =< aux(29)+1
aux(75) =< aux(29)+2
aux(132) =< it(20)*aux(127)
aux(14) =< it(20)*aux(127)
aux(17) =< it(20)*aux(75)
aux(102) =< it(20)*aux(82)
aux(14) =< it(20)*aux(82)
aux(16) =< it(20)*aux(179)
aux(30) =< it(20)*aux(29)
aux(13) =< it(20)*aux(29)
aux(13) =< it(20)*aux(179)
aux(19) =< aux(30)
aux(19) =< aux(16)
aux(20) =< aux(132)
aux(20) =< aux(102)
it(21) =< aux(17)+aux(16)+aux(18)
it(21) =< aux(14)+aux(13)+aux(177)
it(21) =< aux(17)+aux(16)+aux(24)
it(21) =< aux(20)+aux(19)+aux(163)

  with precondition: [I=4,A=H,A>=5,D>=0,F>=2,A>=B,A>=F+1,D+3*F>=9,A>=D+F] 

* Chain [24]: 0
  with precondition: [I=4,H=A,F>=1,H>=B,H>=F+1,H>=D+F] 

* Chain [23]: 0
  with precondition: [I=4,H=A,D>=1,H>=B,F>=D+1,H>=D+F] 


#### Cost of chains of lbl111_loop_cont(A,B,C,D,E,F,G,H,I,J):
* Chain [28]: 0
  with precondition: [A=2,G=0,B=E,B=I,B>=2,H>=2,B>=C+1] 

* Chain [27]: 0
  with precondition: [A=4,H>=2] 


#### Cost of chains of start(A,B,C,D,E,F,G,H,I):
* Chain [33]: 2*s(48)+1*s(61)+0
  Such that:s(43) =< 1
aux(185) =< -D+3
aux(186) =< -E+3
aux(187) =< H
s(42) =< aux(185)
s(44) =< aux(185)
s(42) =< aux(186)
s(44) =< aux(186)
s(42) =< s(44)
s(47) =< aux(187)
s(48) =< aux(187)
s(49) =< aux(187)+2
s(50) =< aux(187)+1
s(47) =< aux(187)
s(51) =< s(47)+1
s(49) =< s(47)+2
s(52) =< s(48)*s(51)
s(53) =< s(48)*s(51)
s(54) =< s(48)*s(49)
s(55) =< s(48)*s(50)
s(53) =< s(48)*s(50)
s(56) =< s(48)*aux(187)
s(57) =< s(48)*s(47)
s(58) =< s(48)*s(47)
s(58) =< s(48)*aux(187)
s(59) =< s(57)
s(59) =< s(56)
s(60) =< s(52)
s(60) =< s(55)
s(61) =< s(54)+s(56)+s(44)
s(61) =< s(53)+s(58)+s(43)
s(61) =< s(54)+s(56)+s(42)
s(61) =< s(60)+s(59)+s(43)

  with precondition: [F=0,G=0,D=A,C=B,D=E,D=H,D>=2,D>=C+1] 

* Chain [32]: 0
  with precondition: [H=A,C=B,E=D,G=F,1>=H] 

* Chain [31]: 4*s(70)+2*s(83)+0
  Such that:aux(188) =< 1
s(65) =< 2
s(64) =< -A+3
s(64) =< -H+3
aux(189) =< H
s(68) =< s(65)
s(68) =< aux(188)
s(69) =< aux(189)
s(70) =< aux(189)
s(71) =< aux(189)+2
s(72) =< aux(189)+1
s(69) =< aux(189)
s(73) =< s(69)+1
s(71) =< s(69)+2
s(74) =< s(70)*s(73)
s(75) =< s(70)*s(73)
s(76) =< s(70)*s(71)
s(77) =< s(70)*s(72)
s(75) =< s(70)*s(72)
s(78) =< s(70)*aux(189)
s(79) =< s(70)*s(69)
s(80) =< s(70)*s(69)
s(80) =< s(70)*aux(189)
s(81) =< s(79)
s(81) =< s(78)
s(82) =< s(74)
s(82) =< s(77)
s(83) =< s(76)+s(78)+s(64)
s(83) =< s(75)+s(80)+aux(188)
s(83) =< s(76)+s(78)+s(68)
s(83) =< s(82)+s(81)+aux(188)

  with precondition: [H=A,C=B,E=D,G=F,H>=2] 

* Chain [30]: 0
  with precondition: [H=A,C=B,E=D,G=F,H>=3] 

* Chain [29]: 2*s(92)+1*s(105)+0
  Such that:s(86) =< 2
s(85) =< -A+3
s(85) =< -H+3
aux(190) =< 1
aux(191) =< H
s(86) =< aux(190)
s(91) =< aux(191)
s(92) =< aux(191)
s(93) =< aux(191)+2
s(94) =< aux(191)+1
s(91) =< aux(191)
s(95) =< s(91)+1
s(93) =< s(91)+2
s(96) =< s(92)*s(95)
s(97) =< s(92)*s(95)
s(98) =< s(92)*s(93)
s(99) =< s(92)*s(94)
s(97) =< s(92)*s(94)
s(100) =< s(92)*aux(191)
s(101) =< s(92)*s(91)
s(102) =< s(92)*s(91)
s(102) =< s(92)*aux(191)
s(103) =< s(101)
s(103) =< s(100)
s(104) =< s(96)
s(104) =< s(99)
s(105) =< s(98)+s(100)+s(85)
s(105) =< s(97)+s(102)+aux(190)
s(105) =< s(98)+s(100)+s(86)
s(105) =< s(104)+s(103)+aux(190)

  with precondition: [H=A,C=B,E=D,G=F,H>=5] 


#### Cost of chains of start0(A,B,C,D,E,F,G,H,I):
* Chain [38]: 2*s(113)+1*s(126)+0
  Such that:s(106) =< 1
s(109) =< E
aux(192) =< -A+3
aux(193) =< -E+3
s(107) =< aux(192)
s(107) =< aux(193)
s(112) =< s(109)
s(113) =< s(109)
s(114) =< s(109)+2
s(115) =< s(109)+1
s(112) =< s(109)
s(116) =< s(112)+1
s(114) =< s(112)+2
s(117) =< s(113)*s(116)
s(118) =< s(113)*s(116)
s(119) =< s(113)*s(114)
s(120) =< s(113)*s(115)
s(118) =< s(113)*s(115)
s(121) =< s(113)*s(109)
s(122) =< s(113)*s(112)
s(123) =< s(113)*s(112)
s(123) =< s(113)*s(109)
s(124) =< s(122)
s(124) =< s(121)
s(125) =< s(117)
s(125) =< s(120)
s(126) =< s(119)+s(121)+s(107)
s(126) =< s(118)+s(123)+s(106)
s(126) =< s(125)+s(124)+s(106)

  with precondition: [G=0,A=E,A>=2,A>=C+1] 

* Chain [37]: 0
  with precondition: [1>=A] 

* Chain [36]: 4*s(133)+2*s(146)+0
  Such that:s(128) =< 2
s(129) =< -A+3
s(130) =< A
aux(194) =< 1
s(129) =< aux(194)
s(131) =< s(128)
s(131) =< aux(194)
s(132) =< s(130)
s(133) =< s(130)
s(134) =< s(130)+2
s(135) =< s(130)+1
s(132) =< s(130)
s(136) =< s(132)+1
s(134) =< s(132)+2
s(137) =< s(133)*s(136)
s(138) =< s(133)*s(136)
s(139) =< s(133)*s(134)
s(140) =< s(133)*s(135)
s(138) =< s(133)*s(135)
s(141) =< s(133)*s(130)
s(142) =< s(133)*s(132)
s(143) =< s(133)*s(132)
s(143) =< s(133)*s(130)
s(144) =< s(142)
s(144) =< s(141)
s(145) =< s(137)
s(145) =< s(140)
s(146) =< s(139)+s(141)+s(129)
s(146) =< s(138)+s(143)+aux(194)
s(146) =< s(139)+s(141)+s(131)
s(146) =< s(145)+s(144)+aux(194)

  with precondition: [A>=2] 

* Chain [35]: 0
  with precondition: [A>=3] 

* Chain [34]: 2*s(152)+1*s(165)+0
  Such that:s(149) =< 1
s(147) =< 2
s(150) =< A
s(147) =< s(149)
s(151) =< s(150)
s(152) =< s(150)
s(153) =< s(150)+2
s(154) =< s(150)+1
s(151) =< s(150)
s(155) =< s(151)+1
s(153) =< s(151)+2
s(156) =< s(152)*s(155)
s(157) =< s(152)*s(155)
s(158) =< s(152)*s(153)
s(159) =< s(152)*s(154)
s(157) =< s(152)*s(154)
s(160) =< s(152)*s(150)
s(161) =< s(152)*s(151)
s(162) =< s(152)*s(151)
s(162) =< s(152)*s(150)
s(163) =< s(161)
s(163) =< s(160)
s(164) =< s(156)
s(164) =< s(159)
s(165) =< s(158)+s(160)
s(165) =< s(157)+s(162)+s(149)
s(165) =< s(158)+s(160)+s(147)
s(165) =< s(164)+s(163)+s(149)

  with precondition: [A>=5] 


Closed-form bounds of start0(A,B,C,D,E,F,G,H,I): 
-------------------------------------
* Chain [38] with precondition: [G=0,A=E,A>=2,A>=C+1] 
    - Upper bound: 2*E*E+4*E+nat(-A+3) 
    - Complexity: n^2 
* Chain [37] with precondition: [1>=A] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [36] with precondition: [A>=2] 
    - Upper bound: 8*A+2+4*A*A 
    - Complexity: n^2 
* Chain [35] with precondition: [A>=3] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [34] with precondition: [A>=5] 
    - Upper bound: 2*A*A+4*A 
    - Complexity: n^2 

### Maximum cost of start0(A,B,C,D,E,F,G,H,I): max([nat(E)*2*nat(E)+nat(E)*4+nat(-A+3),nat(A)*4+2+nat(A)*2*nat(A)+(nat(A)*2*nat(A)+nat(A)*4)]) 
Asymptotic class: n^2 
* Total analysis performed in 1724 ms.