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


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


WORST_CASE(NON_POLY, ?)
proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).

(0) CpxIntTrs
(1) Loat Proof [FINISHED, 530 ms]
(2) BOUNDS(INF, INF)


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
evalEx2start(A, B, C, D) -> Com_1(evalEx2entryin(A, B, C, D)) :|: TRUE
evalEx2entryin(A, B, C, D) -> Com_1(evalEx2bb3in(B, A, C, D)) :|: TRUE
evalEx2bb3in(A, B, C, D) -> Com_1(evalEx2bbin(A, B, C, D)) :|: B >= 1 && A >= 1
evalEx2bb3in(A, B, C, D) -> Com_1(evalEx2returnin(A, B, C, D)) :|: 0 >= B
evalEx2bb3in(A, B, C, D) -> Com_1(evalEx2returnin(A, B, C, D)) :|: 0 >= A
evalEx2bbin(A, B, C, D) -> Com_1(evalEx2bb2in(A, B, A - 1, B - 1)) :|: TRUE
evalEx2bb2in(A, B, C, D) -> Com_1(evalEx2bb1in(A, B, C, D)) :|: 0 >= E + 1
evalEx2bb2in(A, B, C, D) -> Com_1(evalEx2bb1in(A, B, C, D)) :|: E >= 1
evalEx2bb2in(A, B, C, D) -> Com_1(evalEx2bb3in(C, D, C, D)) :|: TRUE
evalEx2bb1in(A, B, C, D) -> Com_1(evalEx2bb2in(A, B, C + 1, D - 1)) :|: TRUE
evalEx2returnin(A, B, C, D) -> Com_1(evalEx2stop(A, B, C, D)) :|: TRUE

The start-symbols are:[evalEx2start_4]


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

(1) Loat Proof (FINISHED)


### Pre-processing the ITS problem ###



Initial linear ITS problem

   Start location: evalEx2start

      0: evalEx2start -> evalEx2entryin : [], cost: 1

      1: evalEx2entryin -> evalEx2bb3in : A'=B, B'=A, [], cost: 1

      2: evalEx2bb3in -> evalEx2bbin : [ B>=1 && A>=1 ], cost: 1

      3: evalEx2bb3in -> evalEx2returnin : [ 0>=B ], cost: 1

      4: evalEx2bb3in -> evalEx2returnin : [ 0>=A ], cost: 1

      5: evalEx2bbin -> evalEx2bb2in : C'=-1+A, D'=-1+B, [], cost: 1

      6: evalEx2bb2in -> evalEx2bb1in : [ 0>=1+free ], cost: 1

      7: evalEx2bb2in -> evalEx2bb1in : [ free_1>=1 ], cost: 1

      8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1

      9: evalEx2bb1in -> evalEx2bb2in : C'=1+C, D'=-1+D, [], cost: 1

     10: evalEx2returnin -> evalEx2stop : [], cost: 1



Checking for constant complexity:

   The following rule is satisfiable with cost >= 1, yielding constant complexity:

      0: evalEx2start -> evalEx2entryin : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalEx2start

      0: evalEx2start -> evalEx2entryin : [], cost: 1

      1: evalEx2entryin -> evalEx2bb3in : A'=B, B'=A, [], cost: 1

      2: evalEx2bb3in -> evalEx2bbin : [ B>=1 && A>=1 ], cost: 1

      5: evalEx2bbin -> evalEx2bb2in : C'=-1+A, D'=-1+B, [], cost: 1

      6: evalEx2bb2in -> evalEx2bb1in : [ 0>=1+free ], cost: 1

      7: evalEx2bb2in -> evalEx2bb1in : [ free_1>=1 ], cost: 1

      8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1

      9: evalEx2bb1in -> evalEx2bb2in : C'=1+C, D'=-1+D, [], cost: 1



Simplified all rules, resulting in:

   Start location: evalEx2start

      0: evalEx2start -> evalEx2entryin : [], cost: 1

      1: evalEx2entryin -> evalEx2bb3in : A'=B, B'=A, [], cost: 1

      2: evalEx2bb3in -> evalEx2bbin : [ B>=1 && A>=1 ], cost: 1

      5: evalEx2bbin -> evalEx2bb2in : C'=-1+A, D'=-1+B, [], cost: 1

      7: evalEx2bb2in -> evalEx2bb1in : [], cost: 1

      8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1

      9: evalEx2bb1in -> evalEx2bb2in : C'=1+C, D'=-1+D, [], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalEx2start

     11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2

     12: evalEx2bb3in -> evalEx2bb2in : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: 2

      8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1

     13: evalEx2bb2in -> evalEx2bb2in : C'=1+C, D'=-1+D, [], cost: 2



Accelerating simple loops of location 4.

   Accelerating the following rules:

     13: evalEx2bb2in -> evalEx2bb2in : C'=1+C, D'=-1+D, [], cost: 2



   Accelerated rule 13 with NONTERM, yielding the new rule 14.

   Removing the simple loops: 13.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalEx2start

     11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2

     12: evalEx2bb3in -> evalEx2bb2in : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: 2

      8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1

     14: evalEx2bb2in -> [8] : [], cost: NONTERM



Chained accelerated rules (with incoming rules):

   Start location: evalEx2start

     11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2

     12: evalEx2bb3in -> evalEx2bb2in : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: 2

     15: evalEx2bb3in -> [8] : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: NONTERM

      8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1



Eliminated locations (on linear paths):

   Start location: evalEx2start

     11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2

     15: evalEx2bb3in -> [8] : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: NONTERM

     16: evalEx2bb3in -> evalEx2bb3in : A'=-1+A, B'=-1+B, C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: 3



Accelerating simple loops of location 2.

   Accelerating the following rules:

     16: evalEx2bb3in -> evalEx2bb3in : A'=-1+A, B'=-1+B, C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: 3



   Accelerated rule 16 with metering function B (after adding A>=B), yielding the new rule 17.

   Accelerated rule 16 with metering function A (after adding A<=B), yielding the new rule 18.

   Removing the simple loops: 16.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalEx2start

     11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2

     15: evalEx2bb3in -> [8] : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: NONTERM

     17: evalEx2bb3in -> evalEx2bb3in : A'=A-B, B'=0, C'=A-B, D'=0, [ B>=1 && A>=1 && A>=B ], cost: 3*B

     18: evalEx2bb3in -> evalEx2bb3in : A'=0, B'=-A+B, C'=0, D'=-A+B, [ B>=1 && A>=1 && A<=B ], cost: 3*A



Chained accelerated rules (with incoming rules):

   Start location: evalEx2start

     11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2

     19: evalEx2start -> evalEx2bb3in : A'=-A+B, B'=0, C'=-A+B, D'=0, [ A>=1 && B>=1 && B>=A ], cost: 2+3*A

     20: evalEx2start -> evalEx2bb3in : A'=0, B'=A-B, C'=0, D'=A-B, [ A>=1 && B>=1 && B<=A ], cost: 2+3*B

     15: evalEx2bb3in -> [8] : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: NONTERM



Eliminated locations (on tree-shaped paths):

   Start location: evalEx2start

     21: evalEx2start -> [8] : A'=B, B'=A, C'=-1+B, D'=-1+A, [ A>=1 && B>=1 ], cost: NONTERM

     22: evalEx2start -> [10] : [ A>=1 && B>=1 && B>=A ], cost: 2+3*A

     23: evalEx2start -> [10] : [ A>=1 && B>=1 && B<=A ], cost: 2+3*B



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalEx2start

     21: evalEx2start -> [8] : A'=B, B'=A, C'=-1+B, D'=-1+A, [ A>=1 && B>=1 ], cost: NONTERM

     22: evalEx2start -> [10] : [ A>=1 && B>=1 && B>=A ], cost: 2+3*A

     23: evalEx2start -> [10] : [ A>=1 && B>=1 && B<=A ], cost: 2+3*B



Computing asymptotic complexity for rule 21

   Guard is satisfiable, yielding nontermination

   Resulting cost NONTERM has complexity: Nonterm



Found new complexity Nonterm.



Obtained the following overall complexity (w.r.t. the length of the input n):

   Complexity:  Nonterm

   Cpx degree:  Nonterm

   Solved cost: NONTERM

   Rule cost:   NONTERM

   Rule guard:  [ A>=1 && B>=1 ]



NO


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

(2)
BOUNDS(INF, INF)