/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(n^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, max(5, 1 + 2 * Arg_1) * max(4, 4 * Arg_0) + max(5, 1 + 2 * Arg_1) * max(5, 5 * Arg_0) + max(5, 1 + 2 * Arg_1) * max(3, 3 * Arg_0) + nat(Arg_1) + max(7 + 2 * Arg_1, 11)). (0) CpxIntTrs (1) Koat Proof [FINISHED, 136 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 411 ms] (4) BOUNDS(1, INF) (5) Koat2 Proof [FINISHED, 632 ms] (6) BOUNDS(1, max(5, 1 + 2 * Arg_1) * max(4, 4 * Arg_0) + max(5, 1 + 2 * Arg_1) * max(5, 5 * Arg_0) + max(5, 1 + 2 * Arg_1) * max(3, 3 * Arg_0) + nat(Arg_1) + max(7 + 2 * Arg_1, 11)) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalspeedpldi4start(A, B) -> Com_1(evalspeedpldi4entryin(A, B)) :|: TRUE evalspeedpldi4entryin(A, B) -> Com_1(evalspeedpldi4returnin(A, B)) :|: 0 >= A evalspeedpldi4entryin(A, B) -> Com_1(evalspeedpldi4returnin(A, B)) :|: A >= B evalspeedpldi4entryin(A, B) -> Com_1(evalspeedpldi4bb5in(A, B)) :|: A >= 1 && B >= A + 1 evalspeedpldi4bb5in(A, B) -> Com_1(evalspeedpldi4bb2in(A, B)) :|: B >= 1 evalspeedpldi4bb5in(A, B) -> Com_1(evalspeedpldi4returnin(A, B)) :|: 0 >= B evalspeedpldi4bb2in(A, B) -> Com_1(evalspeedpldi4bb3in(A, B)) :|: A >= B + 1 evalspeedpldi4bb2in(A, B) -> Com_1(evalspeedpldi4bb4in(A, B)) :|: B >= A evalspeedpldi4bb3in(A, B) -> Com_1(evalspeedpldi4bb5in(A, B - 1)) :|: TRUE evalspeedpldi4bb4in(A, B) -> Com_1(evalspeedpldi4bb5in(A, B - A)) :|: TRUE evalspeedpldi4returnin(A, B) -> Com_1(evalspeedpldi4stop(A, B)) :|: TRUE The start-symbols are:[evalspeedpldi4start_2] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 15*ar_0 + 15*ar_1 + 8) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalspeedpldi4start(ar_0, ar_1) -> Com_1(evalspeedpldi4entryin(ar_0, ar_1)) (Comp: ?, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ 0 >= ar_0 ] (Comp: ?, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb2in(ar_0, ar_1)) [ ar_1 >= 1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ 0 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb3in(ar_0, ar_1)) [ ar_0 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb4in(ar_0, ar_1)) [ ar_1 >= ar_0 ] (Comp: ?, Cost: 1) evalspeedpldi4bb3in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - 1)) (Comp: ?, Cost: 1) evalspeedpldi4bb4in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - ar_0)) (Comp: ?, Cost: 1) evalspeedpldi4returnin(ar_0, ar_1) -> Com_1(evalspeedpldi4stop(ar_0, ar_1)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1) -> Com_1(evalspeedpldi4start(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) evalspeedpldi4start(ar_0, ar_1) -> Com_1(evalspeedpldi4entryin(ar_0, ar_1)) (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ 0 >= ar_0 ] (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb2in(ar_0, ar_1)) [ ar_1 >= 1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ 0 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb3in(ar_0, ar_1)) [ ar_0 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb4in(ar_0, ar_1)) [ ar_1 >= ar_0 ] (Comp: ?, Cost: 1) evalspeedpldi4bb3in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - 1)) (Comp: ?, Cost: 1) evalspeedpldi4bb4in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - ar_0)) (Comp: ?, Cost: 1) evalspeedpldi4returnin(ar_0, ar_1) -> Com_1(evalspeedpldi4stop(ar_0, ar_1)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1) -> Com_1(evalspeedpldi4start(ar_0, ar_1)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalspeedpldi4start) = 2 Pol(evalspeedpldi4entryin) = 2 Pol(evalspeedpldi4returnin) = 1 Pol(evalspeedpldi4bb5in) = 2 Pol(evalspeedpldi4bb2in) = 2 Pol(evalspeedpldi4bb3in) = 2 Pol(evalspeedpldi4bb4in) = 2 Pol(evalspeedpldi4stop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalspeedpldi4returnin(ar_0, ar_1) -> Com_1(evalspeedpldi4stop(ar_0, ar_1)) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ 0 >= ar_1 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalspeedpldi4start(ar_0, ar_1) -> Com_1(evalspeedpldi4entryin(ar_0, ar_1)) (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ 0 >= ar_0 ] (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb2in(ar_0, ar_1)) [ ar_1 >= 1 ] (Comp: 2, Cost: 1) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ 0 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb3in(ar_0, ar_1)) [ ar_0 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb4in(ar_0, ar_1)) [ ar_1 >= ar_0 ] (Comp: ?, Cost: 1) evalspeedpldi4bb3in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - 1)) (Comp: ?, Cost: 1) evalspeedpldi4bb4in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - ar_0)) (Comp: 2, Cost: 1) evalspeedpldi4returnin(ar_0, ar_1) -> Com_1(evalspeedpldi4stop(ar_0, ar_1)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1) -> Com_1(evalspeedpldi4start(ar_0, ar_1)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Applied AI with 'oct' on problem 3 to obtain the following invariants: For symbol evalspeedpldi4bb2in: X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ X_1 - 1 >= 0 For symbol evalspeedpldi4bb3in: X_1 - X_2 - 1 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 3 >= 0 /\ X_1 - 2 >= 0 For symbol evalspeedpldi4bb4in: X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ -X_1 + X_2 >= 0 /\ X_1 - 1 >= 0 For symbol evalspeedpldi4bb5in: X_1 - 1 >= 0 This yielded the following problem: 4: T: (Comp: 1, Cost: 0) koat_start(ar_0, ar_1) -> Com_1(evalspeedpldi4start(ar_0, ar_1)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalspeedpldi4returnin(ar_0, ar_1) -> Com_1(evalspeedpldi4stop(ar_0, ar_1)) (Comp: ?, Cost: 1) evalspeedpldi4bb4in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - ar_0)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: ?, Cost: 1) evalspeedpldi4bb3in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - 1)) [ ar_0 - ar_1 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ ar_0 - 2 >= 0 ] (Comp: ?, Cost: 1) evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb4in(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_0 ] (Comp: ?, Cost: 1) evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb3in(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_1 + 1 ] (Comp: 2, Cost: 1) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ ar_0 - 1 >= 0 /\ 0 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb2in(ar_0, ar_1)) [ ar_0 - 1 >= 0 /\ ar_1 >= 1 ] (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ 0 >= ar_0 ] (Comp: 1, Cost: 1) evalspeedpldi4start(ar_0, ar_1) -> Com_1(evalspeedpldi4entryin(ar_0, ar_1)) start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = 3*V_1 + 3*V_2 Pol(evalspeedpldi4start) = 3*V_1 + 3*V_2 Pol(evalspeedpldi4returnin) = 3*V_1 + 3*V_2 Pol(evalspeedpldi4stop) = 3*V_1 + 3*V_2 Pol(evalspeedpldi4bb4in) = 3*V_2 + 1 Pol(evalspeedpldi4bb5in) = 3*V_1 + 3*V_2 Pol(evalspeedpldi4bb3in) = 3*V_1 + 3*V_2 - 2 Pol(evalspeedpldi4bb2in) = 3*V_1 + 3*V_2 - 1 Pol(evalspeedpldi4entryin) = 3*V_1 + 3*V_2 orients all transitions weakly and the transitions evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb2in(ar_0, ar_1)) [ ar_0 - 1 >= 0 /\ ar_1 >= 1 ] evalspeedpldi4bb4in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - ar_0)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 ] evalspeedpldi4bb3in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - 1)) [ ar_0 - ar_1 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ ar_0 - 2 >= 0 ] evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb4in(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_0 ] evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb3in(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_1 + 1 ] strictly and produces the following problem: 5: T: (Comp: 1, Cost: 0) koat_start(ar_0, ar_1) -> Com_1(evalspeedpldi4start(ar_0, ar_1)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalspeedpldi4returnin(ar_0, ar_1) -> Com_1(evalspeedpldi4stop(ar_0, ar_1)) (Comp: 3*ar_0 + 3*ar_1, Cost: 1) evalspeedpldi4bb4in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - ar_0)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: 3*ar_0 + 3*ar_1, Cost: 1) evalspeedpldi4bb3in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1 - 1)) [ ar_0 - ar_1 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ ar_0 - 2 >= 0 ] (Comp: 3*ar_0 + 3*ar_1, Cost: 1) evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb4in(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_0 ] (Comp: 3*ar_0 + 3*ar_1, Cost: 1) evalspeedpldi4bb2in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb3in(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_1 + 1 ] (Comp: 2, Cost: 1) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ ar_0 - 1 >= 0 /\ 0 >= ar_1 ] (Comp: 3*ar_0 + 3*ar_1, Cost: 1) evalspeedpldi4bb5in(ar_0, ar_1) -> Com_1(evalspeedpldi4bb2in(ar_0, ar_1)) [ ar_0 - 1 >= 0 /\ ar_1 >= 1 ] (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4bb5in(ar_0, ar_1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ ar_0 >= ar_1 ] (Comp: 1, Cost: 1) evalspeedpldi4entryin(ar_0, ar_1) -> Com_1(evalspeedpldi4returnin(ar_0, ar_1)) [ 0 >= ar_0 ] (Comp: 1, Cost: 1) evalspeedpldi4start(ar_0, ar_1) -> Com_1(evalspeedpldi4entryin(ar_0, ar_1)) start location: koat_start leaf cost: 0 Complexity upper bound 15*ar_0 + 15*ar_1 + 8 Time: 0.198 sec (SMT: 0.181 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalspeedpldi4start 0: evalspeedpldi4start -> evalspeedpldi4entryin : [], cost: 1 1: evalspeedpldi4entryin -> evalspeedpldi4returnin : [ 0>=A ], cost: 1 2: evalspeedpldi4entryin -> evalspeedpldi4returnin : [ A>=B ], cost: 1 3: evalspeedpldi4entryin -> evalspeedpldi4bb5in : [ A>=1 && B>=1+A ], cost: 1 4: evalspeedpldi4bb5in -> evalspeedpldi4bb2in : [ B>=1 ], cost: 1 5: evalspeedpldi4bb5in -> evalspeedpldi4returnin : [ 0>=B ], cost: 1 6: evalspeedpldi4bb2in -> evalspeedpldi4bb3in : [ A>=1+B ], cost: 1 7: evalspeedpldi4bb2in -> evalspeedpldi4bb4in : [ B>=A ], cost: 1 8: evalspeedpldi4bb3in -> evalspeedpldi4bb5in : B'=-1+B, [], cost: 1 9: evalspeedpldi4bb4in -> evalspeedpldi4bb5in : B'=-A+B, [], cost: 1 10: evalspeedpldi4returnin -> evalspeedpldi4stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalspeedpldi4start 0: evalspeedpldi4start -> evalspeedpldi4entryin : [], cost: 1 3: evalspeedpldi4entryin -> evalspeedpldi4bb5in : [ A>=1 && B>=1+A ], cost: 1 4: evalspeedpldi4bb5in -> evalspeedpldi4bb2in : [ B>=1 ], cost: 1 6: evalspeedpldi4bb2in -> evalspeedpldi4bb3in : [ A>=1+B ], cost: 1 7: evalspeedpldi4bb2in -> evalspeedpldi4bb4in : [ B>=A ], cost: 1 8: evalspeedpldi4bb3in -> evalspeedpldi4bb5in : B'=-1+B, [], cost: 1 9: evalspeedpldi4bb4in -> evalspeedpldi4bb5in : B'=-A+B, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalspeedpldi4start 11: evalspeedpldi4start -> evalspeedpldi4bb5in : [ A>=1 && B>=1+A ], cost: 2 4: evalspeedpldi4bb5in -> evalspeedpldi4bb2in : [ B>=1 ], cost: 1 12: evalspeedpldi4bb2in -> evalspeedpldi4bb5in : B'=-1+B, [ A>=1+B ], cost: 2 13: evalspeedpldi4bb2in -> evalspeedpldi4bb5in : B'=-A+B, [ B>=A ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalspeedpldi4start 11: evalspeedpldi4start -> evalspeedpldi4bb5in : [ A>=1 && B>=1+A ], cost: 2 14: evalspeedpldi4bb5in -> evalspeedpldi4bb5in : B'=-1+B, [ B>=1 && A>=1+B ], cost: 3 15: evalspeedpldi4bb5in -> evalspeedpldi4bb5in : B'=-A+B, [ B>=1 && B>=A ], cost: 3 Accelerating simple loops of location 2. Accelerating the following rules: 14: evalspeedpldi4bb5in -> evalspeedpldi4bb5in : B'=-1+B, [ B>=1 && A>=1+B ], cost: 3 15: evalspeedpldi4bb5in -> evalspeedpldi4bb5in : B'=-A+B, [ B>=1 && B>=A ], cost: 3 Accelerated rule 14 with metering function B, yielding the new rule 16. Found no metering function for rule 15. Removing the simple loops: 14. Accelerated all simple loops using metering functions (where possible): Start location: evalspeedpldi4start 11: evalspeedpldi4start -> evalspeedpldi4bb5in : [ A>=1 && B>=1+A ], cost: 2 15: evalspeedpldi4bb5in -> evalspeedpldi4bb5in : B'=-A+B, [ B>=1 && B>=A ], cost: 3 16: evalspeedpldi4bb5in -> evalspeedpldi4bb5in : B'=0, [ B>=1 && A>=1+B ], cost: 3*B Chained accelerated rules (with incoming rules): Start location: evalspeedpldi4start 11: evalspeedpldi4start -> evalspeedpldi4bb5in : [ A>=1 && B>=1+A ], cost: 2 17: evalspeedpldi4start -> evalspeedpldi4bb5in : B'=-A+B, [ A>=1 && B>=1+A && B>=1 ], cost: 5 Removed unreachable locations (and leaf rules with constant cost): Start location: evalspeedpldi4start ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalspeedpldi4start Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Unknown Cpx degree: ? Solved cost: 0 Rule cost: 0 Rule guard: [] WORST_CASE(Omega(0),?) ---------------------------------------- (4) BOUNDS(1, INF) ---------------------------------------- (5) Koat2 Proof (FINISHED) YES( ?, 6+max([5, 1+2*Arg_1])*max([3, 3*Arg_0])+max([5, 1+2*Arg_1])*max([4, 4*Arg_0])+max([5, 1+2*Arg_1])*max([5, 5*Arg_0])+max([5, 1+2*Arg_1])+max([0, Arg_1]) {O(n^2)}) Initial Complexity Problem: Start: evalspeedpldi4start Program_Vars: Arg_0, Arg_1 Temp_Vars: Locations: evalspeedpldi4bb2in, evalspeedpldi4bb3in, evalspeedpldi4bb4in, evalspeedpldi4bb5in, evalspeedpldi4entryin, evalspeedpldi4returnin, evalspeedpldi4start, evalspeedpldi4stop Transitions: evalspeedpldi4bb2in(Arg_0,Arg_1) -> evalspeedpldi4bb3in(Arg_0,Arg_1):|:1 <= Arg_0 && Arg_1+1 <= Arg_0 evalspeedpldi4bb2in(Arg_0,Arg_1) -> evalspeedpldi4bb4in(Arg_0,Arg_1):|:1 <= Arg_0 && Arg_0 <= Arg_1 evalspeedpldi4bb3in(Arg_0,Arg_1) -> evalspeedpldi4bb5in(Arg_0,Arg_1-1):|:1+Arg_1 <= Arg_0 && 1 <= Arg_0 evalspeedpldi4bb4in(Arg_0,Arg_1) -> evalspeedpldi4bb5in(Arg_0,Arg_1-Arg_0):|:1 <= Arg_0 evalspeedpldi4bb5in(Arg_0,Arg_1) -> evalspeedpldi4bb2in(Arg_0,Arg_1):|:1 <= Arg_0 && 1 <= Arg_1 evalspeedpldi4bb5in(Arg_0,Arg_1) -> evalspeedpldi4returnin(Arg_0,Arg_1):|:1 <= Arg_0 && Arg_1 <= 0 evalspeedpldi4entryin(Arg_0,Arg_1) -> evalspeedpldi4bb5in(Arg_0,Arg_1):|:1 <= Arg_0 && Arg_0+1 <= Arg_1 evalspeedpldi4entryin(Arg_0,Arg_1) -> evalspeedpldi4returnin(Arg_0,Arg_1):|:Arg_0 <= 0 evalspeedpldi4entryin(Arg_0,Arg_1) -> evalspeedpldi4returnin(Arg_0,Arg_1):|:Arg_1 <= Arg_0 evalspeedpldi4returnin(Arg_0,Arg_1) -> evalspeedpldi4stop(Arg_0,Arg_1):|: evalspeedpldi4start(Arg_0,Arg_1) -> evalspeedpldi4entryin(Arg_0,Arg_1):|: Timebounds: Overall timebound: 6+max([5, 1+2*Arg_1])*max([3, 3*Arg_0])+max([5, 1+2*Arg_1])*max([4, 4*Arg_0])+max([5, 1+2*Arg_1])*max([5, 5*Arg_0])+max([5, 1+2*Arg_1])+max([0, Arg_1]) {O(n^2)} 6: evalspeedpldi4bb2in->evalspeedpldi4bb3in: max([5, 1+2*Arg_1])*max([4, 4*Arg_0]) {O(n^2)} 7: evalspeedpldi4bb2in->evalspeedpldi4bb4in: max([0, Arg_1]) {O(n)} 8: evalspeedpldi4bb3in->evalspeedpldi4bb5in: max([5, 1+2*Arg_1])*max([5, 5*Arg_0]) {O(n^2)} 9: evalspeedpldi4bb4in->evalspeedpldi4bb5in: max([5, 1+2*Arg_1])*max([3, 3*Arg_0]) {O(n^2)} 4: evalspeedpldi4bb5in->evalspeedpldi4bb2in: max([5, 1+2*Arg_1]) {O(n)} 5: evalspeedpldi4bb5in->evalspeedpldi4returnin: 1 {O(1)} 1: evalspeedpldi4entryin->evalspeedpldi4returnin: 1 {O(1)} 2: evalspeedpldi4entryin->evalspeedpldi4returnin: 1 {O(1)} 3: evalspeedpldi4entryin->evalspeedpldi4bb5in: 1 {O(1)} 10: evalspeedpldi4returnin->evalspeedpldi4stop: 1 {O(1)} 0: evalspeedpldi4start->evalspeedpldi4entryin: 1 {O(1)} Costbounds: Overall costbound: 6+max([5, 1+2*Arg_1])*max([3, 3*Arg_0])+max([5, 1+2*Arg_1])*max([4, 4*Arg_0])+max([5, 1+2*Arg_1])*max([5, 5*Arg_0])+max([5, 1+2*Arg_1])+max([0, Arg_1]) {O(n^2)} 6: evalspeedpldi4bb2in->evalspeedpldi4bb3in: max([5, 1+2*Arg_1])*max([4, 4*Arg_0]) {O(n^2)} 7: evalspeedpldi4bb2in->evalspeedpldi4bb4in: max([0, Arg_1]) {O(n)} 8: evalspeedpldi4bb3in->evalspeedpldi4bb5in: max([5, 1+2*Arg_1])*max([5, 5*Arg_0]) {O(n^2)} 9: evalspeedpldi4bb4in->evalspeedpldi4bb5in: max([5, 1+2*Arg_1])*max([3, 3*Arg_0]) {O(n^2)} 4: evalspeedpldi4bb5in->evalspeedpldi4bb2in: max([5, 1+2*Arg_1]) {O(n)} 5: evalspeedpldi4bb5in->evalspeedpldi4returnin: 1 {O(1)} 1: evalspeedpldi4entryin->evalspeedpldi4returnin: 1 {O(1)} 2: evalspeedpldi4entryin->evalspeedpldi4returnin: 1 {O(1)} 3: evalspeedpldi4entryin->evalspeedpldi4bb5in: 1 {O(1)} 10: evalspeedpldi4returnin->evalspeedpldi4stop: 1 {O(1)} 0: evalspeedpldi4start->evalspeedpldi4entryin: 1 {O(1)} Sizebounds: `Lower: 6: evalspeedpldi4bb2in->evalspeedpldi4bb3in, Arg_0: 1 {O(1)} 6: evalspeedpldi4bb2in->evalspeedpldi4bb3in, Arg_1: 1 {O(1)} 7: evalspeedpldi4bb2in->evalspeedpldi4bb4in, Arg_0: 1 {O(1)} 7: evalspeedpldi4bb2in->evalspeedpldi4bb4in, Arg_1: 1 {O(1)} 8: evalspeedpldi4bb3in->evalspeedpldi4bb5in, Arg_0: 1 {O(1)} 8: evalspeedpldi4bb3in->evalspeedpldi4bb5in, Arg_1: 0 {O(1)} 9: evalspeedpldi4bb4in->evalspeedpldi4bb5in, Arg_0: 1 {O(1)} 9: evalspeedpldi4bb4in->evalspeedpldi4bb5in, Arg_1: 1-Arg_0 {O(n)} 4: evalspeedpldi4bb5in->evalspeedpldi4bb2in, Arg_0: 1 {O(1)} 4: evalspeedpldi4bb5in->evalspeedpldi4bb2in, Arg_1: 1 {O(1)} 5: evalspeedpldi4bb5in->evalspeedpldi4returnin, Arg_0: 1 {O(1)} 5: evalspeedpldi4bb5in->evalspeedpldi4returnin, Arg_1: min([0, -(-1+Arg_0)]) {O(n)} 1: evalspeedpldi4entryin->evalspeedpldi4returnin, Arg_0: Arg_0 {O(n)} 1: evalspeedpldi4entryin->evalspeedpldi4returnin, Arg_1: Arg_1 {O(n)} 2: evalspeedpldi4entryin->evalspeedpldi4returnin, Arg_0: Arg_0 {O(n)} 2: evalspeedpldi4entryin->evalspeedpldi4returnin, Arg_1: Arg_1 {O(n)} 3: evalspeedpldi4entryin->evalspeedpldi4bb5in, Arg_0: 1 {O(1)} 3: evalspeedpldi4entryin->evalspeedpldi4bb5in, Arg_1: 2 {O(1)} 10: evalspeedpldi4returnin->evalspeedpldi4stop, Arg_0: min([1, Arg_0]) {O(n)} 10: evalspeedpldi4returnin->evalspeedpldi4stop, Arg_1: min([0, min([Arg_1, -(-1+Arg_0)])]) {O(n)} 0: evalspeedpldi4start->evalspeedpldi4entryin, Arg_0: Arg_0 {O(n)} 0: evalspeedpldi4start->evalspeedpldi4entryin, Arg_1: Arg_1 {O(n)} `Upper: 6: evalspeedpldi4bb2in->evalspeedpldi4bb3in, Arg_0: Arg_0 {O(n)} 6: evalspeedpldi4bb2in->evalspeedpldi4bb3in, Arg_1: Arg_1 {O(n)} 7: evalspeedpldi4bb2in->evalspeedpldi4bb4in, Arg_0: Arg_0 {O(n)} 7: evalspeedpldi4bb2in->evalspeedpldi4bb4in, Arg_1: Arg_1 {O(n)} 8: evalspeedpldi4bb3in->evalspeedpldi4bb5in, Arg_0: Arg_0 {O(n)} 8: evalspeedpldi4bb3in->evalspeedpldi4bb5in, Arg_1: Arg_1 {O(n)} 9: evalspeedpldi4bb4in->evalspeedpldi4bb5in, Arg_0: Arg_0 {O(n)} 9: evalspeedpldi4bb4in->evalspeedpldi4bb5in, Arg_1: Arg_1 {O(n)} 4: evalspeedpldi4bb5in->evalspeedpldi4bb2in, Arg_0: Arg_0 {O(n)} 4: evalspeedpldi4bb5in->evalspeedpldi4bb2in, Arg_1: Arg_1 {O(n)} 5: evalspeedpldi4bb5in->evalspeedpldi4returnin, Arg_0: Arg_0 {O(n)} 5: evalspeedpldi4bb5in->evalspeedpldi4returnin, Arg_1: 0 {O(1)} 1: evalspeedpldi4entryin->evalspeedpldi4returnin, Arg_0: 0 {O(1)} 1: evalspeedpldi4entryin->evalspeedpldi4returnin, Arg_1: Arg_1 {O(n)} 2: evalspeedpldi4entryin->evalspeedpldi4returnin, Arg_0: Arg_0 {O(n)} 2: evalspeedpldi4entryin->evalspeedpldi4returnin, Arg_1: Arg_1 {O(n)} 3: evalspeedpldi4entryin->evalspeedpldi4bb5in, Arg_0: Arg_0 {O(n)} 3: evalspeedpldi4entryin->evalspeedpldi4bb5in, Arg_1: Arg_1 {O(n)} 10: evalspeedpldi4returnin->evalspeedpldi4stop, Arg_0: max([0, Arg_0]) {O(n)} 10: evalspeedpldi4returnin->evalspeedpldi4stop, Arg_1: max([0, Arg_1]) {O(n)} 0: evalspeedpldi4start->evalspeedpldi4entryin, Arg_0: Arg_0 {O(n)} 0: evalspeedpldi4start->evalspeedpldi4entryin, Arg_1: Arg_1 {O(n)} ---------------------------------------- (6) BOUNDS(1, max(5, 1 + 2 * Arg_1) * max(4, 4 * Arg_0) + max(5, 1 + 2 * Arg_1) * max(5, 5 * Arg_0) + max(5, 1 + 2 * Arg_1) * max(3, 3 * Arg_0) + nat(Arg_1) + max(7 + 2 * Arg_1, 11))