64.88/26.62 WORST_CASE(NON_POLY, ?) 64.88/26.62 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 64.88/26.62 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 64.88/26.62 64.88/26.62 64.88/26.62 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 64.88/26.62 64.88/26.62 (0) CpxIntTrs 64.88/26.62 (1) Loat Proof [FINISHED, 24.7 s] 64.88/26.62 (2) BOUNDS(INF, INF) 64.88/26.62 64.88/26.62 64.88/26.62 ---------------------------------------- 64.88/26.62 64.88/26.62 (0) 64.88/26.62 Obligation: 64.88/26.62 Complexity Int TRS consisting of the following rules: 64.88/26.62 f38(A, B, C, D, E, F, G) -> Com_1(f11(A, A, C, D, E, F, G)) :|: A >= B && A <= B 64.88/26.62 f0(A, B, C, D, E, F, G) -> Com_1(f11(0, 0, H, 0, 1, I, I)) :|: H >= 0 && I >= 1 64.88/26.62 f11(A, B, C, D, E, F, G) -> Com_1(f34(0, H, C, D + 1, E, F, G)) :|: H >= 0 && 1 >= H && G >= 1 && 0 >= C && 0 >= D 64.88/26.62 f11(A, B, C, D, E, F, G) -> Com_1(f34(1, H, C, D + 1, E, F, G)) :|: H >= 0 && 1 >= H && G >= 1 && 0 >= C && D >= 1 && D <= 1 64.88/26.62 f11(A, B, C, D, E, F, G) -> Com_1(f34(0, H, C, D + 1, E, F, G)) :|: H >= 0 && 1 >= H && G >= 1 && 0 >= C && D >= 2 && D <= 2 64.88/26.62 f11(A, B, C, D, E, F, G) -> Com_1(f34(I, J, H, 0, E + 1, F, G)) :|: J >= 0 && 1 >= J && I >= 0 && 1 >= I && H >= 0 && G >= 1 && 0 >= C && D >= 3 64.88/26.62 f11(A, B, C, D, E, F, G) -> Com_1(f34(H, I, C - 1, D, E, F, G)) :|: I >= 0 && 1 >= I && H >= 0 && 1 >= H && C >= 1 && G >= 1 64.88/26.62 f34(A, B, C, D, E, F, G) -> Com_1(f38(A, B, C, D + 1, E, F, G)) :|: 0 >= B && 0 >= C && 0 >= D 64.88/26.62 f34(A, B, C, D, E, F, G) -> Com_1(f38(A, B, C, D + 1, E, F, G)) :|: B >= 1 && 0 >= C && D >= 1 && D <= 1 64.88/26.62 f34(A, B, C, D, E, F, G) -> Com_1(f38(A, B, C, D + 1, E, F, G)) :|: 0 >= B && 0 >= C && D >= 2 && D <= 2 64.88/26.62 f34(A, B, C, D, E, F, G) -> Com_1(f38(A, B, H, 0, E + 1, F, G)) :|: H >= 0 && 0 >= C && D >= 3 64.88/26.62 f34(A, B, C, D, E, F, G) -> Com_1(f38(A, B, C - 1, D, E, F, G)) :|: C >= 1 64.88/26.62 f38(A, B, C, D, E, F, G) -> Com_1(f11(A, B, C, D, E, F, G - 1)) :|: B >= A + 1 64.88/26.62 f38(A, B, C, D, E, F, G) -> Com_1(f11(A, B, C, D, E, F, G - 1)) :|: A >= 1 + B 64.88/26.62 f11(A, B, C, D, E, F, G) -> Com_1(f53(A, B, C, D, E, F, G)) :|: 0 >= G 64.88/26.62 64.88/26.62 The start-symbols are:[f0_7] 64.88/26.62 64.88/26.62 64.88/26.62 ---------------------------------------- 64.88/26.62 64.88/26.62 (1) Loat Proof (FINISHED) 64.88/26.62 64.88/26.62 64.88/26.62 ### Pre-processing the ITS problem ### 64.88/26.62 64.88/26.62 64.88/26.62 64.88/26.62 Initial linear ITS problem 64.88/26.62 64.88/26.62 Start location: f0 64.88/26.62 64.88/26.62 0: f38 -> f11 : B'=A, [ A==B ], cost: 1 64.88/26.62 64.88/26.62 12: f38 -> f11 : G'=-1+G, [ B>=1+A ], cost: 1 64.88/26.62 64.88/26.62 13: f38 -> f11 : G'=-1+G, [ A>=1+B ], cost: 1 64.88/26.62 64.88/26.62 1: f0 -> f11 : A'=0, B'=0, C'=free_1, D'=0, E'=1, F'=free, G'=free, [ free_1>=0 && free>=1 ], cost: 1 64.88/26.62 64.88/26.62 2: f11 -> f34 : A'=0, B'=free_2, D'=1+D, [ free_2>=0 && 1>=free_2 && G>=1 && 0>=C && 0>=D ], cost: 1 64.88/26.62 64.88/26.62 3: f11 -> f34 : A'=1, B'=free_3, D'=1+D, [ free_3>=0 && 1>=free_3 && G>=1 && 0>=C && D==1 ], cost: 1 64.88/26.62 64.88/26.62 4: f11 -> f34 : A'=0, B'=free_4, D'=1+D, [ free_4>=0 && 1>=free_4 && G>=1 && 0>=C && D==2 ], cost: 1 64.88/26.62 64.88/26.62 5: f11 -> f34 : A'=free_7, B'=free_5, C'=free_6, D'=0, E'=1+E, [ free_5>=0 && 1>=free_5 && free_7>=0 && 1>=free_7 && free_6>=0 && G>=1 && 0>=C && D>=3 ], cost: 1 64.88/26.62 64.88/26.62 6: f11 -> f34 : A'=free_9, B'=free_8, C'=-1+C, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 ], cost: 1 64.88/26.62 64.88/26.62 14: f11 -> f53 : [ 0>=G ], cost: 1 64.88/26.62 64.88/26.62 7: f34 -> f38 : D'=1+D, [ 0>=B && 0>=C && 0>=D ], cost: 1 64.88/26.62 64.88/26.62 8: f34 -> f38 : D'=1+D, [ B>=1 && 0>=C && D==1 ], cost: 1 64.88/26.62 64.88/26.62 9: f34 -> f38 : D'=1+D, [ 0>=B && 0>=C && D==2 ], cost: 1 64.88/26.62 64.88/26.62 10: f34 -> f38 : C'=free_10, D'=0, E'=1+E, [ free_10>=0 && 0>=C && D>=3 ], cost: 1 64.88/26.62 64.88/26.62 11: f34 -> f38 : C'=-1+C, [ C>=1 ], cost: 1 64.88/26.62 64.88/26.62 64.88/26.62 64.88/26.62 Removed unreachable and leaf rules: 64.88/26.62 64.88/26.62 Start location: f0 64.88/26.62 64.88/26.62 0: f38 -> f11 : B'=A, [ A==B ], cost: 1 64.88/26.62 64.88/26.62 12: f38 -> f11 : G'=-1+G, [ B>=1+A ], cost: 1 64.88/26.62 64.88/26.62 13: f38 -> f11 : G'=-1+G, [ A>=1+B ], cost: 1 64.88/26.62 64.88/26.62 1: f0 -> f11 : A'=0, B'=0, C'=free_1, D'=0, E'=1, F'=free, G'=free, [ free_1>=0 && free>=1 ], cost: 1 64.88/26.62 64.88/26.62 2: f11 -> f34 : A'=0, B'=free_2, D'=1+D, [ free_2>=0 && 1>=free_2 && G>=1 && 0>=C && 0>=D ], cost: 1 64.88/26.62 64.88/26.62 3: f11 -> f34 : A'=1, B'=free_3, D'=1+D, [ free_3>=0 && 1>=free_3 && G>=1 && 0>=C && D==1 ], cost: 1 64.88/26.62 64.88/26.62 4: f11 -> f34 : A'=0, B'=free_4, D'=1+D, [ free_4>=0 && 1>=free_4 && G>=1 && 0>=C && D==2 ], cost: 1 64.88/26.62 64.88/26.62 5: f11 -> f34 : A'=free_7, B'=free_5, C'=free_6, D'=0, E'=1+E, [ free_5>=0 && 1>=free_5 && free_7>=0 && 1>=free_7 && free_6>=0 && G>=1 && 0>=C && D>=3 ], cost: 1 64.88/26.62 64.88/26.62 6: f11 -> f34 : A'=free_9, B'=free_8, C'=-1+C, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 ], cost: 1 64.88/26.62 64.88/26.62 7: f34 -> f38 : D'=1+D, [ 0>=B && 0>=C && 0>=D ], cost: 1 64.88/26.62 64.88/26.62 8: f34 -> f38 : D'=1+D, [ B>=1 && 0>=C && D==1 ], cost: 1 64.88/26.62 64.88/26.62 9: f34 -> f38 : D'=1+D, [ 0>=B && 0>=C && D==2 ], cost: 1 64.88/26.62 64.88/26.62 10: f34 -> f38 : C'=free_10, D'=0, E'=1+E, [ free_10>=0 && 0>=C && D>=3 ], cost: 1 64.88/26.62 64.88/26.62 11: f34 -> f38 : C'=-1+C, [ C>=1 ], cost: 1 64.88/26.62 64.88/26.62 64.88/26.62 64.88/26.62 ### Simplification by acceleration and chaining ### 64.88/26.62 64.88/26.62 64.88/26.62 64.88/26.62 Eliminated locations (on tree-shaped paths): 64.88/26.62 64.88/26.62 Start location: f0 64.88/26.62 64.88/26.62 0: f38 -> f11 : B'=A, [ A==B ], cost: 1 64.88/26.62 64.88/26.62 12: f38 -> f11 : G'=-1+G, [ B>=1+A ], cost: 1 64.88/26.62 64.88/26.62 13: f38 -> f11 : G'=-1+G, [ A>=1+B ], cost: 1 64.88/26.62 64.88/26.62 1: f0 -> f11 : A'=0, B'=0, C'=free_1, D'=0, E'=1, F'=free, G'=free, [ free_1>=0 && free>=1 ], cost: 1 64.88/26.62 64.88/26.62 15: f11 -> f38 : A'=0, B'=free_2, D'=2+D, [ free_2>=0 && G>=1 && 0>=C && 0>=free_2 && 0>=1+D ], cost: 2 64.88/26.62 64.88/26.62 16: f11 -> f38 : A'=0, B'=free_2, D'=2+D, [ 1>=free_2 && G>=1 && 0>=C && free_2>=1 && 1+D==1 ], cost: 2 64.88/26.62 64.88/26.62 17: f11 -> f38 : A'=1, B'=free_3, D'=2+D, [ free_3>=0 && G>=1 && 0>=C && D==1 && 0>=free_3 ], cost: 2 64.88/26.62 64.88/26.62 18: f11 -> f38 : A'=0, B'=free_4, C'=free_10, D'=0, E'=1+E, [ free_4>=0 && 1>=free_4 && G>=1 && 0>=C && D==2 && free_10>=0 ], cost: 2 64.88/26.62 64.88/26.62 19: f11 -> f38 : A'=free_7, B'=free_5, C'=free_6, D'=1, E'=1+E, [ free_5>=0 && free_7>=0 && 1>=free_7 && free_6>=0 && G>=1 && 0>=C && D>=3 && 0>=free_5 && 0>=free_6 ], cost: 2 64.88/26.62 64.88/26.62 20: f11 -> f38 : A'=free_7, B'=free_5, C'=-1+free_6, D'=0, E'=1+E, [ free_5>=0 && 1>=free_5 && free_7>=0 && 1>=free_7 && G>=1 && 0>=C && D>=3 && free_6>=1 ], cost: 2 64.88/26.62 64.88/26.62 21: f11 -> f38 : A'=free_9, B'=free_8, C'=-1+C, D'=1+D, [ free_8>=0 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && 0>=free_8 && 0>=-1+C && 0>=D ], cost: 2 64.88/26.62 64.88/26.62 22: f11 -> f38 : A'=free_9, B'=free_8, C'=-1+C, D'=1+D, [ 1>=free_8 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && free_8>=1 && 0>=-1+C && D==1 ], cost: 2 64.88/26.62 64.88/26.62 23: f11 -> f38 : A'=free_9, B'=free_8, C'=-1+C, D'=1+D, [ free_8>=0 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && 0>=free_8 && 0>=-1+C && D==2 ], cost: 2 64.88/26.62 64.88/26.62 24: f11 -> f38 : A'=free_9, B'=free_8, C'=free_10, D'=0, E'=1+E, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && free_10>=0 && 0>=-1+C && D>=3 ], cost: 2 64.88/26.62 64.88/26.62 25: f11 -> f38 : A'=free_9, B'=free_8, C'=-2+C, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 ], cost: 2 64.88/26.62 64.88/26.62 64.88/26.62 64.88/26.62 Eliminated locations (on tree-shaped paths): 64.88/26.62 64.88/26.62 Start location: f0 64.88/26.62 64.88/26.62 1: f0 -> f11 : A'=0, B'=0, C'=free_1, D'=0, E'=1, F'=free, G'=free, [ free_1>=0 && free>=1 ], cost: 1 64.88/26.62 64.88/26.62 26: f11 -> f11 : A'=0, B'=0, D'=2+D, [ G>=1 && 0>=C && 0>=1+D && 0==free_2 ], cost: 3 64.88/26.62 64.88/26.62 27: f11 -> f11 : A'=0, B'=free_2, D'=2+D, G'=-1+G, [ 1>=free_2 && G>=1 && 0>=C && free_2>=1 && 1+D==1 ], cost: 3 64.88/26.62 64.88/26.62 28: f11 -> f11 : A'=1, B'=free_3, D'=2+D, G'=-1+G, [ free_3>=0 && G>=1 && 0>=C && D==1 && 0>=free_3 ], cost: 3 64.88/26.62 64.88/26.62 29: f11 -> f11 : A'=0, B'=0, C'=free_10, D'=0, E'=1+E, [ G>=1 && 0>=C && D==2 && free_10>=0 && 0==free_4 ], cost: 3 64.88/26.62 64.88/26.62 30: f11 -> f11 : A'=0, B'=free_4, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ 1>=free_4 && G>=1 && 0>=C && D==2 && free_10>=0 && free_4>=1 ], cost: 3 64.88/26.62 64.88/26.62 31: f11 -> f11 : A'=free_7, B'=free_7, C'=free_6, D'=1, E'=1+E, [ free_5>=0 && free_7>=0 && 1>=free_7 && free_6>=0 && G>=1 && 0>=C && D>=3 && 0>=free_5 && 0>=free_6 && free_7==free_5 ], cost: 3 64.88/26.62 64.88/26.62 32: f11 -> f11 : A'=free_7, B'=free_5, C'=free_6, D'=1, E'=1+E, G'=-1+G, [ free_5>=0 && free_7>=0 && 1>=free_7 && free_6>=0 && G>=1 && 0>=C && D>=3 && 0>=free_5 && 0>=free_6 && free_7>=1+free_5 ], cost: 3 64.88/26.62 64.88/26.62 33: f11 -> f11 : A'=free_7, B'=free_7, C'=-1+free_6, D'=0, E'=1+E, [ free_5>=0 && 1>=free_5 && free_7>=0 && 1>=free_7 && G>=1 && 0>=C && D>=3 && free_6>=1 && free_7==free_5 ], cost: 3 64.88/26.62 64.88/26.62 34: f11 -> f11 : A'=free_7, B'=free_5, C'=-1+free_6, D'=0, E'=1+E, G'=-1+G, [ free_5>=0 && 1>=free_5 && free_7>=0 && 1>=free_7 && G>=1 && 0>=C && D>=3 && free_6>=1 && free_5>=1+free_7 ], cost: 3 64.88/26.62 64.88/26.62 35: f11 -> f11 : A'=free_7, B'=free_5, C'=-1+free_6, D'=0, E'=1+E, G'=-1+G, [ free_5>=0 && 1>=free_5 && free_7>=0 && 1>=free_7 && G>=1 && 0>=C && D>=3 && free_6>=1 && free_7>=1+free_5 ], cost: 3 64.88/26.62 64.88/26.62 36: f11 -> f11 : A'=free_9, B'=free_9, C'=-1+C, D'=1+D, [ free_8>=0 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && 0>=free_8 && 0>=-1+C && 0>=D && free_9==free_8 ], cost: 3 64.88/26.62 64.88/26.62 37: f11 -> f11 : A'=free_9, B'=free_8, C'=-1+C, D'=1+D, G'=-1+G, [ free_8>=0 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && 0>=free_8 && 0>=-1+C && 0>=D && free_9>=1+free_8 ], cost: 3 64.88/26.62 64.88/26.62 38: f11 -> f11 : A'=free_9, B'=free_9, C'=-1+C, D'=1+D, [ 1>=free_8 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && free_8>=1 && 0>=-1+C && D==1 && free_9==free_8 ], cost: 3 64.88/26.62 64.88/26.62 39: f11 -> f11 : A'=free_9, B'=free_8, C'=-1+C, D'=1+D, G'=-1+G, [ 1>=free_8 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && free_8>=1 && 0>=-1+C && D==1 && free_8>=1+free_9 ], cost: 3 64.88/26.62 64.88/26.62 40: f11 -> f11 : A'=free_9, B'=free_9, C'=-1+C, D'=1+D, [ free_8>=0 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && 0>=free_8 && 0>=-1+C && D==2 && free_9==free_8 ], cost: 3 64.88/26.62 64.88/26.62 41: f11 -> f11 : A'=free_9, B'=free_8, C'=-1+C, D'=1+D, G'=-1+G, [ free_8>=0 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && 0>=free_8 && 0>=-1+C && D==2 && free_9>=1+free_8 ], cost: 3 64.88/26.62 64.88/26.62 42: f11 -> f11 : A'=free_9, B'=free_9, C'=free_10, D'=0, E'=1+E, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && free_10>=0 && 0>=-1+C && D>=3 && free_9==free_8 ], cost: 3 64.88/26.62 64.88/26.62 43: f11 -> f11 : A'=free_9, B'=free_8, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && free_10>=0 && 0>=-1+C && D>=3 && free_8>=1+free_9 ], cost: 3 64.88/26.62 64.88/26.62 44: f11 -> f11 : A'=free_9, B'=free_8, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && C>=1 && G>=1 && free_10>=0 && 0>=-1+C && D>=3 && free_9>=1+free_8 ], cost: 3 64.88/26.62 64.88/26.62 45: f11 -> f11 : A'=free_9, B'=free_9, C'=-2+C, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 && free_9==free_8 ], cost: 3 64.88/26.63 64.88/26.63 46: f11 -> f11 : A'=free_9, B'=free_8, C'=-2+C, G'=-1+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 && free_8>=1+free_9 ], cost: 3 64.88/26.63 64.88/26.63 47: f11 -> f11 : A'=free_9, B'=free_8, C'=-2+C, G'=-1+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 && free_9>=1+free_8 ], cost: 3 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 Accelerating simple loops of location 2. 64.88/26.63 64.88/26.63 Simplified some of the simple loops (and removed duplicate rules). 64.88/26.63 64.88/26.63 Accelerating the following rules: 64.88/26.63 64.88/26.63 26: f11 -> f11 : A'=0, B'=0, D'=2+D, [ G>=1 && 0>=C && 0>=1+D ], cost: 3 64.88/26.63 64.88/26.63 27: f11 -> f11 : A'=0, B'=1, D'=2+D, G'=-1+G, [ G>=1 && 0>=C && 1+D==1 ], cost: 3 64.88/26.63 64.88/26.63 28: f11 -> f11 : A'=1, B'=0, D'=2+D, G'=-1+G, [ G>=1 && 0>=C && D==1 ], cost: 3 64.88/26.63 64.88/26.63 29: f11 -> f11 : A'=0, B'=0, C'=free_10, D'=0, E'=1+E, [ G>=1 && 0>=C && D==2 && free_10>=0 ], cost: 3 64.88/26.63 64.88/26.63 30: f11 -> f11 : A'=0, B'=1, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ G>=1 && 0>=C && D==2 && free_10>=0 ], cost: 3 64.88/26.63 64.88/26.63 31: f11 -> f11 : A'=0, B'=0, C'=0, D'=1, E'=1+E, [ G>=1 && 0>=C && D>=3 ], cost: 3 64.88/26.63 64.88/26.63 32: f11 -> f11 : A'=free_7, B'=0, C'=0, D'=1, E'=1+E, G'=-1+G, [ 1>=free_7 && G>=1 && 0>=C && D>=3 && free_7>=1 ], cost: 3 64.88/26.63 64.88/26.63 33: f11 -> f11 : A'=free_5, B'=free_5, C'=-1+free_6, D'=0, E'=1+E, [ G>=1 && 0>=C && D>=3 && free_6>=1 ], cost: 3 64.88/26.63 64.88/26.63 34: f11 -> f11 : A'=free_7, B'=free_5, C'=-1+free_6, D'=0, E'=1+E, G'=-1+G, [ free_5>=0 && 1>=free_5 && free_7>=0 && 1>=free_7 && G>=1 && 0>=C && D>=3 && free_6>=1 && free_5>=1+free_7 ], cost: 3 64.88/26.63 64.88/26.63 35: f11 -> f11 : A'=free_7, B'=free_5, C'=-1+free_6, D'=0, E'=1+E, G'=-1+G, [ free_5>=0 && 1>=free_5 && free_7>=0 && 1>=free_7 && G>=1 && 0>=C && D>=3 && free_6>=1 && free_7>=1+free_5 ], cost: 3 64.88/26.63 64.88/26.63 36: f11 -> f11 : A'=0, B'=0, C'=-1+C, D'=1+D, [ 1-C==0 && G>=1 && 0>=D ], cost: 3 64.88/26.63 64.88/26.63 37: f11 -> f11 : A'=free_9, B'=0, C'=-1+C, D'=1+D, G'=-1+G, [ 1>=free_9 && 1-C==0 && G>=1 && 0>=D && free_9>=1 ], cost: 3 64.88/26.63 64.88/26.63 38: f11 -> f11 : A'=1, B'=1, C'=-1+C, D'=1+D, [ 1-C==0 && G>=1 && D==1 ], cost: 3 64.88/26.63 64.88/26.63 39: f11 -> f11 : A'=free_9, B'=1, C'=-1+C, D'=1+D, G'=-1+G, [ free_9>=0 && 1-C==0 && G>=1 && D==1 && 1>=1+free_9 ], cost: 3 64.88/26.63 64.88/26.63 40: f11 -> f11 : A'=0, B'=0, C'=-1+C, D'=1+D, [ 1-C==0 && G>=1 && D==2 ], cost: 3 64.88/26.63 64.88/26.63 41: f11 -> f11 : A'=free_9, B'=0, C'=-1+C, D'=1+D, G'=-1+G, [ 1>=free_9 && 1-C==0 && G>=1 && D==2 && free_9>=1 ], cost: 3 64.88/26.63 64.88/26.63 42: f11 -> f11 : A'=free_8, B'=free_8, C'=free_10, D'=0, E'=1+E, [ 1-C==0 && G>=1 && free_10>=0 && D>=3 ], cost: 3 64.88/26.63 64.88/26.63 43: f11 -> f11 : A'=free_9, B'=free_8, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 1-C==0 && G>=1 && free_10>=0 && D>=3 && free_8>=1+free_9 ], cost: 3 64.88/26.63 64.88/26.63 44: f11 -> f11 : A'=free_9, B'=free_8, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 1-C==0 && G>=1 && free_10>=0 && D>=3 && free_9>=1+free_8 ], cost: 3 64.88/26.63 64.88/26.63 45: f11 -> f11 : A'=free_8, B'=free_8, C'=-2+C, [ G>=1 && -1+C>=1 ], cost: 3 64.88/26.63 64.88/26.63 46: f11 -> f11 : A'=free_9, B'=free_8, C'=-2+C, G'=-1+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 && free_8>=1+free_9 ], cost: 3 64.88/26.63 64.88/26.63 47: f11 -> f11 : A'=free_9, B'=free_8, C'=-2+C, G'=-1+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 && free_9>=1+free_8 ], cost: 3 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 Accelerated rule 26 with metering function meter (where 2*meter==-D), yielding the new rule 48. 64.88/26.63 64.88/26.63 Accelerated rule 27 with metering function meter_1 (where 2*meter_1==-D), yielding the new rule 49. 64.88/26.63 64.88/26.63 Accelerated rule 28 with metering function meter_2 (where 2*meter_2==1-D), yielding the new rule 50. 64.88/26.63 64.88/26.63 Accelerated rule 29 with metering function meter_3 (where 2*meter_3==-2+D), yielding the new rule 51. 64.88/26.63 64.88/26.63 Accelerated rule 30 with metering function meter_4 (where 2*meter_4==-2+D), yielding the new rule 52. 64.88/26.63 64.88/26.63 Found no metering function for rule 31. 64.88/26.63 64.88/26.63 Found no metering function for rule 32. 64.88/26.63 64.88/26.63 Found no metering function for rule 33. 64.88/26.63 64.88/26.63 Found no metering function for rule 34. 64.88/26.63 64.88/26.63 Found no metering function for rule 35. 64.88/26.63 64.88/26.63 Accelerated rule 36 with metering function -1+C, yielding the new rule 53. 64.88/26.63 64.88/26.63 Accelerated rule 37 with metering function -1+C, yielding the new rule 54. 64.88/26.63 64.88/26.63 Accelerated rule 38 with metering function meter_5 (where 2*meter_5==C-D), yielding the new rule 55. 64.88/26.63 64.88/26.63 Accelerated rule 39 with metering function meter_6 (where 2*meter_6==C-D), yielding the new rule 56. 64.88/26.63 64.88/26.63 Accelerated rule 40 with metering function meter_7 (where 2*meter_7==1+C-D), yielding the new rule 57. 64.88/26.63 64.88/26.63 Accelerated rule 41 with metering function meter_8 (where 2*meter_8==1+C-D), yielding the new rule 58. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {free_10==0} 64.88/26.63 64.88/26.63 Accelerated rule 42 with metering function -1+C, yielding the new rule 59. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {free_10==0} 64.88/26.63 64.88/26.63 Accelerated rule 43 with metering function -1+C, yielding the new rule 60. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {free_10==0} 64.88/26.63 64.88/26.63 Accelerated rule 44 with metering function -1+C, yielding the new rule 61. 64.88/26.63 64.88/26.63 Accelerated rule 45 with metering function meter_9 (where 2*meter_9==-1+C), yielding the new rule 62. 64.88/26.63 64.88/26.63 Accelerated rule 46 with metering function meter_10 (where 2*meter_10==-1+C) (after adding C<=G), yielding the new rule 63. 64.88/26.63 64.88/26.63 Accelerated rule 46 with backward acceleration, yielding the new rule 64. 64.88/26.63 64.88/26.63 Accelerated rule 47 with metering function meter_11 (where 2*meter_11==-1+C) (after adding C<=G), yielding the new rule 65. 64.88/26.63 64.88/26.63 Accelerated rule 47 with backward acceleration, yielding the new rule 66. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter==1} 64.88/26.63 64.88/26.63 Nested simple loops 36 (outer loop) and 48 (inner loop) with metering function -1+C, resulting in the new rules: 67. 64.88/26.63 64.88/26.63 Nested simple loops 37 (outer loop) and 48 (inner loop) with metering function -1+C, resulting in the new rules: 68. 64.88/26.63 64.88/26.63 Nested simple loops 45 (outer loop) and 48 (inner loop) with metering function meter_13 (where 2*meter_13==-2+C), resulting in the new rules: 69. 64.88/26.63 64.88/26.63 Nested simple loops 46 (outer loop) and 48 (inner loop) with metering function meter_14 (where 2*meter_14==-2+C), resulting in the new rules: 70. 64.88/26.63 64.88/26.63 Nested simple loops 47 (outer loop) and 48 (inner loop) with metering function meter_15 (where 2*meter_15==-2+C), resulting in the new rules: 71. 64.88/26.63 64.88/26.63 Nested simple loops 29 (outer loop) and 62 (inner loop) with metering function meter_16 (where 2*meter_16==-2+D), resulting in the new rules: 72. 64.88/26.63 64.88/26.63 Nested simple loops 30 (outer loop) and 62 (inner loop) with metering function meter_17 (where 2*meter_17==-2+D), resulting in the new rules: 73. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_9==1} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_9==1} 64.88/26.63 64.88/26.63 Nested simple loops 38 (outer loop) and 62 (inner loop) with metering function 1-D, resulting in the new rules: 74. 64.88/26.63 64.88/26.63 Nested simple loops 39 (outer loop) and 62 (inner loop) with metering function 1-D, resulting in the new rules: 75. 64.88/26.63 64.88/26.63 Nested simple loops 40 (outer loop) and 62 (inner loop) with metering function 2-D, resulting in the new rules: 76. 64.88/26.63 64.88/26.63 Nested simple loops 41 (outer loop) and 62 (inner loop) with metering function 2-D, resulting in the new rules: 77. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_9==1,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_9==1,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_9==1,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_9==1} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_9==1} 64.88/26.63 64.88/26.63 Nested simple loops 29 (outer loop) and 63 (inner loop) with metering function meter_25 (where 2*meter_25==-2+D), resulting in the new rules: 78. 64.88/26.63 64.88/26.63 Nested simple loops 30 (outer loop) and 63 (inner loop) with metering function meter_26 (where 2*meter_26==-2+D), resulting in the new rules: 79. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_10==1} 64.88/26.63 64.88/26.63 Nested simple loops 38 (outer loop) and 63 (inner loop) with metering function 1-D, resulting in the new rules: 80. 64.88/26.63 64.88/26.63 Nested simple loops 39 (outer loop) and 63 (inner loop) with metering function 1-D, resulting in the new rules: 81. 64.88/26.63 64.88/26.63 Nested simple loops 40 (outer loop) and 63 (inner loop) with metering function 2-D, resulting in the new rules: 82. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_10==1,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_10==1,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_10==1} 64.88/26.63 64.88/26.63 Nested simple loops 27 (outer loop) and 64 (inner loop) with metering function meter_31 (where 2*meter_31==-D), resulting in the new rules: 83. 64.88/26.63 64.88/26.63 Nested simple loops 28 (outer loop) and 64 (inner loop) with metering function meter_32 (where 2*meter_32==1-D), resulting in the new rules: 84. 64.88/26.63 64.88/26.63 Nested simple loops 29 (outer loop) and 64 (inner loop) with metering function meter_33 (where 2*meter_33==-2+D), resulting in the new rules: 85. 64.88/26.63 64.88/26.63 Nested simple loops 30 (outer loop) and 64 (inner loop) with metering function meter_34 (where 2*meter_34==-2+D), resulting in the new rules: 86. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G,free_6==1} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==G,free_6==3} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G,free_6==1} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G,free_6==3} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G,free_6==1} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G,free_6==3} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G} 64.88/26.63 64.88/26.63 Nested simple loops 38 (outer loop) and 64 (inner loop) with metering function 1-D, resulting in the new rules: 87. 64.88/26.63 64.88/26.63 Nested simple loops 39 (outer loop) and 64 (inner loop) with metering function 1-D, resulting in the new rules: 88. 64.88/26.63 64.88/26.63 Nested simple loops 40 (outer loop) and 64 (inner loop) with metering function 2-D, resulting in the new rules: 89. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==G,free_10==2} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k==-1+G,free_10==2} 64.88/26.63 64.88/26.63 Nested simple loops 29 (outer loop) and 65 (inner loop) with metering function meter_42 (where 2*meter_42==-2+D), resulting in the new rules: 90. 64.88/26.63 64.88/26.63 Nested simple loops 30 (outer loop) and 65 (inner loop) with metering function meter_43 (where 2*meter_43==-2+D), resulting in the new rules: 91. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_11==1} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_11==1} 64.88/26.63 64.88/26.63 Nested simple loops 38 (outer loop) and 65 (inner loop) with metering function 1-D, resulting in the new rules: 92. 64.88/26.63 64.88/26.63 Nested simple loops 40 (outer loop) and 65 (inner loop) with metering function 2-D, resulting in the new rules: 93. 64.88/26.63 64.88/26.63 Nested simple loops 41 (outer loop) and 65 (inner loop) with metering function 2-D, resulting in the new rules: 94. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_11==1,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_11==1,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {meter_11==1} 64.88/26.63 64.88/26.63 Nested simple loops 27 (outer loop) and 66 (inner loop) with metering function meter_49 (where 2*meter_49==-D), resulting in the new rules: 95. 64.88/26.63 64.88/26.63 Nested simple loops 28 (outer loop) and 66 (inner loop) with metering function meter_50 (where 2*meter_50==1-D), resulting in the new rules: 96. 64.88/26.63 64.88/26.63 Nested simple loops 29 (outer loop) and 66 (inner loop) with metering function meter_51 (where 2*meter_51==-2+D), resulting in the new rules: 97. 64.88/26.63 64.88/26.63 Nested simple loops 30 (outer loop) and 66 (inner loop) with metering function meter_52 (where 2*meter_52==-2+D), resulting in the new rules: 98. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G,free_6==1} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==G,free_6==3} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G,free_6==1} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G,free_6==3} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G,free_6==1} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G,free_6==3} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G} 64.88/26.63 64.88/26.63 Nested simple loops 38 (outer loop) and 66 (inner loop) with metering function 1-D, resulting in the new rules: 99. 64.88/26.63 64.88/26.63 Nested simple loops 40 (outer loop) and 66 (inner loop) with metering function 2-D, resulting in the new rules: 100. 64.88/26.63 64.88/26.63 Nested simple loops 41 (outer loop) and 66 (inner loop) with metering function 2-D, resulting in the new rules: 101. 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==G,free_10==2} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G,free_10==0} 64.88/26.63 64.88/26.63 During metering: Instantiating temporary variables by {k_1==-1+G,free_10==2} 64.88/26.63 64.88/26.63 Removing the simple loops: 26 27 28 29 30 36 37 38 39 40 41 42 43 44 45 46 47. 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 Accelerated all simple loops using metering functions (where possible): 64.88/26.63 64.88/26.63 Start location: f0 64.88/26.63 64.88/26.63 1: f0 -> f11 : A'=0, B'=0, C'=free_1, D'=0, E'=1, F'=free, G'=free, [ free_1>=0 && free>=1 ], cost: 1 64.88/26.63 64.88/26.63 31: f11 -> f11 : A'=0, B'=0, C'=0, D'=1, E'=1+E, [ G>=1 && 0>=C && D>=3 ], cost: 3 64.88/26.63 64.88/26.63 32: f11 -> f11 : A'=free_7, B'=0, C'=0, D'=1, E'=1+E, G'=-1+G, [ 1>=free_7 && G>=1 && 0>=C && D>=3 && free_7>=1 ], cost: 3 64.88/26.63 64.88/26.63 33: f11 -> f11 : A'=free_5, B'=free_5, C'=-1+free_6, D'=0, E'=1+E, [ G>=1 && 0>=C && D>=3 && free_6>=1 ], cost: 3 64.88/26.63 64.88/26.63 34: f11 -> f11 : A'=free_7, B'=free_5, C'=-1+free_6, D'=0, E'=1+E, G'=-1+G, [ free_5>=0 && 1>=free_5 && free_7>=0 && 1>=free_7 && G>=1 && 0>=C && D>=3 && free_6>=1 && free_5>=1+free_7 ], cost: 3 64.88/26.63 64.88/26.63 35: f11 -> f11 : A'=free_7, B'=free_5, C'=-1+free_6, D'=0, E'=1+E, G'=-1+G, [ free_5>=0 && 1>=free_5 && free_7>=0 && 1>=free_7 && G>=1 && 0>=C && D>=3 && free_6>=1 && free_7>=1+free_5 ], cost: 3 64.88/26.63 64.88/26.63 48: f11 -> f11 : A'=0, B'=0, D'=2*meter+D, [ G>=1 && 0>=C && 0>=1+D && 2*meter==-D && meter>=1 ], cost: 3*meter 64.88/26.63 64.88/26.63 49: f11 -> f11 : A'=0, B'=1, D'=2*meter_1+D, G'=-meter_1+G, [ G>=1 && 0>=C && 1+D==1 && 2*meter_1==-D && meter_1>=1 ], cost: 3*meter_1 64.88/26.63 64.88/26.63 50: f11 -> f11 : A'=1, B'=0, D'=2*meter_2+D, G'=-meter_2+G, [ G>=1 && 0>=C && D==1 && 2*meter_2==1-D && meter_2>=1 ], cost: 3*meter_2 64.88/26.63 64.88/26.63 51: f11 -> f11 : A'=0, B'=0, C'=free_10, D'=0, E'=meter_3+E, [ G>=1 && 0>=C && D==2 && free_10>=0 && 2*meter_3==-2+D && meter_3>=1 ], cost: 3*meter_3 64.88/26.63 64.88/26.63 52: f11 -> f11 : A'=0, B'=1, C'=free_10, D'=0, E'=meter_4+E, G'=G-meter_4, [ G>=1 && 0>=C && D==2 && free_10>=0 && 2*meter_4==-2+D && meter_4>=1 ], cost: 3*meter_4 64.88/26.63 64.88/26.63 53: f11 -> f11 : A'=0, B'=0, C'=1, D'=-1+C+D, [ 1-C==0 && G>=1 && 0>=D && -1+C>=1 ], cost: -3+3*C 64.88/26.63 64.88/26.63 54: f11 -> f11 : A'=free_9, B'=0, C'=1, D'=-1+C+D, G'=1-C+G, [ 1>=free_9 && 1-C==0 && G>=1 && 0>=D && free_9>=1 && -1+C>=1 ], cost: -3+3*C 64.88/26.63 64.88/26.63 55: f11 -> f11 : A'=1, B'=1, C'=C-meter_5, D'=D+meter_5, [ 1-C==0 && G>=1 && D==1 && 2*meter_5==C-D && meter_5>=1 ], cost: 3*meter_5 64.88/26.63 64.88/26.63 56: f11 -> f11 : A'=free_9, B'=1, C'=C-meter_6, D'=D+meter_6, G'=G-meter_6, [ free_9>=0 && 1-C==0 && G>=1 && D==1 && 1>=1+free_9 && 2*meter_6==C-D && meter_6>=1 ], cost: 3*meter_6 64.88/26.63 64.88/26.63 57: f11 -> f11 : A'=0, B'=0, C'=C-meter_7, D'=D+meter_7, [ 1-C==0 && G>=1 && D==2 && 2*meter_7==1+C-D && meter_7>=1 ], cost: 3*meter_7 64.88/26.63 64.88/26.63 58: f11 -> f11 : A'=free_9, B'=0, C'=C-meter_8, D'=meter_8+D, G'=-meter_8+G, [ 1>=free_9 && 1-C==0 && G>=1 && D==2 && free_9>=1 && 2*meter_8==1+C-D && meter_8>=1 ], cost: 3*meter_8 64.88/26.63 64.88/26.63 59: f11 -> f11 : A'=free_8, B'=free_8, C'=0, D'=0, E'=-1+C+E, [ 1-C==0 && G>=1 && D>=3 && -1+C>=1 ], cost: -3+3*C 64.88/26.63 64.88/26.63 60: f11 -> f11 : A'=free_9, B'=free_8, C'=0, D'=0, E'=-1+C+E, G'=1-C+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 1-C==0 && G>=1 && D>=3 && free_8>=1+free_9 && -1+C>=1 ], cost: -3+3*C 64.88/26.63 64.88/26.63 61: f11 -> f11 : A'=free_9, B'=free_8, C'=0, D'=0, E'=-1+C+E, G'=1-C+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 1-C==0 && G>=1 && D>=3 && free_9>=1+free_8 && -1+C>=1 ], cost: -3+3*C 64.88/26.63 64.88/26.63 62: f11 -> f11 : A'=free_8, B'=free_8, C'=C-2*meter_9, [ G>=1 && -1+C>=1 && 2*meter_9==-1+C && meter_9>=1 ], cost: 3*meter_9 64.88/26.63 64.88/26.63 63: f11 -> f11 : A'=free_9, B'=free_8, C'=C-2*meter_10, G'=G-meter_10, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 && free_8>=1+free_9 && C<=G && 2*meter_10==-1+C && meter_10>=1 ], cost: 3*meter_10 64.88/26.63 64.88/26.63 64: f11 -> f11 : A'=free_9, B'=free_8, C'=-2*k+C, G'=-k+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 && free_8>=1+free_9 && k>0 && 1-k+G>=1 && 1-2*k+C>=1 ], cost: 3*k 64.88/26.63 64.88/26.63 65: f11 -> f11 : A'=free_9, B'=free_8, C'=-2*meter_11+C, G'=-meter_11+G, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 && free_9>=1+free_8 && C<=G && 2*meter_11==-1+C && meter_11>=1 ], cost: 3*meter_11 64.88/26.63 64.88/26.63 66: f11 -> f11 : A'=free_9, B'=free_8, C'=C-2*k_1, G'=G-k_1, [ free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 && free_9>=1+free_8 && k_1>0 && 1+G-k_1>=1 && 1+C-2*k_1>=1 ], cost: 3*k_1 64.88/26.63 64.88/26.63 67: f11 -> f11 : A'=0, B'=0, C'=1, D'=-1+C+D+2*meter*(-1+C), [ 1-C==0 && G>=1 && 0>=2+D && 2*meter==-1-D && meter>=1 && -1+C>=1 ], cost: -3+3*C+3*meter*(-1+C) 64.88/26.63 64.88/26.63 68: f11 -> f11 : A'=0, B'=0, C'=1, D'=-1+C+D+2*meter*(-1+C), G'=1-C+G, [ 1-C==0 && -1+G>=1 && 0>=2+D && 2*meter==-1-D && meter>=1 && -1+C>=1 ], cost: -3+3*C+3*meter*(-1+C) 64.88/26.63 64.88/26.63 69: f11 -> f11 : A'=0, B'=0, C'=-2*meter_13+C, D'=D+2*meter_13*meter, [ G>=1 && 2-C==0 && 0>=1+D && 2*meter==-D && meter>=1 && 2*meter_13==-2+C && meter_13>=1 ], cost: 3*meter_13+3*meter_13*meter 64.88/26.63 64.88/26.63 70: f11 -> f11 : A'=0, B'=0, C'=C-2*meter_14, D'=2*meter*meter_14+D, G'=G-meter_14, [ 2-C==0 && -1+G>=1 && 0>=1+D && 2*meter==-D && meter>=1 && 2*meter_14==-2+C && meter_14>=1 ], cost: 3*meter*meter_14+3*meter_14 64.88/26.63 64.88/26.63 71: f11 -> f11 : A'=0, B'=0, C'=C-2*meter_15, D'=D+2*meter_15*meter, G'=-meter_15+G, [ 2-C==0 && -1+G>=1 && 0>=1+D && 2*meter==-D && meter>=1 && 2*meter_15==-2+C && meter_15>=1 ], cost: 3*meter_15+3*meter_15*meter 64.88/26.63 64.88/26.63 72: f11 -> f11 : A'=free_8, B'=free_8, C'=1, D'=0, E'=meter_16+E, [ G>=1 && 0>=C && D==2 && 2*meter_9>=1 && meter_9>=1 && 2*meter_16==-2+D && meter_16>=1 ], cost: 3*meter_16+3*meter_16*meter_9 64.88/26.63 64.88/26.63 73: f11 -> f11 : A'=free_8, B'=free_8, C'=1, D'=0, E'=meter_17+E, G'=G-meter_17, [ 0>=C && D==2 && -1+G>=1 && 2*meter_9>=1 && meter_9>=1 && 2*meter_17==-2+D && meter_17>=1 ], cost: 3*meter_17*meter_9+3*meter_17 64.88/26.63 64.88/26.63 74: f11 -> f11 : A'=1, B'=1, C'=-1+C+D+2*(-1+D)*meter_9, D'=1, [ G>=1 && -1+C>=1 && 2*meter_9==-1+C && meter_9>=1 && D==1 && 1-D>=1 ], cost: 3-3*D-3*(-1+D)*meter_9 64.88/26.63 64.88/26.63 75: f11 -> f11 : A'=0, B'=1, C'=-1+C+D+2*(-1+D)*meter_9, D'=1, G'=-1+G+D, [ G>=1 && -1+C>=1 && 2*meter_9==-1+C && meter_9>=1 && D==1 && 1-D>=1 ], cost: 3-3*D-3*(-1+D)*meter_9 64.88/26.63 64.88/26.63 76: f11 -> f11 : A'=0, B'=0, C'=-2+C+2*(-2+D)*meter_9+D, D'=2, [ G>=1 && -1+C>=1 && 2*meter_9==-1+C && meter_9>=1 && D==2 && 2-D>=1 ], cost: 6-3*(-2+D)*meter_9-3*D 64.88/26.63 64.88/26.63 77: f11 -> f11 : A'=1, B'=0, C'=-2+C+2*(-2+D)*meter_9+D, D'=2, G'=-2+G+D, [ G>=1 && -1+C>=1 && 2*meter_9==-1+C && meter_9>=1 && D==2 && 2-D>=1 ], cost: 6-3*(-2+D)*meter_9-3*D 64.88/26.63 64.88/26.63 78: f11 -> f11 : A'=free_9, B'=free_8, C'=1, D'=0, E'=meter_25+E, G'=G-meter_25*meter_10, [ G>=1 && 0>=C && D==2 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 2*meter_10>=1 && free_8>=1+free_9 && 1+2*meter_10<=G && meter_10>=1 && 2*meter_25==-2+D && meter_25>=1 ], cost: 3*meter_25+3*meter_25*meter_10 64.88/26.63 64.88/26.63 79: f11 -> f11 : A'=free_9, B'=free_8, C'=1, D'=0, E'=meter_26+E, G'=-meter_26+G-meter_26*meter_10, [ 0>=C && D==2 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && -1+G>=1 && 2*meter_10>=1 && free_8>=1+free_9 && 1+2*meter_10<=-1+G && meter_10>=1 && 2*meter_26==-2+D && meter_26>=1 ], cost: 3*meter_26+3*meter_26*meter_10 64.88/26.63 64.88/26.63 80: f11 -> f11 : A'=1, B'=1, C'=-1+C+D+2*(-1+D)*meter_10, D'=1, G'=G+(-1+D)*meter_10, [ G>=1 && -1+C>=1 && C<=G && 2*meter_10==-1+C && meter_10>=1 && G-meter_10>=1 && D==1 && 1-D>=1 ], cost: 3-3*D-3*(-1+D)*meter_10 64.88/26.63 64.88/26.63 81: f11 -> f11 : A'=0, B'=1, C'=-1+C+D+2*(-1+D)*meter_10, D'=1, G'=-1+G+D+(-1+D)*meter_10, [ G>=1 && -1+C>=1 && C<=G && 2*meter_10==-1+C && meter_10>=1 && G-meter_10>=1 && D==1 && 1-D>=1 ], cost: 3-3*D-3*(-1+D)*meter_10 64.88/26.63 64.88/26.63 82: f11 -> f11 : A'=0, B'=0, C'=-2+C+2*meter_10*(-2+D)+D, D'=2, G'=meter_10*(-2+D)+G, [ G>=1 && -1+C>=1 && C<=G && 2*meter_10==-1+C && meter_10>=1 && G-meter_10>=1 && D==2 && 2-D>=1 ], cost: 6-3*meter_10*(-2+D)-3*D 64.88/26.63 64.88/26.63 83: f11 -> f11 : A'=0, B'=1, C'=C-2*k*meter_31, D'=D+2*meter_31, G'=G-meter_31-k*meter_31, [ G>=1 && -1+C>=1 && k>0 && 2*k-C==0 && -k+G>=1 && 1+D==1 && 2*meter_31==-D && meter_31>=1 ], cost: 3*meter_31+3*k*meter_31 64.88/26.63 64.88/26.63 84: f11 -> f11 : A'=1, B'=0, C'=C-2*k*meter_32, D'=D+2*meter_32, G'=-k*meter_32+G-meter_32, [ G>=1 && -1+C>=1 && k>0 && 2*k-C==0 && -k+G>=1 && D==1 && 2*meter_32==1-D && meter_32>=1 ], cost: 3*k*meter_32+3*meter_32 64.88/26.63 64.88/26.63 85: f11 -> f11 : A'=0, B'=0, C'=free_10, D'=0, E'=meter_33+E, G'=-meter_33*k+G, [ G>=1 && -1+C>=1 && k>0 && 2*k-C==0 && -k+G>=1 && D==2 && free_10>=0 && 2*meter_33==-2+D && meter_33>=1 ], cost: 3*meter_33+3*meter_33*k 64.88/26.63 64.88/26.63 86: f11 -> f11 : A'=0, B'=1, C'=free_10, D'=0, E'=meter_34+E, G'=-meter_34+G-k*meter_34, [ G>=1 && -1+C>=1 && k>0 && 2*k-C==0 && -k+G>=1 && D==2 && free_10>=0 && 2*meter_34==-2+D && meter_34>=1 ], cost: 3*meter_34+3*k*meter_34 64.88/26.63 64.88/26.63 87: f11 -> f11 : A'=1, B'=1, C'=-1+2*k*(-1+D)+C+D, D'=1, G'=k*(-1+D)+G, [ G>=1 && -1+C>=1 && k>0 && 1+2*k-C==0 && -k+G>=1 && D==1 && 1-D>=1 ], cost: 3-3*k*(-1+D)-3*D 64.88/26.63 64.88/26.63 88: f11 -> f11 : A'=0, B'=1, C'=-1+2*k*(-1+D)+C+D, D'=1, G'=-1+k*(-1+D)+G+D, [ G>=1 && -1+C>=1 && k>0 && 1+2*k-C==0 && -k+G>=1 && D==1 && 1-D>=1 ], cost: 3-3*k*(-1+D)-3*D 64.88/26.63 64.88/26.63 89: f11 -> f11 : A'=0, B'=0, C'=-2+C+D+2*k*(-2+D), D'=2, G'=G+k*(-2+D), [ G>=1 && -1+C>=1 && k>0 && 1+2*k-C==0 && -k+G>=1 && D==2 && 2-D>=1 ], cost: 6-3*D-3*k*(-2+D) 64.88/26.63 64.88/26.63 90: f11 -> f11 : A'=free_9, B'=free_8, C'=1, D'=0, E'=meter_42+E, G'=-meter_11*meter_42+G, [ G>=1 && 0>=C && D==2 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 2*meter_11>=1 && free_9>=1+free_8 && 1+2*meter_11<=G && meter_11>=1 && 2*meter_42==-2+D && meter_42>=1 ], cost: 3*meter_11*meter_42+3*meter_42 64.88/26.63 64.88/26.63 91: f11 -> f11 : A'=free_9, B'=free_8, C'=1, D'=0, E'=meter_43+E, G'=-meter_11*meter_43+G-meter_43, [ 0>=C && D==2 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && -1+G>=1 && 2*meter_11>=1 && free_9>=1+free_8 && 1+2*meter_11<=-1+G && meter_11>=1 && 2*meter_43==-2+D && meter_43>=1 ], cost: 3*meter_11*meter_43+3*meter_43 64.88/26.63 64.88/26.63 92: f11 -> f11 : A'=1, B'=1, C'=-1+2*meter_11*(-1+D)+C+D, D'=1, G'=meter_11*(-1+D)+G, [ G>=1 && -1+C>=1 && C<=G && 2*meter_11==-1+C && meter_11>=1 && -meter_11+G>=1 && D==1 && 1-D>=1 ], cost: 3-3*meter_11*(-1+D)-3*D 64.88/26.63 64.88/26.63 93: f11 -> f11 : A'=0, B'=0, C'=-2+C+D+2*meter_11*(-2+D), D'=2, G'=G+meter_11*(-2+D), [ G>=1 && -1+C>=1 && C<=G && 2*meter_11==-1+C && meter_11>=1 && -meter_11+G>=1 && D==2 && 2-D>=1 ], cost: 6-3*D-3*meter_11*(-2+D) 64.88/26.63 64.88/26.63 94: f11 -> f11 : A'=1, B'=0, C'=-2+C+D+2*meter_11*(-2+D), D'=2, G'=-2+G+D+meter_11*(-2+D), [ G>=1 && -1+C>=1 && C<=G && 2*meter_11==-1+C && meter_11>=1 && -meter_11+G>=1 && D==2 && 2-D>=1 ], cost: 6-3*D-3*meter_11*(-2+D) 64.88/26.63 64.88/26.63 95: f11 -> f11 : A'=0, B'=1, C'=C-2*meter_49*k_1, D'=2*meter_49+D, G'=-meter_49+G-meter_49*k_1, [ G>=1 && -1+C>=1 && k_1>0 && -C+2*k_1==0 && G-k_1>=1 && 1+D==1 && 2*meter_49==-D && meter_49>=1 ], cost: 3*meter_49+3*meter_49*k_1 64.88/26.63 64.88/26.63 96: f11 -> f11 : A'=1, B'=0, C'=C-2*meter_50*k_1, D'=2*meter_50+D, G'=-meter_50*k_1-meter_50+G, [ G>=1 && -1+C>=1 && k_1>0 && -C+2*k_1==0 && G-k_1>=1 && D==1 && 2*meter_50==1-D && meter_50>=1 ], cost: 3*meter_50*k_1+3*meter_50 64.88/26.63 64.88/26.63 97: f11 -> f11 : A'=0, B'=0, C'=free_10, D'=0, E'=meter_51+E, G'=-k_1*meter_51+G, [ G>=1 && -1+C>=1 && k_1>0 && -C+2*k_1==0 && G-k_1>=1 && D==2 && free_10>=0 && 2*meter_51==-2+D && meter_51>=1 ], cost: 3*k_1*meter_51+3*meter_51 64.88/26.63 64.88/26.63 98: f11 -> f11 : A'=0, B'=1, C'=free_10, D'=0, E'=E+meter_52, G'=-k_1*meter_52+G-meter_52, [ G>=1 && -1+C>=1 && k_1>0 && -C+2*k_1==0 && G-k_1>=1 && D==2 && free_10>=0 && 2*meter_52==-2+D && meter_52>=1 ], cost: 3*k_1*meter_52+3*meter_52 64.88/26.63 64.88/26.63 99: f11 -> f11 : A'=1, B'=1, C'=-1+C+D+2*(-1+D)*k_1, D'=1, G'=G+(-1+D)*k_1, [ G>=1 && -1+C>=1 && k_1>0 && 1-C+2*k_1==0 && G-k_1>=1 && D==1 && 1-D>=1 ], cost: 3-3*D-3*(-1+D)*k_1 64.88/26.63 64.88/26.63 100: f11 -> f11 : A'=0, B'=0, C'=-2+C+D+2*k_1*(-2+D), D'=2, G'=G+k_1*(-2+D), [ G>=1 && -1+C>=1 && k_1>0 && 1-C+2*k_1==0 && G-k_1>=1 && D==2 && 2-D>=1 ], cost: 6-3*D-3*k_1*(-2+D) 64.88/26.63 64.88/26.63 101: f11 -> f11 : A'=1, B'=0, C'=-2+C+D+2*k_1*(-2+D), D'=2, G'=-2+G+D+k_1*(-2+D), [ G>=1 && -1+C>=1 && k_1>0 && 1-C+2*k_1==0 && G-k_1>=1 && D==2 && 2-D>=1 ], cost: 6-3*D-3*k_1*(-2+D) 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 Chained accelerated rules (with incoming rules): 64.88/26.63 64.88/26.63 Start location: f0 64.88/26.63 64.88/26.63 1: f0 -> f11 : A'=0, B'=0, C'=free_1, D'=0, E'=1, F'=free, G'=free, [ free_1>=0 && free>=1 ], cost: 1 64.88/26.63 64.88/26.63 102: f0 -> f11 : A'=free_8, B'=free_8, C'=1, D'=0, E'=1, F'=free, G'=free, [ free>=1 && 2*meter_9>=1 && meter_9>=1 ], cost: 1+3*meter_9 64.88/26.63 64.88/26.63 103: f0 -> f11 : A'=free_9, B'=free_8, C'=1, D'=0, E'=1, F'=free, G'=-meter_10+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 2*meter_10>=1 && free_8>=1+free_9 && 1+2*meter_10<=free && meter_10>=1 ], cost: 1+3*meter_10 64.88/26.63 64.88/26.63 104: f0 -> f11 : A'=free_9, B'=free_8, C'=free_1-2*k, D'=0, E'=1, F'=free, G'=-k+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && -1+free_1>=1 && free_8>=1+free_9 && k>0 && 1-k+free>=1 && 1+free_1-2*k>=1 ], cost: 1+3*k 64.88/26.63 64.88/26.63 105: f0 -> f11 : A'=free_9, B'=free_8, C'=1, D'=0, E'=1, F'=free, G'=-meter_11+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 2*meter_11>=1 && free_9>=1+free_8 && 1+2*meter_11<=free && meter_11>=1 ], cost: 1+3*meter_11 64.88/26.63 64.88/26.63 106: f0 -> f11 : A'=free_9, B'=free_8, C'=free_1-2*k_1, D'=0, E'=1, F'=free, G'=-k_1+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && -1+free_1>=1 && free_9>=1+free_8 && k_1>0 && 1-k_1+free>=1 && 1+free_1-2*k_1>=1 ], cost: 1+3*k_1 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 Removed unreachable locations (and leaf rules with constant cost): 64.88/26.63 64.88/26.63 Start location: f0 64.88/26.63 64.88/26.63 102: f0 -> f11 : A'=free_8, B'=free_8, C'=1, D'=0, E'=1, F'=free, G'=free, [ free>=1 && 2*meter_9>=1 && meter_9>=1 ], cost: 1+3*meter_9 64.88/26.63 64.88/26.63 103: f0 -> f11 : A'=free_9, B'=free_8, C'=1, D'=0, E'=1, F'=free, G'=-meter_10+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 2*meter_10>=1 && free_8>=1+free_9 && 1+2*meter_10<=free && meter_10>=1 ], cost: 1+3*meter_10 64.88/26.63 64.88/26.63 104: f0 -> f11 : A'=free_9, B'=free_8, C'=free_1-2*k, D'=0, E'=1, F'=free, G'=-k+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && -1+free_1>=1 && free_8>=1+free_9 && k>0 && 1-k+free>=1 && 1+free_1-2*k>=1 ], cost: 1+3*k 64.88/26.63 64.88/26.63 105: f0 -> f11 : A'=free_9, B'=free_8, C'=1, D'=0, E'=1, F'=free, G'=-meter_11+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 2*meter_11>=1 && free_9>=1+free_8 && 1+2*meter_11<=free && meter_11>=1 ], cost: 1+3*meter_11 64.88/26.63 64.88/26.63 106: f0 -> f11 : A'=free_9, B'=free_8, C'=free_1-2*k_1, D'=0, E'=1, F'=free, G'=-k_1+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && -1+free_1>=1 && free_9>=1+free_8 && k_1>0 && 1-k_1+free>=1 && 1+free_1-2*k_1>=1 ], cost: 1+3*k_1 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 ### Computing asymptotic complexity ### 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 Fully simplified ITS problem 64.88/26.63 64.88/26.63 Start location: f0 64.88/26.63 64.88/26.63 102: f0 -> f11 : A'=free_8, B'=free_8, C'=1, D'=0, E'=1, F'=free, G'=free, [ free>=1 && 2*meter_9>=1 && meter_9>=1 ], cost: 1+3*meter_9 64.88/26.63 64.88/26.63 103: f0 -> f11 : A'=free_9, B'=free_8, C'=1, D'=0, E'=1, F'=free, G'=-meter_10+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 2*meter_10>=1 && free_8>=1+free_9 && 1+2*meter_10<=free && meter_10>=1 ], cost: 1+3*meter_10 64.88/26.63 64.88/26.63 104: f0 -> f11 : A'=free_9, B'=free_8, C'=free_1-2*k, D'=0, E'=1, F'=free, G'=-k+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && -1+free_1>=1 && free_8>=1+free_9 && k>0 && 1-k+free>=1 && 1+free_1-2*k>=1 ], cost: 1+3*k 64.88/26.63 64.88/26.63 105: f0 -> f11 : A'=free_9, B'=free_8, C'=1, D'=0, E'=1, F'=free, G'=-meter_11+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && 2*meter_11>=1 && free_9>=1+free_8 && 1+2*meter_11<=free && meter_11>=1 ], cost: 1+3*meter_11 64.88/26.63 64.88/26.63 106: f0 -> f11 : A'=free_9, B'=free_8, C'=free_1-2*k_1, D'=0, E'=1, F'=free, G'=-k_1+free, [ free>=1 && free_8>=0 && 1>=free_8 && free_9>=0 && 1>=free_9 && -1+free_1>=1 && free_9>=1+free_8 && k_1>0 && 1-k_1+free>=1 && 1+free_1-2*k_1>=1 ], cost: 1+3*k_1 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 Computing asymptotic complexity for rule 102 64.88/26.63 64.88/26.63 Solved the limit problem by the following transformations: 64.88/26.63 64.88/26.63 Created initial limit problem: 64.88/26.63 64.88/26.63 2*meter_9 (+/+!), 1+3*meter_9 (+), free (+/+!) [not solved] 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 applying transformation rule (C) using substitution {free==1} 64.88/26.63 64.88/26.63 resulting limit problem: 64.88/26.63 64.88/26.63 1 (+/+!), 2*meter_9 (+/+!), 1+3*meter_9 (+) [not solved] 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 applying transformation rule (B), deleting 1 (+/+!) 64.88/26.63 64.88/26.63 resulting limit problem: 64.88/26.63 64.88/26.63 2*meter_9 (+/+!), 1+3*meter_9 (+) [not solved] 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 removing all constraints (solved by SMT) 64.88/26.63 64.88/26.63 resulting limit problem: [solved] 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 applying transformation rule (C) using substitution {meter_9==n} 64.88/26.63 64.88/26.63 resulting limit problem: 64.88/26.63 64.88/26.63 [solved] 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 Solution: 64.88/26.63 64.88/26.63 meter_9 / n 64.88/26.63 64.88/26.63 free / 1 64.88/26.63 64.88/26.63 Resulting cost 1+3*n has complexity: Unbounded 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 Found new complexity Unbounded. 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 Obtained the following overall complexity (w.r.t. the length of the input n): 64.88/26.63 64.88/26.63 Complexity: Unbounded 64.88/26.63 64.88/26.63 Cpx degree: Unbounded 64.88/26.63 64.88/26.63 Solved cost: 1+3*n 64.88/26.63 64.88/26.63 Rule cost: 1+3*meter_9 64.88/26.63 64.88/26.63 Rule guard: [ free>=1 && 2*meter_9>=1 ] 64.88/26.63 64.88/26.63 64.88/26.63 64.88/26.63 WORST_CASE(INF,?) 64.88/26.63 64.88/26.63 64.88/26.63 ---------------------------------------- 64.88/26.63 64.88/26.63 (2) 64.88/26.63 BOUNDS(INF, INF) 64.88/26.65 EOF