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


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


WORST_CASE(?,O(n^1))  

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

#### Computed strongly connected components 
0. recursive  : [f3/25,f4/25]
1. non_recursive  : [exit_location/1]
2. non_recursive  : [f8/13]
3. non_recursive  : [f3_loop_cont/14]
4. non_recursive  : [f0/13]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into f4/25
1. SCC is completely evaluated into other SCCs
2. SCC is completely evaluated into other SCCs
3. SCC is partially evaluated into f3_loop_cont/14
4. SCC is partially evaluated into f0/13

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

### Specialization of cost equations f4/25 
* CE 24 is refined into CE [25] 
* CE 22 is refined into CE [26] 
* CE 23 is refined into CE [27] 
* CE 18 is refined into CE [28] 
* CE 19 is refined into CE [29] 
* CE 20 is refined into CE [30] 
* CE 21 is refined into CE [31] 


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

### Ranking functions of CR f4(A,B,C,D,E,F,G,H,I,J,K,L,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1) 
* RF of phase [27]: [A-B-1]
* RF of phase [29]: [-A+B-1]

#### Partial ranking functions of CR f4(A,B,C,D,E,F,G,H,I,J,K,L,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1) 
* Partial RF of phase [27]:
  - RF of loop [27:1]:
    A-B-1
* Partial RF of phase [29]:
  - RF of loop [29:1]:
    -A+B-1


### Specialization of cost equations f3_loop_cont/14 
* CE 17 is refined into CE [32] 
* CE 16 is refined into CE [33] 


### Cost equations --> "Loop" of f3_loop_cont/14 
* CEs [32] --> Loop 30 
* CEs [33] --> Loop 31 

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

#### Partial ranking functions of CR f3_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N) 


### Specialization of cost equations f0/13 
* CE 8 is refined into CE [34,35,36,37] 
* CE 12 is refined into CE [38,39,40,41] 
* CE 10 is refined into CE [42,43,44,45] 
* CE 13 is refined into CE [46,47,48,49] 
* CE 11 is refined into CE [50,51,52,53] 
* CE 7 is refined into CE [54,55,56,57] 
* CE 9 is refined into CE [58,59,60,61] 
* CE 6 is refined into CE [62,63,64,65] 
* CE 4 is refined into CE [66] 
* CE 2 is refined into CE [67] 
* CE 5 is refined into CE [68] 
* CE 3 is refined into CE [69] 
* CE 1 is refined into CE [70] 
* CE 14 is refined into CE [71,72,73,74,75,76,77,78,79,80] 
* CE 15 is refined into CE [81] 


### Cost equations --> "Loop" of f0/13 
* CEs [35,37] --> Loop 32 
* CEs [36] --> Loop 33 
* CEs [39,41] --> Loop 34 
* CEs [40] --> Loop 35 
* CEs [43,45] --> Loop 36 
* CEs [44,47,49,74,80] --> Loop 37 
* CEs [48,51,53] --> Loop 38 
* CEs [52,79] --> Loop 39 
* CEs [55,57] --> Loop 40 
* CEs [56,59,61,75,78] --> Loop 41 
* CEs [60,63,65,77] --> Loop 42 
* CEs [64] --> Loop 43 
* CEs [34] --> Loop 44 
* CEs [66] --> Loop 45 
* CEs [38] --> Loop 46 
* CEs [42] --> Loop 47 
* CEs [46,67,73] --> Loop 48 
* CEs [50,62,68,72,76] --> Loop 49 
* CEs [58,69,71] --> Loop 50 
* CEs [54] --> Loop 51 
* CEs [70,81] --> Loop 52 

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

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


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

#### Cost of chains of f4(A,B,C,D,E,F,G,H,I,J,K,L,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1):
* Chain [[29],26]: 1*it(29)+1
  Such that:it(29) =< -A+X

  with precondition: [Q=2,D=T,F=V,B=X,B=Y,U=Z,W=A1,R=B1,S=C1,B>=A+2] 

* Chain [[29],24]: 1*it(29)+1
  Such that:it(29) =< -A+B

  with precondition: [Q=3,B>=A+2] 

* Chain [[27],25]: 1*it(27)+1
  Such that:it(27) =< A-B

  with precondition: [Q=2,D=T,F=V,A=X,A=Y,U=Z,W=A1,R=B1,S=C1,A>=B+2] 

* Chain [[27],23]: 1*it(27)+1
  Such that:it(27) =< A-B

  with precondition: [Q=3,A>=B+2] 

* Chain [28,26]: 2
  with precondition: [Q=2,X=A+1,X=B+1,D=T,F=V,X=Y,U=Z,W=A1,R=B1,S=C1] 

* Chain [28,24]: 2
  with precondition: [Q=3,A=B] 

* Chain [26]: 1
  with precondition: [Q=2,B=A+1,T=D,V=F,B1=R,C1=S,Z=U,A1=W,B=X,B=Y] 

* Chain [25]: 1
  with precondition: [Q=2,A=B+1,T=D,V=F,B1=R,C1=S,Z=U,A1=W,A=X,A=Y] 

* Chain [24]: 1
  with precondition: [Q=3,B>=A+1] 

* Chain [23]: 1
  with precondition: [Q=3,A>=B] 


#### Cost of chains of f3_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N):
* Chain [31]: 0
  with precondition: [A=2] 

* Chain [30]: 0
  with precondition: [A=3] 


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

* Chain [51]: 1
  with precondition: [B=A+2] 

* Chain [50]: 1
  with precondition: [B=A+1] 

* Chain [49]: 2
  with precondition: [B=A] 

* Chain [48]: 1
  with precondition: [B+1=A] 

* Chain [47]: 1
  with precondition: [B+2=A] 

* Chain [46]: 1
  with precondition: [F=D+1] 

* Chain [45]: 0
  with precondition: [F=D] 

* Chain [44]: 1
  with precondition: [F+1=D] 

* Chain [43]: 1
  with precondition: [B>=A] 

* Chain [42]: 2*s(1)+1
  Such that:aux(1) =< -A+B+1
s(1) =< aux(1)

  with precondition: [B>=A+1] 

* Chain [41]: 4*s(3)+1
  Such that:aux(2) =< -A+B
s(3) =< aux(2)

  with precondition: [B>=A+2] 

* Chain [40]: 2*s(7)+1
  Such that:aux(3) =< -A+B
s(7) =< aux(3)

  with precondition: [B>=A+3] 

* Chain [39]: 1
  with precondition: [A>=B] 

* Chain [38]: 2*s(9)+1
  Such that:aux(4) =< A-B+1
s(9) =< aux(4)

  with precondition: [A>=B+1] 

* Chain [37]: 4*s(11)+1
  Such that:aux(5) =< A-B
s(11) =< aux(5)

  with precondition: [A>=B+2] 

* Chain [36]: 2*s(15)+1
  Such that:aux(6) =< A-B
s(15) =< aux(6)

  with precondition: [A>=B+3] 

* Chain [35]: 1
  with precondition: [F>=D+1] 

* Chain [34]: 2*s(17)+1
  Such that:aux(7) =< -D+F
s(17) =< aux(7)

  with precondition: [F>=D+2] 

* Chain [33]: 1
  with precondition: [D>=F+1] 

* Chain [32]: 2*s(19)+1
  Such that:aux(8) =< D-F
s(19) =< aux(8)

  with precondition: [D>=F+2] 


Closed-form bounds of f0(A,B,C,D,E,F,G,H,I,J,K,L,Q): 
-------------------------------------
* Chain [52] with precondition: [] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [51] with precondition: [B=A+2] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [50] with precondition: [B=A+1] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [49] with precondition: [B=A] 
    - Upper bound: 2 
    - Complexity: constant 
* Chain [48] with precondition: [B+1=A] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [47] with precondition: [B+2=A] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [46] with precondition: [F=D+1] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [45] with precondition: [F=D] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [44] with precondition: [F+1=D] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [43] with precondition: [B>=A] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [42] with precondition: [B>=A+1] 
    - Upper bound: -2*A+2*B+3 
    - Complexity: n 
* Chain [41] with precondition: [B>=A+2] 
    - Upper bound: -4*A+4*B+1 
    - Complexity: n 
* Chain [40] with precondition: [B>=A+3] 
    - Upper bound: -2*A+2*B+1 
    - Complexity: n 
* Chain [39] with precondition: [A>=B] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [38] with precondition: [A>=B+1] 
    - Upper bound: 2*A-2*B+3 
    - Complexity: n 
* Chain [37] with precondition: [A>=B+2] 
    - Upper bound: 4*A-4*B+1 
    - Complexity: n 
* Chain [36] with precondition: [A>=B+3] 
    - Upper bound: 2*A-2*B+1 
    - Complexity: n 
* Chain [35] with precondition: [F>=D+1] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [34] with precondition: [F>=D+2] 
    - Upper bound: -2*D+2*F+1 
    - Complexity: n 
* Chain [33] with precondition: [D>=F+1] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [32] with precondition: [D>=F+2] 
    - Upper bound: 2*D-2*F+1 
    - Complexity: n 

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