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


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


WORST_CASE(?,O(n^2))  
WARNING: Excluded non-linear constraints:[X=C+R*S,Y=D+T*U,Z=E+V*W]
WARNING: Excluded non-linear constraints:[M=B+I*J,N=C+K*L]

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

#### Computed strongly connected components 
0. non_recursive  : [f1/19]
1. recursive  : [f20/8]
2. recursive  : [f31/13]
3. recursive  : [f45/17]
4. recursive  : [f60/18]
5. recursive  : [f13/37,f20_loop_cont/38,f31_loop_cont/38,f45_loop_cont/38,f60_loop_cont/38]
6. non_recursive  : [exit_location/1]
7. non_recursive  : [f13_loop_cont/20]
8. non_recursive  : [f2/19]

#### Obtained direct recursion through partial evaluation 
0. SCC is completely evaluated into other SCCs
1. SCC is partially evaluated into f20/8
2. SCC is partially evaluated into f31/13
3. SCC is partially evaluated into f45/17
4. SCC is partially evaluated into f60/18
5. SCC is partially evaluated into f13/37
6. SCC is completely evaluated into other SCCs
7. SCC is partially evaluated into f13_loop_cont/20
8. SCC is partially evaluated into f2/19

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

### Specialization of cost equations f20/8 
* CE 16 is refined into CE [30] 
* CE 15 is refined into CE [31] 
* CE 18 is refined into CE [32] 
* CE 17 is refined into CE [33] 
* CE 14 is refined into CE [34] 


### Cost equations --> "Loop" of f20/8 
* CEs [34] --> Loop 27 
* CEs [30] --> Loop 28 
* CEs [31] --> Loop 29 
* CEs [32] --> Loop 30 
* CEs [33] --> Loop 31 

### Ranking functions of CR f20(B,D,E,F,Y,Z,A1,B1) 
* RF of phase [27]: [B-F+1]

#### Partial ranking functions of CR f20(B,D,E,F,Y,Z,A1,B1) 
* Partial RF of phase [27]:
  - RF of loop [27:1]:
    B-F+1


### Specialization of cost equations f31/13 
* CE 21 is refined into CE [35] 
* CE 22 is refined into CE [36] 
* CE 20 is refined into CE [37] 
* CE 23 is refined into CE [38] 
* CE 19 is refined into CE [39] 


### Cost equations --> "Loop" of f31/13 
* CEs [39] --> Loop 32 
* CEs [35] --> Loop 33 
* CEs [36] --> Loop 34 
* CEs [37] --> Loop 35 
* CEs [38] --> Loop 36 

### Ranking functions of CR f31(A,B,C,F,G,H,I,Y,Z,A1,B1,C1,D1) 
* RF of phase [32]: [A-F+1,B-F+1,C-F]

#### Partial ranking functions of CR f31(A,B,C,F,G,H,I,Y,Z,A1,B1,C1,D1) 
* Partial RF of phase [32]:
  - RF of loop [32:1]:
    A-F+1
    B-F+1
    C-F


### Specialization of cost equations f45/17 
* CE 25 is refined into CE [40] 
* CE 26 is refined into CE [41] 
* CE 24 is refined into CE [42] 


### Cost equations --> "Loop" of f45/17 
* CEs [42] --> Loop 37 
* CEs [40] --> Loop 38 
* CEs [41] --> Loop 39 

### Ranking functions of CR f45(B,F,G,H,I,J,K,Q,R,Y,Z,A1,B1,C1,D1,E1,F1) 
* RF of phase [37]: [B-F+1]

#### Partial ranking functions of CR f45(B,F,G,H,I,J,K,Q,R,Y,Z,A1,B1,C1,D1,E1,F1) 
* Partial RF of phase [37]:
  - RF of loop [37:1]:
    B-F+1


### Specialization of cost equations f60/18 
* CE 29 is refined into CE [43] 
* CE 28 is refined into CE [44] 
* CE 27 is refined into CE [45] 


### Cost equations --> "Loop" of f60/18 
* CEs [45] --> Loop 40 
* CEs [43] --> Loop 41 
* CEs [44] --> Loop 42 

### Ranking functions of CR f60(B,F,J,K,L,M,N,O,P,Y,Z,A1,B1,C1,D1,E1,F1,G1) 
* RF of phase [40]: [-F+J+1]

#### Partial ranking functions of CR f60(B,F,J,K,L,M,N,O,P,Y,Z,A1,B1,C1,D1,E1,F1,G1) 
* Partial RF of phase [40]:
  - RF of loop [40:1]:
    -F+J+1


### Specialization of cost equations f13/37 
* CE 8 is refined into CE [46,47,48,49,50,51] 
* CE 10 is refined into CE [52] 
* CE 4 is refined into CE [53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70] 
* CE 6 is refined into CE [71,72,73,74,75,76,77,78,79,80,81,82] 
* CE 7 is refined into CE [83,84,85,86,87,88,89,90,91] 
* CE 9 is refined into CE [92,93] 
* CE 11 is refined into CE [94] 
* CE 5 is refined into CE [95,96,97,98,99,100] 


### Cost equations --> "Loop" of f13/37 
* CEs [100] --> Loop 43 
* CEs [98] --> Loop 44 
* CEs [99] --> Loop 45 
* CEs [97] --> Loop 46 
* CEs [96] --> Loop 47 
* CEs [95] --> Loop 48 
* CEs [52] --> Loop 49 
* CEs [51] --> Loop 50 
* CEs [50] --> Loop 51 
* CEs [49] --> Loop 52 
* CEs [48] --> Loop 53 
* CEs [47] --> Loop 54 
* CEs [46] --> Loop 55 
* CEs [92] --> Loop 56 
* CEs [57,58,65,66,69,70,73,74,77,78,81,82] --> Loop 57 
* CEs [84,85,88,89,90,91,93] --> Loop 58 
* CEs [54,60,62] --> Loop 59 
* CEs [83,86,87] --> Loop 60 
* CEs [55,56,63,64,67,68,71,72,75,76,79,80] --> Loop 61 
* CEs [53,59,61] --> Loop 62 
* CEs [94] --> Loop 63 

### Ranking functions of CR f13(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1,O1,P1,Q1) 
* RF of phase [43,44,47]: [A-B-1]

#### Partial ranking functions of CR f13(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1,O1,P1,Q1) 
* Partial RF of phase [43,44,47]:
  - RF of loop [43:1,44:1,47:1]:
    A-B-1


### Specialization of cost equations f13_loop_cont/20 
* CE 12 is refined into CE [101] 
* CE 13 is refined into CE [102] 


### Cost equations --> "Loop" of f13_loop_cont/20 
* CEs [101] --> Loop 64 
* CEs [102] --> Loop 65 

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

#### Partial ranking functions of CR f13_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T) 


### Specialization of cost equations f2/19 
* CE 3 is refined into CE [103,104,105,106,107,108,109,110,111,112] 
* CE 2 is refined into CE [113,114] 
* CE 1 is refined into CE [115] 


### Cost equations --> "Loop" of f2/19 
* CEs [106] --> Loop 66 
* CEs [105,108,111,112] --> Loop 67 
* CEs [103,104] --> Loop 68 
* CEs [113,114] --> Loop 69 
* CEs [107,109,110] --> Loop 70 
* CEs [115] --> Loop 71 

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

#### Partial ranking functions of CR f2(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,Y) 


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

#### Cost of chains of f20(B,D,E,F,Y,Z,A1,B1):
* Chain [[27],31]: 1*it(27)+0
  Such that:it(27) =< B-F+1

  with precondition: [Y=7,A1=0,B1=1,F>=1,B>=F] 

* Chain [[27],30]: 1*it(27)+0
  Such that:it(27) =< B-F+1

  with precondition: [Y=3,F>=1,B>=F] 

* Chain [[27],29]: 1*it(27)+0
  Such that:it(27) =< B-F+1

  with precondition: [Y=7,B1=1,0>=A1+1,F>=1,B>=F] 

* Chain [[27],28]: 1*it(27)+0
  Such that:it(27) =< B-F+1

  with precondition: [Y=7,B1=1,F>=1,A1>=1,B>=F] 

* Chain [31]: 0
  with precondition: [E=0,Y=7,A1=0,B1=1,Z=D,F>=1,F>=B+1] 

* Chain [30]: 0
  with precondition: [Y=3,F>=1] 

* Chain [29]: 0
  with precondition: [Y=7,B1=1,Z=D,E=A1,0>=E+1,F>=1,F>=B+1] 

* Chain [28]: 0
  with precondition: [Y=7,B1=1,Z=D,E=A1,E>=1,F>=1,F>=B+1] 


#### Cost of chains of f31(A,B,C,F,G,H,I,Y,Z,A1,B1,C1,D1):
* Chain [[32],36]: 1*it(32)+0
  Such that:it(32) =< C-F

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

* Chain [[32],35]: 1*it(32)+0
  Such that:it(32) =< A-F

  with precondition: [Y=5,A=B+1,A=C,A=Z,A=A1,G=B1,H=C1,I=D1,A>=F+1] 

* Chain [[32],34]: 1*it(32)+0
  Such that:it(32) =< A-F+1

  with precondition: [Y=6,A1=1,A=B,A+1=C,A+1=Z,A>=F] 

* Chain [[32],33]: 1*it(32)+0
  Such that:it(32) =< -F+Z

  with precondition: [Y=6,A1=1,B+1=C,B+1=Z,A>=B+2,B>=F] 

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

* Chain [35]: 0
  with precondition: [Y=5,B+1=A,B+1=C,B1=G,C1=H,D1=I,B+1=Z,F=A1,F>=B+1] 

* Chain [34]: 0
  with precondition: [Y=6,A1=1,B=A,B+1=C,B+1=Z,F>=B+1] 

* Chain [33]: 0
  with precondition: [Y=6,A1=1,B+1=C,B+1=Z,A>=B+2,F>=B+1] 


#### Cost of chains of f45(B,F,G,H,I,J,K,Q,R,Y,Z,A1,B1,C1,D1,E1,F1):
* Chain [[37],39]: 1*it(37)+0
  Such that:it(37) =< B-F+1

  with precondition: [Y=3,B>=F] 

* Chain [[37],38]: 1*it(37)+0
  Such that:it(37) =< B-F+1

  with precondition: [Y=4,Z=1,B+1>=2*D1,3*D1>=B+2,B>=F] 

* Chain [39]: 0
  with precondition: [Y=3] 

* Chain [38]: 0
  with precondition: [Y=4,Z=1,A1=G,B1=H,C1=I,B+1>=2*D1,F>=B+1,3*D1>=B+2] 


#### Cost of chains of f60(B,F,J,K,L,M,N,O,P,Y,Z,A1,B1,C1,D1,E1,F1,G1):
* Chain [[40],42]: 1*it(40)+0
  Such that:it(40) =< -F+A1

  with precondition: [Y=2,B+1=Z,J+1=A1,F+K=J+B1+1,F+K=J+G1,J>=F,B>=K] 

* Chain [[40],41]: 1*it(40)+0
  Such that:it(40) =< -F+J+1

  with precondition: [Y=3,J>=F,B>=K] 

* Chain [42]: 0
  with precondition: [Y=2,C1=L,D1=M,E1=N,F1=O,G1=P,B+1=Z,F=A1,K=B1,F>=J+1,B>=K] 

* Chain [41]: 0
  with precondition: [Y=3,B>=K] 


#### Cost of chains of f13(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1,O1,P1,Q1):
* Chain [[43,44,47],63]: 3*it(43)+3*s(22)+3*s(23)+6*s(25)+0
  Such that:aux(4) =< A
aux(12) =< A-B
it(43) =< aux(12)
aux(5) =< aux(4)*(1/2)+1
aux(6) =< aux(4)
s(24) =< it(43)*aux(4)
s(23) =< it(43)*aux(5)
s(27) =< it(43)*aux(6)
s(25) =< s(27)
s(22) =< s(24)

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

* Chain [[43,44,47],58]: 3*it(43)+3*s(22)+3*s(23)+6*s(25)+10*s(31)+0
  Such that:aux(17) =< A
aux(18) =< A-B
s(31) =< aux(17)
it(43) =< aux(18)
aux(5) =< aux(17)*(1/2)+1
aux(6) =< aux(17)
s(24) =< it(43)*aux(17)
s(23) =< it(43)*aux(5)
s(27) =< it(43)*aux(6)
s(25) =< s(27)
s(22) =< s(24)

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

* Chain [[43,44,47],57]: 3*it(43)+3*s(22)+3*s(23)+6*s(25)+33*s(41)+3*s(59)+0
  Such that:aux(32) =< A/2
aux(33) =< A
aux(34) =< A-B
s(59) =< aux(32)
s(41) =< aux(33)
it(43) =< aux(34)
aux(5) =< aux(33)*(1/2)+1
aux(6) =< aux(33)
s(24) =< it(43)*aux(33)
s(23) =< it(43)*aux(5)
s(27) =< it(43)*aux(6)
s(25) =< s(27)
s(22) =< s(24)

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

* Chain [[43,44,47],56]: 3*it(43)+3*s(22)+3*s(23)+6*s(25)+0
  Such that:aux(4) =< A
aux(35) =< A-B
it(43) =< aux(35)
aux(5) =< aux(4)*(1/2)+1
aux(6) =< aux(4)
s(24) =< it(43)*aux(4)
s(23) =< it(43)*aux(5)
s(27) =< it(43)*aux(6)
s(25) =< s(27)
s(22) =< s(24)

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

* Chain [[43,44,47],54]: 3*it(43)+3*s(22)+3*s(23)+6*s(25)+2*s(77)+0
  Such that:aux(37) =< -B+Z
aux(38) =< Z
s(77) =< aux(38)
it(43) =< aux(37)
aux(5) =< aux(38)*(1/2)+1
aux(6) =< aux(38)
s(24) =< it(43)*aux(38)
s(23) =< it(43)*aux(5)
s(27) =< it(43)*aux(6)
s(25) =< s(27)
s(22) =< s(24)

  with precondition: [Y=5,D1=0,A=Z,A=A1+1,A=B1,A=E1,A=I1+J1+2,A=I1+O1+1,B>=1,A>=2*I1+1,3*I1>=A,A>=B+2] 

* Chain [[43,44,47],51]: 3*it(43)+3*s(22)+3*s(23)+6*s(25)+2*s(79)+0
  Such that:aux(40) =< -B+Z
aux(41) =< Z
s(79) =< aux(41)
it(43) =< aux(40)
aux(5) =< aux(41)*(1/2)+1
aux(6) =< aux(41)
s(24) =< it(43)*aux(41)
s(23) =< it(43)*aux(5)
s(27) =< it(43)*aux(6)
s(25) =< s(27)
s(22) =< s(24)

  with precondition: [Y=5,A=Z,A=A1+1,A=B1,A=E1,A=I1+J1+2,A=I1+O1+1,0>=D1+1,B>=1,A>=2*I1+1,3*I1>=A,A>=B+2] 

* Chain [[43,44,47],50]: 3*it(43)+3*s(22)+3*s(23)+6*s(25)+2*s(81)+0
  Such that:aux(43) =< -B+Z
aux(44) =< Z
s(81) =< aux(44)
it(43) =< aux(43)
aux(5) =< aux(44)*(1/2)+1
aux(6) =< aux(44)
s(24) =< it(43)*aux(44)
s(23) =< it(43)*aux(5)
s(27) =< it(43)*aux(6)
s(25) =< s(27)
s(22) =< s(24)

  with precondition: [Y=5,A=Z,A=A1+1,A=B1,A=E1,A=I1+J1+2,A=I1+O1+1,B>=1,D1>=1,A>=2*I1+1,3*I1>=A,A>=B+2] 

* Chain [63]: 0
  with precondition: [Y=3,B>=1] 

* Chain [61]: 36
  with precondition: [A=1,B=1,Y=3] 

* Chain [58]: 10*s(31)+0
  Such that:aux(16) =< B
s(31) =< aux(16)

  with precondition: [Y=3,B>=1,A>=B] 

* Chain [57]: 33*s(41)+3*s(59)+0
  Such that:aux(31) =< B
aux(32) =< B/2+1/2
s(59) =< aux(32)
s(41) =< aux(31)

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

* Chain [56]: 0
  with precondition: [Y=3,B>=1,A>=B] 

* Chain [54]: 2*s(77)+0
  Such that:aux(36) =< B
s(77) =< aux(36)

  with precondition: [Y=5,D1=0,B+1=A,F1=G,G1=H,H1=I,I1=J,J1=K,K1=L,L1=M,M1=N,N1=O,O1=P,P1=Q,Q1=R,B+1=Z,B=A1,B+1=B1,B+1=E1,B>=1] 

* Chain [51]: 2*s(79)+0
  Such that:aux(39) =< B
s(79) =< aux(39)

  with precondition: [Y=5,B+1=A,F1=G,G1=H,H1=I,I1=J,J1=K,K1=L,L1=M,M1=N,N1=O,O1=P,P1=Q,Q1=R,B+1=Z,B=A1,B+1=B1,B+1=E1,0>=D1+1,B>=1] 

* Chain [50]: 2*s(81)+0
  Such that:aux(42) =< B
s(81) =< aux(42)

  with precondition: [Y=5,B+1=A,F1=G,G1=H,H1=I,I1=J,J1=K,K1=L,L1=M,M1=N,N1=O,O1=P,P1=Q,Q1=R,B+1=Z,B=A1,B+1=B1,B+1=E1,B>=1,D1>=1] 

* Chain [49]: 0
  with precondition: [Y=5,B1=C,C1=D,D1=E,E1=F,F1=G,G1=H,H1=I,I1=J,J1=K,K1=L,L1=M,M1=N,N1=O,O1=P,P1=Q,Q1=R,A=Z,B=A1,2>=B,B>=1,B>=A+1] 

* Chain [48,63]: 4*s(119)+1
  Such that:aux(58) =< 1
s(119) =< aux(58)

  with precondition: [A=1,B=1,Y=3] 

* Chain [48,49]: 4*s(119)+1
  Such that:aux(58) =< 1
s(119) =< aux(58)

  with precondition: [A=1,B=1,Y=5,Z=1,A1=2,B1=2,D1=0,E1=2,I1=1,J1=0,O1=1] 

* Chain [46,63]: 4*s(123)+1
  Such that:aux(59) =< 1
s(123) =< aux(59)

  with precondition: [A=1,B=1,Y=3] 

* Chain [46,49]: 4*s(123)+1
  Such that:aux(59) =< 1
s(123) =< aux(59)

  with precondition: [A=1,B=1,Y=5,Z=1,A1=2,B1=2,E1=2,I1=1,J1=0,O1=1,0>=D1+1] 

* Chain [45,63]: 4*s(127)+1
  Such that:aux(60) =< 1
s(127) =< aux(60)

  with precondition: [A=1,B=1,Y=3] 

* Chain [45,49]: 4*s(127)+1
  Such that:aux(60) =< 1
s(127) =< aux(60)

  with precondition: [A=1,B=1,Y=5,Z=1,A1=2,B1=2,E1=2,I1=1,J1=0,O1=1,D1>=1] 


#### Cost of chains of f13_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T):
* Chain [65]: 0
  with precondition: [A=3] 

* Chain [64]: 0
  with precondition: [A=5] 


#### Cost of chains of f2(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,Y):
* Chain [71]: 0
  with precondition: [A=1] 

* Chain [70]: 6
  with precondition: [A=2] 

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

* Chain [68]: 10
  with precondition: [A>=2] 

* Chain [67]: 34*s(186)+18*s(190)+36*s(192)+18*s(193)+36*s(195)+0
  Such that:aux(65) =< 1
aux(70) =< A
s(186) =< aux(70)
s(187) =< aux(70)*(1/2)+1
s(188) =< aux(70)
s(189) =< s(186)*aux(70)
s(190) =< s(186)*s(187)
s(191) =< s(186)*s(188)
s(192) =< s(191)
s(193) =< s(189)
s(195) =< aux(65)

  with precondition: [A>=3] 

* Chain [66]: 3*s(233)+36*s(234)+3*s(239)+6*s(241)+3*s(242)+0
  Such that:s(230) =< A/2
aux(71) =< A
s(233) =< s(230)
s(234) =< aux(71)
s(236) =< aux(71)*(1/2)+1
s(237) =< aux(71)
s(238) =< s(234)*aux(71)
s(239) =< s(234)*s(236)
s(240) =< s(234)*s(237)
s(241) =< s(240)
s(242) =< s(238)

  with precondition: [A>=4] 


Closed-form bounds of f2(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,Y): 
-------------------------------------
* Chain [71] with precondition: [A=1] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [70] with precondition: [A=2] 
    - Upper bound: 6 
    - Complexity: constant 
* Chain [69] with precondition: [0>=A] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [68] with precondition: [A>=2] 
    - Upper bound: 10 
    - Complexity: constant 
* Chain [67] with precondition: [A>=3] 
    - Upper bound: 52*A+36+63*A*A 
    - Complexity: n^2 
* Chain [66] with precondition: [A>=4] 
    - Upper bound: 21/2*A*A+39*A+3/2*A 
    - Complexity: n^2 

### Maximum cost of f2(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,Y): max([10,21/2*nat(A)*nat(A)+nat(A)*39+max([nat(A/2)*3,nat(A)*13+36+105/2*nat(A)*nat(A)])]) 
Asymptotic class: n^2 
* Total analysis performed in 3864 ms.