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


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


WORST_CASE(?,O(n^3))  

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

#### Computed strongly connected components 
0. recursive  : [c/8]
1. recursive  : [b/9,c_loop_cont/10]
2. recursive  : [b_loop_cont/10,d/9]
3. non_recursive  : [exit_location/1]
4. non_recursive  : [halt/9]
5. non_recursive  : [d_loop_cont/10]
6. non_recursive  : [a/9]
7. non_recursive  : [start/9]
8. non_recursive  : [start0/9]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into c/8
1. SCC is partially evaluated into b/9
2. SCC is partially evaluated into d/9
3. SCC is completely evaluated into other SCCs
4. SCC is completely evaluated into other SCCs
5. SCC is partially evaluated into d_loop_cont/10
6. SCC is partially evaluated into a/9
7. SCC is completely evaluated into other SCCs
8. SCC is partially evaluated into start0/9

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

### Specialization of cost equations c/8 
* CE 15 is refined into CE [16] 
* CE 14 is refined into CE [17] 
* CE 13 is refined into CE [18] 


### Cost equations --> "Loop" of c/8 
* CEs [18] --> Loop 16 
* CEs [16] --> Loop 17 
* CEs [17] --> Loop 18 

### Ranking functions of CR c(A,B,C,E,G,I,J,K) 
* RF of phase [16]: [-C+E,E-1]

#### Partial ranking functions of CR c(A,B,C,E,G,I,J,K) 
* Partial RF of phase [16]:
  - RF of loop [16:1]:
    -C+E
    E-1


### Specialization of cost equations b/9 
* CE 11 is refined into CE [19] 
* CE 9 is refined into CE [20,21] 
* CE 12 is refined into CE [22] 
* CE 10 is refined into CE [23] 


### Cost equations --> "Loop" of b/9 
* CEs [23] --> Loop 19 
* CEs [19] --> Loop 20 
* CEs [20,21] --> Loop 21 
* CEs [22] --> Loop 22 

### Ranking functions of CR b(A,B,C,E,G,I,J,K,L) 
* RF of phase [19]: [A-G+1,B-G+1]

#### Partial ranking functions of CR b(A,B,C,E,G,I,J,K,L) 
* Partial RF of phase [19]:
  - RF of loop [19:1]:
    A-G+1
    B-G+1


### Specialization of cost equations d/9 
* CE 5 is refined into CE [24] 
* CE 3 is refined into CE [25,26,27,28] 
* CE 6 is refined into CE [29] 
* CE 4 is refined into CE [30] 


### Cost equations --> "Loop" of d/9 
* CEs [30] --> Loop 23 
* CEs [24] --> Loop 24 
* CEs [28] --> Loop 25 
* CEs [25,26,27] --> Loop 26 
* CEs [29] --> Loop 27 

### Ranking functions of CR d(A,B,C,E,G,I,J,K,L) 
* RF of phase [23]: [A-C,B-C]

#### Partial ranking functions of CR d(A,B,C,E,G,I,J,K,L) 
* Partial RF of phase [23]:
  - RF of loop [23:1]:
    A-C
    B-C


### Specialization of cost equations d_loop_cont/10 
* CE 7 is refined into CE [31] 
* CE 8 is refined into CE [32] 


### Cost equations --> "Loop" of d_loop_cont/10 
* CEs [31] --> Loop 28 
* CEs [32] --> Loop 29 

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

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


### Specialization of cost equations a/9 
* CE 2 is refined into CE [33,34,35,36,37,38,39,40] 


### Cost equations --> "Loop" of a/9 
* CEs [38] --> Loop 30 
* CEs [35,37] --> Loop 31 
* CEs [34,36,40] --> Loop 32 
* CEs [33] --> Loop 33 
* CEs [39] --> Loop 34 

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

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


### Specialization of cost equations start0/9 
* CE 1 is refined into CE [41,42,43,44,45] 


### Cost equations --> "Loop" of start0/9 
* CEs [45] --> Loop 35 
* CEs [44] --> Loop 36 
* CEs [43] --> Loop 37 
* CEs [42] --> Loop 38 
* CEs [41] --> Loop 39 

### 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 c(A,B,C,E,G,I,J,K):
* Chain [[16],18]: 1*it(16)+0
  Such that:it(16) =< E-J

  with precondition: [I=2,A=B,C=J,G+1=K,C>=1,E>=C+1,G>=C+1,A>=E,A>=G] 

* Chain [[16],17]: 1*it(16)+0
  Such that:it(16) =< -C+E

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

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


#### Cost of chains of b(A,B,C,E,G,I,J,K,L):
* Chain [[19],22]: 1*it(19)+1*s(3)+0
  Such that:aux(1) =< A-C
it(19) =< A-G+1
s(3) =< it(19)*aux(1)

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

* Chain [[19],21]: 1*it(19)+1*s(3)+1*s(4)+0
  Such that:it(19) =< B-G
aux(2) =< B-C
s(4) =< aux(2)
s(3) =< it(19)*aux(2)

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

* Chain [[19],20]: 1*it(19)+1*s(3)+0
  Such that:it(19) =< A-G+1
aux(1) =< A-K
s(3) =< it(19)*aux(1)

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

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

* Chain [21]: 1*s(4)+0
  Such that:s(4) =< A-C

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


#### Cost of chains of d(A,B,C,E,G,I,J,K,L):
* Chain [[23],27]: 1*it(23)+1*s(11)+1*s(12)+0
  Such that:aux(7) =< A-C
it(23) =< aux(7)
aux(4) =< aux(7)
aux(4) =< aux(7)
s(13) =< it(23)*aux(4)
s(11) =< s(13)
s(12) =< s(11)*aux(7)

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

* Chain [[23],26]: 3*it(23)+1*s(11)+1*s(12)+1*s(17)+0
  Such that:aux(9) =< A-C
it(23) =< aux(9)
s(17) =< it(23)*aux(9)
aux(4) =< aux(9)
aux(4) =< aux(9)
s(13) =< it(23)*aux(4)
s(11) =< s(13)
s(12) =< s(11)*aux(9)

  with precondition: [I=3,A=B,C>=1,A>=C+2] 

* Chain [[23],25]: 3*it(23)+1*s(11)+1*s(12)+1*s(21)+0
  Such that:aux(11) =< A-C
it(23) =< aux(11)
s(21) =< it(23)*aux(11)
aux(4) =< aux(11)
aux(4) =< aux(11)
s(13) =< it(23)*aux(4)
s(11) =< s(13)
s(12) =< s(11)*aux(11)

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

* Chain [[23],24]: 1*it(23)+1*s(11)+1*s(12)+0
  Such that:aux(12) =< -C+J
it(23) =< aux(12)
aux(4) =< aux(12)
aux(4) =< aux(12)
s(13) =< it(23)*aux(4)
s(11) =< s(13)
s(12) =< s(11)*aux(12)

  with precondition: [I=5,A=B,A=J,A=K+1,A+1=L,C>=1,A>=C+1] 

* Chain [27]: 0
  with precondition: [I=3,B=A,C>=1,B>=C] 

* Chain [26]: 1*s(14)+1*s(16)+1*s(17)+0
  Such that:aux(8) =< A-C
s(14) =< B-C
s(16) =< aux(8)
s(17) =< s(16)*aux(8)

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

* Chain [25]: 2*s(18)+1*s(21)+0
  Such that:aux(10) =< A-C
s(18) =< aux(10)
s(21) =< s(18)*aux(10)

  with precondition: [I=3,B=A,C>=1,B>=C+2] 

* Chain [24]: 0
  with precondition: [I=5,B=A,B=C,K=E,L=G,B=J,B>=1] 


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

* Chain [28]: 0
  with precondition: [A=5,C=B,C>=1] 


#### Cost of chains of a(A,B,C,D,E,F,G,H,I):
* Chain [34]: 0
  with precondition: [A=1,B=1,D=C,F=E,H=G] 

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

* Chain [32]: 4*s(23)+1*s(25)+2*s(30)+2*s(31)+0
  Such that:aux(14) =< A
s(23) =< aux(14)
s(25) =< s(23)*aux(14)
s(28) =< aux(14)
s(28) =< aux(14)
s(29) =< s(23)*s(28)
s(30) =< s(29)
s(31) =< s(30)*aux(14)

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

* Chain [31]: 5*s(39)+2*s(40)+1*s(46)+1*s(47)+0
  Such that:aux(15) =< A
s(39) =< aux(15)
s(40) =< s(39)*aux(15)
s(44) =< aux(15)
s(44) =< aux(15)
s(45) =< s(39)*s(44)
s(46) =< s(45)
s(47) =< s(46)*aux(15)

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

* Chain [30]: 3*s(49)+1*s(50)+1*s(53)+1*s(54)+0
  Such that:s(48) =< A
s(49) =< s(48)
s(50) =< s(49)*s(48)
s(51) =< s(48)
s(51) =< s(48)
s(52) =< s(49)*s(51)
s(53) =< s(52)
s(54) =< s(53)*s(48)

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


#### Cost of chains of start0(A,B,C,D,E,F,G,H,I):
* Chain [39]: 0
  with precondition: [A=1] 

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

* Chain [37]: 4*s(56)+1*s(57)+2*s(60)+2*s(61)+0
  Such that:s(55) =< A
s(56) =< s(55)
s(57) =< s(56)*s(55)
s(58) =< s(55)
s(58) =< s(55)
s(59) =< s(56)*s(58)
s(60) =< s(59)
s(61) =< s(60)*s(55)

  with precondition: [A>=2] 

* Chain [36]: 5*s(63)+2*s(64)+1*s(67)+1*s(68)+0
  Such that:s(62) =< A
s(63) =< s(62)
s(64) =< s(63)*s(62)
s(65) =< s(62)
s(65) =< s(62)
s(66) =< s(63)*s(65)
s(67) =< s(66)
s(68) =< s(67)*s(62)

  with precondition: [A>=3] 

* Chain [35]: 3*s(70)+1*s(71)+1*s(74)+1*s(75)+0
  Such that:s(69) =< A
s(70) =< s(69)
s(71) =< s(70)*s(69)
s(72) =< s(69)
s(72) =< s(69)
s(73) =< s(70)*s(72)
s(74) =< s(73)
s(75) =< s(74)*s(69)

  with precondition: [A>=4] 


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

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