/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  : [f10/7]
1. non_recursive  : [exit_location/1]
2. recursive  : [f22/10]
3. recursive  : [f18/10,f22_loop_cont/11]
4. recursive  : [f34/4]
5. non_recursive  : [f43/9]
6. non_recursive  : [f34_loop_cont/10]
7. non_recursive  : [f18_loop_cont/10]
8. non_recursive  : [f10_loop_cont/10]
9. non_recursive  : [f0/9]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into f10/7
1. SCC is completely evaluated into other SCCs
2. SCC is partially evaluated into f22/10
3. SCC is partially evaluated into f18/10
4. SCC is partially evaluated into f34/4
5. SCC is completely evaluated into other SCCs
6. SCC is partially evaluated into f34_loop_cont/10
7. SCC is partially evaluated into f18_loop_cont/10
8. SCC is partially evaluated into f10_loop_cont/10
9. SCC is partially evaluated into f0/9

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

### Specialization of cost equations f10/7 
* CE 4 is refined into CE [22] 
* CE 3 is refined into CE [23] 
* CE 2 is refined into CE [24] 


### Cost equations --> "Loop" of f10/7 
* CEs [24] --> Loop 22 
* CEs [22] --> Loop 23 
* CEs [23] --> Loop 24 

### Ranking functions of CR f10(B,C,D,E,J,K,L) 
* RF of phase [22]: [-B+C]

#### Partial ranking functions of CR f10(B,C,D,E,J,K,L) 
* Partial RF of phase [22]:
  - RF of loop [22:1]:
    -B+C


### Specialization of cost equations f22/10 
* CE 16 is refined into CE [25] 
* CE 15 is refined into CE [26] 
* CE 14 is refined into CE [27] 
* CE 13 is refined into CE [28] 


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

### Ranking functions of CR f22(D,E,F,G,H,J,K,L,M,N) 
* RF of phase [25,26]: [D-G]

#### Partial ranking functions of CR f22(D,E,F,G,H,J,K,L,M,N) 
* Partial RF of phase [25,26]:
  - RF of loop [25:1]:
    D-F-1
  - RF of loop [25:1,26:1]:
    D-G


### Specialization of cost equations f18/10 
* CE 9 is refined into CE [29] 
* CE 7 is refined into CE [30,31] 
* CE 10 is refined into CE [32] 
* CE 8 is refined into CE [33] 


### Cost equations --> "Loop" of f18/10 
* CEs [33] --> Loop 29 
* CEs [29] --> Loop 30 
* CEs [30,31] --> Loop 31 
* CEs [32] --> Loop 32 

### Ranking functions of CR f18(D,E,F,G,H,J,K,L,M,N) 
* RF of phase [29]: [D-E-1]

#### Partial ranking functions of CR f18(D,E,F,G,H,J,K,L,M,N) 
* Partial RF of phase [29]:
  - RF of loop [29:1]:
    D-E-1


### Specialization of cost equations f34/4 
* CE 18 is refined into CE [34] 
* CE 19 is refined into CE [35] 
* CE 17 is refined into CE [36] 


### Cost equations --> "Loop" of f34/4 
* CEs [36] --> Loop 33 
* CEs [34] --> Loop 34 
* CEs [35] --> Loop 35 

### Ranking functions of CR f34(D,E,J,K) 
* RF of phase [33]: [D-E-1]

#### Partial ranking functions of CR f34(D,E,J,K) 
* Partial RF of phase [33]:
  - RF of loop [33:1]:
    D-E-1


### Specialization of cost equations f34_loop_cont/10 
* CE 20 is refined into CE [37] 
* CE 21 is refined into CE [38] 


### Cost equations --> "Loop" of f34_loop_cont/10 
* CEs [37] --> Loop 36 
* CEs [38] --> Loop 37 

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

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


### Specialization of cost equations f18_loop_cont/10 
* CE 12 is refined into CE [39,40,41,42] 
* CE 11 is refined into CE [43] 


### Cost equations --> "Loop" of f18_loop_cont/10 
* CEs [40,41] --> Loop 38 
* CEs [42] --> Loop 39 
* CEs [39] --> Loop 40 
* CEs [43] --> Loop 41 

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

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


### Specialization of cost equations f10_loop_cont/10 
* CE 5 is refined into CE [44] 
* CE 6 is refined into CE [45,46,47,48,49,50,51,52,53] 


### Cost equations --> "Loop" of f10_loop_cont/10 
* CEs [44] --> Loop 42 
* CEs [47] --> Loop 43 
* CEs [46,51] --> Loop 44 
* CEs [48] --> Loop 45 
* CEs [53] --> Loop 46 
* CEs [50] --> Loop 47 
* CEs [52] --> Loop 48 
* CEs [49] --> Loop 49 
* CEs [45] --> Loop 50 

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

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


### Specialization of cost equations f0/9 
* CE 1 is refined into CE [54,55,56,57,58,59,60,61,62,63,64] 


### Cost equations --> "Loop" of f0/9 
* CEs [62] --> Loop 51 
* CEs [59,61] --> Loop 52 
* CEs [57,64] --> Loop 53 
* CEs [54,55,56] --> Loop 54 
* CEs [58,60] --> Loop 55 
* CEs [63] --> Loop 56 

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

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


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

#### Cost of chains of f10(B,C,D,E,J,K,L):
* Chain [[22],24]: 1*it(22)+0
  Such that:it(22) =< -B+C

  with precondition: [J=2,L=0,C=K,B>=0,C>=B+1] 

* Chain [[22],23]: 1*it(22)+0
  Such that:it(22) =< -B+C

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

* Chain [24]: 0
  with precondition: [J=2,L=0,B=K,B>=0,B>=C] 

* Chain [23]: 0
  with precondition: [J=3,B>=0] 


#### Cost of chains of f22(D,E,F,G,H,J,K,L,M,N):
* Chain [[25,26],28]: 1*it(25)+1*it(26)+0
  Such that:it(25) =< -F+L
aux(3) =< D-G
it(25) =< aux(3)
it(26) =< aux(3)

  with precondition: [J=2,E+1=K,D=M,F>=E,G>=F+1,L>=F,D>=G+1,D>=L+1] 

* Chain [[25,26],27]: 1*it(25)+1*it(26)+0
  Such that:it(25) =< D-F
aux(4) =< D-G
it(25) =< aux(4)
it(26) =< aux(4)

  with precondition: [J=3,F>=E,G>=F+1,D>=G+1] 

* Chain [27]: 0
  with precondition: [J=3,D>=E+2,F>=E,G>=F+1] 


#### Cost of chains of f18(D,E,F,G,H,J,K,L,M,N):
* Chain [[29],32]: 1*it(29)+1*s(7)+1*s(8)+0
  Such that:aux(8) =< D-E
it(29) =< aux(8)
aux(6) =< aux(8)-1
s(9) =< it(29)*aux(8)
s(7) =< it(29)*aux(6)
s(7) =< s(9)
s(8) =< s(9)

  with precondition: [J=3,D>=E+2] 

* Chain [[29],31]: 3*it(29)+1*s(7)+1*s(8)+0
  Such that:aux(10) =< D-E
it(29) =< aux(10)
aux(6) =< aux(10)-1
s(9) =< it(29)*aux(10)
s(7) =< it(29)*aux(6)
s(7) =< s(9)
s(8) =< s(9)

  with precondition: [J=3,D>=E+3] 

* Chain [[29],30]: 1*it(29)+1*s(7)+1*s(8)+0
  Such that:aux(11) =< D-E
it(29) =< aux(11)
aux(6) =< aux(11)-1
s(9) =< it(29)*aux(11)
s(7) =< it(29)*aux(6)
s(7) =< s(9)
s(8) =< s(9)

  with precondition: [J=5,K=0,D=M,L+2>=D,D>=E+2,D>=L+1] 

* Chain [32]: 0
  with precondition: [J=3] 

* Chain [31]: 2*s(10)+0
  Such that:aux(9) =< D-E
s(10) =< aux(9)

  with precondition: [J=3,D>=E+2] 

* Chain [30]: 0
  with precondition: [J=5,K=0,L=F,M=G,N=H,E+1>=D] 


#### Cost of chains of f34(D,E,J,K):
* Chain [[33],35]: 1*it(33)+0
  Such that:it(33) =< D-E

  with precondition: [J=3,D>=E+2] 

* Chain [[33],34]: 1*it(33)+0
  Such that:it(33) =< D-E

  with precondition: [J=4,D=K+1,D>=E+2] 

* Chain [35]: 0
  with precondition: [J=3] 

* Chain [34]: 0
  with precondition: [J=4,E=K,E+1>=D] 


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

* Chain [36]: 0
  with precondition: [A=4,E=D] 


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

* Chain [40]: 0
  with precondition: [A=5,E=D] 

* Chain [39]: 0
  with precondition: [A=5,E=D,F+1>=E] 

* Chain [38]: 2*s(21)+0
  Such that:aux(13) =< D-F
s(21) =< aux(13)

  with precondition: [A=5,E=D,E>=F+2] 


#### Cost of chains of f10_loop_cont(A,B,C,D,E,F,G,H,I,J):
* Chain [50]: 0
  with precondition: [A=2,E=D] 

* Chain [49]: 0
  with precondition: [A=2,E=D,1>=E,F+1>=E] 

* Chain [48]: 1*s(24)+1*s(27)+1*s(28)+0
  Such that:s(23) =< D-F
s(24) =< s(23)
s(25) =< s(23)-1
s(26) =< s(24)*s(23)
s(27) =< s(24)*s(25)
s(27) =< s(26)
s(28) =< s(26)

  with precondition: [A=2,E=D,1>=E,E>=F+2] 

* Chain [47]: 2*s(30)+0
  Such that:s(29) =< D
s(30) =< s(29)

  with precondition: [A=2,E=D,E>=2,F+1>=E] 

* Chain [46]: 1*s(32)+1*s(35)+1*s(36)+2*s(38)+0
  Such that:s(37) =< D
s(31) =< D-F
s(38) =< s(37)
s(32) =< s(31)
s(33) =< s(31)-1
s(34) =< s(32)*s(31)
s(35) =< s(32)*s(33)
s(35) =< s(34)
s(36) =< s(34)

  with precondition: [A=2,E=D,E>=2,E>=F+2] 

* Chain [45]: 0
  with precondition: [A=2,E=D,F+1>=E] 

* Chain [44]: 4*s(40)+2*s(43)+2*s(44)+0
  Such that:aux(14) =< D-F
s(40) =< aux(14)
s(41) =< aux(14)-1
s(42) =< s(40)*aux(14)
s(43) =< s(40)*s(41)
s(43) =< s(42)
s(44) =< s(42)

  with precondition: [A=2,E=D,E>=F+2] 

* Chain [43]: 3*s(52)+1*s(55)+1*s(56)+0
  Such that:s(51) =< D-F
s(52) =< s(51)
s(53) =< s(51)-1
s(54) =< s(52)*s(51)
s(55) =< s(52)*s(53)
s(55) =< s(54)
s(56) =< s(54)

  with precondition: [A=2,E=D,E>=F+3] 

* Chain [42]: 0
  with precondition: [A=3,E=D] 


#### Cost of chains of f0(A,B,C,D,E,F,G,H,J):
* Chain [56]: 0
  with precondition: [] 

* Chain [55]: 2
  with precondition: [C=1] 

* Chain [54]: 0
  with precondition: [0>=C] 

* Chain [53]: 2*s(59)+0
  Such that:aux(16) =< C
s(59) =< aux(16)

  with precondition: [C>=1] 

* Chain [52]: 9*s(61)+3*s(68)+3*s(69)+0
  Such that:aux(19) =< C
s(61) =< aux(19)
s(66) =< aux(19)-1
s(67) =< s(61)*aux(19)
s(68) =< s(61)*s(66)
s(68) =< s(67)
s(69) =< s(67)

  with precondition: [C>=2] 

* Chain [51]: 4*s(77)+1*s(82)+1*s(83)+0
  Such that:aux(20) =< C
s(77) =< aux(20)
s(80) =< aux(20)-1
s(81) =< s(77)*aux(20)
s(82) =< s(77)*s(80)
s(82) =< s(81)
s(83) =< s(81)

  with precondition: [C>=3] 


Closed-form bounds of f0(A,B,C,D,E,F,G,H,J): 
-------------------------------------
* Chain [56] with precondition: [] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [55] with precondition: [C=1] 
    - Upper bound: 2 
    - Complexity: constant 
* Chain [54] with precondition: [0>=C] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [53] with precondition: [C>=1] 
    - Upper bound: 2*C 
    - Complexity: n 
* Chain [52] with precondition: [C>=2] 
    - Upper bound: 3*C*C+9*C+(C-1)*(3*C) 
    - Complexity: n^2 
* Chain [51] with precondition: [C>=3] 
    - Upper bound: 4*C+C*C+(C-1)*C 
    - Complexity: n^2 

### Maximum cost of f0(A,B,C,D,E,F,G,H,J): max([2,nat(C)*2*nat(C)+nat(C)*5+nat(C)*2*nat(nat(C)+ -1)+(nat(C)*nat(C)+nat(C)*2+nat(nat(C)+ -1)*nat(C))+nat(C)*2]) 
Asymptotic class: n^2 
* Total analysis performed in 598 ms.