/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  : [lbl141/9]
1. recursive  : [lbl121/17,lbl141_loop_cont/18]
2. non_recursive  : [stop/9]
3. non_recursive  : [cut/9]
4. non_recursive  : [exit_location/1]
5. non_recursive  : [lbl121_loop_cont/10]
6. non_recursive  : [lbl6/9]
7. non_recursive  : [start/9]
8. non_recursive  : [start0/9]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into lbl141/9
1. SCC is partially evaluated into lbl121/17
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 lbl121_loop_cont/10
6. SCC is completely evaluated into other SCCs
7. SCC is partially evaluated into start/9
8. SCC is partially evaluated into start0/9

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

### Specialization of cost equations lbl141/9 
* CE 14 is refined into CE [15] 
* CE 13 is refined into CE [16] 
* CE 12 is refined into CE [17] 


### Cost equations --> "Loop" of lbl141/9 
* CEs [15] --> Loop 15 
* CEs [16] --> Loop 16 
* CEs [17] --> Loop 17 

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

#### Partial ranking functions of CR lbl141(A,B,C,D,E,G,I,J,K) 


### Specialization of cost equations lbl121/17 
* CE 5 is refined into CE [18] 
* CE 9 is refined into CE [19] 
* CE 7 is refined into CE [20] 
* CE 8 is refined into CE [21] 
* CE 6 is refined into CE [22] 


### Cost equations --> "Loop" of lbl121/17 
* CEs [21] --> Loop 18 
* CEs [22] --> Loop 19 
* CEs [19] --> Loop 20 
* CEs [18] --> Loop 21 
* CEs [20] --> Loop 22 

### Ranking functions of CR lbl121(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q) 

#### Partial ranking functions of CR lbl121(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q) 
* Partial RF of phase [18,19]:
  - RF of loop [18:1]:
    A-E depends on loops [19:1] 
    B-E-1 depends on loops [19:1] 
    C-E-1 depends on loops [19:1] 
    D-E depends on loops [19:1] 
  - RF of loop [19:1]:
    -A+E+1 depends on loops [18:1] 
    B-G-1
    C-G-1
    -D+E+1 depends on loops [18:1] 
    E-1 depends on loops [18:1] 


### Specialization of cost equations lbl121_loop_cont/10 
* CE 10 is refined into CE [23] 
* CE 11 is refined into CE [24] 


### Cost equations --> "Loop" of lbl121_loop_cont/10 
* CEs [23] --> Loop 23 
* CEs [24] --> Loop 24 

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

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


### Specialization of cost equations start/9 
* CE 3 is refined into CE [25] 
* CE 4 is refined into CE [26,27,28,29] 
* CE 2 is refined into CE [30] 


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

### 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 [31,32,33,34,35] 


### Cost equations --> "Loop" of start0/9 
* CEs [35] --> Loop 30 
* CEs [33] --> Loop 31 
* CEs [34] --> Loop 32 
* CEs [32] --> Loop 33 
* CEs [31] --> Loop 34 

### 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 lbl141(A,B,C,D,E,G,I,J,K):
* Chain [17]: 0
  with precondition: [E=0,I=2,J=0,D=A,C=B,C=G,C=K,D>=2,C>=D+1] 

* Chain [16]: 0
  with precondition: [E=0,I=3,J=1,D=A,C=B,G=K,D>=2,G>=1,C>=D+1,C>=G+1] 

* Chain [15]: 0
  with precondition: [E=0,I=4,D=A,C=B,D>=1,G>=1,C>=D+1,C>=G,C+D>=G+2] 


#### Cost of chains of lbl121(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q):
* Chain [[18,19],22]: 1*it(18)+1*it(19)+0
  Such that:it(19) =< C-G
aux(41) =< C-G+M
aux(57) =< C-E
aux(58) =< -E+M
aux(59) =< M
aux(41) =< aux(59)
aux(51) =< aux(59)
aux(41) =< aux(59)
aux(51) =< aux(41)
aux(52) =< it(19)*aux(51)
aux(1) =< it(19)*aux(51)
aux(3) =< it(19)*aux(41)
aux(7) =< it(19)*aux(59)
aux(1) =< it(19)*aux(59)
aux(9) =< aux(52)
aux(5) =< aux(3)
aux(5) =< aux(7)
aux(9) =< aux(7)
it(18) =< aux(7)+aux(58)
it(18) =< aux(3)+aux(57)
it(18) =< aux(1)+aux(58)
it(18) =< aux(5)+aux(58)
it(18) =< aux(9)+aux(58)
it(18) =< aux(5)+aux(57)

  with precondition: [I=2,N=0,B=C,A=D,A=J,B=K,B=L,A=M,F=O,B=P,H=Q,A>=2,E>=1,G>=0,B>=A+1,A>=E,B>=G+1,A+B>=E+G+2] 

* Chain [[18,19],21]: 1*it(18)+1*it(19)+0
  Such that:aux(41) =< A+B-G
it(19) =< B-G
aux(60) =< A
aux(61) =< A-E
aux(62) =< B-E
aux(41) =< aux(60)
aux(51) =< aux(60)
aux(41) =< aux(60)
aux(51) =< aux(41)
aux(52) =< it(19)*aux(51)
aux(1) =< it(19)*aux(51)
aux(3) =< it(19)*aux(41)
aux(7) =< it(19)*aux(60)
aux(1) =< it(19)*aux(60)
aux(9) =< aux(52)
aux(5) =< aux(3)
aux(5) =< aux(7)
aux(9) =< aux(7)
it(18) =< aux(7)+aux(61)
it(18) =< aux(3)+aux(62)
it(18) =< aux(1)+aux(61)
it(18) =< aux(5)+aux(61)
it(18) =< aux(9)+aux(61)
it(18) =< aux(5)+aux(62)

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

* Chain [[18,19],20]: 1*it(18)+1*it(19)+0
  Such that:aux(41) =< A+C-G
it(19) =< C-G
aux(63) =< A
aux(64) =< A-E
aux(65) =< C-E
aux(66) =< D-E
aux(10) =< aux(64)
aux(10) =< aux(66)
aux(41) =< aux(63)
aux(51) =< aux(63)
aux(41) =< aux(63)
aux(51) =< aux(41)
aux(52) =< it(19)*aux(51)
aux(1) =< it(19)*aux(51)
aux(3) =< it(19)*aux(41)
aux(7) =< it(19)*aux(63)
aux(1) =< it(19)*aux(63)
aux(9) =< aux(52)
aux(5) =< aux(3)
aux(5) =< aux(7)
aux(9) =< aux(7)
it(18) =< aux(7)+aux(64)
it(18) =< aux(3)+aux(65)
it(18) =< aux(1)+aux(64)
it(18) =< aux(5)+aux(10)
it(18) =< aux(9)+aux(10)
it(18) =< aux(5)+aux(65)

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

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

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


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

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


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

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

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

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

* Chain [25]: 3*s(29)+3*s(41)+0
  Such that:aux(74) =< C
aux(75) =< C+D
aux(76) =< D
s(30) =< aux(75)
s(29) =< aux(74)
s(30) =< aux(76)
s(34) =< aux(76)
s(30) =< aux(76)
s(34) =< s(30)
s(35) =< s(29)*s(34)
s(36) =< s(29)*s(34)
s(37) =< s(29)*s(30)
s(38) =< s(29)*aux(76)
s(36) =< s(29)*aux(76)
s(39) =< s(35)
s(40) =< s(37)
s(40) =< s(38)
s(39) =< s(38)
s(41) =< s(38)+aux(76)
s(41) =< s(37)+aux(74)
s(41) =< s(36)+aux(76)
s(41) =< s(40)+aux(76)
s(41) =< s(39)+aux(76)
s(41) =< s(40)+aux(74)

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


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

* Chain [33]: 0
  with precondition: [0>=A] 

* Chain [32]: 0
  with precondition: [A>=1,C>=A+1] 

* Chain [31]: 0
  with precondition: [A>=1,A>=C] 

* Chain [30]: 3*s(72)+3*s(80)+0
  Such that:s(70) =< A
s(69) =< A+C
s(68) =< C
s(71) =< s(69)
s(72) =< s(68)
s(71) =< s(70)
s(73) =< s(70)
s(71) =< s(70)
s(73) =< s(71)
s(74) =< s(72)*s(73)
s(75) =< s(72)*s(73)
s(76) =< s(72)*s(71)
s(77) =< s(72)*s(70)
s(75) =< s(72)*s(70)
s(78) =< s(74)
s(79) =< s(76)
s(79) =< s(77)
s(78) =< s(77)
s(80) =< s(77)+s(70)
s(80) =< s(76)+s(68)
s(80) =< s(75)+s(70)
s(80) =< s(79)+s(70)
s(80) =< s(78)+s(70)
s(80) =< s(79)+s(68)

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


Closed-form bounds of start0(A,B,C,D,E,F,G,H,I): 
-------------------------------------
* Chain [34] with precondition: [A=1,C>=2] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [33] with precondition: [0>=A] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [32] with precondition: [A>=1,C>=A+1] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [31] with precondition: [A>=1,A>=C] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [30] with precondition: [A>=2,C>=A+1] 
    - Upper bound: 3*A*C+3*A+3*C 
    - Complexity: n^2 

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