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


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


MAYBE
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(1, INF).

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


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f0(A, B, C, D, E, F) -> Com_1(f8(1, 1, 0, 1, 1, F)) :|: TRUE
f8(A, B, C, D, E, F) -> Com_1(f10(A, B, C, D, E, F)) :|: 29 >= D
f10(A, B, C, D, E, F) -> Com_1(f14(A, B, C, D, G, F)) :|: D >= E + 1 && E >= 6
f10(A, B, C, D, E, F) -> Com_1(f14(A, B, C, D, E + 2, F)) :|: D >= E + 1 && 5 >= E
f14(A, B, C, D, E, F) -> Com_1(f10(A, B, C, D + 10, E, F)) :|: 12 >= E && E >= 10
f14(A, B, C, D, E, F) -> Com_1(f10(A, B, C, D + 1, E, F)) :|: E >= 13
f14(A, B, C, D, E, F) -> Com_1(f10(A, B, C, D + 1, E, F)) :|: 9 >= E
f10(A, B, C, D, E, F) -> Com_1(f8(A, B, C, D + 2, E - 10, F)) :|: E >= D
f8(A, B, C, D, E, F) -> Com_1(f28(A, B, 1, D, E, 1)) :|: D >= 30

The start-symbols are:[f0_6]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f0

      0: f0 -> f8 : A'=1, B'=1, C'=0, D'=1, E'=1, [], cost: 1

      1: f8 -> f10 : [ 29>=D ], cost: 1

      8: f8 -> f28 : C'=1, F'=1, [ D>=30 ], cost: 1

      2: f10 -> f14 : E'=free, [ D>=1+E && E>=6 ], cost: 1

      3: f10 -> f14 : E'=2+E, [ D>=1+E && 5>=E ], cost: 1

      7: f10 -> f8 : D'=2+D, E'=-10+E, [ E>=D ], cost: 1

      4: f14 -> f10 : D'=10+D, [ 12>=E && E>=10 ], cost: 1

      5: f14 -> f10 : D'=1+D, [ E>=13 ], cost: 1

      6: f14 -> f10 : D'=1+D, [ 9>=E ], cost: 1



Checking for constant complexity:

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

      0: f0 -> f8 : A'=1, B'=1, C'=0, D'=1, E'=1, [], cost: 1



Removed unreachable and leaf rules:

   Start location: f0

      0: f0 -> f8 : A'=1, B'=1, C'=0, D'=1, E'=1, [], cost: 1

      1: f8 -> f10 : [ 29>=D ], cost: 1

      2: f10 -> f14 : E'=free, [ D>=1+E && E>=6 ], cost: 1

      3: f10 -> f14 : E'=2+E, [ D>=1+E && 5>=E ], cost: 1

      7: f10 -> f8 : D'=2+D, E'=-10+E, [ E>=D ], cost: 1

      4: f14 -> f10 : D'=10+D, [ 12>=E && E>=10 ], cost: 1

      5: f14 -> f10 : D'=1+D, [ E>=13 ], cost: 1

      6: f14 -> f10 : D'=1+D, [ 9>=E ], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on tree-shaped paths):

   Start location: f0

      0: f0 -> f8 : A'=1, B'=1, C'=0, D'=1, E'=1, [], cost: 1

      1: f8 -> f10 : [ 29>=D ], cost: 1

      7: f10 -> f8 : D'=2+D, E'=-10+E, [ E>=D ], cost: 1

      9: f10 -> f10 : D'=10+D, E'=free, [ D>=1+E && E>=6 && 12>=free && free>=10 ], cost: 2

     10: f10 -> f10 : D'=1+D, E'=free, [ D>=1+E && E>=6 && free>=13 ], cost: 2

     11: f10 -> f10 : D'=1+D, E'=free, [ D>=1+E && E>=6 && 9>=free ], cost: 2

     12: f10 -> f10 : D'=1+D, E'=2+E, [ D>=1+E && 5>=E ], cost: 2



Accelerating simple loops of location 2.

   Accelerating the following rules:

      9: f10 -> f10 : D'=10+D, E'=free, [ D>=1+E && E>=6 && 12>=free && free>=10 ], cost: 2

     10: f10 -> f10 : D'=1+D, E'=free, [ D>=1+E && E>=6 && free>=13 ], cost: 2

     11: f10 -> f10 : D'=1+D, E'=free, [ D>=1+E && E>=6 && 9>=free ], cost: 2

     12: f10 -> f10 : D'=1+D, E'=2+E, [ D>=1+E && 5>=E ], cost: 2



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

      During metering: Instantiating temporary variables by {free==13}

   Accelerated rule 10 with metering function meter (where 6*meter==D-E), yielding the new rule 14.

      During metering: Instantiating temporary variables by {free==9}

   Accelerated rule 11 with metering function meter_1 (where 2*meter_1==D-E), yielding the new rule 15.

   Found no metering function for rule 12.

      During metering: Instantiating temporary variables by {meter==14-D,free==9}

      During metering: Instantiating temporary variables by {meter==1}

      During metering: Instantiating temporary variables by {free==13,meter_1==10-D}

   Nested simple loops 10 (outer loop) and 15 (inner loop) with NONTERM, resulting in the new rules: 16, 17.

      During metering: Instantiating temporary variables by {meter_1==1}

   Removing the simple loops: 9 10 11.



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

   Start location: f0

      0: f0 -> f8 : A'=1, B'=1, C'=0, D'=1, E'=1, [], cost: 1

      1: f8 -> f10 : [ 29>=D ], cost: 1

      7: f10 -> f8 : D'=2+D, E'=-10+E, [ E>=D ], cost: 1

     12: f10 -> f10 : D'=1+D, E'=2+E, [ D>=1+E && 5>=E ], cost: 2

     13: f10 -> [5] : [ D>=1+E && E>=6 && 12>=free && free>=10 ], cost: NONTERM

     14: f10 -> f10 : D'=D+meter, E'=13, [ D>=1+E && E>=6 && 6*meter==D-E && meter>=1 ], cost: 2*meter

     15: f10 -> f10 : D'=D+meter_1, E'=9, [ D>=1+E && E>=6 && 2*meter_1==D-E && meter_1>=1 ], cost: 2*meter_1

     16: f10 -> [5] : [ D>=1+E && E>=6 && 1+D-2*meter_1>=13 && 1+D>=2+D-2*meter_1 && meter_1>=1 ], cost: NONTERM

     17: f10 -> [5] : D'=D+meter_1, E'=9, [ D>=1+E && E>=6 && 2*meter_1==D-E && meter_1>=1 && D+meter_1>=10 && 1+D-meter_1>=13 && 1+D+meter_1>=2+D-meter_1 ], cost: NONTERM



Chained accelerated rules (with incoming rules):

   Start location: f0

      0: f0 -> f8 : A'=1, B'=1, C'=0, D'=1, E'=1, [], cost: 1

      1: f8 -> f10 : [ 29>=D ], cost: 1

     18: f8 -> f10 : D'=1+D, E'=2+E, [ 29>=D && D>=1+E && 5>=E ], cost: 3

     19: f8 -> [5] : [ 29>=D && D>=1+E && E>=6 ], cost: NONTERM

     20: f8 -> f10 : D'=D+meter, E'=13, [ 29>=D && D>=1+E && E>=6 && 6*meter==D-E && meter>=1 ], cost: 1+2*meter

     21: f8 -> f10 : D'=D+meter_1, E'=9, [ 29>=D && D>=1+E && E>=6 && 2*meter_1==D-E && meter_1>=1 ], cost: 1+2*meter_1

     22: f8 -> [5] : [ 29>=D && D>=1+E && E>=6 && 1+D-2*meter_1>=13 && 1+D>=2+D-2*meter_1 && meter_1>=1 ], cost: NONTERM

     23: f8 -> [5] : D'=D+meter_1, E'=9, [ 29>=D && D>=1+E && E>=6 && 2*meter_1==D-E && meter_1>=1 && D+meter_1>=10 && 1+D-meter_1>=13 && 1+D+meter_1>=2+D-meter_1 ], cost: NONTERM

      7: f10 -> f8 : D'=2+D, E'=-10+E, [ E>=D ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: f0

      0: f0 -> f8 : A'=1, B'=1, C'=0, D'=1, E'=1, [], cost: 1

     19: f8 -> [5] : [ 29>=D && D>=1+E && E>=6 ], cost: NONTERM

     22: f8 -> [5] : [ 29>=D && D>=1+E && E>=6 && 1+D-2*meter_1>=13 && 1+D>=2+D-2*meter_1 && meter_1>=1 ], cost: NONTERM

     23: f8 -> [5] : D'=D+meter_1, E'=9, [ 29>=D && D>=1+E && E>=6 && 2*meter_1==D-E && meter_1>=1 && D+meter_1>=10 && 1+D-meter_1>=13 && 1+D+meter_1>=2+D-meter_1 ], cost: NONTERM

     24: f8 -> f8 : D'=2+D, E'=-10+E, [ 29>=D && E>=D ], cost: 2

     25: f8 -> f8 : D'=3+D, E'=-8+E, [ 29>=D && D>=1+E && 5>=E && 2+E>=1+D ], cost: 4

     26: f8 -> f8 : D'=2+D+meter, E'=3, [ 29>=D && D>=1+E && E>=6 && 6*meter==D-E && meter>=1 && 13>=D+meter ], cost: 2+2*meter

     27: f8 -> f8 : D'=2+D+meter_1, E'=-1, [ 29>=D && D>=1+E && E>=6 && 2*meter_1==D-E && meter_1>=1 && 9>=D+meter_1 ], cost: 2+2*meter_1



Accelerating simple loops of location 1.

   Simplified some of the simple loops (and removed duplicate rules).

   Accelerating the following rules:

     24: f8 -> f8 : D'=2+D, E'=-10+E, [ 29>=D && E>=D ], cost: 2

     25: f8 -> f8 : D'=3+D, E'=-8+E, [ 29>=D && 1-D+E==0 && 5>=E ], cost: 4

     26: f8 -> f8 : D'=2+D+meter, E'=3, [ 29>=D && D>=1+E && E>=6 && 6*meter==D-E && meter>=1 && 13>=D+meter ], cost: 2+2*meter

     27: f8 -> f8 : D'=2+D+meter_1, E'=-1, [ 29>=D && D>=1+E && E>=6 && 2*meter_1==D-E && meter_1>=1 && 9>=D+meter_1 ], cost: 2+2*meter_1



   Accelerated rule 24 with metering function meter_6 (where 12*meter_6==-D+E) (after adding D>=E), yielding the new rule 28.

   Accelerated rule 25 with metering function meter_7 (where 11*meter_7==2-D+E), yielding the new rule 29.

   Accelerated rule 26 with metering function meter_8 (where 11*meter_8==7-D-meter+E), yielding the new rule 30.

   Accelerated rule 27 with metering function meter_9 (where 31*meter_9==3-D+E-meter_1), yielding the new rule 31.

   Removing the simple loops: 25 26 27.



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

   Start location: f0

      0: f0 -> f8 : A'=1, B'=1, C'=0, D'=1, E'=1, [], cost: 1

     19: f8 -> [5] : [ 29>=D && D>=1+E && E>=6 ], cost: NONTERM

     22: f8 -> [5] : [ 29>=D && D>=1+E && E>=6 && 1+D-2*meter_1>=13 && 1+D>=2+D-2*meter_1 && meter_1>=1 ], cost: NONTERM

     23: f8 -> [5] : D'=D+meter_1, E'=9, [ 29>=D && D>=1+E && E>=6 && 2*meter_1==D-E && meter_1>=1 && D+meter_1>=10 && 1+D-meter_1>=13 && 1+D+meter_1>=2+D-meter_1 ], cost: NONTERM

     24: f8 -> f8 : D'=2+D, E'=-10+E, [ 29>=D && E>=D ], cost: 2

     28: f8 -> f8 : D'=2*meter_6+D, E'=-10*meter_6+E, [ 29>=D && E>=D && D>=E && 12*meter_6==-D+E && meter_6>=1 ], cost: 2*meter_6

     29: f8 -> f8 : D'=3*meter_7+D, E'=-8*meter_7+E, [ 29>=D && 1-D+E==0 && 5>=E && 11*meter_7==2-D+E && meter_7>=1 ], cost: 4*meter_7

     30: f8 -> f8 : D'=D+2*meter_8+meter*meter_8, E'=3, [ 29>=D && D>=1+E && E>=6 && 6*meter==D-E && meter>=1 && 13>=D+meter && 11*meter_8==7-D-meter+E && meter_8>=1 ], cost: 2*meter_8+2*meter*meter_8

     31: f8 -> f8 : D'=2*meter_9+D+meter_9*meter_1, E'=-1, [ 29>=D && D>=1+E && E>=6 && 2*meter_1==D-E && meter_1>=1 && 9>=D+meter_1 && 31*meter_9==3-D+E-meter_1 && meter_9>=1 ], cost: 2*meter_9+2*meter_9*meter_1



Chained accelerated rules (with incoming rules):

   Start location: f0

      0: f0 -> f8 : A'=1, B'=1, C'=0, D'=1, E'=1, [], cost: 1

     32: f0 -> f8 : A'=1, B'=1, C'=0, D'=3, E'=-9, [], cost: 3

     19: f8 -> [5] : [ 29>=D && D>=1+E && E>=6 ], cost: NONTERM

     22: f8 -> [5] : [ 29>=D && D>=1+E && E>=6 && 1+D-2*meter_1>=13 && 1+D>=2+D-2*meter_1 && meter_1>=1 ], cost: NONTERM

     23: f8 -> [5] : D'=D+meter_1, E'=9, [ 29>=D && D>=1+E && E>=6 && 2*meter_1==D-E && meter_1>=1 && D+meter_1>=10 && 1+D-meter_1>=13 && 1+D+meter_1>=2+D-meter_1 ], cost: NONTERM



Eliminated locations (on tree-shaped paths):

   Start location: f0

     <empty>



Applied pruning (of leafs and parallel rules):

   Start location: f0

     <empty>



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f0

     <empty>



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

   Complexity:  Constant

   Cpx degree:  0

   Solved cost: 1

   Rule cost:   1

   Rule guard:  []



WORST_CASE(Omega(1),?)


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

(2)
BOUNDS(1, INF)