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


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


WORST_CASE(?,O(n^1))  

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

#### Computed strongly connected components 
0. recursive  : [f16/13,f25/13,f5/13,f7/13,f9/13]
1. non_recursive  : [exit_location/1]
2. non_recursive  : [f30/7]
3. non_recursive  : [f5_loop_cont/8]
4. non_recursive  : [f0/7]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into f5/13
1. SCC is completely evaluated into other SCCs
2. SCC is completely evaluated into other SCCs
3. SCC is partially evaluated into f5_loop_cont/8
4. SCC is partially evaluated into f0/7

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

### Specialization of cost equations f5/13 
* CE 81 is refined into CE [84] 
* CE 14 is refined into CE [85] 
* CE 40 is discarded (unfeasible) 
* CE 27 is discarded (unfeasible) 
* CE 53 is discarded (unfeasible) 
* CE 3 is refined into CE [86] 
* CE 4 is discarded (unfeasible) 
* CE 29 is discarded (unfeasible) 
* CE 30 is discarded (unfeasible) 
* CE 16 is discarded (unfeasible) 
* CE 17 is discarded (unfeasible) 
* CE 42 is discarded (unfeasible) 
* CE 43 is discarded (unfeasible) 
* CE 9 is discarded (unfeasible) 
* CE 10 is refined into CE [87] 
* CE 35 is discarded (unfeasible) 
* CE 36 is discarded (unfeasible) 
* CE 22 is discarded (unfeasible) 
* CE 23 is discarded (unfeasible) 
* CE 48 is discarded (unfeasible) 
* CE 49 is discarded (unfeasible) 
* CE 8 is refined into CE [88] 
* CE 34 is discarded (unfeasible) 
* CE 21 is discarded (unfeasible) 
* CE 47 is discarded (unfeasible) 
* CE 2 is refined into CE [89] 
* CE 28 is discarded (unfeasible) 
* CE 15 is discarded (unfeasible) 
* CE 41 is discarded (unfeasible) 
* CE 66 is refined into CE [90] 
* CE 79 is discarded (unfeasible) 
* CE 55 is refined into CE [91] 
* CE 56 is refined into CE [92] 
* CE 68 is discarded (unfeasible) 
* CE 69 is discarded (unfeasible) 
* CE 61 is discarded (unfeasible) 
* CE 62 is refined into CE [93] 
* CE 74 is discarded (unfeasible) 
* CE 75 is discarded (unfeasible) 
* CE 60 is refined into CE [94] 
* CE 73 is discarded (unfeasible) 
* CE 54 is refined into CE [95] 
* CE 67 is discarded (unfeasible) 
* CE 80 is refined into CE [96] 
* CE 6 is refined into CE [97] 
* CE 7 is discarded (unfeasible) 
* CE 32 is discarded (unfeasible) 
* CE 33 is discarded (unfeasible) 
* CE 19 is discarded (unfeasible) 
* CE 20 is discarded (unfeasible) 
* CE 45 is discarded (unfeasible) 
* CE 46 is discarded (unfeasible) 
* CE 12 is discarded (unfeasible) 
* CE 13 is refined into CE [98] 
* CE 38 is discarded (unfeasible) 
* CE 39 is discarded (unfeasible) 
* CE 25 is discarded (unfeasible) 
* CE 26 is discarded (unfeasible) 
* CE 51 is discarded (unfeasible) 
* CE 52 is discarded (unfeasible) 
* CE 11 is refined into CE [99] 
* CE 37 is discarded (unfeasible) 
* CE 24 is discarded (unfeasible) 
* CE 50 is discarded (unfeasible) 
* CE 5 is refined into CE [100] 
* CE 31 is discarded (unfeasible) 
* CE 18 is discarded (unfeasible) 
* CE 44 is discarded (unfeasible) 
* CE 58 is refined into CE [101] 
* CE 59 is refined into CE [102] 
* CE 71 is discarded (unfeasible) 
* CE 72 is discarded (unfeasible) 
* CE 64 is discarded (unfeasible) 
* CE 65 is refined into CE [103] 
* CE 77 is discarded (unfeasible) 
* CE 78 is discarded (unfeasible) 
* CE 63 is refined into CE [104] 
* CE 76 is discarded (unfeasible) 
* CE 57 is refined into CE [105] 
* CE 70 is discarded (unfeasible) 


### Cost equations --> "Loop" of f5/13 
* CEs [97] --> Loop 84 
* CEs [98] --> Loop 85 
* CEs [99] --> Loop 86 
* CEs [100] --> Loop 87 
* CEs [103] --> Loop 88 
* CEs [101] --> Loop 89 
* CEs [104] --> Loop 90 
* CEs [105] --> Loop 91 
* CEs [102] --> Loop 92 
* CEs [84] --> Loop 93 
* CEs [85] --> Loop 94 
* CEs [86] --> Loop 95 
* CEs [87] --> Loop 96 
* CEs [88] --> Loop 97 
* CEs [89] --> Loop 98 
* CEs [90] --> Loop 99 
* CEs [93] --> Loop 100 
* CEs [91] --> Loop 101 
* CEs [94] --> Loop 102 
* CEs [95] --> Loop 103 
* CEs [92] --> Loop 104 
* CEs [96] --> Loop 105 

### Ranking functions of CR f5(A,B,C,D,E,F,H,I,J,K,L,M,N) 
* RF of phase [84,85,86,87]: [A-1]
* RF of phase [88]: [C/4-3/4]
* RF of phase [89]: [-C/4+63]

#### Partial ranking functions of CR f5(A,B,C,D,E,F,H,I,J,K,L,M,N) 
* Partial RF of phase [84,85,86,87]:
  - RF of loop [84:1,85:1,86:1,87:1]:
    A-1
  - RF of loop [84:1,87:1]:
    -C+255 depends on loops [85:1,86:1] 
  - RF of loop [85:1,86:1]:
    C depends on loops [84:1,87:1] 
  - RF of loop [86:1]:
    E-1 depends on loops [85:1,87:1] 
  - RF of loop [87:1]:
    -E+2 depends on loops [84:1,86:1] 
* Partial RF of phase [88]:
  - RF of loop [88:1]:
    C/4-3/4
* Partial RF of phase [89]:
  - RF of loop [89:1]:
    -C/4+63


### Specialization of cost equations f5_loop_cont/8 
* CE 83 is refined into CE [106] 
* CE 82 is refined into CE [107] 


### Cost equations --> "Loop" of f5_loop_cont/8 
* CEs [106] --> Loop 106 
* CEs [107] --> Loop 107 

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

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


### Specialization of cost equations f0/7 
* CE 1 is refined into CE [108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139] 


### Cost equations --> "Loop" of f0/7 
* CEs [133] --> Loop 108 
* CEs [132] --> Loop 109 
* CEs [128] --> Loop 110 
* CEs [120] --> Loop 111 
* CEs [129,130,131,135,136,138] --> Loop 112 
* CEs [119] --> Loop 113 
* CEs [117] --> Loop 114 
* CEs [109] --> Loop 115 
* CEs [118] --> Loop 116 
* CEs [114] --> Loop 117 
* CEs [134] --> Loop 118 
* CEs [111,113,116,123,124,127] --> Loop 119 
* CEs [122] --> Loop 120 
* CEs [110,112,115,125] --> Loop 121 
* CEs [121,126] --> Loop 122 
* CEs [108] --> Loop 123 
* CEs [137,139] --> Loop 124 

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

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


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

#### Cost of chains of f5(A,B,C,D,E,F,H,I,J,K,L,M,N):
* Chain [[88],103]: 1*it(88)+0
  Such that:it(88) =< C/4-K/4+3/4

  with precondition: [A=4,B=0,H=2,I=3,J=1,M=2,F=N,1>=E,E>=0,K>=256,F>=D+1,L>=F+1,C>=K+1] 

* Chain [[88],100]: 1*it(88)+0
  Such that:it(88) =< C/4-K/4

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

* Chain [[88],99]: 1*it(88)+0
  Such that:it(88) =< C/4-K/4

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

* Chain [[88],93]: 1*it(88)+0
  Such that:it(88) =< C/4

  with precondition: [A=4,B=0,H=3,1>=E,C>=4,E>=0,F>=D+1] 

* Chain [[88],91,[84,85,86,87],105]: 4*it(84)+1*it(88)+1
  Such that:aux(19) =< 3
it(88) =< C/4
it(88) =< C/4-K/4+M/2+1/2
it(84) =< aux(19)

  with precondition: [A=4,B=0,H=2,I=1,J=1,F=N,1>=E,2>=M,C>=4,E>=0,M>=1,K+2>=2*M,F>=D+1,2*M+254>=K,C+2*M>=K+2] 

* Chain [[88],91,[84,85,86,87],95]: 4*it(84)+1*it(88)+1
  Such that:aux(14) =< 1
aux(13) =< 3
it(88) =< C/4-K/4+3/2
it(84) =< aux(13)
it(84) =< aux(14)

  with precondition: [A=4,B=0,H=2,I=1,J=1,K=256,M=2,F=N,1>=E,C>=254,E>=0,F>=D+1,L>=F+1] 

* Chain [[88],91,[84,85,86,87],94]: 4*it(84)+1*it(88)+1
  Such that:aux(14) =< 1
aux(13) =< 3
it(88) =< C/4-K/4+M
it(84) =< aux(13)
it(84) =< aux(14)

  with precondition: [A=4,B=0,H=2,I=1,J=1,F=L,F=N,1>=E,2>=M,E>=0,M>=1,K+3>=4*M,F>=D+1,4*M+249>=K,C+4*M>=K+7] 

* Chain [[88],91,[84,85,86,87],93]: 4*it(84)+1*it(88)+1
  Such that:aux(20) =< 3
it(88) =< C/4
it(84) =< aux(20)

  with precondition: [A=4,B=0,H=3,1>=E,C>=4,E>=0,F>=D+1] 

* Chain [[88],91,95]: 1*it(88)+1
  Such that:it(88) =< C/4-K/4+5/4

  with precondition: [A=4,B=0,H=2,I=2,J=1,M=2,F=N,1>=E,257>=K,E>=0,K>=256,F>=D+1,L>=F+1,C+1>=K] 

* Chain [[88],91,94]: 1*it(88)+1
  Such that:it(88) =< C/4-K/4+3/4

  with precondition: [A=4,B=0,H=2,I=2,J=1,M=2,F=L,F=N,1>=E,255>=K,E>=0,K>=3,F>=D+1,C>=K+1] 

* Chain [[88],91,93]: 1*it(88)+1
  Such that:it(88) =< C/4

  with precondition: [A=4,B=0,H=3,1>=E,C>=4,E>=0,F>=D+1] 

* Chain [104]: 0
  with precondition: [A=4,B=0,E=0,H=2,I=4,J=0,M=2,K=C+4,D=L,F=N,K>=256,D>=F+1] 

* Chain [100]: 0
  with precondition: [A=4,B=0,H=2,I=4,J=0,M=1,K+4=C,D=L,F=N,1>=E,0>=K+1,E>=0,F>=D+1] 

* Chain [99]: 0
  with precondition: [A=4,B=0,H=2,I=4,J=0,K=C,D=F,D=L,E=M,D=N,2>=E,E>=0] 

* Chain [93]: 0
  with precondition: [H=3,1>=B,B>=0,4>=A+B,E+4>=2*B+A,6>=A+B+E] 

* Chain [92,[89],102]: 1*it(89)+1
  Such that:it(89) =< -C/4+K/4

  with precondition: [A=4,B=0,E=0,H=2,I=3,J=1,M=1,F=N,0>=K+1,K>=C+5,D>=F+1,F>=L+1] 

* Chain [92,[89],101]: 1*it(89)+1
  Such that:it(89) =< -C/4+62

  with precondition: [A=4,B=0,E=0,H=2,I=4,J=0,M=2,F=N,259>=K,K>=256,K>=C+12,D>=F+1,L>=F+1] 

* Chain [92,[89],99]: 1*it(89)+1
  Such that:it(89) =< -C/4+62
it(89) =< -C/4+K/4

  with precondition: [A=4,B=0,E=0,H=2,I=4,J=0,M=2,F=L,F=N,255>=K,K>=C+8,D>=F+1] 

* Chain [92,[89],93]: 1*it(89)+1
  Such that:it(89) =< -C/4+62

  with precondition: [A=4,B=0,E=0,H=3,247>=C,D>=F+1] 

* Chain [92,[89],90,[84,85,86,87],105]: 4*it(84)+1*it(89)+2
  Such that:aux(19) =< 3
it(89) =< -C/4+62
it(89) =< -C/4+K/4-M/2+1
it(84) =< aux(19)

  with precondition: [A=4,B=0,E=0,H=2,I=1,J=1,F=N,247>=C,2>=M,M>=1,K+5>=2*M,D>=F+1,2*M+251>=K,K>=2*M+C] 

* Chain [92,[89],90,[84,85,86,87],96]: 4*it(84)+1*it(89)+2
  Such that:aux(14) =< 1
aux(13) =< 3
it(89) =< -C/4+K/4+1/2
it(84) =< aux(13)
it(84) =< aux(14)

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

* Chain [92,[89],90,[84,85,86,87],94]: 4*it(84)+1*it(89)+2
  Such that:aux(14) =< 1
aux(13) =< 3
it(89) =< -C/4+62
it(89) =< -C/4+K/4-M+5/4
it(84) =< aux(13)
it(84) =< aux(14)

  with precondition: [A=4,B=0,E=0,H=2,I=1,J=1,F=L,F=N,2>=M,M>=1,K+6>=4*M,D>=F+1,4*M+246>=K,K+1>=4*M+C] 

* Chain [92,[89],90,[84,85,86,87],93]: 4*it(84)+1*it(89)+2
  Such that:aux(20) =< 3
it(89) =< -C/4+62
it(84) =< aux(20)

  with precondition: [A=4,B=0,E=0,H=3,247>=C,D>=F+1] 

* Chain [92,[89],90,96]: 1*it(89)+2
  Such that:it(89) =< -C/4+K/4+1/4

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

* Chain [92,[89],90,94]: 1*it(89)+2
  Such that:it(89) =< -C/4+62
it(89) =< -C/4+K/4

  with precondition: [A=4,B=0,E=0,H=2,I=2,J=1,M=1,F=L,F=N,252>=K,K>=0,K>=C+5,D>=F+1] 

* Chain [92,[89],90,93]: 1*it(89)+2
  Such that:it(89) =< -C/4+62

  with precondition: [A=4,B=0,E=0,H=3,247>=C,D>=F+1] 

* Chain [92,102]: 1
  with precondition: [A=4,B=0,E=0,H=2,I=3,J=1,M=1,K=C+1,F=N,0>=K+1,D>=F+1,F>=L+1] 

* Chain [92,101]: 1
  with precondition: [A=4,B=0,E=0,H=2,I=4,J=0,M=2,K=C+8,F=N,259>=K,K>=256,D>=F+1,L>=F+1] 

* Chain [92,99]: 1
  with precondition: [A=4,B=0,E=0,H=2,I=4,J=0,M=2,K=C+4,F=L,F=N,255>=K,D>=F+1] 

* Chain [92,93]: 1
  with precondition: [A=4,B=0,E=0,H=3,251>=C,D>=F+1] 

* Chain [92,90,[84,85,86,87],105]: 4*it(84)+2
  Such that:aux(19) =< 3
it(84) =< aux(19)

  with precondition: [A=4,B=0,E=0,H=2,I=1,J=1,F=N,251>=C,2>=M,C+1>=0,M>=1,D>=F+1,K+4>=2*M+C,C+2*M>=K] 

* Chain [92,90,[84,85,86,87],96]: 4*it(84)+2
  Such that:aux(14) =< 1
aux(13) =< 3
it(84) =< aux(13)
it(84) =< aux(14)

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

* Chain [92,90,[84,85,86,87],94]: 4*it(84)+2
  Such that:aux(14) =< 1
aux(13) =< 3
it(84) =< aux(13)
it(84) =< aux(14)

  with precondition: [A=4,B=0,E=0,H=2,I=1,J=1,F=L,F=N,C+4*M=K+5,2>=M,M>=1,K+6>=4*M,D>=F+1,4*M+246>=K] 

* Chain [92,90,[84,85,86,87],93]: 4*it(84)+2
  Such that:aux(20) =< 3
it(84) =< aux(20)

  with precondition: [A=4,B=0,E=0,H=3,251>=C,C+1>=0,D>=F+1] 

* Chain [92,90,96]: 2
  with precondition: [A=4,B=0,E=0,H=2,I=2,J=1,M=1,K+1=C,F=N,0>=K+1,K+2>=0,D>=F+1,F>=L+1] 

* Chain [92,90,94]: 2
  with precondition: [A=4,B=0,E=0,H=2,I=2,J=1,M=1,K=C+1,F=L,F=N,252>=K,K>=0,D>=F+1] 

* Chain [92,90,93]: 2
  with precondition: [A=4,B=0,E=0,H=3,251>=C,C+1>=0,D>=F+1] 


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

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


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

* Chain [123]: 4*s(15)+2
  Such that:s(13) =< 1
s(14) =< 3
s(15) =< s(14)
s(15) =< s(13)

  with precondition: [C=1] 

* Chain [122]: 1
  with precondition: [251>=C] 

* Chain [121]: 38
  with precondition: [251>=C,C+1>=0] 

* Chain [120]: 1
  with precondition: [251>=C,C>=248] 

* Chain [119]: 8*s(23)+4*s(24)+8*s(27)+2
  Such that:s(21) =< 1
aux(24) =< 3
aux(25) =< -C/4+62
s(23) =< aux(25)
s(24) =< aux(24)
s(24) =< s(21)
s(27) =< aux(24)

  with precondition: [247>=C] 

* Chain [118]: 0
  with precondition: [3>=C] 

* Chain [117]: 2
  with precondition: [0>=C,C+1>=0] 

* Chain [116]: 1
  with precondition: [0>=C+2] 

* Chain [115]: 1*s(37)+4*s(38)+2
  Such that:s(35) =< 1
s(36) =< 3
s(37) =< -C/4+1/4
s(38) =< s(36)
s(38) =< s(35)

  with precondition: [0>=C+3] 

* Chain [114]: 1*s(39)+2
  Such that:s(39) =< -C/4

  with precondition: [0>=C+4] 

* Chain [113]: 1*s(40)+1
  Such that:s(40) =< -C/4

  with precondition: [0>=C+6] 

* Chain [112]: 1*s(43)+4*s(44)+6*s(46)+8*s(47)+1*s(50)+1
  Such that:s(41) =< 1
s(50) =< C/4+1
s(43) =< C/4+3/4
aux(26) =< 3
aux(27) =< C/4
s(46) =< aux(27)
s(44) =< aux(26)
s(44) =< s(41)
s(47) =< aux(26)

  with precondition: [C>=4] 

* Chain [111]: 0
  with precondition: [C>=252] 

* Chain [110]: 1*s(57)+4*s(58)+1
  Such that:s(55) =< 1
s(56) =< 3
s(57) =< C/4
s(58) =< s(56)
s(58) =< s(55)

  with precondition: [C>=254] 

* Chain [109]: 1*s(59)+1
  Such that:s(59) =< C/4

  with precondition: [C>=255] 

* Chain [108]: 1*s(60)+0
  Such that:s(60) =< C/4

  with precondition: [C>=257] 


Closed-form bounds of f0(A,B,C,D,E,F,H): 
-------------------------------------
* Chain [124] with precondition: [] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [123] with precondition: [C=1] 
    - Upper bound: 14 
    - Complexity: constant 
* Chain [122] with precondition: [251>=C] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [121] with precondition: [251>=C,C+1>=0] 
    - Upper bound: 38 
    - Complexity: constant 
* Chain [120] with precondition: [251>=C,C>=248] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [119] with precondition: [247>=C] 
    - Upper bound: -2*C+534 
    - Complexity: n 
* Chain [118] with precondition: [3>=C] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [117] with precondition: [0>=C,C+1>=0] 
    - Upper bound: 2 
    - Complexity: constant 
* Chain [116] with precondition: [0>=C+2] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [115] with precondition: [0>=C+3] 
    - Upper bound: -C/4+57/4 
    - Complexity: n 
* Chain [114] with precondition: [0>=C+4] 
    - Upper bound: -C/4+2 
    - Complexity: n 
* Chain [113] with precondition: [0>=C+6] 
    - Upper bound: -C/4+1 
    - Complexity: n 
* Chain [112] with precondition: [C>=4] 
    - Upper bound: 2*C+155/4 
    - Complexity: n 
* Chain [111] with precondition: [C>=252] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [110] with precondition: [C>=254] 
    - Upper bound: C/4+13 
    - Complexity: n 
* Chain [109] with precondition: [C>=255] 
    - Upper bound: C/4+1 
    - Complexity: n 
* Chain [108] with precondition: [C>=257] 
    - Upper bound: C/4 
    - Complexity: n 

### Maximum cost of f0(A,B,C,D,E,F,H): max([max([max([38,nat(-C/4+1/4)+14,nat(-C/4+62)*8+38]),nat(-C/4)+2]),nat(C/4)+max([13,nat(C/4+1)+37+nat(C/4+3/4)+nat(C/4)*5])]) 
Asymptotic class: n 
* Total analysis performed in 5935 ms.