/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- KILLED 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, 5437 ms] (2) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f4(A, B, C, D, E, F) -> Com_1(f14(A, B, C, D, E, F)) :|: 0 >= A f13(A, B, C, D, E, F) -> Com_1(f4(A, B, C, D, E, F)) :|: TRUE f13(A, B, C, D, E, F) -> Com_1(f400(A, B, C, D, E, F)) :|: B >= A + 1 f2(A, B, C, D, E, F) -> Com_1(f23(G, I, H, J, 1, F)) :|: G >= 1 && H >= 1 && 0 >= I f2(A, B, C, D, E, F) -> Com_1(f23(G, I, H, J, 1, 0)) :|: G >= 1 && H >= 1 && I >= 1 f23(A, B, C, D, E, F) -> Com_1(f4(A, B, C, D, E, F)) :|: E >= C f23(A, B, C, D, E, F) -> Com_1(f4(A, B, C, D, E, 1)) :|: C >= E + 1 f4(A, B, C, D, E, F) -> Com_1(f33(A - 1, B, H, J, C, F)) :|: H >= C && 0 >= B && A >= 1 f4(A, B, C, D, E, F) -> Com_1(f33(A - 1, B, H, J, C, 0)) :|: H >= C && B >= 1 && A >= 1 f33(A, B, C, D, E, F) -> Com_1(f6(A, B, C, D, E, F)) :|: E >= C f33(A, B, C, D, E, F) -> Com_1(f6(A, B, C, D, E, 1)) :|: C >= E + 1 f6(A, B, C, D, E, F) -> Com_1(f43(A, B, H, J, C, F)) :|: H >= C && 0 >= C && 0 >= B f6(A, B, C, D, E, F) -> Com_1(f43(A, B, H, J, C, 0)) :|: H >= C && 0 >= C && B >= 1 f43(A, B, C, D, E, F) -> Com_1(f6(A, B, C, D, C, F)) :|: C >= E && C <= E f43(A, B, C, D, E, F) -> Com_1(f6(A, B, C, D, E, 1)) :|: C >= E + 1 f6(A, B, C, D, E, F) -> Com_1(f53(A, B, H, J, C - 1, F)) :|: H + 1 >= C && C >= 1 && 0 >= B f6(A, B, C, D, E, F) -> Com_1(f53(A, B, H, J, C - 1, 0)) :|: H + 1 >= C && C >= 1 && B >= 1 f53(A, B, C, D, E, F) -> Com_1(f61(A, A, C, D, C, F)) :|: E >= C f53(A, B, C, D, E, F) -> Com_1(f61(A, A, C, D, C, 1)) :|: C >= E + 1 f61(A, B, C, D, E, F) -> Com_1(f63(A, B, H, J, E, F)) :|: 0 >= B && H >= E f61(A, B, C, D, E, F) -> Com_1(f63(A, B, H, J, E, 0)) :|: B >= 1 && H >= E f63(A, B, C, D, E, F) -> Com_1(f71(A, B, C, D + 1, C, F)) :|: E >= C f63(A, B, C, D, E, F) -> Com_1(f71(A, B, C, D + 1, C, 1)) :|: C >= E + 1 f71(A, B, C, D, E, F) -> Com_1(f73(A, B, H, J, E, F)) :|: 0 >= B && H >= E f71(A, B, C, D, E, F) -> Com_1(f73(A, B, H, J, E, 0)) :|: B >= 1 && H >= E f73(A, B, C, D, E, F) -> Com_1(f13(A, B, C, D, E, F)) :|: E >= C f73(A, B, C, D, E, F) -> Com_1(f13(A, B, C, D, E, 1)) :|: C >= E + 1 The start-symbols are:[f2_6] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f2 0: f4 -> f14 : [ 0>=A ], cost: 1 7: f4 -> f33 : A'=-1+A, C'=free_8, D'=free_9, E'=C, [ free_8>=C && 0>=B && A>=1 ], cost: 1 8: f4 -> f33 : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=0, [ free_10>=C && B>=1 && A>=1 ], cost: 1 1: f13 -> f4 : [], cost: 1 2: f13 -> f400 : [ B>=1+A ], cost: 1 3: f2 -> f23 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 ], cost: 1 4: f2 -> f23 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 ], cost: 1 5: f23 -> f4 : [ E>=C ], cost: 1 6: f23 -> f4 : F'=1, [ C>=1+E ], cost: 1 9: f33 -> f6 : [ E>=C ], cost: 1 10: f33 -> f6 : F'=1, [ C>=1+E ], cost: 1 11: f6 -> f43 : C'=free_12, D'=free_13, E'=C, [ free_12>=C && 0>=C && 0>=B ], cost: 1 12: f6 -> f43 : C'=free_14, D'=free_15, E'=C, F'=0, [ free_14>=C && 0>=C && B>=1 ], cost: 1 15: f6 -> f53 : C'=free_16, D'=free_17, E'=-1+C, [ 1+free_16>=C && C>=1 && 0>=B ], cost: 1 16: f6 -> f53 : C'=free_18, D'=free_19, E'=-1+C, F'=0, [ 1+free_18>=C && C>=1 && B>=1 ], cost: 1 13: f43 -> f6 : E'=C, [ C==E ], cost: 1 14: f43 -> f6 : F'=1, [ C>=1+E ], cost: 1 17: f53 -> f61 : B'=A, E'=C, [ E>=C ], cost: 1 18: f53 -> f61 : B'=A, E'=C, F'=1, [ C>=1+E ], cost: 1 19: f61 -> f63 : C'=free_20, D'=free_21, [ 0>=B && free_20>=E ], cost: 1 20: f61 -> f63 : C'=free_22, D'=free_23, F'=0, [ B>=1 && free_22>=E ], cost: 1 21: f63 -> f71 : D'=1+D, E'=C, [ E>=C ], cost: 1 22: f63 -> f71 : D'=1+D, E'=C, F'=1, [ C>=1+E ], cost: 1 23: f71 -> f73 : C'=free_24, D'=free_25, [ 0>=B && free_24>=E ], cost: 1 24: f71 -> f73 : C'=free_26, D'=free_27, F'=0, [ B>=1 && free_26>=E ], cost: 1 25: f73 -> f13 : [ E>=C ], cost: 1 26: f73 -> f13 : F'=1, [ C>=1+E ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 3: f2 -> f23 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 ], cost: 1 Removed unreachable and leaf rules: Start location: f2 7: f4 -> f33 : A'=-1+A, C'=free_8, D'=free_9, E'=C, [ free_8>=C && 0>=B && A>=1 ], cost: 1 8: f4 -> f33 : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=0, [ free_10>=C && B>=1 && A>=1 ], cost: 1 1: f13 -> f4 : [], cost: 1 3: f2 -> f23 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 ], cost: 1 4: f2 -> f23 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 ], cost: 1 5: f23 -> f4 : [ E>=C ], cost: 1 6: f23 -> f4 : F'=1, [ C>=1+E ], cost: 1 9: f33 -> f6 : [ E>=C ], cost: 1 10: f33 -> f6 : F'=1, [ C>=1+E ], cost: 1 11: f6 -> f43 : C'=free_12, D'=free_13, E'=C, [ free_12>=C && 0>=C && 0>=B ], cost: 1 12: f6 -> f43 : C'=free_14, D'=free_15, E'=C, F'=0, [ free_14>=C && 0>=C && B>=1 ], cost: 1 15: f6 -> f53 : C'=free_16, D'=free_17, E'=-1+C, [ 1+free_16>=C && C>=1 && 0>=B ], cost: 1 16: f6 -> f53 : C'=free_18, D'=free_19, E'=-1+C, F'=0, [ 1+free_18>=C && C>=1 && B>=1 ], cost: 1 13: f43 -> f6 : E'=C, [ C==E ], cost: 1 14: f43 -> f6 : F'=1, [ C>=1+E ], cost: 1 17: f53 -> f61 : B'=A, E'=C, [ E>=C ], cost: 1 18: f53 -> f61 : B'=A, E'=C, F'=1, [ C>=1+E ], cost: 1 19: f61 -> f63 : C'=free_20, D'=free_21, [ 0>=B && free_20>=E ], cost: 1 20: f61 -> f63 : C'=free_22, D'=free_23, F'=0, [ B>=1 && free_22>=E ], cost: 1 21: f63 -> f71 : D'=1+D, E'=C, [ E>=C ], cost: 1 22: f63 -> f71 : D'=1+D, E'=C, F'=1, [ C>=1+E ], cost: 1 23: f71 -> f73 : C'=free_24, D'=free_25, [ 0>=B && free_24>=E ], cost: 1 24: f71 -> f73 : C'=free_26, D'=free_27, F'=0, [ B>=1 && free_26>=E ], cost: 1 25: f73 -> f13 : [ E>=C ], cost: 1 26: f73 -> f13 : F'=1, [ C>=1+E ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on tree-shaped paths): Start location: f2 31: f4 -> f6 : A'=-1+A, C'=free_8, D'=free_9, E'=C, [ free_8>=C && 0>=B && A>=1 && C>=free_8 ], cost: 2 32: f4 -> f6 : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C ], cost: 2 33: f4 -> f6 : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=0, [ free_10>=C && B>=1 && A>=1 && C>=free_10 ], cost: 2 34: f4 -> f6 : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C ], cost: 2 1: f13 -> f4 : [], cost: 1 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 35: f6 -> f6 : C'=free_12, D'=free_13, E'=free_12, [ 0>=C && 0>=B && free_12==C ], cost: 2 36: f6 -> f6 : C'=free_12, D'=free_13, E'=C, F'=1, [ 0>=C && 0>=B && free_12>=1+C ], cost: 2 37: f6 -> f6 : C'=free_14, D'=free_15, E'=free_14, F'=0, [ 0>=C && B>=1 && free_14==C ], cost: 2 38: f6 -> f6 : C'=free_14, D'=free_15, E'=C, F'=1, [ 0>=C && B>=1 && free_14>=1+C ], cost: 2 39: f6 -> f61 : B'=A, C'=free_16, D'=free_17, E'=free_16, [ 1+free_16>=C && C>=1 && 0>=B && -1+C>=free_16 ], cost: 2 40: f6 -> f61 : B'=A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ C>=1 && 0>=B && free_16>=C ], cost: 2 41: f6 -> f61 : B'=A, C'=free_18, D'=free_19, E'=free_18, F'=0, [ 1+free_18>=C && C>=1 && B>=1 && -1+C>=free_18 ], cost: 2 42: f6 -> f61 : B'=A, C'=free_18, D'=free_19, E'=free_18, F'=1, [ C>=1 && B>=1 && free_18>=C ], cost: 2 43: f61 -> f71 : C'=free_20, D'=1+free_21, E'=free_20, [ 0>=B && free_20>=E && E>=free_20 ], cost: 2 44: f61 -> f71 : C'=free_20, D'=1+free_21, E'=free_20, F'=1, [ 0>=B && free_20>=1+E ], cost: 2 45: f61 -> f71 : C'=free_22, D'=1+free_23, E'=free_22, F'=0, [ B>=1 && free_22>=E && E>=free_22 ], cost: 2 46: f61 -> f71 : C'=free_22, D'=1+free_23, E'=free_22, F'=1, [ B>=1 && free_22>=1+E ], cost: 2 47: f71 -> f13 : C'=free_24, D'=free_25, [ 0>=B && free_24>=E && E>=free_24 ], cost: 2 48: f71 -> f13 : C'=free_24, D'=free_25, F'=1, [ 0>=B && free_24>=1+E ], cost: 2 49: f71 -> f13 : C'=free_26, D'=free_27, F'=0, [ B>=1 && free_26>=E && E>=free_26 ], cost: 2 50: f71 -> f13 : C'=free_26, D'=free_27, F'=1, [ B>=1 && free_26>=1+E ], cost: 2 Accelerating simple loops of location 5. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 35: f6 -> f6 : D'=free_13, E'=C, [ 0>=C && 0>=B ], cost: 2 36: f6 -> f6 : C'=free_12, D'=free_13, E'=C, F'=1, [ 0>=C && 0>=B && free_12>=1+C ], cost: 2 37: f6 -> f6 : D'=free_15, E'=C, F'=0, [ 0>=C && B>=1 ], cost: 2 38: f6 -> f6 : C'=free_14, D'=free_15, E'=C, F'=1, [ 0>=C && B>=1 && free_14>=1+C ], cost: 2 Accelerated rule 35 with NONTERM, yielding the new rule 51. During metering: Instantiating temporary variables by {free_12==1+C} Accelerated rule 36 with metering function 1-C, yielding the new rule 52. Accelerated rule 37 with NONTERM, yielding the new rule 53. During metering: Instantiating temporary variables by {free_14==1+C} Accelerated rule 38 with metering function 1-C, yielding the new rule 54. Removing the simple loops: 35 36 37 38. Accelerated all simple loops using metering functions (where possible): Start location: f2 31: f4 -> f6 : A'=-1+A, C'=free_8, D'=free_9, E'=C, [ free_8>=C && 0>=B && A>=1 && C>=free_8 ], cost: 2 32: f4 -> f6 : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C ], cost: 2 33: f4 -> f6 : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=0, [ free_10>=C && B>=1 && A>=1 && C>=free_10 ], cost: 2 34: f4 -> f6 : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C ], cost: 2 1: f13 -> f4 : [], cost: 1 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 39: f6 -> f61 : B'=A, C'=free_16, D'=free_17, E'=free_16, [ 1+free_16>=C && C>=1 && 0>=B && -1+C>=free_16 ], cost: 2 40: f6 -> f61 : B'=A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ C>=1 && 0>=B && free_16>=C ], cost: 2 41: f6 -> f61 : B'=A, C'=free_18, D'=free_19, E'=free_18, F'=0, [ 1+free_18>=C && C>=1 && B>=1 && -1+C>=free_18 ], cost: 2 42: f6 -> f61 : B'=A, C'=free_18, D'=free_19, E'=free_18, F'=1, [ C>=1 && B>=1 && free_18>=C ], cost: 2 51: f6 -> [14] : [ 0>=C && 0>=B ], cost: NONTERM 52: f6 -> f6 : C'=1, D'=free_13, E'=0, F'=1, [ 0>=C && 0>=B ], cost: 2-2*C 53: f6 -> [14] : [ 0>=C && B>=1 ], cost: NONTERM 54: f6 -> f6 : C'=1, D'=free_15, E'=0, F'=1, [ 0>=C && B>=1 ], cost: 2-2*C 43: f61 -> f71 : C'=free_20, D'=1+free_21, E'=free_20, [ 0>=B && free_20>=E && E>=free_20 ], cost: 2 44: f61 -> f71 : C'=free_20, D'=1+free_21, E'=free_20, F'=1, [ 0>=B && free_20>=1+E ], cost: 2 45: f61 -> f71 : C'=free_22, D'=1+free_23, E'=free_22, F'=0, [ B>=1 && free_22>=E && E>=free_22 ], cost: 2 46: f61 -> f71 : C'=free_22, D'=1+free_23, E'=free_22, F'=1, [ B>=1 && free_22>=1+E ], cost: 2 47: f71 -> f13 : C'=free_24, D'=free_25, [ 0>=B && free_24>=E && E>=free_24 ], cost: 2 48: f71 -> f13 : C'=free_24, D'=free_25, F'=1, [ 0>=B && free_24>=1+E ], cost: 2 49: f71 -> f13 : C'=free_26, D'=free_27, F'=0, [ B>=1 && free_26>=E && E>=free_26 ], cost: 2 50: f71 -> f13 : C'=free_26, D'=free_27, F'=1, [ B>=1 && free_26>=1+E ], cost: 2 Chained accelerated rules (with incoming rules): Start location: f2 31: f4 -> f6 : A'=-1+A, C'=free_8, D'=free_9, E'=C, [ free_8>=C && 0>=B && A>=1 && C>=free_8 ], cost: 2 32: f4 -> f6 : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C ], cost: 2 33: f4 -> f6 : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=0, [ free_10>=C && B>=1 && A>=1 && C>=free_10 ], cost: 2 34: f4 -> f6 : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C ], cost: 2 55: f4 -> [14] : A'=-1+A, D'=free_9, E'=C, [ 0>=B && A>=1 && 0>=C ], cost: NONTERM 56: f4 -> [14] : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: NONTERM 57: f4 -> f6 : A'=-1+A, C'=1, D'=free_13, E'=0, F'=1, [ 0>=B && A>=1 && 0>=C ], cost: 4-2*C 58: f4 -> f6 : A'=-1+A, C'=1, D'=free_13, E'=0, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: 4-2*free_8 59: f4 -> [14] : A'=-1+A, D'=free_11, E'=C, F'=0, [ B>=1 && A>=1 && 0>=C ], cost: NONTERM 60: f4 -> [14] : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: NONTERM 61: f4 -> f6 : A'=-1+A, C'=1, D'=free_15, E'=0, F'=1, [ B>=1 && A>=1 && 0>=C ], cost: 4-2*C 62: f4 -> f6 : A'=-1+A, C'=1, D'=free_15, E'=0, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: 4-2*free_10 1: f13 -> f4 : [], cost: 1 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 39: f6 -> f61 : B'=A, C'=free_16, D'=free_17, E'=free_16, [ 1+free_16>=C && C>=1 && 0>=B && -1+C>=free_16 ], cost: 2 40: f6 -> f61 : B'=A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ C>=1 && 0>=B && free_16>=C ], cost: 2 41: f6 -> f61 : B'=A, C'=free_18, D'=free_19, E'=free_18, F'=0, [ 1+free_18>=C && C>=1 && B>=1 && -1+C>=free_18 ], cost: 2 42: f6 -> f61 : B'=A, C'=free_18, D'=free_19, E'=free_18, F'=1, [ C>=1 && B>=1 && free_18>=C ], cost: 2 43: f61 -> f71 : C'=free_20, D'=1+free_21, E'=free_20, [ 0>=B && free_20>=E && E>=free_20 ], cost: 2 44: f61 -> f71 : C'=free_20, D'=1+free_21, E'=free_20, F'=1, [ 0>=B && free_20>=1+E ], cost: 2 45: f61 -> f71 : C'=free_22, D'=1+free_23, E'=free_22, F'=0, [ B>=1 && free_22>=E && E>=free_22 ], cost: 2 46: f61 -> f71 : C'=free_22, D'=1+free_23, E'=free_22, F'=1, [ B>=1 && free_22>=1+E ], cost: 2 47: f71 -> f13 : C'=free_24, D'=free_25, [ 0>=B && free_24>=E && E>=free_24 ], cost: 2 48: f71 -> f13 : C'=free_24, D'=free_25, F'=1, [ 0>=B && free_24>=1+E ], cost: 2 49: f71 -> f13 : C'=free_26, D'=free_27, F'=0, [ B>=1 && free_26>=E && E>=free_26 ], cost: 2 50: f71 -> f13 : C'=free_26, D'=free_27, F'=1, [ B>=1 && free_26>=1+E ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: f2 55: f4 -> [14] : A'=-1+A, D'=free_9, E'=C, [ 0>=B && A>=1 && 0>=C ], cost: NONTERM 56: f4 -> [14] : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: NONTERM 59: f4 -> [14] : A'=-1+A, D'=free_11, E'=C, F'=0, [ B>=1 && A>=1 && 0>=C ], cost: NONTERM 60: f4 -> [14] : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: NONTERM 63: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_16, D'=free_17, E'=free_16, [ free_8>=C && 0>=B && A>=1 && C>=free_8 && 1+free_16>=free_8 && free_8>=1 && -1+free_8>=free_16 ], cost: 4 64: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ free_8>=C && 0>=B && A>=1 && C>=free_8 && free_8>=1 && free_16>=free_8 ], cost: 4 65: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 1+free_16>=free_8 && free_8>=1 && -1+free_8>=free_16 ], cost: 4 66: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ 0>=B && A>=1 && free_8>=1+C && free_8>=1 && free_16>=free_8 ], cost: 4 67: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=0, [ free_10>=C && B>=1 && A>=1 && C>=free_10 && 1+free_18>=free_10 && free_10>=1 && -1+free_10>=free_18 ], cost: 4 68: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=1, [ free_10>=C && B>=1 && A>=1 && C>=free_10 && free_10>=1 && free_18>=free_10 ], cost: 4 69: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=0, [ B>=1 && A>=1 && free_10>=1+C && 1+free_18>=free_10 && free_10>=1 && -1+free_10>=free_18 ], cost: 4 70: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=1, [ B>=1 && A>=1 && free_10>=1+C && free_10>=1 && free_18>=free_10 ], cost: 4 71: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ 0>=B && A>=1 && 0>=C && 1+free_16>=1 && 0>=free_16 ], cost: 6-2*C 72: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ 0>=B && A>=1 && 0>=C && free_16>=1 ], cost: 6-2*C 73: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 && 1+free_16>=1 && 0>=free_16 ], cost: 6-2*free_8 74: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 && free_16>=1 ], cost: 6-2*free_8 75: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=0, [ B>=1 && A>=1 && 0>=C && 1+free_18>=1 && 0>=free_18 ], cost: 6-2*C 76: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=1, [ B>=1 && A>=1 && 0>=C && free_18>=1 ], cost: 6-2*C 77: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=0, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && 1+free_18>=1 && 0>=free_18 ], cost: 6-2*free_10 78: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 ], cost: 6-2*free_10 79: f4 -> [15] : [ 0>=B && A>=1 && 0>=C ], cost: 4-2*C 80: f4 -> [15] : [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: 4-2*free_8 81: f4 -> [15] : [ B>=1 && A>=1 && 0>=C ], cost: 4-2*C 82: f4 -> [15] : [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: 4-2*free_10 1: f13 -> f4 : [], cost: 1 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 83: f61 -> f13 : C'=free_24, D'=free_25, E'=free_20, [ 0>=B && free_20>=E && E>=free_20 && free_24>=free_20 && free_20>=free_24 ], cost: 4 84: f61 -> f13 : C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && free_20>=E && E>=free_20 && free_24>=1+free_20 ], cost: 4 85: f61 -> f13 : C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && free_20>=1+E && free_24>=free_20 && free_20>=free_24 ], cost: 4 86: f61 -> f13 : C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && free_20>=1+E && free_24>=1+free_20 ], cost: 4 87: f61 -> f13 : C'=free_26, D'=free_27, E'=free_22, F'=0, [ B>=1 && free_22>=E && E>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 4 88: f61 -> f13 : C'=free_26, D'=free_27, E'=free_22, F'=1, [ B>=1 && free_22>=E && E>=free_22 && free_26>=1+free_22 ], cost: 4 89: f61 -> f13 : C'=free_26, D'=free_27, E'=free_22, F'=0, [ B>=1 && free_22>=1+E && free_26>=free_22 && free_22>=free_26 ], cost: 4 90: f61 -> f13 : C'=free_26, D'=free_27, E'=free_22, F'=1, [ B>=1 && free_22>=1+E && free_26>=1+free_22 ], cost: 4 Applied pruning (of leafs and parallel rules): Start location: f2 55: f4 -> [14] : A'=-1+A, D'=free_9, E'=C, [ 0>=B && A>=1 && 0>=C ], cost: NONTERM 56: f4 -> [14] : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: NONTERM 59: f4 -> [14] : A'=-1+A, D'=free_11, E'=C, F'=0, [ B>=1 && A>=1 && 0>=C ], cost: NONTERM 60: f4 -> [14] : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: NONTERM 72: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ 0>=B && A>=1 && 0>=C && free_16>=1 ], cost: 6-2*C 74: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_16, D'=free_17, E'=free_16, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 && free_16>=1 ], cost: 6-2*free_8 76: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=1, [ B>=1 && A>=1 && 0>=C && free_18>=1 ], cost: 6-2*C 77: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=0, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && 1+free_18>=1 && 0>=free_18 ], cost: 6-2*free_10 78: f4 -> f61 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_19, E'=free_18, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 ], cost: 6-2*free_10 79: f4 -> [15] : [ 0>=B && A>=1 && 0>=C ], cost: 4-2*C 80: f4 -> [15] : [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: 4-2*free_8 81: f4 -> [15] : [ B>=1 && A>=1 && 0>=C ], cost: 4-2*C 82: f4 -> [15] : [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: 4-2*free_10 1: f13 -> f4 : [], cost: 1 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 83: f61 -> f13 : C'=free_24, D'=free_25, E'=free_20, [ 0>=B && free_20>=E && E>=free_20 && free_24>=free_20 && free_20>=free_24 ], cost: 4 84: f61 -> f13 : C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && free_20>=E && E>=free_20 && free_24>=1+free_20 ], cost: 4 86: f61 -> f13 : C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && free_20>=1+E && free_24>=1+free_20 ], cost: 4 87: f61 -> f13 : C'=free_26, D'=free_27, E'=free_22, F'=0, [ B>=1 && free_22>=E && E>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 4 88: f61 -> f13 : C'=free_26, D'=free_27, E'=free_22, F'=1, [ B>=1 && free_22>=E && E>=free_22 && free_26>=1+free_22 ], cost: 4 Eliminated locations (on tree-shaped paths): Start location: f2 55: f4 -> [14] : A'=-1+A, D'=free_9, E'=C, [ 0>=B && A>=1 && 0>=C ], cost: NONTERM 56: f4 -> [14] : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: NONTERM 59: f4 -> [14] : A'=-1+A, D'=free_11, E'=C, F'=0, [ B>=1 && A>=1 && 0>=C ], cost: NONTERM 60: f4 -> [14] : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: NONTERM 79: f4 -> [15] : [ 0>=B && A>=1 && 0>=C ], cost: 4-2*C 80: f4 -> [15] : [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: 4-2*free_8 81: f4 -> [15] : [ B>=1 && A>=1 && 0>=C ], cost: 4-2*C 82: f4 -> [15] : [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: 4-2*free_10 91: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && A>=1 && 0>=C && free_16>=1 && 0>=-1+A && free_20>=free_16 && free_16>=free_20 && free_24>=free_20 && free_20>=free_24 ], cost: 10-2*C 92: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && A>=1 && 0>=C && free_16>=1 && 0>=-1+A && free_20>=free_16 && free_16>=free_20 && free_24>=1+free_20 ], cost: 10-2*C 93: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && A>=1 && 0>=C && free_16>=1 && 0>=-1+A && free_20>=1+free_16 && free_24>=1+free_20 ], cost: 10-2*C 94: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=0, [ 0>=B && 0>=C && free_16>=1 && -1+A>=1 && free_22>=free_16 && free_16>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 10-2*C 95: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=1, [ 0>=B && 0>=C && free_16>=1 && -1+A>=1 && free_22>=free_16 && free_16>=free_22 && free_26>=1+free_22 ], cost: 10-2*C 96: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 && free_16>=1 && 0>=-1+A && free_20>=free_16 && free_16>=free_20 && free_24>=free_20 && free_20>=free_24 ], cost: 10-2*free_8 97: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 && free_16>=1 && 0>=-1+A && free_20>=free_16 && free_16>=free_20 && free_24>=1+free_20 ], cost: 10-2*free_8 98: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 && free_16>=1 && 0>=-1+A && free_20>=1+free_16 && free_24>=1+free_20 ], cost: 10-2*free_8 99: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=0, [ 0>=B && free_8>=1+C && 0>=free_8 && free_16>=1 && -1+A>=1 && free_22>=free_16 && free_16>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 10-2*free_8 100: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=1, [ 0>=B && free_8>=1+C && 0>=free_8 && free_16>=1 && -1+A>=1 && free_22>=free_16 && free_16>=free_22 && free_26>=1+free_22 ], cost: 10-2*free_8 101: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ B>=1 && A>=1 && 0>=C && free_18>=1 && 0>=-1+A && free_20>=free_18 && free_18>=free_20 && free_24>=free_20 && free_20>=free_24 ], cost: 10-2*C 102: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ B>=1 && A>=1 && 0>=C && free_18>=1 && 0>=-1+A && free_20>=free_18 && free_18>=free_20 && free_24>=1+free_20 ], cost: 10-2*C 103: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ B>=1 && A>=1 && 0>=C && free_18>=1 && 0>=-1+A && free_20>=1+free_18 && free_24>=1+free_20 ], cost: 10-2*C 104: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=0, [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 10-2*C 105: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=1, [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=1+free_22 ], cost: 10-2*C 106: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=0, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && 1+free_18>=1 && 0>=free_18 && 0>=-1+A && free_20>=free_18 && free_18>=free_20 && free_24>=free_20 && free_20>=free_24 ], cost: 10-2*free_10 107: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && 1+free_18>=1 && 0>=free_18 && 0>=-1+A && free_20>=free_18 && free_18>=free_20 && free_24>=1+free_20 ], cost: 10-2*free_10 108: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && 1+free_18>=1 && 0>=free_18 && 0>=-1+A && free_20>=1+free_18 && free_24>=1+free_20 ], cost: 10-2*free_10 109: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=0, [ B>=1 && free_10>=1+C && 0>=free_10 && 1+free_18>=1 && 0>=free_18 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 10-2*free_10 110: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=1, [ B>=1 && free_10>=1+C && 0>=free_10 && 1+free_18>=1 && 0>=free_18 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=1+free_22 ], cost: 10-2*free_10 111: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && 0>=-1+A && free_20>=free_18 && free_18>=free_20 && free_24>=free_20 && free_20>=free_24 ], cost: 10-2*free_10 112: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && 0>=-1+A && free_20>=free_18 && free_18>=free_20 && free_24>=1+free_20 ], cost: 10-2*free_10 113: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && 0>=-1+A && free_20>=1+free_18 && free_24>=1+free_20 ], cost: 10-2*free_10 114: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=0, [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 10-2*free_10 115: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=1, [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=1+free_22 ], cost: 10-2*free_10 1: f13 -> f4 : [], cost: 1 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 Applied pruning (of leafs and parallel rules): Start location: f2 55: f4 -> [14] : A'=-1+A, D'=free_9, E'=C, [ 0>=B && A>=1 && 0>=C ], cost: NONTERM 56: f4 -> [14] : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: NONTERM 59: f4 -> [14] : A'=-1+A, D'=free_11, E'=C, F'=0, [ B>=1 && A>=1 && 0>=C ], cost: NONTERM 60: f4 -> [14] : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: NONTERM 79: f4 -> [15] : [ 0>=B && A>=1 && 0>=C ], cost: 4-2*C 80: f4 -> [15] : [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: 4-2*free_8 81: f4 -> [15] : [ B>=1 && A>=1 && 0>=C ], cost: 4-2*C 82: f4 -> [15] : [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: 4-2*free_10 104: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=0, [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 10-2*C 105: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=1, [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=1+free_22 ], cost: 10-2*C 111: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && 0>=-1+A && free_20>=free_18 && free_18>=free_20 && free_24>=free_20 && free_20>=free_24 ], cost: 10-2*free_10 114: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=0, [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 10-2*free_10 115: f4 -> f13 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=1, [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=1+free_22 ], cost: 10-2*free_10 1: f13 -> f4 : [], cost: 1 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: f2 55: f4 -> [14] : A'=-1+A, D'=free_9, E'=C, [ 0>=B && A>=1 && 0>=C ], cost: NONTERM 56: f4 -> [14] : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: NONTERM 59: f4 -> [14] : A'=-1+A, D'=free_11, E'=C, F'=0, [ B>=1 && A>=1 && 0>=C ], cost: NONTERM 60: f4 -> [14] : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: NONTERM 79: f4 -> [15] : [ 0>=B && A>=1 && 0>=C ], cost: 4-2*C 80: f4 -> [15] : [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: 4-2*free_8 81: f4 -> [15] : [ B>=1 && A>=1 && 0>=C ], cost: 4-2*C 82: f4 -> [15] : [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: 4-2*free_10 116: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=0, [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 11-2*C 117: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=1, [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=1+free_22 ], cost: 11-2*C 118: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_24, D'=free_25, E'=free_20, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && 0>=-1+A && free_20>=free_18 && free_18>=free_20 && free_24>=free_20 && free_20>=free_24 ], cost: 11-2*free_10 119: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=0, [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=free_22 && free_22>=free_26 ], cost: 11-2*free_10 120: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_22, F'=1, [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 && free_22>=free_18 && free_18>=free_22 && free_26>=1+free_22 ], cost: 11-2*free_10 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 Accelerating simple loops of location 0. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 116: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_27, E'=free_18, F'=0, [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 ], cost: 11-2*C 117: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_18, F'=1, [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 && free_26>=1+free_18 ], cost: 11-2*C 118: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_25, E'=free_18, F'=1, [ B>=1 && 1-A==0 && free_10>=1+C && 0>=free_10 && free_18>=1 ], cost: 11-2*free_10 119: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_27, E'=free_18, F'=0, [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 ], cost: 11-2*free_10 120: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_18, F'=1, [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 && free_26>=1+free_18 ], cost: 11-2*free_10 Accelerated rule 116 with NONTERM (after strengthening guard), yielding the new rule 121. Accelerated rule 117 with NONTERM (after strengthening guard), yielding the new rule 122. Accelerated rule 118 with metering function -1+A, yielding the new rule 123. Accelerated rule 119 with NONTERM (after strengthening guard), yielding the new rule 124. Accelerated rule 120 with NONTERM (after strengthening guard), yielding the new rule 125. Removing the simple loops: 118. Accelerated all simple loops using metering functions (where possible): Start location: f2 55: f4 -> [14] : A'=-1+A, D'=free_9, E'=C, [ 0>=B && A>=1 && 0>=C ], cost: NONTERM 56: f4 -> [14] : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: NONTERM 59: f4 -> [14] : A'=-1+A, D'=free_11, E'=C, F'=0, [ B>=1 && A>=1 && 0>=C ], cost: NONTERM 60: f4 -> [14] : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: NONTERM 79: f4 -> [15] : [ 0>=B && A>=1 && 0>=C ], cost: 4-2*C 80: f4 -> [15] : [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: 4-2*free_8 81: f4 -> [15] : [ B>=1 && A>=1 && 0>=C ], cost: 4-2*C 82: f4 -> [15] : [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: 4-2*free_10 116: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_27, E'=free_18, F'=0, [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 ], cost: 11-2*C 117: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_18, F'=1, [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 && free_26>=1+free_18 ], cost: 11-2*C 119: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_18, D'=free_27, E'=free_18, F'=0, [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 ], cost: 11-2*free_10 120: f4 -> f4 : A'=-1+A, B'=-1+A, C'=free_26, D'=free_27, E'=free_18, F'=1, [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 && free_26>=1+free_18 ], cost: 11-2*free_10 121: f4 -> [16] : [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 && 0>=free_18 && 11-2*C>=1 ], cost: NONTERM 122: f4 -> [16] : [ B>=1 && 0>=C && free_18>=1 && -1+A>=1 && free_26>=1+free_18 && 0>=free_26 && 11-2*C>=1 ], cost: NONTERM 123: f4 -> f4 : A'=1, B'=1, C'=free_18, D'=free_25, E'=free_18, F'=1, [ B>=1 && 1-A==0 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 ], cost: -11+11*A-2*(-1+A)*free_10 124: f4 -> [16] : [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 && free_10>=1+free_18 && 11-2*free_10>=1 ], cost: NONTERM 125: f4 -> [16] : [ B>=1 && free_10>=1+C && 0>=free_10 && free_18>=1 && -1+A>=1 && free_26>=1+free_18 && free_10>=1+free_26 && 11-2*free_10>=1 ], cost: NONTERM 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 Chained accelerated rules (with incoming rules): Start location: f2 55: f4 -> [14] : A'=-1+A, D'=free_9, E'=C, [ 0>=B && A>=1 && 0>=C ], cost: NONTERM 56: f4 -> [14] : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: NONTERM 59: f4 -> [14] : A'=-1+A, D'=free_11, E'=C, F'=0, [ B>=1 && A>=1 && 0>=C ], cost: NONTERM 60: f4 -> [14] : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: NONTERM 79: f4 -> [15] : [ 0>=B && A>=1 && 0>=C ], cost: 4-2*C 80: f4 -> [15] : [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: 4-2*free_8 81: f4 -> [15] : [ B>=1 && A>=1 && 0>=C ], cost: 4-2*C 82: f4 -> [15] : [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: 4-2*free_10 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 Removed unreachable locations (and leaf rules with constant cost): Start location: f2 55: f4 -> [14] : A'=-1+A, D'=free_9, E'=C, [ 0>=B && A>=1 && 0>=C ], cost: NONTERM 56: f4 -> [14] : A'=-1+A, C'=free_8, D'=free_9, E'=C, F'=1, [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: NONTERM 59: f4 -> [14] : A'=-1+A, D'=free_11, E'=C, F'=0, [ B>=1 && A>=1 && 0>=C ], cost: NONTERM 60: f4 -> [14] : A'=-1+A, C'=free_10, D'=free_11, E'=C, F'=1, [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: NONTERM 79: f4 -> [15] : [ 0>=B && A>=1 && 0>=C ], cost: 4-2*C 80: f4 -> [15] : [ 0>=B && A>=1 && free_8>=1+C && 0>=free_8 ], cost: 4-2*free_8 81: f4 -> [15] : [ B>=1 && A>=1 && 0>=C ], cost: 4-2*C 82: f4 -> [15] : [ B>=1 && A>=1 && free_10>=1+C && 0>=free_10 ], cost: 4-2*free_10 27: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, [ free_1>=1 && free_2>=1 && 0>=free_3 && 1>=free_2 ], cost: 2 28: f2 -> f4 : A'=free_1, B'=free_3, C'=free_2, D'=free, E'=1, F'=1, [ free_1>=1 && 0>=free_3 && free_2>=2 ], cost: 2 29: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=0, [ free_5>=1 && free_6>=1 && free_7>=1 && 1>=free_6 ], cost: 2 30: f2 -> f4 : A'=free_5, B'=free_7, C'=free_6, D'=free_4, E'=1, F'=1, [ free_5>=1 && free_7>=1 && free_6>=2 ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: f2 Applied pruning (of leafs and parallel rules): Start location: f2 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f2 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: [ free_1>=1 && free_2>=1 && 0>=free_3 ] WORST_CASE(Omega(1),?) ---------------------------------------- (2) BOUNDS(1, INF)