/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/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, 454 ms] (2) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalspeedFails4start(A, B, C, D) -> Com_1(evalspeedFails4entryin(A, B, C, D)) :|: TRUE evalspeedFails4entryin(A, B, C, D) -> Com_1(evalspeedFails4bb6in(1, C, A, B)) :|: A >= 1 evalspeedFails4entryin(A, B, C, D) -> Com_1(evalspeedFails4bb6in(-(1), C, A, B)) :|: 0 >= A evalspeedFails4bb6in(A, B, C, D) -> Com_1(evalspeedFails4bb3in(A, B, C, D)) :|: B >= D evalspeedFails4bb6in(A, B, C, D) -> Com_1(evalspeedFails4returnin(A, B, C, D)) :|: D >= B + 1 evalspeedFails4bb3in(A, B, C, D) -> Com_1(evalspeedFails4bb4in(A, B, C, D)) :|: C >= 1 evalspeedFails4bb3in(A, B, C, D) -> Com_1(evalspeedFails4bb5in(A, B, C, D)) :|: 0 >= C evalspeedFails4bb4in(A, B, C, D) -> Com_1(evalspeedFails4bb6in(A, B, C, D + A)) :|: TRUE evalspeedFails4bb5in(A, B, C, D) -> Com_1(evalspeedFails4bb6in(A, B, C, D - A)) :|: TRUE evalspeedFails4returnin(A, B, C, D) -> Com_1(evalspeedFails4stop(A, B, C, D)) :|: TRUE The start-symbols are:[evalspeedFails4start_4] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalspeedFails4start 0: evalspeedFails4start -> evalspeedFails4entryin : [], cost: 1 1: evalspeedFails4entryin -> evalspeedFails4bb6in : A'=1, B'=C, C'=A, D'=B, [ A>=1 ], cost: 1 2: evalspeedFails4entryin -> evalspeedFails4bb6in : A'=-1, B'=C, C'=A, D'=B, [ 0>=A ], cost: 1 3: evalspeedFails4bb6in -> evalspeedFails4bb3in : [ B>=D ], cost: 1 4: evalspeedFails4bb6in -> evalspeedFails4returnin : [ D>=1+B ], cost: 1 5: evalspeedFails4bb3in -> evalspeedFails4bb4in : [ C>=1 ], cost: 1 6: evalspeedFails4bb3in -> evalspeedFails4bb5in : [ 0>=C ], cost: 1 7: evalspeedFails4bb4in -> evalspeedFails4bb6in : D'=D+A, [], cost: 1 8: evalspeedFails4bb5in -> evalspeedFails4bb6in : D'=D-A, [], cost: 1 9: evalspeedFails4returnin -> evalspeedFails4stop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalspeedFails4start -> evalspeedFails4entryin : [], cost: 1 Removed unreachable and leaf rules: Start location: evalspeedFails4start 0: evalspeedFails4start -> evalspeedFails4entryin : [], cost: 1 1: evalspeedFails4entryin -> evalspeedFails4bb6in : A'=1, B'=C, C'=A, D'=B, [ A>=1 ], cost: 1 2: evalspeedFails4entryin -> evalspeedFails4bb6in : A'=-1, B'=C, C'=A, D'=B, [ 0>=A ], cost: 1 3: evalspeedFails4bb6in -> evalspeedFails4bb3in : [ B>=D ], cost: 1 5: evalspeedFails4bb3in -> evalspeedFails4bb4in : [ C>=1 ], cost: 1 6: evalspeedFails4bb3in -> evalspeedFails4bb5in : [ 0>=C ], cost: 1 7: evalspeedFails4bb4in -> evalspeedFails4bb6in : D'=D+A, [], cost: 1 8: evalspeedFails4bb5in -> evalspeedFails4bb6in : D'=D-A, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalspeedFails4start 0: evalspeedFails4start -> evalspeedFails4entryin : [], cost: 1 1: evalspeedFails4entryin -> evalspeedFails4bb6in : A'=1, B'=C, C'=A, D'=B, [ A>=1 ], cost: 1 2: evalspeedFails4entryin -> evalspeedFails4bb6in : A'=-1, B'=C, C'=A, D'=B, [ 0>=A ], cost: 1 3: evalspeedFails4bb6in -> evalspeedFails4bb3in : [ B>=D ], cost: 1 10: evalspeedFails4bb3in -> evalspeedFails4bb6in : D'=D+A, [ C>=1 ], cost: 2 11: evalspeedFails4bb3in -> evalspeedFails4bb6in : D'=D-A, [ 0>=C ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalspeedFails4start 12: evalspeedFails4start -> evalspeedFails4bb6in : A'=1, B'=C, C'=A, D'=B, [ A>=1 ], cost: 2 13: evalspeedFails4start -> evalspeedFails4bb6in : A'=-1, B'=C, C'=A, D'=B, [ 0>=A ], cost: 2 14: evalspeedFails4bb6in -> evalspeedFails4bb6in : D'=D+A, [ B>=D && C>=1 ], cost: 3 15: evalspeedFails4bb6in -> evalspeedFails4bb6in : D'=D-A, [ B>=D && 0>=C ], cost: 3 Accelerating simple loops of location 2. Accelerating the following rules: 14: evalspeedFails4bb6in -> evalspeedFails4bb6in : D'=D+A, [ B>=D && C>=1 ], cost: 3 15: evalspeedFails4bb6in -> evalspeedFails4bb6in : D'=D-A, [ B>=D && 0>=C ], cost: 3 Found no metering function for rule 14. Found no metering function for rule 15. Removing the simple loops:. Accelerated all simple loops using metering functions (where possible): Start location: evalspeedFails4start 12: evalspeedFails4start -> evalspeedFails4bb6in : A'=1, B'=C, C'=A, D'=B, [ A>=1 ], cost: 2 13: evalspeedFails4start -> evalspeedFails4bb6in : A'=-1, B'=C, C'=A, D'=B, [ 0>=A ], cost: 2 14: evalspeedFails4bb6in -> evalspeedFails4bb6in : D'=D+A, [ B>=D && C>=1 ], cost: 3 15: evalspeedFails4bb6in -> evalspeedFails4bb6in : D'=D-A, [ B>=D && 0>=C ], cost: 3 Chained accelerated rules (with incoming rules): Start location: evalspeedFails4start 12: evalspeedFails4start -> evalspeedFails4bb6in : A'=1, B'=C, C'=A, D'=B, [ A>=1 ], cost: 2 13: evalspeedFails4start -> evalspeedFails4bb6in : A'=-1, B'=C, C'=A, D'=B, [ 0>=A ], cost: 2 16: evalspeedFails4start -> evalspeedFails4bb6in : A'=1, B'=C, C'=A, D'=1+B, [ A>=1 && C>=B ], cost: 5 17: evalspeedFails4start -> evalspeedFails4bb6in : A'=-1, B'=C, C'=A, D'=1+B, [ 0>=A && C>=B ], cost: 5 Removed unreachable locations (and leaf rules with constant cost): Start location: evalspeedFails4start ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalspeedFails4start 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: [] WORST_CASE(Omega(1),?) ---------------------------------------- (2) BOUNDS(1, INF)