329.85/289.64 MAYBE 329.85/289.66 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 329.85/289.66 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 329.85/289.66 329.85/289.66 329.85/289.66 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, INF). 329.85/289.66 329.85/289.66 (0) CpxIntTrs 329.85/289.66 (1) Loat Proof [FINISHED, 288.5 s] 329.85/289.66 (2) BOUNDS(1, INF) 329.85/289.66 329.85/289.66 329.85/289.66 ---------------------------------------- 329.85/289.66 329.85/289.66 (0) 329.85/289.66 Obligation: 329.85/289.66 Complexity Int TRS consisting of the following rules: 329.85/289.66 f0(A, B, C, D, E, F, G) -> Com_1(f1(A, B, C, D, E, F, G)) :|: A >= 0 && 3 >= A && B >= 0 && 3 >= B && 3 >= C && D >= 0 && 3 >= E && E >= 0 329.85/289.66 f1(A, B, C, D, E, F, G) -> Com_1(f2(A, B, C, D, E, D + 1, G)) :|: 1 + B >= 2 * D 329.85/289.66 f1(A, B, C, D, E, F, G) -> Com_1(f2(A, B, C, D, E, D - 1, G)) :|: 2 * D >= 4 + B 329.85/289.66 f1(A, B, C, D, E, F, G) -> Com_1(f2(A, B, C, D, E, D, G)) :|: B + 2 >= 2 * D && B + 2 <= 2 * D 329.85/289.66 f1(A, B, C, D, E, F, G) -> Com_1(f2(A, B, C, D, E, D, G)) :|: B + 3 >= 2 * D && B + 3 <= 2 * D 329.85/289.66 f2(A, B, C, D, E, F, G) -> Com_1(f3(A, B, C, D, E, F, E + 1)) :|: D + A >= 2 * E + 1 329.85/289.66 f2(A, B, C, D, E, F, G) -> Com_1(f3(A, B, C, D, E, F, E - 1)) :|: 2 * E >= 2 + D + A 329.85/289.66 f2(A, B, C, D, E, F, G) -> Com_1(f3(A, B, C, D, E, F, E)) :|: D + A >= 2 * E && D + A <= 2 * E 329.85/289.66 f2(A, B, C, D, E, F, G) -> Com_1(f3(A, B, C, D, E, F, E)) :|: D + A + 1 >= 2 * E && D + A + 1 <= 2 * E 329.85/289.66 f3(A, B, C, D, E, F, G) -> Com_1(f1(A, B, C, F, G, F, G)) :|: D >= F + 1 329.85/289.66 f3(A, B, C, D, E, F, G) -> Com_1(f1(A, B, C, F, G, F, G)) :|: F >= D + 1 329.85/289.66 f3(A, B, C, D, E, F, G) -> Com_1(f1(A, B, C, F, G, F, G)) :|: E >= G + 1 329.85/289.66 f3(A, B, C, D, E, F, G) -> Com_1(f1(A, B, C, F, G, F, G)) :|: G >= E + 1 329.85/289.66 329.85/289.66 The start-symbols are:[f0_7] 329.85/289.66 329.85/289.66 329.85/289.66 ---------------------------------------- 329.85/289.66 329.85/289.66 (1) Loat Proof (FINISHED) 329.85/289.66 329.85/289.66 329.85/289.66 ### Pre-processing the ITS problem ### 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Initial linear ITS problem 329.85/289.66 329.85/289.66 Start location: f0 329.85/289.66 329.85/289.66 0: f0 -> f1 : [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 ], cost: 1 329.85/289.66 329.85/289.66 1: f1 -> f2 : F'=1+D, [ 1+B>=2*D ], cost: 1 329.85/289.66 329.85/289.66 2: f1 -> f2 : F'=-1+D, [ 2*D>=4+B ], cost: 1 329.85/289.66 329.85/289.66 3: f1 -> f2 : F'=D, [ 2+B==2*D ], cost: 1 329.85/289.66 329.85/289.66 4: f1 -> f2 : F'=D, [ 3+B==2*D ], cost: 1 329.85/289.66 329.85/289.66 5: f2 -> f3 : G'=1+E, [ D+A>=1+2*E ], cost: 1 329.85/289.66 329.85/289.66 6: f2 -> f3 : G'=-1+E, [ 2*E>=2+D+A ], cost: 1 329.85/289.66 329.85/289.66 7: f2 -> f3 : G'=E, [ D+A==2*E ], cost: 1 329.85/289.66 329.85/289.66 8: f2 -> f3 : G'=E, [ 1+D+A==2*E ], cost: 1 329.85/289.66 329.85/289.66 9: f3 -> f1 : D'=F, E'=G, [ D>=1+F ], cost: 1 329.85/289.66 329.85/289.66 10: f3 -> f1 : D'=F, E'=G, [ F>=1+D ], cost: 1 329.85/289.66 329.85/289.66 11: f3 -> f1 : D'=F, E'=G, [ E>=1+G ], cost: 1 329.85/289.66 329.85/289.66 12: f3 -> f1 : D'=F, E'=G, [ G>=1+E ], cost: 1 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 ### Simplification by acceleration and chaining ### 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Eliminated locations (on tree-shaped paths): 329.85/289.66 329.85/289.66 Start location: f0 329.85/289.66 329.85/289.66 0: f0 -> f1 : [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 ], cost: 1 329.85/289.66 329.85/289.66 13: f1 -> f3 : F'=1+D, G'=1+E, [ 1+B>=2*D && D+A>=1+2*E ], cost: 2 329.85/289.66 329.85/289.66 14: f1 -> f3 : F'=1+D, G'=-1+E, [ 1+B>=2*D && 2*E>=2+D+A ], cost: 2 329.85/289.66 329.85/289.66 15: f1 -> f3 : F'=1+D, G'=E, [ 1+B>=2*D && D+A==2*E ], cost: 2 329.85/289.66 329.85/289.66 16: f1 -> f3 : F'=1+D, G'=E, [ 1+B>=2*D && 1+D+A==2*E ], cost: 2 329.85/289.66 329.85/289.66 17: f1 -> f3 : F'=-1+D, G'=1+E, [ 2*D>=4+B && D+A>=1+2*E ], cost: 2 329.85/289.66 329.85/289.66 18: f1 -> f3 : F'=-1+D, G'=-1+E, [ 2*D>=4+B && 2*E>=2+D+A ], cost: 2 329.85/289.66 329.85/289.66 19: f1 -> f3 : F'=-1+D, G'=E, [ 2*D>=4+B && D+A==2*E ], cost: 2 329.85/289.66 329.85/289.66 20: f1 -> f3 : F'=-1+D, G'=E, [ 2*D>=4+B && 1+D+A==2*E ], cost: 2 329.85/289.66 329.85/289.66 21: f1 -> f3 : F'=D, G'=1+E, [ 2+B==2*D && D+A>=1+2*E ], cost: 2 329.85/289.66 329.85/289.66 22: f1 -> f3 : F'=D, G'=-1+E, [ 2+B==2*D && 2*E>=2+D+A ], cost: 2 329.85/289.66 329.85/289.66 23: f1 -> f3 : F'=D, G'=E, [ 2+B==2*D && D+A==2*E ], cost: 2 329.85/289.66 329.85/289.66 24: f1 -> f3 : F'=D, G'=E, [ 2+B==2*D && 1+D+A==2*E ], cost: 2 329.85/289.66 329.85/289.66 25: f1 -> f3 : F'=D, G'=1+E, [ 3+B==2*D && D+A>=1+2*E ], cost: 2 329.85/289.66 329.85/289.66 26: f1 -> f3 : F'=D, G'=-1+E, [ 3+B==2*D && 2*E>=2+D+A ], cost: 2 329.85/289.66 329.85/289.66 27: f1 -> f3 : F'=D, G'=E, [ 3+B==2*D && D+A==2*E ], cost: 2 329.85/289.66 329.85/289.66 28: f1 -> f3 : F'=D, G'=E, [ 3+B==2*D && 1+D+A==2*E ], cost: 2 329.85/289.66 329.85/289.66 9: f3 -> f1 : D'=F, E'=G, [ D>=1+F ], cost: 1 329.85/289.66 329.85/289.66 10: f3 -> f1 : D'=F, E'=G, [ F>=1+D ], cost: 1 329.85/289.66 329.85/289.66 11: f3 -> f1 : D'=F, E'=G, [ E>=1+G ], cost: 1 329.85/289.66 329.85/289.66 12: f3 -> f1 : D'=F, E'=G, [ G>=1+E ], cost: 1 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Eliminated locations (on tree-shaped paths): 329.85/289.66 329.85/289.66 Start location: f0 329.85/289.66 329.85/289.66 0: f0 -> f1 : [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 ], cost: 1 329.85/289.66 329.85/289.66 29: f1 -> f1 : D'=1+D, E'=1+E, F'=1+D, G'=1+E, [ 1+B>=2*D && D+A>=1+2*E ], cost: 3 329.85/289.66 329.85/289.66 30: f1 -> f1 : D'=1+D, E'=1+E, F'=1+D, G'=1+E, [ 1+B>=2*D && D+A>=1+2*E ], cost: 3 329.85/289.66 329.85/289.66 31: f1 -> f1 : D'=1+D, E'=-1+E, F'=1+D, G'=-1+E, [ 1+B>=2*D && 2*E>=2+D+A ], cost: 3 329.85/289.66 329.85/289.66 32: f1 -> f1 : D'=1+D, E'=-1+E, F'=1+D, G'=-1+E, [ 1+B>=2*D && 2*E>=2+D+A ], cost: 3 329.85/289.66 329.85/289.66 33: f1 -> f1 : D'=1+D, E'=E, F'=1+D, G'=E, [ 1+B>=2*D && D+A==2*E ], cost: 3 329.85/289.66 329.85/289.66 34: f1 -> f1 : D'=1+D, E'=E, F'=1+D, G'=E, [ 1+B>=2*D && 1+D+A==2*E ], cost: 3 329.85/289.66 329.85/289.66 35: f1 -> f1 : D'=-1+D, E'=1+E, F'=-1+D, G'=1+E, [ 2*D>=4+B && D+A>=1+2*E ], cost: 3 329.85/289.66 329.85/289.66 36: f1 -> f1 : D'=-1+D, E'=1+E, F'=-1+D, G'=1+E, [ 2*D>=4+B && D+A>=1+2*E ], cost: 3 329.85/289.66 329.85/289.66 37: f1 -> f1 : D'=-1+D, E'=-1+E, F'=-1+D, G'=-1+E, [ 2*D>=4+B && 2*E>=2+D+A ], cost: 3 329.85/289.66 329.85/289.66 38: f1 -> f1 : D'=-1+D, E'=-1+E, F'=-1+D, G'=-1+E, [ 2*D>=4+B && 2*E>=2+D+A ], cost: 3 329.85/289.66 329.85/289.66 39: f1 -> f1 : D'=-1+D, E'=E, F'=-1+D, G'=E, [ 2*D>=4+B && D+A==2*E ], cost: 3 329.85/289.66 329.85/289.66 40: f1 -> f1 : D'=-1+D, E'=E, F'=-1+D, G'=E, [ 2*D>=4+B && 1+D+A==2*E ], cost: 3 329.85/289.66 329.85/289.66 41: f1 -> f1 : D'=D, E'=1+E, F'=D, G'=1+E, [ 2+B==2*D && D+A>=1+2*E ], cost: 3 329.85/289.66 329.85/289.66 42: f1 -> f1 : D'=D, E'=-1+E, F'=D, G'=-1+E, [ 2+B==2*D && 2*E>=2+D+A ], cost: 3 329.85/289.66 329.85/289.66 43: f1 -> f1 : D'=D, E'=1+E, F'=D, G'=1+E, [ 3+B==2*D && D+A>=1+2*E ], cost: 3 329.85/289.66 329.85/289.66 44: f1 -> f1 : D'=D, E'=-1+E, F'=D, G'=-1+E, [ 3+B==2*D && 2*E>=2+D+A ], cost: 3 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Accelerating simple loops of location 1. 329.85/289.66 329.85/289.66 Simplified some of the simple loops (and removed duplicate rules). 329.85/289.66 329.85/289.66 Accelerating the following rules: 329.85/289.66 329.85/289.66 30: f1 -> f1 : D'=1+D, E'=1+E, F'=1+D, G'=1+E, [ 1+B>=2*D && D+A>=1+2*E ], cost: 3 329.85/289.66 329.85/289.66 32: f1 -> f1 : D'=1+D, E'=-1+E, F'=1+D, G'=-1+E, [ 1+B>=2*D && 2*E>=2+D+A ], cost: 3 329.85/289.66 329.85/289.66 33: f1 -> f1 : D'=1+D, F'=1+D, G'=E, [ 1+B>=2*D && D+A==2*E ], cost: 3 329.85/289.66 329.85/289.66 34: f1 -> f1 : D'=1+D, F'=1+D, G'=E, [ 1+B>=2*D && 1+D+A==2*E ], cost: 3 329.85/289.66 329.85/289.66 36: f1 -> f1 : D'=-1+D, E'=1+E, F'=-1+D, G'=1+E, [ 2*D>=4+B && D+A>=1+2*E ], cost: 3 329.85/289.66 329.85/289.66 38: f1 -> f1 : D'=-1+D, E'=-1+E, F'=-1+D, G'=-1+E, [ 2*D>=4+B && 2*E>=2+D+A ], cost: 3 329.85/289.66 329.85/289.66 39: f1 -> f1 : D'=-1+D, F'=-1+D, G'=E, [ 2*D>=4+B && D+A==2*E ], cost: 3 329.85/289.66 329.85/289.66 40: f1 -> f1 : D'=-1+D, F'=-1+D, G'=E, [ 2*D>=4+B && 1+D+A==2*E ], cost: 3 329.85/289.66 329.85/289.66 41: f1 -> f1 : E'=1+E, F'=D, G'=1+E, [ 2+B==2*D && D+A>=1+2*E ], cost: 3 329.85/289.66 329.85/289.66 42: f1 -> f1 : E'=-1+E, F'=D, G'=-1+E, [ 2+B==2*D && 2*E>=2+D+A ], cost: 3 329.85/289.66 329.85/289.66 43: f1 -> f1 : E'=1+E, F'=D, G'=1+E, [ 3+B==2*D && D+A>=1+2*E ], cost: 3 329.85/289.66 329.85/289.66 44: f1 -> f1 : E'=-1+E, F'=D, G'=-1+E, [ 3+B==2*D && 2*E>=2+D+A ], cost: 3 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Accelerated rule 30 with backward acceleration, yielding the new rule 45. 329.85/289.66 329.85/289.66 Accelerated rule 32 with backward acceleration, yielding the new rule 46. 329.85/289.66 329.85/289.66 Accelerated rule 33 with metering function -D-A+2*E, yielding the new rule 47. 329.85/289.66 329.85/289.66 Accelerated rule 34 with metering function -1-D-A+2*E, yielding the new rule 48. 329.85/289.66 329.85/289.66 Accelerated rule 36 with backward acceleration, yielding the new rule 49. 329.85/289.66 329.85/289.66 Accelerated rule 38 with backward acceleration, yielding the new rule 50. 329.85/289.66 329.85/289.66 Accelerated rule 39 with metering function D+A-2*E, yielding the new rule 51. 329.85/289.66 329.85/289.66 Accelerated rule 40 with metering function 1+D+A-2*E, yielding the new rule 52. 329.85/289.66 329.85/289.66 Accelerated rule 41 with metering function meter (where 2*meter==D+A-2*E), yielding the new rule 53. 329.85/289.66 329.85/289.66 Accelerated rule 42 with metering function meter_1 (where 2*meter_1==-1-D-A+2*E), yielding the new rule 54. 329.85/289.66 329.85/289.66 Accelerated rule 43 with metering function meter_2 (where 2*meter_2==D+A-2*E), yielding the new rule 55. 329.85/289.66 329.85/289.66 Accelerated rule 44 with metering function meter_3 (where 2*meter_3==-1-D-A+2*E), yielding the new rule 56. 329.85/289.66 329.85/289.66 Nested simple loops 32 (outer loop) and 45 (inner loop) with metering function meter_4 (where 2*meter_4==-1-D-A-k+2*E), resulting in the new rules: 57. 329.85/289.66 329.85/289.66 Nested simple loops 33 (outer loop) and 45 (inner loop) with metering function meter_6 (where 4*meter_6==1-2*D-k+B), resulting in the new rules: 58, 59. 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k==-1+D+A-2*E} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k==-1+D+A-2*E} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_1==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_1==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_1==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_1==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_1==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_1==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_1==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_2==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_2==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_2==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_2==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_2==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_2==1} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_2==1} 329.85/289.66 329.85/289.66 Nested simple loops 36 (outer loop) and 50 (inner loop) with metering function meter_23 (where 2*meter_23==D+A-k_3-2*E), resulting in the new rules: 60. 329.85/289.66 329.85/289.66 Nested simple loops 40 (outer loop) and 50 (inner loop) with metering function meter_25 (where 4*meter_25==-4+2*D-k_3-B), resulting in the new rules: 61, 62. 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_3==-2-D-A+2*E} 329.85/289.66 329.85/289.66 During metering: Instantiating temporary variables by {k_3==-2-D-A+2*E} 329.85/289.66 329.85/289.66 Nested simple loops 30 (outer loop) and 53 (inner loop) with metering function meter_28 (where 2*meter_28==-2*D+B), resulting in the new rules: 63. 329.85/289.66 329.85/289.66 Nested simple loops 36 (outer loop) and 53 (inner loop) with metering function meter_29 (where 2*meter_29==-4+2*D-B), resulting in the new rules: 64. 329.85/289.66 329.85/289.66 Nested simple loops 32 (outer loop) and 54 (inner loop) with metering function meter_30 (where 2*meter_30==-2*D+B), resulting in the new rules: 65. 329.85/289.66 329.85/289.66 Nested simple loops 38 (outer loop) and 54 (inner loop) with metering function meter_31 (where 2*meter_31==-4+2*D-B), resulting in the new rules: 66. 329.85/289.66 329.85/289.66 Nested simple loops 30 (outer loop) and 55 (inner loop) with metering function meter_32 (where 2*meter_32==1-2*D+B), resulting in the new rules: 67. 329.85/289.66 329.85/289.66 Nested simple loops 36 (outer loop) and 55 (inner loop) with metering function meter_33 (where 2*meter_33==-5+2*D-B), resulting in the new rules: 68. 329.85/289.66 329.85/289.66 Nested simple loops 32 (outer loop) and 56 (inner loop) with metering function meter_34 (where 2*meter_34==1-2*D+B), resulting in the new rules: 69. 329.85/289.66 329.85/289.66 Nested simple loops 38 (outer loop) and 56 (inner loop) with metering function meter_35 (where 2*meter_35==-5+2*D-B), resulting in the new rules: 70. 329.85/289.66 329.85/289.66 Removing the simple loops: 30 32 33 34 36 38 39 40 41 42 43 44. 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Accelerated all simple loops using metering functions (where possible): 329.85/289.66 329.85/289.66 Start location: f0 329.85/289.66 329.85/289.66 0: f0 -> f1 : [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 ], cost: 1 329.85/289.66 329.85/289.66 45: f1 -> f1 : D'=D+k, E'=k+E, F'=D+k, G'=k+E, [ 1+B>=2*D && D+A>=1+2*E && k>0 && 1+B>=-2+2*D+2*k && -1+D+A+k>=-1+2*k+2*E ], cost: 3*k 329.85/289.66 329.85/289.66 46: f1 -> f1 : D'=k_1+D, E'=-k_1+E, F'=k_1+D, G'=-k_1+E, [ 1+B>=2*D && 2*E>=2+D+A && k_1>0 && 1+B>=-2+2*k_1+2*D && 2-2*k_1+2*E>=1+k_1+D+A ], cost: 3*k_1 329.85/289.66 329.85/289.66 47: f1 -> f1 : D'=-A+2*E, F'=-A+2*E, G'=E, [ 1+B>=2*D && D+A==2*E && -D-A+2*E>=1 ], cost: -3*D-3*A+6*E 329.85/289.66 329.85/289.66 48: f1 -> f1 : D'=-1-A+2*E, F'=-1-A+2*E, G'=E, [ 1+B>=2*D && 1+D+A==2*E && -1-D-A+2*E>=1 ], cost: -3-3*D-3*A+6*E 329.85/289.66 329.85/289.66 49: f1 -> f1 : D'=-k_2+D, E'=k_2+E, F'=-k_2+D, G'=k_2+E, [ 2*D>=4+B && D+A>=1+2*E && k_2>0 && 2-2*k_2+2*D>=4+B && 1-k_2+D+A>=-1+2*k_2+2*E ], cost: 3*k_2 329.85/289.66 329.85/289.66 50: f1 -> f1 : D'=D-k_3, E'=-k_3+E, F'=D-k_3, G'=-k_3+E, [ 2*D>=4+B && 2*E>=2+D+A && k_3>0 && 2+2*D-2*k_3>=4+B && 2-2*k_3+2*E>=3+D+A-k_3 ], cost: 3*k_3 329.85/289.66 329.85/289.66 51: f1 -> f1 : D'=-A+2*E, F'=-A+2*E, G'=E, [ 2*D>=4+B && D+A==2*E && D+A-2*E>=1 ], cost: 3*D+3*A-6*E 329.85/289.66 329.85/289.66 52: f1 -> f1 : D'=-1-A+2*E, F'=-1-A+2*E, G'=E, [ 2*D>=4+B && 1+D+A==2*E && 1+D+A-2*E>=1 ], cost: 3+3*D+3*A-6*E 329.85/289.66 329.85/289.66 53: f1 -> f1 : E'=meter+E, F'=D, G'=meter+E, [ 2+B==2*D && D+A>=1+2*E && 2*meter==D+A-2*E && meter>=1 ], cost: 3*meter 329.85/289.66 329.85/289.66 54: f1 -> f1 : E'=-meter_1+E, F'=D, G'=-meter_1+E, [ 2+B==2*D && 2*E>=2+D+A && 2*meter_1==-1-D-A+2*E && meter_1>=1 ], cost: 3*meter_1 329.85/289.66 329.85/289.66 55: f1 -> f1 : E'=E+meter_2, F'=D, G'=E+meter_2, [ 3+B==2*D && D+A>=1+2*E && 2*meter_2==D+A-2*E && meter_2>=1 ], cost: 3*meter_2 329.85/289.66 329.85/289.66 56: f1 -> f1 : E'=-meter_3+E, F'=D, G'=-meter_3+E, [ 3+B==2*D && 2*E>=2+D+A && 2*meter_3==-1-D-A+2*E && meter_3>=1 ], cost: 3*meter_3 329.85/289.66 329.85/289.66 57: f1 -> f1 : D'=meter_4*k+meter_4+D, E'=meter_4*k-meter_4+E, F'=meter_4*k+meter_4+D, G'=meter_4*k-meter_4+E, [ 2+D+A-2*E==0 && 1+B>=2+2*D && k>0 && 1+B>=2*D+2*k && D+A+k>=-3+2*k+2*E && 2*meter_4==-1-D-A-k+2*E && meter_4>=1 ], cost: 3*meter_4*k+3*meter_4 329.85/289.66 329.85/289.66 58: f1 -> f1 : D'=meter_6+D+meter_6*k, E'=meter_6*k+E, F'=meter_6+D+meter_6*k, G'=meter_6*k+E, [ D+A==2*E && 1+B>=2+2*D && k>0 && 1+B>=2*D+2*k && D+A+k>=-1+2*k+2*E && 4*meter_6==1-2*D-k+B && meter_6>=1 ], cost: 3*meter_6+3*meter_6*k 329.85/289.66 329.85/289.66 59: f1 -> f1 : D'=meter_6+D+k+meter_6*k, E'=k+meter_6*k+E, F'=meter_6+D+k+meter_6*k, G'=k+meter_6*k+E, [ 1+B>=2*D && D+A>=1+2*E && k>0 && D+A+k==2*k+2*E && 1+B>=2+2*D+2*k && 1+B>=2*D+4*k && D+A+2*k>=-1+4*k+2*E && 4*meter_6==1-2*D-3*k+B && meter_6>=1 ], cost: 3*meter_6+3*k+3*meter_6*k 329.85/289.66 329.85/289.66 60: f1 -> f1 : D'=-k_3*meter_23+D-meter_23, E'=-k_3*meter_23+meter_23+E, F'=-k_3*meter_23+D-meter_23, G'=-k_3*meter_23+meter_23+E, [ 1-D-A+2*E==0 && -2+2*D>=4+B && k_3>0 && 2*D-2*k_3>=4+B && 4-2*k_3+2*E>=2+D+A-k_3 && 2*meter_23==D+A-k_3-2*E && meter_23>=1 ], cost: 3*k_3*meter_23+3*meter_23 329.85/289.66 329.85/289.66 61: f1 -> f1 : D'=D-meter_25-meter_25*k_3, E'=-meter_25*k_3+E, F'=D-meter_25-meter_25*k_3, G'=-meter_25*k_3+E, [ 1+D+A==2*E && -2+2*D>=4+B && k_3>0 && 2*D-2*k_3>=4+B && 2-2*k_3+2*E>=2+D+A-k_3 && 4*meter_25==-4+2*D-k_3-B && meter_25>=1 ], cost: 3*meter_25+3*meter_25*k_3 329.85/289.66 329.85/289.66 62: f1 -> f1 : D'=D-meter_25-meter_25*k_3-k_3, E'=-meter_25*k_3-k_3+E, F'=D-meter_25-meter_25*k_3-k_3, G'=-meter_25*k_3-k_3+E, [ 2*D>=4+B && 2*E>=2+D+A && k_3>0 && 1+D+A-k_3==-2*k_3+2*E && -2+2*D-2*k_3>=4+B && 2*D-4*k_3>=4+B && 2-4*k_3+2*E>=2+D+A-2*k_3 && 4*meter_25==-4+2*D-3*k_3-B && meter_25>=1 ], cost: 3*meter_25+3*meter_25*k_3+3*k_3 329.85/289.66 329.85/289.66 63: f1 -> f1 : D'=D+meter_28, E'=meter*meter_28+meter_28+E, F'=D+meter_28, G'=meter*meter_28+meter_28+E, [ 2+B==2+2*D && 1+D+A>=3+2*E && 2*meter==-1+D+A-2*E && meter>=1 && 2*meter_28==-2*D+B && meter_28>=1 ], cost: 3*meter*meter_28+3*meter_28 329.85/289.66 329.85/289.66 64: f1 -> f1 : D'=-meter_29+D, E'=meter_29+meter_29*meter+E, F'=-meter_29+D, G'=meter_29+meter_29*meter+E, [ 2+B==-2+2*D && -1+D+A>=3+2*E && 2*meter==-3+D+A-2*E && meter>=1 && 2*meter_29==-4+2*D-B && meter_29>=1 ], cost: 3*meter_29+3*meter_29*meter 329.85/289.66 329.85/289.66 65: f1 -> f1 : D'=meter_30+D, E'=-meter_30-meter_30*meter_1+E, F'=meter_30+D, G'=-meter_30-meter_30*meter_1+E, [ 2+B==2+2*D && -2+2*E>=3+D+A && 2*meter_1==-4-D-A+2*E && meter_1>=1 && 2*meter_30==-2*D+B && meter_30>=1 ], cost: 3*meter_30+3*meter_30*meter_1 329.85/289.66 329.85/289.66 66: f1 -> f1 : D'=D-meter_31, E'=-meter_1*meter_31-meter_31+E, F'=D-meter_31, G'=-meter_1*meter_31-meter_31+E, [ 2+B==-2+2*D && -2+2*E>=1+D+A && 2*meter_1==-2-D-A+2*E && meter_1>=1 && 2*meter_31==-4+2*D-B && meter_31>=1 ], cost: 3*meter_1*meter_31+3*meter_31 329.85/289.66 329.85/289.66 67: f1 -> f1 : D'=meter_32+D, E'=meter_32+meter_32*meter_2+E, F'=meter_32+D, G'=meter_32+meter_32*meter_2+E, [ 3+B==2+2*D && 1+D+A>=3+2*E && 2*meter_2==-1+D+A-2*E && meter_2>=1 && 2*meter_32==1-2*D+B && meter_32>=1 ], cost: 3*meter_32+3*meter_32*meter_2 329.85/289.66 329.85/289.66 68: f1 -> f1 : D'=-meter_33+D, E'=meter_33+meter_33*meter_2+E, F'=-meter_33+D, G'=meter_33+meter_33*meter_2+E, [ 3+B==-2+2*D && -1+D+A>=3+2*E && 2*meter_2==-3+D+A-2*E && meter_2>=1 && 2*meter_33==-5+2*D-B && meter_33>=1 ], cost: 3*meter_33+3*meter_33*meter_2 329.85/289.66 329.85/289.66 69: f1 -> f1 : D'=meter_34+D, E'=-meter_34-meter_34*meter_3+E, F'=meter_34+D, G'=-meter_34-meter_34*meter_3+E, [ 3+B==2+2*D && -2+2*E>=3+D+A && 2*meter_3==-4-D-A+2*E && meter_3>=1 && 2*meter_34==1-2*D+B && meter_34>=1 ], cost: 3*meter_34+3*meter_34*meter_3 329.85/289.66 329.85/289.66 70: f1 -> f1 : D'=D-meter_35, E'=-meter_3*meter_35-meter_35+E, F'=D-meter_35, G'=-meter_3*meter_35-meter_35+E, [ 3+B==-2+2*D && -2+2*E>=1+D+A && 2*meter_3==-2-D-A+2*E && meter_3>=1 && 2*meter_35==-5+2*D-B && meter_35>=1 ], cost: 3*meter_3*meter_35+3*meter_35 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Chained accelerated rules (with incoming rules): 329.85/289.66 329.85/289.66 Start location: f0 329.85/289.66 329.85/289.66 0: f0 -> f1 : [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 ], cost: 1 329.85/289.66 329.85/289.66 71: f0 -> f1 : D'=D+k, E'=k+E, F'=D+k, G'=k+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && D+A>=1+2*E && k>0 && 1+B>=-2+2*D+2*k && -1+D+A+k>=-1+2*k+2*E ], cost: 1+3*k 329.85/289.66 329.85/289.66 72: f0 -> f1 : D'=k_1+D, E'=-k_1+E, F'=k_1+D, G'=-k_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && 2*E>=2+D+A && k_1>0 && 1+B>=-2+2*k_1+2*D && 2-2*k_1+2*E>=1+k_1+D+A ], cost: 1+3*k_1 329.85/289.66 329.85/289.66 73: f0 -> f1 : D'=-k_2+D, E'=k_2+E, F'=-k_2+D, G'=k_2+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && D+A>=1+2*E && k_2>0 && 2-2*k_2+2*D>=4+B && 1-k_2+D+A>=-1+2*k_2+2*E ], cost: 1+3*k_2 329.85/289.66 329.85/289.66 74: f0 -> f1 : D'=D-k_3, E'=-k_3+E, F'=D-k_3, G'=-k_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && 2*E>=2+D+A && k_3>0 && 2+2*D-2*k_3>=4+B && 2-2*k_3+2*E>=3+D+A-k_3 ], cost: 1+3*k_3 329.85/289.66 329.85/289.66 75: f0 -> f1 : E'=meter+E, F'=D, G'=meter+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && D+A>=1+2*E && 2*meter==D+A-2*E && meter>=1 ], cost: 1+3*meter 329.85/289.66 329.85/289.66 76: f0 -> f1 : E'=-meter_1+E, F'=D, G'=-meter_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && 2*E>=2+D+A && 2*meter_1==-1-D-A+2*E && meter_1>=1 ], cost: 1+3*meter_1 329.85/289.66 329.85/289.66 77: f0 -> f1 : E'=E+meter_2, F'=D, G'=E+meter_2, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && D+A>=1+2*E && 2*meter_2==D+A-2*E && meter_2>=1 ], cost: 1+3*meter_2 329.85/289.66 329.85/289.66 78: f0 -> f1 : E'=-meter_3+E, F'=D, G'=-meter_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && 2*E>=2+D+A && 2*meter_3==-1-D-A+2*E && meter_3>=1 ], cost: 1+3*meter_3 329.85/289.66 329.85/289.66 79: f0 -> f1 : D'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), E'=-meter_25*(-4+2*D-4*meter_25-B)+E, F'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), G'=-meter_25*(-4+2*D-4*meter_25-B)+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+D+A==2*E && -2+2*D>=4+B && -4+2*D-4*meter_25-B>0 && 8-2*D+8*meter_25+2*B>=4+B && 10-4*D+8*meter_25+2*E+2*B>=6-D+4*meter_25+A+B && meter_25>=1 ], cost: 1+3*meter_25+3*meter_25*(-4+2*D-4*meter_25-B) 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Removed unreachable locations (and leaf rules with constant cost): 329.85/289.66 329.85/289.66 Start location: f0 329.85/289.66 329.85/289.66 71: f0 -> f1 : D'=D+k, E'=k+E, F'=D+k, G'=k+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && D+A>=1+2*E && k>0 && 1+B>=-2+2*D+2*k && -1+D+A+k>=-1+2*k+2*E ], cost: 1+3*k 329.85/289.66 329.85/289.66 72: f0 -> f1 : D'=k_1+D, E'=-k_1+E, F'=k_1+D, G'=-k_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && 2*E>=2+D+A && k_1>0 && 1+B>=-2+2*k_1+2*D && 2-2*k_1+2*E>=1+k_1+D+A ], cost: 1+3*k_1 329.85/289.66 329.85/289.66 73: f0 -> f1 : D'=-k_2+D, E'=k_2+E, F'=-k_2+D, G'=k_2+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && D+A>=1+2*E && k_2>0 && 2-2*k_2+2*D>=4+B && 1-k_2+D+A>=-1+2*k_2+2*E ], cost: 1+3*k_2 329.85/289.66 329.85/289.66 74: f0 -> f1 : D'=D-k_3, E'=-k_3+E, F'=D-k_3, G'=-k_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && 2*E>=2+D+A && k_3>0 && 2+2*D-2*k_3>=4+B && 2-2*k_3+2*E>=3+D+A-k_3 ], cost: 1+3*k_3 329.85/289.66 329.85/289.66 75: f0 -> f1 : E'=meter+E, F'=D, G'=meter+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && D+A>=1+2*E && 2*meter==D+A-2*E && meter>=1 ], cost: 1+3*meter 329.85/289.66 329.85/289.66 76: f0 -> f1 : E'=-meter_1+E, F'=D, G'=-meter_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && 2*E>=2+D+A && 2*meter_1==-1-D-A+2*E && meter_1>=1 ], cost: 1+3*meter_1 329.85/289.66 329.85/289.66 77: f0 -> f1 : E'=E+meter_2, F'=D, G'=E+meter_2, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && D+A>=1+2*E && 2*meter_2==D+A-2*E && meter_2>=1 ], cost: 1+3*meter_2 329.85/289.66 329.85/289.66 78: f0 -> f1 : E'=-meter_3+E, F'=D, G'=-meter_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && 2*E>=2+D+A && 2*meter_3==-1-D-A+2*E && meter_3>=1 ], cost: 1+3*meter_3 329.85/289.66 329.85/289.66 79: f0 -> f1 : D'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), E'=-meter_25*(-4+2*D-4*meter_25-B)+E, F'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), G'=-meter_25*(-4+2*D-4*meter_25-B)+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+D+A==2*E && -2+2*D>=4+B && -4+2*D-4*meter_25-B>0 && 8-2*D+8*meter_25+2*B>=4+B && 10-4*D+8*meter_25+2*E+2*B>=6-D+4*meter_25+A+B && meter_25>=1 ], cost: 1+3*meter_25+3*meter_25*(-4+2*D-4*meter_25-B) 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 ### Computing asymptotic complexity ### 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Fully simplified ITS problem 329.85/289.66 329.85/289.66 Start location: f0 329.85/289.66 329.85/289.66 71: f0 -> f1 : D'=D+k, E'=k+E, F'=D+k, G'=k+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && D+A>=1+2*E && k>0 && 1+B>=-2+2*D+2*k && -1+D+A+k>=-1+2*k+2*E ], cost: 1+3*k 329.85/289.66 329.85/289.66 72: f0 -> f1 : D'=k_1+D, E'=-k_1+E, F'=k_1+D, G'=-k_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && 2*E>=2+D+A && k_1>0 && 1+B>=-2+2*k_1+2*D && 2-2*k_1+2*E>=1+k_1+D+A ], cost: 1+3*k_1 329.85/289.66 329.85/289.66 73: f0 -> f1 : D'=-k_2+D, E'=k_2+E, F'=-k_2+D, G'=k_2+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && D+A>=1+2*E && k_2>0 && 2-2*k_2+2*D>=4+B && 1-k_2+D+A>=-1+2*k_2+2*E ], cost: 1+3*k_2 329.85/289.66 329.85/289.66 74: f0 -> f1 : D'=D-k_3, E'=-k_3+E, F'=D-k_3, G'=-k_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && 2*E>=2+D+A && k_3>0 && 2+2*D-2*k_3>=4+B && 2-2*k_3+2*E>=3+D+A-k_3 ], cost: 1+3*k_3 329.85/289.66 329.85/289.66 75: f0 -> f1 : E'=meter+E, F'=D, G'=meter+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && D+A>=1+2*E && 2*meter==D+A-2*E && meter>=1 ], cost: 1+3*meter 329.85/289.66 329.85/289.66 76: f0 -> f1 : E'=-meter_1+E, F'=D, G'=-meter_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && 2*E>=2+D+A && 2*meter_1==-1-D-A+2*E && meter_1>=1 ], cost: 1+3*meter_1 329.85/289.66 329.85/289.66 77: f0 -> f1 : E'=E+meter_2, F'=D, G'=E+meter_2, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && D+A>=1+2*E && 2*meter_2==D+A-2*E && meter_2>=1 ], cost: 1+3*meter_2 329.85/289.66 329.85/289.66 78: f0 -> f1 : E'=-meter_3+E, F'=D, G'=-meter_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && 2*E>=2+D+A && 2*meter_3==-1-D-A+2*E && meter_3>=1 ], cost: 1+3*meter_3 329.85/289.66 329.85/289.66 79: f0 -> f1 : D'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), E'=-meter_25*(-4+2*D-4*meter_25-B)+E, F'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), G'=-meter_25*(-4+2*D-4*meter_25-B)+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+D+A==2*E && -2+2*D>=4+B && -4+2*D-4*meter_25-B>0 && 8-2*D+8*meter_25+2*B>=4+B && 10-4*D+8*meter_25+2*E+2*B>=6-D+4*meter_25+A+B && meter_25>=1 ], cost: 1+3*meter_25+3*meter_25*(-4+2*D-4*meter_25-B) 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Computing asymptotic complexity for rule 71 329.85/289.66 329.85/289.66 Simplified the guard: 329.85/289.66 329.85/289.66 71: f0 -> f1 : D'=D+k, E'=k+E, F'=D+k, G'=k+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && k>0 && 1+B>=-2+2*D+2*k && -1+D+A+k>=-1+2*k+2*E ], cost: 1+3*k 329.85/289.66 329.85/289.66 Could not solve the limit problem. 329.85/289.66 329.85/289.66 Resulting cost 0 has complexity: Unknown 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 Obtained the following overall complexity (w.r.t. the length of the input n): 329.85/289.66 329.85/289.66 Complexity: Unknown 329.85/289.66 329.85/289.66 Cpx degree: ? 329.85/289.66 329.85/289.66 Solved cost: 0 329.85/289.66 329.85/289.66 Rule cost: 0 329.85/289.66 329.85/289.66 Rule guard: [] 329.85/289.66 329.85/289.66 329.85/289.66 329.85/289.66 WORST_CASE(Omega(0),?) 329.85/289.66 329.85/289.66 329.85/289.66 ---------------------------------------- 329.85/289.66 329.85/289.66 (2) 329.85/289.66 BOUNDS(1, INF) 329.85/289.68 EOF