/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) 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^1, n^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 21 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 550 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalSequentialSinglestart(A, B) -> Com_1(evalSequentialSingleentryin(A, B)) :|: TRUE evalSequentialSingleentryin(A, B) -> Com_1(evalSequentialSinglebb1in(0, B)) :|: TRUE evalSequentialSinglebb1in(A, B) -> Com_1(evalSequentialSinglebb5in(A, B)) :|: A >= B evalSequentialSinglebb1in(A, B) -> Com_1(evalSequentialSinglebb2in(A, B)) :|: B >= A + 1 evalSequentialSinglebb2in(A, B) -> Com_1(evalSequentialSinglebbin(A, B)) :|: 0 >= C + 1 evalSequentialSinglebb2in(A, B) -> Com_1(evalSequentialSinglebbin(A, B)) :|: C >= 1 evalSequentialSinglebb2in(A, B) -> Com_1(evalSequentialSinglebb5in(A, B)) :|: TRUE evalSequentialSinglebbin(A, B) -> Com_1(evalSequentialSinglebb1in(A + 1, B)) :|: TRUE evalSequentialSinglebb5in(A, B) -> Com_1(evalSequentialSinglebb4in(A, B)) :|: B >= A + 1 evalSequentialSinglebb5in(A, B) -> Com_1(evalSequentialSinglereturnin(A, B)) :|: A >= B evalSequentialSinglebb4in(A, B) -> Com_1(evalSequentialSinglebb5in(A + 1, B)) :|: TRUE evalSequentialSinglereturnin(A, B) -> Com_1(evalSequentialSinglestop(A, B)) :|: TRUE The start-symbols are:[evalSequentialSinglestart_2] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 7*Ar_1 + 21) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalSequentialSinglestart(Ar_0, Ar_1) -> Com_1(evalSequentialSingleentryin(Ar_0, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSingleentryin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb1in(0, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb2in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebbin(Ar_0, Ar_1)) [ 0 >= C + 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebbin(Ar_0, Ar_1)) [ C >= 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglebbin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb1in(Ar_0 + 1, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb4in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglereturnin(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb4in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0 + 1, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglereturnin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestop(Ar_0, Ar_1)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestart(Ar_0, Ar_1)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 1 produces the following problem: 2: T: (Comp: 1, Cost: 1) evalSequentialSinglestart(Ar_0, Ar_1) -> Com_1(evalSequentialSingleentryin(Ar_0, Ar_1)) (Comp: 1, Cost: 1) evalSequentialSingleentryin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb1in(0, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb2in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebbin(Ar_0, Ar_1)) [ 0 >= C + 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebbin(Ar_0, Ar_1)) [ C >= 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglebbin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb1in(Ar_0 + 1, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb4in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglereturnin(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb4in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0 + 1, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglereturnin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestop(Ar_0, Ar_1)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestart(Ar_0, Ar_1)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalSequentialSinglestart) = 3 Pol(evalSequentialSingleentryin) = 3 Pol(evalSequentialSinglebb1in) = 3 Pol(evalSequentialSinglebb5in) = 2 Pol(evalSequentialSinglebb2in) = 3 Pol(evalSequentialSinglebbin) = 3 Pol(evalSequentialSinglebb4in) = 2 Pol(evalSequentialSinglereturnin) = 1 Pol(evalSequentialSinglestop) = 0 Pol(koat_start) = 3 orients all transitions weakly and the transitions evalSequentialSinglereturnin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestop(Ar_0, Ar_1)) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglereturnin(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalSequentialSinglestart(Ar_0, Ar_1) -> Com_1(evalSequentialSingleentryin(Ar_0, Ar_1)) (Comp: 1, Cost: 1) evalSequentialSingleentryin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb1in(0, Ar_1)) (Comp: 3, Cost: 1) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb2in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebbin(Ar_0, Ar_1)) [ 0 >= C + 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebbin(Ar_0, Ar_1)) [ C >= 1 ] (Comp: 3, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglebbin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb1in(Ar_0 + 1, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb4in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 3, Cost: 1) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglereturnin(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb4in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0 + 1, Ar_1)) (Comp: 3, Cost: 1) evalSequentialSinglereturnin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestop(Ar_0, Ar_1)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestart(Ar_0, Ar_1)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalSequentialSinglestart) = V_2 + 1 Pol(evalSequentialSingleentryin) = V_2 + 1 Pol(evalSequentialSinglebb1in) = -V_1 + V_2 + 1 Pol(evalSequentialSinglebb5in) = -V_1 + V_2 Pol(evalSequentialSinglebb2in) = -V_1 + V_2 Pol(evalSequentialSinglebbin) = -V_1 + V_2 Pol(evalSequentialSinglebb4in) = -V_1 + V_2 - 1 Pol(evalSequentialSinglereturnin) = -V_1 + V_2 Pol(evalSequentialSinglestop) = -V_1 + V_2 Pol(koat_start) = V_2 + 1 orients all transitions weakly and the transitions evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb4in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb2in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 1) evalSequentialSinglestart(Ar_0, Ar_1) -> Com_1(evalSequentialSingleentryin(Ar_0, Ar_1)) (Comp: 1, Cost: 1) evalSequentialSingleentryin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb1in(0, Ar_1)) (Comp: 3, Cost: 1) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1 + 1, Cost: 1) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb2in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebbin(Ar_0, Ar_1)) [ 0 >= C + 1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebbin(Ar_0, Ar_1)) [ C >= 1 ] (Comp: 3, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) (Comp: ?, Cost: 1) evalSequentialSinglebbin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb1in(Ar_0 + 1, Ar_1)) (Comp: Ar_1 + 1, Cost: 1) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb4in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 3, Cost: 1) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglereturnin(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalSequentialSinglebb4in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0 + 1, Ar_1)) (Comp: 3, Cost: 1) evalSequentialSinglereturnin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestop(Ar_0, Ar_1)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestart(Ar_0, Ar_1)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 4 produces the following problem: 5: T: (Comp: 1, Cost: 1) evalSequentialSinglestart(Ar_0, Ar_1) -> Com_1(evalSequentialSingleentryin(Ar_0, Ar_1)) (Comp: 1, Cost: 1) evalSequentialSingleentryin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb1in(0, Ar_1)) (Comp: 3, Cost: 1) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1 + 1, Cost: 1) evalSequentialSinglebb1in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb2in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] (Comp: Ar_1 + 1, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebbin(Ar_0, Ar_1)) [ 0 >= C + 1 ] (Comp: Ar_1 + 1, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebbin(Ar_0, Ar_1)) [ C >= 1 ] (Comp: 3, Cost: 1) evalSequentialSinglebb2in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0, Ar_1)) (Comp: 2*Ar_1 + 2, Cost: 1) evalSequentialSinglebbin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb1in(Ar_0 + 1, Ar_1)) (Comp: Ar_1 + 1, Cost: 1) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb4in(Ar_0, Ar_1)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 3, Cost: 1) evalSequentialSinglebb5in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglereturnin(Ar_0, Ar_1)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1 + 1, Cost: 1) evalSequentialSinglebb4in(Ar_0, Ar_1) -> Com_1(evalSequentialSinglebb5in(Ar_0 + 1, Ar_1)) (Comp: 3, Cost: 1) evalSequentialSinglereturnin(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestop(Ar_0, Ar_1)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1) -> Com_1(evalSequentialSinglestart(Ar_0, Ar_1)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 7*Ar_1 + 21 Time: 0.062 sec (SMT: 0.054 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalSequentialSinglestart 0: evalSequentialSinglestart -> evalSequentialSingleentryin : [], cost: 1 1: evalSequentialSingleentryin -> evalSequentialSinglebb1in : A'=0, [], cost: 1 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 4: evalSequentialSinglebb2in -> evalSequentialSinglebbin : [ 0>=1+free ], cost: 1 5: evalSequentialSinglebb2in -> evalSequentialSinglebbin : [ free_1>=1 ], cost: 1 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 7: evalSequentialSinglebbin -> evalSequentialSinglebb1in : A'=1+A, [], cost: 1 8: evalSequentialSinglebb5in -> evalSequentialSinglebb4in : [ B>=1+A ], cost: 1 9: evalSequentialSinglebb5in -> evalSequentialSinglereturnin : [ A>=B ], cost: 1 10: evalSequentialSinglebb4in -> evalSequentialSinglebb5in : A'=1+A, [], cost: 1 11: evalSequentialSinglereturnin -> evalSequentialSinglestop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalSequentialSinglestart -> evalSequentialSingleentryin : [], cost: 1 Removed unreachable and leaf rules: Start location: evalSequentialSinglestart 0: evalSequentialSinglestart -> evalSequentialSingleentryin : [], cost: 1 1: evalSequentialSingleentryin -> evalSequentialSinglebb1in : A'=0, [], cost: 1 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 4: evalSequentialSinglebb2in -> evalSequentialSinglebbin : [ 0>=1+free ], cost: 1 5: evalSequentialSinglebb2in -> evalSequentialSinglebbin : [ free_1>=1 ], cost: 1 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 7: evalSequentialSinglebbin -> evalSequentialSinglebb1in : A'=1+A, [], cost: 1 8: evalSequentialSinglebb5in -> evalSequentialSinglebb4in : [ B>=1+A ], cost: 1 10: evalSequentialSinglebb4in -> evalSequentialSinglebb5in : A'=1+A, [], cost: 1 Simplified all rules, resulting in: Start location: evalSequentialSinglestart 0: evalSequentialSinglestart -> evalSequentialSingleentryin : [], cost: 1 1: evalSequentialSingleentryin -> evalSequentialSinglebb1in : A'=0, [], cost: 1 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 5: evalSequentialSinglebb2in -> evalSequentialSinglebbin : [], cost: 1 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 7: evalSequentialSinglebbin -> evalSequentialSinglebb1in : A'=1+A, [], cost: 1 8: evalSequentialSinglebb5in -> evalSequentialSinglebb4in : [ B>=1+A ], cost: 1 10: evalSequentialSinglebb4in -> evalSequentialSinglebb5in : A'=1+A, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalSequentialSinglestart 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 13: evalSequentialSinglebb2in -> evalSequentialSinglebb1in : A'=1+A, [], cost: 2 14: evalSequentialSinglebb5in -> evalSequentialSinglebb5in : A'=1+A, [ B>=1+A ], cost: 2 Accelerating simple loops of location 5. Accelerating the following rules: 14: evalSequentialSinglebb5in -> evalSequentialSinglebb5in : A'=1+A, [ B>=1+A ], cost: 2 Accelerated rule 14 with metering function -A+B, yielding the new rule 15. Removing the simple loops: 14. Accelerated all simple loops using metering functions (where possible): Start location: evalSequentialSinglestart 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 13: evalSequentialSinglebb2in -> evalSequentialSinglebb1in : A'=1+A, [], cost: 2 15: evalSequentialSinglebb5in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: -2*A+2*B Chained accelerated rules (with incoming rules): Start location: evalSequentialSinglestart 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 2: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : [ A>=B ], cost: 1 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 6: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : [], cost: 1 13: evalSequentialSinglebb2in -> evalSequentialSinglebb1in : A'=1+A, [], cost: 2 16: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: 1-2*A+2*B Removed unreachable locations (and leaf rules with constant cost): Start location: evalSequentialSinglestart 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 3: evalSequentialSinglebb1in -> evalSequentialSinglebb2in : [ B>=1+A ], cost: 1 13: evalSequentialSinglebb2in -> evalSequentialSinglebb1in : A'=1+A, [], cost: 2 16: evalSequentialSinglebb2in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: 1-2*A+2*B Eliminated locations (on tree-shaped paths): Start location: evalSequentialSinglestart 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 17: evalSequentialSinglebb1in -> evalSequentialSinglebb1in : A'=1+A, [ B>=1+A ], cost: 3 18: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: 2-2*A+2*B Accelerating simple loops of location 2. Accelerating the following rules: 17: evalSequentialSinglebb1in -> evalSequentialSinglebb1in : A'=1+A, [ B>=1+A ], cost: 3 Accelerated rule 17 with metering function -A+B, yielding the new rule 19. Removing the simple loops: 17. Accelerated all simple loops using metering functions (where possible): Start location: evalSequentialSinglestart 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 18: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: 2-2*A+2*B 19: evalSequentialSinglebb1in -> evalSequentialSinglebb1in : A'=B, [ B>=1+A ], cost: -3*A+3*B Chained accelerated rules (with incoming rules): Start location: evalSequentialSinglestart 12: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=0, [], cost: 2 20: evalSequentialSinglestart -> evalSequentialSinglebb1in : A'=B, [ B>=1 ], cost: 2+3*B 18: evalSequentialSinglebb1in -> evalSequentialSinglebb5in : A'=B, [ B>=1+A ], cost: 2-2*A+2*B Eliminated locations (on tree-shaped paths): Start location: evalSequentialSinglestart 21: evalSequentialSinglestart -> evalSequentialSinglebb5in : A'=B, [ B>=1 ], cost: 4+2*B 22: evalSequentialSinglestart -> [11] : [ B>=1 ], cost: 2+3*B ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalSequentialSinglestart 21: evalSequentialSinglestart -> evalSequentialSinglebb5in : A'=B, [ B>=1 ], cost: 4+2*B 22: evalSequentialSinglestart -> [11] : [ B>=1 ], cost: 2+3*B Computing asymptotic complexity for rule 21 Solved the limit problem by the following transformations: Created initial limit problem: 4+2*B (+), B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {B==n} resulting limit problem: [solved] Solution: B / n Resulting cost 4+2*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^1) Cpx degree: 1 Solved cost: 4+2*n Rule cost: 4+2*B Rule guard: [ B>=1 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)