/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^2), O(n^2)) 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(n^2, max(2 + 4 * Arg_0, 6) + max(17 + 8 * Arg_0, 9) + 19 * nat(1 + Arg_0) * nat(Arg_0) + 3 * nat(2 + 2 * Arg_0) * nat(1 + Arg_0) * nat(Arg_0) + 12 * nat(1 + Arg_0) * nat(Arg_0)^2 + 4 * nat(2 + 2 * Arg_0) * nat(1 + Arg_0) + 7 * nat(2 + 2 * Arg_0) * nat(Arg_0) + 9 * nat(Arg_0)^2 + 3 * nat(2 + 2 * Arg_0) * nat(Arg_0)^2 + nat(2 + 2 * Arg_0) + nat(15 * Arg_0)). (0) CpxIntTrs (1) Loat Proof [FINISHED, 6773 ms] (2) BOUNDS(n^2, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: start(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, D, H)) :|: 0 >= A + 1 && B >= C && B <= C && D >= A && D <= A && E >= F && E <= F && G >= H && G <= H start(A, B, C, D, E, F, G, H) -> Com_1(lbl142(A, B, C, D, 0, F, D - 1, H)) :|: D >= 0 && D <= 0 && B >= C && B <= C && A >= 0 && A <= 0 && E >= F && E <= F && G >= H && G <= H start(A, B, C, D, E, F, G, H) -> Com_1(lbl91(A, I, C, D, 0, F, D, H)) :|: A >= 1 && B >= C && B <= C && D >= A && D <= A && E >= F && E <= F && G >= H && G <= H start(A, B, C, D, E, F, G, H) -> Com_1(lbl131(A, B, C, D, 1, F, D, H)) :|: A >= 1 && B >= C && B <= C && D >= A && D <= A && E >= F && E <= F && G >= H && G <= H lbl142(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: A >= 0 && G + 1 >= 0 && G + 1 <= 0 && E >= 0 && E <= 0 && D >= A && D <= A lbl142(A, B, C, D, E, F, G, H) -> Com_1(lbl142(A, B, C, D, 0, F, G - 1, H)) :|: A >= 1 && G >= 0 && G <= 0 && E >= 1 && E <= 1 && D >= A && D <= A lbl142(A, B, C, D, E, F, G, H) -> Com_1(lbl91(A, I, C, D, 0, F, G, H)) :|: E >= 2 && E >= 0 && A >= E && G + 1 >= E && G + 1 <= E && D >= A && D <= A lbl142(A, B, C, D, E, F, G, H) -> Com_1(lbl131(A, B, C, D, 1, F, G, H)) :|: E >= 2 && E >= 0 && A >= E && G + 1 >= E && G + 1 <= E && D >= A && D <= A lbl131(A, B, C, D, E, F, G, H) -> Com_1(lbl142(A, B, C, D, E, F, G - 1, H)) :|: G >= 1 && A >= G && E >= G && E <= G && D >= A && D <= A lbl131(A, B, C, D, E, F, G, H) -> Com_1(lbl91(A, I, C, D, E, F, G, H)) :|: G >= E + 1 && G >= E && E >= 1 && A >= G && D >= A && D <= A lbl131(A, B, C, D, E, F, G, H) -> Com_1(lbl131(A, B, C, D, 1 + E, F, G, H)) :|: G >= E + 1 && G >= E && E >= 1 && A >= G && D >= A && D <= A lbl91(A, B, C, D, E, F, G, H) -> Com_1(lbl131(A, B, C, D, 1 + E, F, G, H)) :|: E >= 0 && G >= E + 1 && A >= G && D >= A && D <= A start0(A, B, C, D, E, F, G, H) -> Com_1(start(A, C, C, A, F, F, H, H)) :|: TRUE The start-symbols are:[start0_8] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: start0 0: start -> stop : G'=D, [ 0>=1+A && B==C && D==A && E==F && G==H ], cost: 1 1: start -> lbl142 : E'=0, G'=-1+D, [ D==0 && B==C && A==0 && E==F && G==H ], cost: 1 2: start -> lbl91 : B'=free, E'=0, G'=D, [ A>=1 && B==C && D==A && E==F && G==H ], cost: 1 3: start -> lbl131 : E'=1, G'=D, [ A>=1 && B==C && D==A && E==F && G==H ], cost: 1 4: lbl142 -> stop : [ A>=0 && 1+G==0 && E==0 && D==A ], cost: 1 5: lbl142 -> lbl142 : E'=0, G'=-1+G, [ A>=1 && G==0 && E==1 && D==A ], cost: 1 6: lbl142 -> lbl91 : B'=free_1, E'=0, [ E>=2 && E>=0 && A>=E && 1+G==E && D==A ], cost: 1 7: lbl142 -> lbl131 : E'=1, [ E>=2 && E>=0 && A>=E && 1+G==E && D==A ], cost: 1 8: lbl131 -> lbl142 : G'=-1+G, [ G>=1 && A>=G && E==G && D==A ], cost: 1 9: lbl131 -> lbl91 : B'=free_2, [ G>=1+E && G>=E && E>=1 && A>=G && D==A ], cost: 1 10: lbl131 -> lbl131 : E'=1+E, [ G>=1+E && G>=E && E>=1 && A>=G && D==A ], cost: 1 11: lbl91 -> lbl131 : E'=1+E, [ E>=0 && G>=1+E && A>=G && D==A ], cost: 1 12: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 12: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1 Removed unreachable and leaf rules: Start location: start0 1: start -> lbl142 : E'=0, G'=-1+D, [ D==0 && B==C && A==0 && E==F && G==H ], cost: 1 2: start -> lbl91 : B'=free, E'=0, G'=D, [ A>=1 && B==C && D==A && E==F && G==H ], cost: 1 3: start -> lbl131 : E'=1, G'=D, [ A>=1 && B==C && D==A && E==F && G==H ], cost: 1 5: lbl142 -> lbl142 : E'=0, G'=-1+G, [ A>=1 && G==0 && E==1 && D==A ], cost: 1 6: lbl142 -> lbl91 : B'=free_1, E'=0, [ E>=2 && E>=0 && A>=E && 1+G==E && D==A ], cost: 1 7: lbl142 -> lbl131 : E'=1, [ E>=2 && E>=0 && A>=E && 1+G==E && D==A ], cost: 1 8: lbl131 -> lbl142 : G'=-1+G, [ G>=1 && A>=G && E==G && D==A ], cost: 1 9: lbl131 -> lbl91 : B'=free_2, [ G>=1+E && G>=E && E>=1 && A>=G && D==A ], cost: 1 10: lbl131 -> lbl131 : E'=1+E, [ G>=1+E && G>=E && E>=1 && A>=G && D==A ], cost: 1 11: lbl91 -> lbl131 : E'=1+E, [ E>=0 && G>=1+E && A>=G && D==A ], cost: 1 12: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1 Simplified all rules, resulting in: Start location: start0 1: start -> lbl142 : E'=0, G'=-1+D, [ D==0 && B==C && A==0 && E==F && G==H ], cost: 1 2: start -> lbl91 : B'=free, E'=0, G'=D, [ A>=1 && B==C && D==A && E==F && G==H ], cost: 1 3: start -> lbl131 : E'=1, G'=D, [ A>=1 && B==C && D==A && E==F && G==H ], cost: 1 5: lbl142 -> lbl142 : E'=0, G'=-1+G, [ A>=1 && G==0 && E==1 && D==A ], cost: 1 6: lbl142 -> lbl91 : B'=free_1, E'=0, [ E>=2 && A>=E && 1+G==E && D==A ], cost: 1 7: lbl142 -> lbl131 : E'=1, [ E>=2 && A>=E && 1+G==E && D==A ], cost: 1 8: lbl131 -> lbl142 : G'=-1+G, [ G>=1 && A>=G && E==G && D==A ], cost: 1 9: lbl131 -> lbl91 : B'=free_2, [ G>=1+E && E>=1 && A>=G && D==A ], cost: 1 10: lbl131 -> lbl131 : E'=1+E, [ G>=1+E && E>=1 && A>=G && D==A ], cost: 1 11: lbl91 -> lbl131 : E'=1+E, [ E>=0 && G>=1+E && A>=G && D==A ], cost: 1 12: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 5: lbl142 -> lbl142 : E'=0, G'=-1+G, [ A>=1 && G==0 && E==1 && D==A ], cost: 1 Accelerated rule 5 with metering function meter (where 2*meter==G+E), yielding the new rule 13. Removing the simple loops: 5. Accelerating simple loops of location 2. Accelerating the following rules: 10: lbl131 -> lbl131 : E'=1+E, [ G>=1+E && E>=1 && A>=G && D==A ], cost: 1 Accelerated rule 10 with metering function G-E, yielding the new rule 14. Removing the simple loops: 10. Accelerated all simple loops using metering functions (where possible): Start location: start0 1: start -> lbl142 : E'=0, G'=-1+D, [ D==0 && B==C && A==0 && E==F && G==H ], cost: 1 2: start -> lbl91 : B'=free, E'=0, G'=D, [ A>=1 && B==C && D==A && E==F && G==H ], cost: 1 3: start -> lbl131 : E'=1, G'=D, [ A>=1 && B==C && D==A && E==F && G==H ], cost: 1 6: lbl142 -> lbl91 : B'=free_1, E'=0, [ E>=2 && A>=E && 1+G==E && D==A ], cost: 1 7: lbl142 -> lbl131 : E'=1, [ E>=2 && A>=E && 1+G==E && D==A ], cost: 1 13: lbl142 -> lbl142 : E'=0, G'=G-meter, [ A>=1 && G==0 && E==1 && D==A && 2*meter==G+E && meter>=1 ], cost: meter 8: lbl131 -> lbl142 : G'=-1+G, [ G>=1 && A>=G && E==G && D==A ], cost: 1 9: lbl131 -> lbl91 : B'=free_2, [ G>=1+E && E>=1 && A>=G && D==A ], cost: 1 14: lbl131 -> lbl131 : E'=G, [ G>=1+E && E>=1 && A>=G && D==A ], cost: G-E 11: lbl91 -> lbl131 : E'=1+E, [ E>=0 && G>=1+E && A>=G && D==A ], cost: 1 12: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: start0 1: start -> lbl142 : E'=0, G'=-1+D, [ D==0 && B==C && A==0 && E==F && G==H ], cost: 1 2: start -> lbl91 : B'=free, E'=0, G'=D, [ A>=1 && B==C && D==A && E==F && G==H ], cost: 1 3: start -> lbl131 : E'=1, G'=D, [ A>=1 && B==C && D==A && E==F && G==H ], cost: 1 15: start -> lbl131 : E'=D, G'=D, [ A>=1 && B==C && D==A && E==F && G==H && D>=2 ], cost: D 6: lbl142 -> lbl91 : B'=free_1, E'=0, [ E>=2 && A>=E && 1+G==E && D==A ], cost: 1 7: lbl142 -> lbl131 : E'=1, [ E>=2 && A>=E && 1+G==E && D==A ], cost: 1 16: lbl142 -> lbl131 : E'=G, [ E>=2 && A>=E && 1+G==E && D==A && G>=2 && A>=G ], cost: G 8: lbl131 -> lbl142 : G'=-1+G, [ G>=1 && A>=G && E==G && D==A ], cost: 1 9: lbl131 -> lbl91 : B'=free_2, [ G>=1+E && E>=1 && A>=G && D==A ], cost: 1 11: lbl91 -> lbl131 : E'=1+E, [ E>=0 && G>=1+E && A>=G && D==A ], cost: 1 17: lbl91 -> lbl131 : E'=G, [ E>=0 && A>=G && D==A && G>=2+E ], cost: G-E 12: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1 Eliminated locations (on tree-shaped paths): Start location: start0 6: lbl142 -> lbl91 : B'=free_1, E'=0, [ E>=2 && A>=E && 1+G==E && D==A ], cost: 1 7: lbl142 -> lbl131 : E'=1, [ E>=2 && A>=E && 1+G==E && D==A ], cost: 1 16: lbl142 -> lbl131 : E'=G, [ E>=2 && A>=E && 1+G==E && D==A && G>=2 && A>=G ], cost: G 8: lbl131 -> lbl142 : G'=-1+G, [ G>=1 && A>=G && E==G && D==A ], cost: 1 9: lbl131 -> lbl91 : B'=free_2, [ G>=1+E && E>=1 && A>=G && D==A ], cost: 1 11: lbl91 -> lbl131 : E'=1+E, [ E>=0 && G>=1+E && A>=G && D==A ], cost: 1 17: lbl91 -> lbl131 : E'=G, [ E>=0 && A>=G && D==A && G>=2+E ], cost: G-E 18: start0 -> lbl142 : B'=C, D'=A, E'=0, G'=-1+A, [ A==0 ], cost: 2 19: start0 -> lbl91 : B'=free, D'=A, E'=0, G'=A, [ A>=1 ], cost: 2 20: start0 -> lbl131 : B'=C, D'=A, E'=1, G'=A, [ A>=1 ], cost: 2 21: start0 -> lbl131 : B'=C, D'=A, E'=A, G'=A, [ A>=2 ], cost: 1+A Eliminated location lbl142 (as a last resort): Start location: start0 9: lbl131 -> lbl91 : B'=free_2, [ G>=1+E && E>=1 && A>=G && D==A ], cost: 1 22: lbl131 -> lbl91 : B'=free_1, E'=0, G'=-1+G, [ G>=1 && A>=G && E==G && D==A && E>=2 && A>=E && G==E ], cost: 2 23: lbl131 -> lbl131 : E'=1, G'=-1+G, [ G>=1 && A>=G && E==G && D==A && E>=2 && A>=E && G==E ], cost: 2 24: lbl131 -> lbl131 : E'=-1+G, G'=-1+G, [ A>=G && E==G && D==A && E>=2 && A>=E && G==E && -1+G>=2 ], cost: G 11: lbl91 -> lbl131 : E'=1+E, [ E>=0 && G>=1+E && A>=G && D==A ], cost: 1 17: lbl91 -> lbl131 : E'=G, [ E>=0 && A>=G && D==A && G>=2+E ], cost: G-E 19: start0 -> lbl91 : B'=free, D'=A, E'=0, G'=A, [ A>=1 ], cost: 2 20: start0 -> lbl131 : B'=C, D'=A, E'=1, G'=A, [ A>=1 ], cost: 2 21: start0 -> lbl131 : B'=C, D'=A, E'=A, G'=A, [ A>=2 ], cost: 1+A Accelerating simple loops of location 2. Accelerating the following rules: 23: lbl131 -> lbl131 : E'=1, G'=-1+G, [ G>=1 && A>=G && E==G && D==A && E>=2 && A>=E && G==E ], cost: 2 24: lbl131 -> lbl131 : E'=-1+G, G'=-1+G, [ A>=G && E==G && D==A && E>=2 && A>=E && G==E && -1+G>=2 ], cost: G Accelerated rule 23 with metering function -1-G+2*E (after strengthening guard), yielding the new rule 25. Accelerated rule 24 with metering function -2+G, yielding the new rule 26. Removing the simple loops: 24. Accelerated all simple loops using metering functions (where possible): Start location: start0 9: lbl131 -> lbl91 : B'=free_2, [ G>=1+E && E>=1 && A>=G && D==A ], cost: 1 22: lbl131 -> lbl91 : B'=free_1, E'=0, G'=-1+G, [ G>=1 && A>=G && E==G && D==A && E>=2 && A>=E && G==E ], cost: 2 23: lbl131 -> lbl131 : E'=1, G'=-1+G, [ G>=1 && A>=G && E==G && D==A && E>=2 && A>=E && G==E ], cost: 2 25: lbl131 -> lbl131 : E'=1, G'=1+2*G-2*E, [ A>=G && E==G && D==A && E>=2 && A>=E && G==E && 1==-1+G && -1+G==1 && -1-G+2*E>=1 ], cost: -2-2*G+4*E 26: lbl131 -> lbl131 : E'=2, G'=2, [ A>=G && E==G && D==A && E>=2 && A>=E && G==E && -1+G>=2 ], cost: -1+G*(-2+G)+1/2*G-1/2*(-2+G)^2 11: lbl91 -> lbl131 : E'=1+E, [ E>=0 && G>=1+E && A>=G && D==A ], cost: 1 17: lbl91 -> lbl131 : E'=G, [ E>=0 && A>=G && D==A && G>=2+E ], cost: G-E 19: start0 -> lbl91 : B'=free, D'=A, E'=0, G'=A, [ A>=1 ], cost: 2 20: start0 -> lbl131 : B'=C, D'=A, E'=1, G'=A, [ A>=1 ], cost: 2 21: start0 -> lbl131 : B'=C, D'=A, E'=A, G'=A, [ A>=2 ], cost: 1+A Chained accelerated rules (with incoming rules): Start location: start0 9: lbl131 -> lbl91 : B'=free_2, [ G>=1+E && E>=1 && A>=G && D==A ], cost: 1 22: lbl131 -> lbl91 : B'=free_1, E'=0, G'=-1+G, [ G>=1 && A>=G && E==G && D==A && E>=2 && A>=E && G==E ], cost: 2 11: lbl91 -> lbl131 : E'=1+E, [ E>=0 && G>=1+E && A>=G && D==A ], cost: 1 17: lbl91 -> lbl131 : E'=G, [ E>=0 && A>=G && D==A && G>=2+E ], cost: G-E 27: lbl91 -> lbl131 : E'=1, G'=-1+G, [ A>=G && D==A && G>=1 && 1+E==G && 1+E>=2 && A>=1+E && G==1+E ], cost: 3 28: lbl91 -> lbl131 : E'=1, G'=-1+G, [ E>=0 && A>=G && D==A && G>=2+E && G>=2 ], cost: 2+G-E 30: lbl91 -> lbl131 : E'=1, G'=-1+2*G-2*E, [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && 1==-1+G && -1+G==1 && 1-G+2*E>=1 ], cost: 3-2*G+4*E 31: lbl91 -> lbl131 : E'=1, G'=1, [ E>=0 && A>=G && D==A && G>=2+E && 1==-1+G && -1+G==1 ], cost: -2+3*G-E 33: lbl91 -> lbl131 : E'=2, G'=2, [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && -1+G>=2 ], cost: G*(-2+G)+1/2*G-1/2*(-2+G)^2 34: lbl91 -> lbl131 : E'=2, G'=2, [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 ], cost: -1+G*(-2+G)+3/2*G-1/2*(-2+G)^2-E 19: start0 -> lbl91 : B'=free, D'=A, E'=0, G'=A, [ A>=1 ], cost: 2 20: start0 -> lbl131 : B'=C, D'=A, E'=1, G'=A, [ A>=1 ], cost: 2 21: start0 -> lbl131 : B'=C, D'=A, E'=A, G'=A, [ A>=2 ], cost: 1+A 29: start0 -> lbl131 : B'=C, D'=A, E'=1, G'=-1+A, [ A>=2 ], cost: 3+A 32: start0 -> lbl131 : B'=C, D'=A, E'=1, G'=1, [ 1==-1+A && -1+A==1 ], cost: -1+3*A 35: start0 -> lbl131 : B'=C, D'=A, E'=2, G'=2, [ -1+A>=2 ], cost: A*(-2+A)+3/2*A-1/2*(-2+A)^2 Eliminated location lbl131 (as a last resort): Start location: start0 36: lbl91 -> lbl91 : B'=free_2, E'=1+E, [ E>=0 && A>=G && D==A && G>=2+E ], cost: 2 37: lbl91 -> lbl91 : B'=free_1, E'=0, G'=-1+G, [ A>=G && D==A && G>=1 && 1+E==G && 1+E>=2 && A>=1+E && G==1+E ], cost: 3 38: lbl91 -> lbl91 : B'=free_1, E'=0, G'=-1+G, [ E>=0 && A>=G && D==A && G>=2+E && G>=2 ], cost: 2+G-E 41: lbl91 -> lbl91 : B'=free_2, E'=1, G'=-1+G, [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && -1+G>=2 ], cost: 4 42: lbl91 -> lbl91 : B'=free_2, E'=1, G'=-1+G, [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 ], cost: 3+G-E 44: lbl91 -> lbl91 : B'=free_1, E'=0, G'=1, [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && -1+G>=2 && A>=2 ], cost: 2+G*(-2+G)+1/2*G-1/2*(-2+G)^2 45: lbl91 -> lbl91 : B'=free_1, E'=0, G'=1, [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 && A>=2 ], cost: 1+G*(-2+G)+3/2*G-1/2*(-2+G)^2-E 47: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E ], cost: G-E 49: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && G>=2 ], cost: 2+G-E 51: lbl91 -> [9] : [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && 1==-1+G && -1+G==1 && 1-G+2*E>=1 ], cost: 3-2*G+4*E 52: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && 1==-1+G && -1+G==1 ], cost: -2+3*G-E 54: lbl91 -> [9] : [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && -1+G>=2 ], cost: G*(-2+G)+1/2*G-1/2*(-2+G)^2 55: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 ], cost: -1+G*(-2+G)+3/2*G-1/2*(-2+G)^2-E 19: start0 -> lbl91 : B'=free, D'=A, E'=0, G'=A, [ A>=1 ], cost: 2 39: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=A, [ A>=2 ], cost: 3 40: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=-1+A, [ A>=2 ], cost: 3+A 43: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=-1+A, [ -1+A>=2 ], cost: 4+A 46: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=1, [ -1+A>=2 ], cost: 2+A*(-2+A)+3/2*A-1/2*(-2+A)^2 48: start0 -> [9] : [ A>=2 ], cost: 1+A 50: start0 -> [9] : [ A>=2 ], cost: 3+A 53: start0 -> [9] : [ 1==-1+A && -1+A==1 ], cost: -1+3*A 56: start0 -> [9] : [ -1+A>=2 ], cost: A*(-2+A)+3/2*A-1/2*(-2+A)^2 Applied pruning (of leafs and parallel rules): Start location: start0 37: lbl91 -> lbl91 : B'=free_1, E'=0, G'=-1+G, [ A>=G && D==A && G>=1 && 1+E==G && 1+E>=2 && A>=1+E && G==1+E ], cost: 3 38: lbl91 -> lbl91 : B'=free_1, E'=0, G'=-1+G, [ E>=0 && A>=G && D==A && G>=2+E && G>=2 ], cost: 2+G-E 42: lbl91 -> lbl91 : B'=free_2, E'=1, G'=-1+G, [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 ], cost: 3+G-E 44: lbl91 -> lbl91 : B'=free_1, E'=0, G'=1, [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && -1+G>=2 && A>=2 ], cost: 2+G*(-2+G)+1/2*G-1/2*(-2+G)^2 45: lbl91 -> lbl91 : B'=free_1, E'=0, G'=1, [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 && A>=2 ], cost: 1+G*(-2+G)+3/2*G-1/2*(-2+G)^2-E 47: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E ], cost: G-E 49: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && G>=2 ], cost: 2+G-E 52: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && 1==-1+G && -1+G==1 ], cost: -2+3*G-E 54: lbl91 -> [9] : [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && -1+G>=2 ], cost: G*(-2+G)+1/2*G-1/2*(-2+G)^2 55: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 ], cost: -1+G*(-2+G)+3/2*G-1/2*(-2+G)^2-E 19: start0 -> lbl91 : B'=free, D'=A, E'=0, G'=A, [ A>=1 ], cost: 2 39: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=A, [ A>=2 ], cost: 3 40: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=-1+A, [ A>=2 ], cost: 3+A 43: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=-1+A, [ -1+A>=2 ], cost: 4+A 46: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=1, [ -1+A>=2 ], cost: 2+A*(-2+A)+3/2*A-1/2*(-2+A)^2 50: start0 -> [9] : [ A>=2 ], cost: 3+A 53: start0 -> [9] : [ 1==-1+A && -1+A==1 ], cost: -1+3*A 56: start0 -> [9] : [ -1+A>=2 ], cost: A*(-2+A)+3/2*A-1/2*(-2+A)^2 Accelerating simple loops of location 3. Accelerating the following rules: 37: lbl91 -> lbl91 : B'=free_1, E'=0, G'=-1+G, [ A>=G && D==A && G>=1 && 1+E==G && 1+E>=2 && A>=1+E && G==1+E ], cost: 3 38: lbl91 -> lbl91 : B'=free_1, E'=0, G'=-1+G, [ E>=0 && A>=G && D==A && G>=2+E && G>=2 ], cost: 2+G-E 42: lbl91 -> lbl91 : B'=free_2, E'=1, G'=-1+G, [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 ], cost: 3+G-E 44: lbl91 -> lbl91 : B'=free_1, E'=0, G'=1, [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && -1+G>=2 && A>=2 ], cost: 2+G*(-2+G)+1/2*G-1/2*(-2+G)^2 45: lbl91 -> lbl91 : B'=free_1, E'=0, G'=1, [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 && A>=2 ], cost: 1+G*(-2+G)+3/2*G-1/2*(-2+G)^2-E Accelerated rule 37 with metering function 1-G+2*E (after strengthening guard), yielding the new rule 57. Accelerated rule 38 with metering function -1+G-E, yielding the new rule 58. Accelerated rule 42 with metering function meter_1 (where 2*meter_1==-2+G-E), yielding the new rule 59. Accelerated rule 44 with metering function 1-G+E, yielding the new rule 60. Found no metering function for rule 45. Nested simple loops 42 (outer loop) and 57 (inner loop) with metering function meter_2 (where 2*meter_2==-2+G-E), resulting in the new rules: 61. During metering: Instantiating temporary variables by {meter_1==1} During metering: Instantiating temporary variables by {meter_1==-3+G} During metering: Instantiating temporary variables by {meter_1==1} During metering: Instantiating temporary variables by {meter_1==-3+G} Removing the simple loops: 38 42 44. Accelerated all simple loops using metering functions (where possible): Start location: start0 37: lbl91 -> lbl91 : B'=free_1, E'=0, G'=-1+G, [ A>=G && D==A && G>=1 && 1+E==G && 1+E>=2 && A>=1+E && G==1+E ], cost: 3 45: lbl91 -> lbl91 : B'=free_1, E'=0, G'=1, [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 && A>=2 ], cost: 1+G*(-2+G)+3/2*G-1/2*(-2+G)^2-E 47: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E ], cost: G-E 49: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && G>=2 ], cost: 2+G-E 52: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && 1==-1+G && -1+G==1 ], cost: -2+3*G-E 54: lbl91 -> [9] : [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && -1+G>=2 ], cost: G*(-2+G)+1/2*G-1/2*(-2+G)^2 55: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 ], cost: -1+G*(-2+G)+3/2*G-1/2*(-2+G)^2-E 57: lbl91 -> lbl91 : B'=free_1, E'=0, G'=-1+2*G-2*E, [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && 1==-1+G && -1+G==1 && 1-G+2*E>=1 ], cost: 3-3*G+6*E 58: lbl91 -> lbl91 : B'=free_1, E'=0, G'=1+E, [ E>=0 && A>=G && D==A && G>=2+E && G>=2 ], cost: -5/2-1/2*(-1+G-E)^2+(-1+G-E)*G+5/2*G-5/2*E 59: lbl91 -> lbl91 : B'=free_2, E'=1, G'=G-meter_1, [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 && 2*meter_1==-2+G-E && meter_1>=1 ], cost: -1/2*meter_1^2+G*meter_1+5/2*meter_1 60: lbl91 -> lbl91 : B'=free_1, E'=0, G'=1, [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && -1+G>=2 && A>=2 && 1-G+E>=1 ], cost: 1-G+E 61: lbl91 -> lbl91 : B'=free_1, E'=0, G'=5+G*2^meter_2-5*2^meter_2, [ E>=0 && A>=G && D==A && G>=2+E && 3-G==0 && A>=2 && -1+G==2 && 2*meter_2==-2+G-E && meter_2>=1 ], cost: -10+5*meter_2+2*G-2*G*2^meter_2+10*2^meter_2 19: start0 -> lbl91 : B'=free, D'=A, E'=0, G'=A, [ A>=1 ], cost: 2 39: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=A, [ A>=2 ], cost: 3 40: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=-1+A, [ A>=2 ], cost: 3+A 43: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=-1+A, [ -1+A>=2 ], cost: 4+A 46: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=1, [ -1+A>=2 ], cost: 2+A*(-2+A)+3/2*A-1/2*(-2+A)^2 50: start0 -> [9] : [ A>=2 ], cost: 3+A 53: start0 -> [9] : [ 1==-1+A && -1+A==1 ], cost: -1+3*A 56: start0 -> [9] : [ -1+A>=2 ], cost: A*(-2+A)+3/2*A-1/2*(-2+A)^2 Chained accelerated rules (with incoming rules): Start location: start0 47: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E ], cost: G-E 49: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && G>=2 ], cost: 2+G-E 52: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && 1==-1+G && -1+G==1 ], cost: -2+3*G-E 54: lbl91 -> [9] : [ A>=G && D==A && 1+E==G && 1+E>=2 && A>=1+E && G==1+E && -1+G>=2 ], cost: G*(-2+G)+1/2*G-1/2*(-2+G)^2 55: lbl91 -> [9] : [ E>=0 && A>=G && D==A && G>=2+E && -1+G>=2 ], cost: -1+G*(-2+G)+3/2*G-1/2*(-2+G)^2-E 19: start0 -> lbl91 : B'=free, D'=A, E'=0, G'=A, [ A>=1 ], cost: 2 39: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=A, [ A>=2 ], cost: 3 40: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=-1+A, [ A>=2 ], cost: 3+A 43: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=-1+A, [ -1+A>=2 ], cost: 4+A 46: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=1, [ -1+A>=2 ], cost: 2+A*(-2+A)+3/2*A-1/2*(-2+A)^2 50: start0 -> [9] : [ A>=2 ], cost: 3+A 53: start0 -> [9] : [ 1==-1+A && -1+A==1 ], cost: -1+3*A 56: start0 -> [9] : [ -1+A>=2 ], cost: A*(-2+A)+3/2*A-1/2*(-2+A)^2 62: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=-1+A, [ 2==A && A==2 ], cost: 6 63: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=-2+A, [ 2==-1+A && -1+A==2 ], cost: 7+A 64: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=1, [ -1+A>=2 ], cost: 3+A*(-2+A)+3/2*A-1/2*(-2+A)^2 65: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=1, [ A>=3 ], cost: 3+A*(-2+A)+3/2*A-1/2*(-2+A)^2 66: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=1, [ -2+A>=2 ], cost: 5/2+(-1+A)*(-3+A)+5/2*A-1/2*(-3+A)^2 67: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=1, [ -1+A>=3 ], cost: 5/2+(-1+A)*(-3+A)+5/2*A-1/2*(-3+A)^2 68: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=-3+2*A, [ 2-A==0 && A==2 ], cost: 12-3*A 69: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=-5+2*A, [ 3-A==0 && -1+A==2 ], cost: 16-2*A 70: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=1, [ A>=2 ], cost: -1/2-1/2*(-1+A)^2+(-1+A)*A+5/2*A 71: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=2, [ A>=3 ], cost: -2+A*(-2+A)+5/2*A-1/2*(-2+A)^2 72: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=1, [ -1+A>=2 ], cost: -2+(-1+A)*(-2+A)+7/2*A-1/2*(-2+A)^2 73: start0 -> lbl91 : B'=free_1, D'=A, E'=0, G'=2, [ -1+A>=3 ], cost: -7/2+(-1+A)*(-3+A)+7/2*A-1/2*(-3+A)^2 74: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ -1+A>=2 && 2*meter_1==-2+A && meter_1>=1 ], cost: 2-1/2*meter_1^2+5/2*meter_1+A*meter_1 75: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ A>=3 && 2*meter_1==-3+A && meter_1>=1 ], cost: 3-1/2*meter_1^2+5/2*meter_1+A*meter_1 76: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -2+A>=2 && 2*meter_1==-3+A && meter_1>=1 ], cost: 3-1/2*meter_1^2+A+5/2*meter_1+(-1+A)*meter_1 77: start0 -> lbl91 : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 ], cost: 4-1/2*meter_1^2+A+5/2*meter_1+(-1+A)*meter_1 Eliminated locations (on tree-shaped paths): Start location: start0 50: start0 -> [9] : [ A>=2 ], cost: 3+A 53: start0 -> [9] : [ 1==-1+A && -1+A==1 ], cost: -1+3*A 56: start0 -> [9] : [ -1+A>=2 ], cost: A*(-2+A)+3/2*A-1/2*(-2+A)^2 78: start0 -> [9] : B'=free, D'=A, E'=0, G'=A, [ A>=2 ], cost: 2+A 79: start0 -> [9] : B'=free, D'=A, E'=0, G'=A, [ A>=2 ], cost: 4+A 80: start0 -> [9] : B'=free, D'=A, E'=0, G'=A, [ 1==-1+A && -1+A==1 ], cost: 3*A 81: start0 -> [9] : B'=free, D'=A, E'=0, G'=A, [ -1+A>=2 ], cost: 1+A*(-2+A)+3/2*A-1/2*(-2+A)^2 82: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A, [ A>=3 ], cost: 2+A 83: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A, [ A>=3 ], cost: 4+A 84: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A, [ A>=3 ], cost: 1+A*(-2+A)+3/2*A-1/2*(-2+A)^2 85: start0 -> [9] : B'=free_1, D'=A, E'=0, G'=-1+A, [ -1+A>=2 ], cost: 2+2*A 86: start0 -> [9] : B'=free_1, D'=A, E'=0, G'=-1+A, [ -1+A>=2 ], cost: 4+2*A 87: start0 -> [9] : B'=free_1, D'=A, E'=0, G'=-1+A, [ 1==-2+A && -2+A==1 ], cost: -2+4*A 88: start0 -> [9] : B'=free_1, D'=A, E'=0, G'=-1+A, [ -2+A>=2 ], cost: 1/2+(-1+A)*(-3+A)+5/2*A-1/2*(-3+A)^2 89: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A, [ -1+A>=3 ], cost: 2+2*A 90: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A, [ -1+A>=3 ], cost: 4+2*A 91: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A, [ -1+A>=3 ], cost: 1/2+(-1+A)*(-3+A)+5/2*A-1/2*(-3+A)^2 92: start0 -> [9] : B'=free_1, D'=A, E'=0, G'=2, [ A>=3 ], cost: A*(-2+A)+5/2*A-1/2*(-2+A)^2 93: start0 -> [9] : B'=free_1, D'=A, E'=0, G'=2, [ A>=3 ], cost: 2+A*(-2+A)+5/2*A-1/2*(-2+A)^2 94: start0 -> [9] : B'=free_1, D'=A, E'=0, G'=2, [ A>=3 ], cost: 2+A*(-2+A)+5/2*A-1/2*(-2+A)^2 95: start0 -> [9] : B'=free_1, D'=A, E'=0, G'=2, [ -1+A>=3 ], cost: -3/2+(-1+A)*(-3+A)+7/2*A-1/2*(-3+A)^2 96: start0 -> [9] : B'=free_1, D'=A, E'=0, G'=2, [ -1+A>=3 ], cost: 1/2+(-1+A)*(-3+A)+7/2*A-1/2*(-3+A)^2 97: start0 -> [9] : B'=free_1, D'=A, E'=0, G'=2, [ -1+A>=3 ], cost: 1/2+(-1+A)*(-3+A)+7/2*A-1/2*(-3+A)^2 98: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ -1+A>=2 && 2*meter_1==-2+A && meter_1>=1 && A-meter_1>=3 ], cost: 1-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 99: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ -1+A>=2 && 2*meter_1==-2+A && meter_1>=1 && A-meter_1>=3 ], cost: 3-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 100: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ -1+A>=2 && 2*meter_1==-2+A && meter_1>=1 && A-meter_1>=3 ], cost: -1/2*meter_1^2+3/2*A+(-2+A-meter_1)*(A-meter_1)+meter_1+A*meter_1-1/2*(-2+A-meter_1)^2 101: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ A>=3 && 2*meter_1==-3+A && meter_1>=1 && A-meter_1>=3 ], cost: 2-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 102: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ A>=3 && 2*meter_1==-3+A && meter_1>=1 && A-meter_1>=3 ], cost: 4-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 103: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ A>=3 && 2*meter_1==-3+A && meter_1>=1 && A-meter_1>=3 ], cost: 1-1/2*meter_1^2+3/2*A+(-2+A-meter_1)*(A-meter_1)+meter_1+A*meter_1-1/2*(-2+A-meter_1)^2 104: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -2+A>=2 && 2*meter_1==-3+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: 1-1/2*meter_1^2+2*A+3/2*meter_1+(-1+A)*meter_1 105: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -2+A>=2 && 2*meter_1==-3+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: 3-1/2*meter_1^2+2*A+3/2*meter_1+(-1+A)*meter_1 106: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -2+A>=2 && 2*meter_1==-3+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: -1/2-1/2*meter_1^2+5/2*A+(-3+A-meter_1)*(-1+A-meter_1)-1/2*(-3+A-meter_1)^2+meter_1+(-1+A)*meter_1 107: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: 2-1/2*meter_1^2+2*A+3/2*meter_1+(-1+A)*meter_1 108: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: 4-1/2*meter_1^2+2*A+3/2*meter_1+(-1+A)*meter_1 109: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: 1/2-1/2*meter_1^2+5/2*A+(-3+A-meter_1)*(-1+A-meter_1)-1/2*(-3+A-meter_1)^2+meter_1+(-1+A)*meter_1 110: start0 -> [11] : [ A>=2 ], cost: 3+A 111: start0 -> [11] : [ -1+A>=2 ], cost: 4+A 112: start0 -> [11] : [ -1+A>=2 ], cost: 2+A*(-2+A)+3/2*A-1/2*(-2+A)^2 113: start0 -> [11] : [ 2==-1+A && -1+A==2 ], cost: 7+A 114: start0 -> [11] : [ -1+A>=2 ], cost: 3+A*(-2+A)+3/2*A-1/2*(-2+A)^2 115: start0 -> [11] : [ A>=3 ], cost: 3+A*(-2+A)+3/2*A-1/2*(-2+A)^2 116: start0 -> [11] : [ -2+A>=2 ], cost: 5/2+(-1+A)*(-3+A)+5/2*A-1/2*(-3+A)^2 117: start0 -> [11] : [ -1+A>=3 ], cost: 5/2+(-1+A)*(-3+A)+5/2*A-1/2*(-3+A)^2 118: start0 -> [11] : [ 2-A==0 && A==2 ], cost: 12-3*A 119: start0 -> [11] : [ 3-A==0 && -1+A==2 ], cost: 16-2*A 120: start0 -> [11] : [ A>=2 ], cost: -1/2-1/2*(-1+A)^2+(-1+A)*A+5/2*A 121: start0 -> [11] : [ A>=3 ], cost: -2+A*(-2+A)+5/2*A-1/2*(-2+A)^2 122: start0 -> [11] : [ -1+A>=2 ], cost: -2+(-1+A)*(-2+A)+7/2*A-1/2*(-2+A)^2 123: start0 -> [11] : [ -1+A>=3 ], cost: -7/2+(-1+A)*(-3+A)+7/2*A-1/2*(-3+A)^2 124: start0 -> [11] : [ -1+A>=2 && 2*meter_1==-2+A && meter_1>=1 ], cost: 2-1/2*meter_1^2+5/2*meter_1+A*meter_1 125: start0 -> [11] : [ A>=3 && 2*meter_1==-3+A && meter_1>=1 ], cost: 3-1/2*meter_1^2+5/2*meter_1+A*meter_1 126: start0 -> [11] : [ -2+A>=2 && 2*meter_1==-3+A && meter_1>=1 ], cost: 3-1/2*meter_1^2+A+5/2*meter_1+(-1+A)*meter_1 127: start0 -> [11] : [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 ], cost: 4-1/2*meter_1^2+A+5/2*meter_1+(-1+A)*meter_1 Applied pruning (of leafs and parallel rules): Start location: start0 100: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ -1+A>=2 && 2*meter_1==-2+A && meter_1>=1 && A-meter_1>=3 ], cost: -1/2*meter_1^2+3/2*A+(-2+A-meter_1)*(A-meter_1)+meter_1+A*meter_1-1/2*(-2+A-meter_1)^2 102: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ A>=3 && 2*meter_1==-3+A && meter_1>=1 && A-meter_1>=3 ], cost: 4-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 106: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -2+A>=2 && 2*meter_1==-3+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: -1/2-1/2*meter_1^2+5/2*A+(-3+A-meter_1)*(-1+A-meter_1)-1/2*(-3+A-meter_1)^2+meter_1+(-1+A)*meter_1 108: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: 4-1/2*meter_1^2+2*A+3/2*meter_1+(-1+A)*meter_1 109: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: 1/2-1/2*meter_1^2+5/2*A+(-3+A-meter_1)*(-1+A-meter_1)-1/2*(-3+A-meter_1)^2+meter_1+(-1+A)*meter_1 114: start0 -> [11] : [ -1+A>=2 ], cost: 3+A*(-2+A)+3/2*A-1/2*(-2+A)^2 124: start0 -> [11] : [ -1+A>=2 && 2*meter_1==-2+A && meter_1>=1 ], cost: 2-1/2*meter_1^2+5/2*meter_1+A*meter_1 125: start0 -> [11] : [ A>=3 && 2*meter_1==-3+A && meter_1>=1 ], cost: 3-1/2*meter_1^2+5/2*meter_1+A*meter_1 126: start0 -> [11] : [ -2+A>=2 && 2*meter_1==-3+A && meter_1>=1 ], cost: 3-1/2*meter_1^2+A+5/2*meter_1+(-1+A)*meter_1 127: start0 -> [11] : [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 ], cost: 4-1/2*meter_1^2+A+5/2*meter_1+(-1+A)*meter_1 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: start0 100: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ -1+A>=2 && 2*meter_1==-2+A && meter_1>=1 && A-meter_1>=3 ], cost: -1/2*meter_1^2+3/2*A+(-2+A-meter_1)*(A-meter_1)+meter_1+A*meter_1-1/2*(-2+A-meter_1)^2 102: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ A>=3 && 2*meter_1==-3+A && meter_1>=1 && A-meter_1>=3 ], cost: 4-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 106: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -2+A>=2 && 2*meter_1==-3+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: -1/2-1/2*meter_1^2+5/2*A+(-3+A-meter_1)*(-1+A-meter_1)-1/2*(-3+A-meter_1)^2+meter_1+(-1+A)*meter_1 108: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: 4-1/2*meter_1^2+2*A+3/2*meter_1+(-1+A)*meter_1 109: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 && -1+A-meter_1>=3 ], cost: 1/2-1/2*meter_1^2+5/2*A+(-3+A-meter_1)*(-1+A-meter_1)-1/2*(-3+A-meter_1)^2+meter_1+(-1+A)*meter_1 114: start0 -> [11] : [ -1+A>=2 ], cost: 3+A*(-2+A)+3/2*A-1/2*(-2+A)^2 124: start0 -> [11] : [ -1+A>=2 && 2*meter_1==-2+A && meter_1>=1 ], cost: 2-1/2*meter_1^2+5/2*meter_1+A*meter_1 125: start0 -> [11] : [ A>=3 && 2*meter_1==-3+A && meter_1>=1 ], cost: 3-1/2*meter_1^2+5/2*meter_1+A*meter_1 126: start0 -> [11] : [ -2+A>=2 && 2*meter_1==-3+A && meter_1>=1 ], cost: 3-1/2*meter_1^2+A+5/2*meter_1+(-1+A)*meter_1 127: start0 -> [11] : [ -1+A>=3 && 2*meter_1==-4+A && meter_1>=1 ], cost: 4-1/2*meter_1^2+A+5/2*meter_1+(-1+A)*meter_1 Computing asymptotic complexity for rule 100 Solved the limit problem by the following transformations: Created initial limit problem: 3-A+2*meter_1 (+/+!), -1+A-2*meter_1 (+/+!), -2+A (+/+!), -2+3/2*A+1/2*A^2+meter_1 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==2*n,meter_1==-1+n} resulting limit problem: [solved] Solution: A / 2*n meter_1 / -1+n Resulting cost -3+4*n+2*n^2 has complexity: Poly(n^2) Found new complexity Poly(n^2). Computing asymptotic complexity for rule 102 Simplified the guard: 102: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=A-meter_1, [ 2*meter_1==-3+A && meter_1>=1 ], cost: 4-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 Solved the limit problem by the following transformations: Created initial limit problem: 4-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 (+), -2+A-2*meter_1 (+/+!), meter_1 (+/+!), 4-A+2*meter_1 (+/+!) [not solved] applying transformation rule (C) using substitution {A==3+2*meter_1} resulting limit problem: 1 (+/+!), 7-1/2*meter_1^2+(3+2*meter_1)*meter_1+7/2*meter_1 (+), meter_1 (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 7-1/2*meter_1^2+(3+2*meter_1)*meter_1+7/2*meter_1 (+), meter_1 (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solution: A / 3+2*n meter_1 / n Resulting cost 7+3/2*n^2+13/2*n has complexity: Poly(n^2) Computing asymptotic complexity for rule 106 Solved the limit problem by the following transformations: Created initial limit problem: -2+A-2*meter_1 (+/+!), 4-A+2*meter_1 (+/+!), -3+A (+/+!), -2+3/2*A+1/2*A^2+meter_1 (+) [not solved] applying transformation rule (C) using substitution {A==3+2*meter_1} resulting limit problem: 1 (+/+!), 2*meter_1 (+/+!), 5/2+4*meter_1+1/2*(3+2*meter_1)^2 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2*meter_1 (+/+!), 5/2+4*meter_1+1/2*(3+2*meter_1)^2 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: -2+A-2*meter_1 (+/+!), 4-A+2*meter_1 (+/+!), -3+A (+/+!), -2+3/2*A+1/2*A^2+meter_1 (+) [not solved] applying transformation rule (C) using substitution {A==3+2*meter_1} resulting limit problem: 1 (+/+!), 2*meter_1 (+/+!), 5/2+4*meter_1+1/2*(3+2*meter_1)^2 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2*meter_1 (+/+!), 5/2+4*meter_1+1/2*(3+2*meter_1)^2 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solution: A / 3+2*n meter_1 / n Resulting cost 7+2*n^2+10*n has complexity: Poly(n^2) Computing asymptotic complexity for rule 108 Simplified the guard: 108: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ 2*meter_1==-4+A && meter_1>=1 ], cost: 4-1/2*meter_1^2+2*A+3/2*meter_1+(-1+A)*meter_1 Solved the limit problem by the following transformations: Created initial limit problem: -3+A-2*meter_1 (+/+!), meter_1 (+/+!), 4-1/2*meter_1^2+2*A+1/2*meter_1+A*meter_1 (+), 5-A+2*meter_1 (+/+!) [not solved] applying transformation rule (C) using substitution {A==4+2*meter_1} resulting limit problem: 1 (+/+!), 12-1/2*meter_1^2+2*(2+meter_1)*meter_1+9/2*meter_1 (+), meter_1 (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 12-1/2*meter_1^2+2*(2+meter_1)*meter_1+9/2*meter_1 (+), meter_1 (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solution: A / 4+2*n meter_1 / n Resulting cost 12+17/2*n+3/2*n^2 has complexity: Poly(n^2) Computing asymptotic complexity for rule 109 Simplified the guard: 109: start0 -> [9] : B'=free_2, D'=A, E'=1, G'=-1+A-meter_1, [ 2*meter_1==-4+A && meter_1>=1 ], cost: 1/2-1/2*meter_1^2+5/2*A+(-3+A-meter_1)*(-1+A-meter_1)-1/2*(-3+A-meter_1)^2+meter_1+(-1+A)*meter_1 Solved the limit problem by the following transformations: Created initial limit problem: -1+3/2*A+1/2*A^2+meter_1 (+), -3+A-2*meter_1 (+/+!), meter_1 (+/+!), 5-A+2*meter_1 (+/+!) [not solved] applying transformation rule (C) using substitution {A==4+2*meter_1} resulting limit problem: 1 (+/+!), 5+2*(2+meter_1)^2+4*meter_1 (+), meter_1 (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 5+2*(2+meter_1)^2+4*meter_1 (+), meter_1 (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solution: A / 4+2*n meter_1 / n Resulting cost 13+12*n+2*n^2 has complexity: Poly(n^2) Computing asymptotic complexity for rule 124 Solved the limit problem by the following transformations: Created initial limit problem: 3-A+2*meter_1 (+/+!), -1+A-2*meter_1 (+/+!), -2+A (+/+!), 2-1/2*meter_1^2+5/2*meter_1+A*meter_1 (+) [not solved] applying transformation rule (C) using substitution {A==2+2*meter_1} resulting limit problem: 1 (+/+!), 2*meter_1 (+/+!), 2-1/2*meter_1^2+5/2*meter_1+2*(1+meter_1)*meter_1 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2*meter_1 (+/+!), 2-1/2*meter_1^2+5/2*meter_1+2*(1+meter_1)*meter_1 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 3-A+2*meter_1 (+/+!), -1+A-2*meter_1 (+/+!), -2+A (+/+!), 2-1/2*meter_1^2+5/2*meter_1+A*meter_1 (+) [not solved] applying transformation rule (C) using substitution {A==2+2*meter_1} resulting limit problem: 1 (+/+!), 2*meter_1 (+/+!), 2-1/2*meter_1^2+5/2*meter_1+2*(1+meter_1)*meter_1 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2*meter_1 (+/+!), 2-1/2*meter_1^2+5/2*meter_1+2*(1+meter_1)*meter_1 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solution: A / 2+2*n meter_1 / n Resulting cost 2+9/2*n+3/2*n^2 has complexity: Poly(n^2) Computing asymptotic complexity for rule 125 Simplified the guard: 125: start0 -> [11] : [ 2*meter_1==-3+A && meter_1>=1 ], cost: 3-1/2*meter_1^2+5/2*meter_1+A*meter_1 Solved the limit problem by the following transformations: Created initial limit problem: -2+A-2*meter_1 (+/+!), meter_1 (+/+!), 3-1/2*meter_1^2+5/2*meter_1+A*meter_1 (+), 4-A+2*meter_1 (+/+!) [not solved] applying transformation rule (C) using substitution {A==3+2*meter_1} resulting limit problem: 1 (+/+!), 3-1/2*meter_1^2+(3+2*meter_1)*meter_1+5/2*meter_1 (+), meter_1 (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 3-1/2*meter_1^2+(3+2*meter_1)*meter_1+5/2*meter_1 (+), meter_1 (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solution: A / 3+2*n meter_1 / n Resulting cost 3+3/2*n^2+11/2*n has complexity: Poly(n^2) Computing asymptotic complexity for rule 126 Solved the limit problem by the following transformations: Created initial limit problem: 3-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 (+), -2+A-2*meter_1 (+/+!), 4-A+2*meter_1 (+/+!), -3+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==3+2*meter_1} resulting limit problem: 1 (+/+!), 6-1/2*meter_1^2+(3+2*meter_1)*meter_1+7/2*meter_1 (+), 2*meter_1 (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6-1/2*meter_1^2+(3+2*meter_1)*meter_1+7/2*meter_1 (+), 2*meter_1 (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 3-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 (+), -2+A-2*meter_1 (+/+!), 4-A+2*meter_1 (+/+!), -3+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==3+2*meter_1} resulting limit problem: 1 (+/+!), 6-1/2*meter_1^2+(3+2*meter_1)*meter_1+7/2*meter_1 (+), 2*meter_1 (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6-1/2*meter_1^2+(3+2*meter_1)*meter_1+7/2*meter_1 (+), 2*meter_1 (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solution: A / 3+2*n meter_1 / n Resulting cost 6+13/2*n+3/2*n^2 has complexity: Poly(n^2) Computing asymptotic complexity for rule 127 Simplified the guard: 127: start0 -> [11] : [ 2*meter_1==-4+A && meter_1>=1 ], cost: 4-1/2*meter_1^2+A+5/2*meter_1+(-1+A)*meter_1 Solved the limit problem by the following transformations: Created initial limit problem: 4-1/2*meter_1^2+A+3/2*meter_1+A*meter_1 (+), -3+A-2*meter_1 (+/+!), meter_1 (+/+!), 5-A+2*meter_1 (+/+!) [not solved] applying transformation rule (C) using substitution {A==4+2*meter_1} resulting limit problem: 1 (+/+!), 8-1/2*meter_1^2+2*(2+meter_1)*meter_1+7/2*meter_1 (+), meter_1 (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 8-1/2*meter_1^2+2*(2+meter_1)*meter_1+7/2*meter_1 (+), meter_1 (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_1==n} resulting limit problem: [solved] Solution: A / 4+2*n meter_1 / n Resulting cost 8+3/2*n^2+15/2*n has complexity: Poly(n^2) Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^2) Cpx degree: 2 Solved cost: -3+4*n+2*n^2 Rule cost: -1/2*meter_1^2+3/2*A+(-2+A-meter_1)*(A-meter_1)+meter_1+A*meter_1-1/2*(-2+A-meter_1)^2 Rule guard: [ -1+A>=2 && 2*meter_1==-2+A ] WORST_CASE(Omega(n^2),?) ---------------------------------------- (2) BOUNDS(n^2, INF)