/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  : [evalfbb2in/4,evalfbb3in/4,evalfbb4in/4]
1. recursive  : [evalfbb3in_loop_cont/11,evalfbb5in/10,evalfbb6in/10,evalfbb7in/10,evalfbbin/10]
2. non_recursive  : [evalfstop/6]
3. non_recursive  : [evalfreturnin/6]
4. non_recursive  : [exit_location/1]
5. non_recursive  : [evalfbb7in_loop_cont/7]
6. non_recursive  : [evalfentryin/6]
7. non_recursive  : [evalfstart/6]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into evalfbb3in/4
1. SCC is partially evaluated into evalfbb7in/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 evalfbb7in_loop_cont/7
6. SCC is partially evaluated into evalfentryin/6
7. SCC is partially evaluated into evalfstart/6

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

### Specialization of cost equations evalfbb3in/4 
* CE 14 is refined into CE [15] 
* CE 11 is refined into CE [16] 
* CE 13 is refined into CE [17] 
* CE 12 is refined into CE [18] 


### Cost equations --> "Loop" of evalfbb3in/4 
* CEs [18] --> Loop 15 
* CEs [15] --> Loop 16 
* CEs [16] --> Loop 17 
* CEs [17] --> Loop 18 

### Ranking functions of CR evalfbb3in(B,D,G,H) 
* RF of phase [15]: [B-D+1]

#### Partial ranking functions of CR evalfbb3in(B,D,G,H) 
* Partial RF of phase [15]:
  - RF of loop [15:1]:
    B-D+1


### Specialization of cost equations evalfbb7in/10 
* CE 7 is refined into CE [19] 
* CE 6 is refined into CE [20] 
* CE 3 is refined into CE [21,22] 
* CE 8 is refined into CE [23] 
* CE 5 is refined into CE [24] 
* CE 4 is refined into CE [25,26,27,28] 


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

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

#### Partial ranking functions of CR evalfbb7in(A,B,C,D,E,G,H,I,J,K) 
* Partial RF of phase [19,20,21,22,23]:
  - RF of loop [19:1,22:1]:
    C+1 depends on loops [20:1,23:1] 
  - RF of loop [20:1,21:1,22:1,23:1]:
    A+1
  - RF of loop [21:1]:
    -B+C depends on loops [20:1,23:1] 
    C depends on loops [20:1,23:1] 


### Specialization of cost equations evalfbb7in_loop_cont/7 
* CE 9 is refined into CE [29] 
* CE 10 is refined into CE [30] 


### Cost equations --> "Loop" of evalfbb7in_loop_cont/7 
* CEs [29] --> Loop 29 
* CEs [30] --> Loop 30 

### Ranking functions of CR evalfbb7in_loop_cont(A,B,C,D,E,F,G) 

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


### Specialization of cost equations evalfentryin/6 
* CE 2 is refined into CE [31,32,33,34,35,36,37] 


### Cost equations --> "Loop" of evalfentryin/6 
* CEs [33] --> Loop 31 
* CEs [31,32,35,36] --> Loop 32 
* CEs [37] --> Loop 33 
* CEs [34] --> Loop 34 

### Ranking functions of CR evalfentryin(A,B,C,D,E,G) 

#### Partial ranking functions of CR evalfentryin(A,B,C,D,E,G) 


### Specialization of cost equations evalfstart/6 
* CE 1 is refined into CE [38,39,40,41] 


### Cost equations --> "Loop" of evalfstart/6 
* CEs [41] --> Loop 35 
* CEs [40] --> Loop 36 
* CEs [39] --> Loop 37 
* CEs [38] --> Loop 38 

### Ranking functions of CR evalfstart(A,B,C,D,E,G) 

#### Partial ranking functions of CR evalfstart(A,B,C,D,E,G) 


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

#### Cost of chains of evalfbb3in(B,D,G,H):
* Chain [[15],18]: 1*it(15)+0
  Such that:it(15) =< -D+H

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

* Chain [[15],17]: 1*it(15)+0
  Such that:it(15) =< -D+H

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

* Chain [[15],16]: 1*it(15)+0
  Such that:it(15) =< B-D+1

  with precondition: [G=3,D>=0,B>=D] 

* Chain [18]: 0
  with precondition: [G=2,D=H,B>=0,D>=B+1] 

* Chain [17]: 0
  with precondition: [G=2,D=H,D>=0,B>=D] 

* Chain [16]: 0
  with precondition: [G=3,B>=0,D>=0] 


#### Cost of chains of evalfbb7in(A,B,C,D,E,G,H,I,J,K):
* Chain [[19,20,21,22,23],28]: 1*it(19)+2*it(20)+2*it(21)+1*s(5)+1*s(6)+0
  Such that:aux(49) =< A
aux(47) =< A+1
aux(48) =< A+B
aux(34) =< A+B-C+1
aux(48) =< 2*A+B
aux(50) =< B
aux(52) =< C
aux(51) =< C+1
it(20) =< aux(47)
it(21) =< aux(47)
it(20) =< aux(49)
it(21) =< aux(49)
aux(36) =< aux(50)+1
aux(12) =< aux(50)
aux(11) =< it(20)*aux(50)
aux(1) =< it(20)*aux(50)
s(5) =< it(20)*aux(50)
aux(13) =< it(20)*aux(12)
aux(4) =< aux(11)
aux(1) =< it(20)*aux(12)
aux(4) =< aux(13)
aux(2) =< it(20)*aux(36)
s(6) =< it(20)*aux(36)
it(19) =< aux(2)+aux(1)+aux(51)
it(21) =< aux(2)+aux(1)+aux(51)
it(19) =< aux(2)+aux(4)+aux(52)
it(21) =< aux(2)+aux(4)+aux(52)
s(6) =< it(19)+aux(48)
s(6) =< it(19)+aux(34)

  with precondition: [G=3,A>=0,C>=0,B>=A,A+C>=1] 

* Chain [[19,20,21,22,23],27]: 1*it(19)+2*it(20)+2*it(21)+1*s(5)+1*s(6)+1*s(7)+0
  Such that:aux(49) =< A
aux(47) =< A+1
aux(48) =< A+B-C
aux(34) =< A+B-C+1
aux(48) =< 2*A+B
aux(50) =< B
s(7) =< B+1
aux(52) =< C
aux(51) =< C+1
it(20) =< aux(47)
it(21) =< aux(47)
it(20) =< aux(49)
it(21) =< aux(49)
aux(36) =< aux(50)+1
aux(12) =< aux(50)
aux(11) =< it(20)*aux(50)
aux(1) =< it(20)*aux(50)
s(5) =< it(20)*aux(50)
aux(13) =< it(20)*aux(12)
aux(4) =< aux(11)
aux(1) =< it(20)*aux(12)
aux(4) =< aux(13)
aux(2) =< it(20)*aux(36)
s(6) =< it(20)*aux(36)
it(19) =< aux(2)+aux(1)+aux(51)
it(21) =< aux(2)+aux(1)+aux(51)
it(19) =< aux(2)+aux(4)+aux(52)
it(21) =< aux(2)+aux(4)+aux(52)
s(6) =< it(19)+aux(48)
s(6) =< it(19)+aux(34)

  with precondition: [G=3,A>=0,C>=0,B>=A,A+C>=1] 

* Chain [[19,20,21,22,23],26]: 1*it(19)+2*it(20)+2*it(21)+1*s(5)+1*s(6)+0
  Such that:aux(48) =< A+B+1
aux(34) =< A+B-C+1
aux(50) =< B
aux(48) =< 2*B+1
aux(53) =< A+1
aux(54) =< C+1
it(20) =< aux(53)
it(21) =< aux(53)
aux(36) =< aux(50)+1
aux(12) =< aux(50)
aux(11) =< it(20)*aux(50)
aux(1) =< it(20)*aux(50)
s(5) =< it(20)*aux(50)
aux(13) =< it(20)*aux(12)
aux(4) =< aux(11)
aux(1) =< it(20)*aux(12)
aux(4) =< aux(13)
aux(2) =< it(20)*aux(36)
s(6) =< it(20)*aux(36)
it(19) =< aux(2)+aux(1)+aux(54)
it(21) =< aux(2)+aux(1)+aux(54)
it(19) =< aux(2)+aux(4)+aux(54)
it(21) =< aux(2)+aux(4)+aux(54)
s(6) =< it(19)+aux(48)
s(6) =< it(19)+aux(34)

  with precondition: [G=3,A>=0,C>=0,B>=A] 

* Chain [[19,20,21,22,23],25]: 1*it(19)+2*it(20)+2*it(21)+1*s(5)+1*s(6)+0
  Such that:aux(34) =< A+B-C+1
aux(48) =< A-C+K
aux(50) =< B
aux(48) =< B-C+K
aux(51) =< C+1
aux(52) =< C-K+1
aux(55) =< A+1
it(20) =< aux(55)
it(21) =< aux(55)
aux(36) =< aux(50)+1
aux(12) =< aux(50)
aux(11) =< it(20)*aux(50)
aux(1) =< it(20)*aux(50)
s(5) =< it(20)*aux(50)
aux(13) =< it(20)*aux(12)
aux(4) =< aux(11)
aux(1) =< it(20)*aux(12)
aux(4) =< aux(13)
aux(2) =< it(20)*aux(36)
s(6) =< it(20)*aux(36)
it(19) =< aux(2)+aux(1)+aux(51)
it(21) =< aux(2)+aux(1)+aux(51)
it(19) =< aux(2)+aux(4)+aux(52)
it(21) =< aux(2)+aux(4)+aux(52)
s(6) =< it(19)+aux(48)
s(6) =< it(19)+aux(34)

  with precondition: [G=4,H+1=0,J+1=0,I+1=K,A>=0,C>=0,I+1>=0,B>=A] 

* Chain [[19,20,21,22,23],24]: 1*it(19)+2*it(20)+2*it(21)+1*s(5)+1*s(6)+0
  Such that:aux(47) =< A+1
aux(34) =< A+B-C+1
aux(48) =< A-C-H
aux(49) =< A-J
aux(50) =< B
aux(48) =< B-C-H
aux(56) =< C+1
it(20) =< aux(47)
it(21) =< aux(47)
it(20) =< aux(49)
it(21) =< aux(49)
aux(36) =< aux(50)+1
aux(12) =< aux(50)
aux(11) =< it(20)*aux(50)
aux(1) =< it(20)*aux(50)
s(5) =< it(20)*aux(50)
aux(13) =< it(20)*aux(12)
aux(4) =< aux(11)
aux(1) =< it(20)*aux(12)
aux(4) =< aux(13)
aux(2) =< it(20)*aux(36)
s(6) =< it(20)*aux(36)
it(19) =< aux(2)+aux(1)+aux(56)
it(21) =< aux(2)+aux(1)+aux(56)
it(19) =< aux(2)+aux(4)+aux(56)
it(21) =< aux(2)+aux(4)+aux(56)
s(6) =< it(19)+aux(48)
s(6) =< it(19)+aux(34)

  with precondition: [G=4,I+1=0,K=0,H=J,A>=0,C>=0,H+1>=0,B>=A,A>=H] 

* Chain [28]: 0
  with precondition: [G=3,A>=0,C>=0,B>=A] 

* Chain [27]: 1*s(7)+0
  Such that:s(7) =< B-C+1

  with precondition: [G=3,A>=0,C>=0,B>=A,B>=C] 

* Chain [26]: 0
  with precondition: [G=3,C+1>=0,B>=A] 

* Chain [25]: 0
  with precondition: [G=4,J=D,K=E,A=H,C=I,0>=A+1,C+1>=0,B>=A] 


#### Cost of chains of evalfbb7in_loop_cont(A,B,C,D,E,F,G):
* Chain [30]: 0
  with precondition: [A=3] 

* Chain [29]: 0
  with precondition: [A=4] 


#### Cost of chains of evalfentryin(A,B,C,D,E,G):
* Chain [34]: 0
  with precondition: [] 

* Chain [33]: 0
  with precondition: [0>=B+1] 

* Chain [32]: 7*s(69)+6*s(70)+3*s(75)+2*s(79)+3*s(80)+1*s(116)+0
  Such that:aux(67) =< 1
aux(68) =< B
aux(69) =< B+1
aux(70) =< 2*B+1
s(69) =< aux(69)
s(70) =< aux(69)
s(71) =< aux(68)+1
s(72) =< aux(68)
s(73) =< s(69)*aux(68)
s(74) =< s(69)*aux(68)
s(75) =< s(69)*aux(68)
s(76) =< s(69)*s(72)
s(77) =< s(73)
s(74) =< s(69)*s(72)
s(77) =< s(76)
s(78) =< s(69)*s(71)
s(79) =< s(69)*s(71)
s(80) =< s(78)+s(74)+aux(67)
s(70) =< s(78)+s(74)+aux(67)
s(80) =< s(78)+s(77)+aux(67)
s(70) =< s(78)+s(77)+aux(67)
s(79) =< s(80)+aux(70)
s(116) =< s(69)*s(71)
s(116) =< s(80)+aux(69)
s(116) =< s(80)+aux(70)

  with precondition: [B>=0] 

* Chain [31]: 1*s(120)+4*s(128)+4*s(129)+2*s(134)+2*s(138)+2*s(139)+0
  Such that:s(127) =< 1
s(123) =< 2*B+1
s(124) =< 3*B
aux(71) =< B
aux(72) =< B+1
aux(73) =< 2*B
s(120) =< aux(72)
s(118) =< aux(73)
s(118) =< s(124)
s(128) =< aux(72)
s(129) =< aux(72)
s(128) =< aux(71)
s(129) =< aux(71)
s(130) =< aux(71)+1
s(131) =< aux(71)
s(132) =< s(128)*aux(71)
s(133) =< s(128)*aux(71)
s(134) =< s(128)*aux(71)
s(135) =< s(128)*s(131)
s(136) =< s(132)
s(133) =< s(128)*s(131)
s(136) =< s(135)
s(137) =< s(128)*s(130)
s(138) =< s(128)*s(130)
s(139) =< s(137)+s(133)+s(127)
s(129) =< s(137)+s(133)+s(127)
s(139) =< s(137)+s(136)
s(129) =< s(137)+s(136)
s(138) =< s(139)+s(118)
s(138) =< s(139)+s(123)

  with precondition: [B>=1] 


#### Cost of chains of evalfstart(A,B,C,D,E,G):
* Chain [38]: 0
  with precondition: [] 

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

* Chain [36]: 7*s(145)+6*s(146)+3*s(151)+2*s(155)+3*s(156)+1*s(157)+0
  Such that:s(141) =< 1
s(142) =< B
s(143) =< B+1
s(144) =< 2*B+1
s(145) =< s(143)
s(146) =< s(143)
s(147) =< s(142)+1
s(148) =< s(142)
s(149) =< s(145)*s(142)
s(150) =< s(145)*s(142)
s(151) =< s(145)*s(142)
s(152) =< s(145)*s(148)
s(153) =< s(149)
s(150) =< s(145)*s(148)
s(153) =< s(152)
s(154) =< s(145)*s(147)
s(155) =< s(145)*s(147)
s(156) =< s(154)+s(150)+s(141)
s(146) =< s(154)+s(150)+s(141)
s(156) =< s(154)+s(153)+s(141)
s(146) =< s(154)+s(153)+s(141)
s(155) =< s(156)+s(144)
s(157) =< s(145)*s(147)
s(157) =< s(156)+s(143)
s(157) =< s(156)+s(144)

  with precondition: [B>=0] 

* Chain [35]: 1*s(164)+4*s(166)+4*s(167)+2*s(172)+2*s(176)+2*s(177)+0
  Such that:s(158) =< 1
s(161) =< B
s(162) =< B+1
s(163) =< 2*B
s(159) =< 2*B+1
s(160) =< 3*B
s(164) =< s(162)
s(165) =< s(163)
s(165) =< s(160)
s(166) =< s(162)
s(167) =< s(162)
s(166) =< s(161)
s(167) =< s(161)
s(168) =< s(161)+1
s(169) =< s(161)
s(170) =< s(166)*s(161)
s(171) =< s(166)*s(161)
s(172) =< s(166)*s(161)
s(173) =< s(166)*s(169)
s(174) =< s(170)
s(171) =< s(166)*s(169)
s(174) =< s(173)
s(175) =< s(166)*s(168)
s(176) =< s(166)*s(168)
s(177) =< s(175)+s(171)+s(158)
s(167) =< s(175)+s(171)+s(158)
s(177) =< s(175)+s(174)
s(167) =< s(175)+s(174)
s(176) =< s(177)+s(165)
s(176) =< s(177)+s(159)

  with precondition: [B>=1] 


Closed-form bounds of evalfstart(A,B,C,D,E,G): 
-------------------------------------
* Chain [38] with precondition: [] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [37] with precondition: [0>=B+1] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [36] with precondition: [B>=0] 
    - Upper bound: (B+1)*(12*B)+3+(19*B+19) 
    - Complexity: n^2 
* Chain [35] with precondition: [B>=1] 
    - Upper bound: (B+1)*(8*B)+2+(13*B+13) 
    - Complexity: n^2 

### Maximum cost of evalfstart(A,B,C,D,E,G): nat(B)*8*nat(B+1)+2+nat(B+1)*13+(nat(B)*4*nat(B+1)+1+nat(B+1)*6) 
Asymptotic class: n^2 
* Total analysis performed in 838 ms.