/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(NON_POLY, ?) 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(INF, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 613 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalcousot9start(A, B, C) -> Com_1(evalcousot9entryin(A, B, C)) :|: TRUE evalcousot9entryin(A, B, C) -> Com_1(evalcousot9bb3in(D, C, C)) :|: TRUE evalcousot9bb3in(A, B, C) -> Com_1(evalcousot9bbin(A, B, C)) :|: B >= 1 evalcousot9bb3in(A, B, C) -> Com_1(evalcousot9returnin(A, B, C)) :|: 0 >= B evalcousot9bbin(A, B, C) -> Com_1(evalcousot9bb1in(A, B, C)) :|: A >= 1 evalcousot9bbin(A, B, C) -> Com_1(evalcousot9bb2in(A, B, C)) :|: 0 >= A evalcousot9bb1in(A, B, C) -> Com_1(evalcousot9bb3in(A - 1, B, C)) :|: TRUE evalcousot9bb2in(A, B, C) -> Com_1(evalcousot9bb3in(C, B - 1, C)) :|: TRUE evalcousot9returnin(A, B, C) -> Com_1(evalcousot9stop(A, B, C)) :|: TRUE The start-symbols are:[evalcousot9start_3] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalcousot9start 0: evalcousot9start -> evalcousot9entryin : [], cost: 1 1: evalcousot9entryin -> evalcousot9bb3in : A'=free, B'=C, [], cost: 1 2: evalcousot9bb3in -> evalcousot9bbin : [ B>=1 ], cost: 1 3: evalcousot9bb3in -> evalcousot9returnin : [ 0>=B ], cost: 1 4: evalcousot9bbin -> evalcousot9bb1in : [ A>=1 ], cost: 1 5: evalcousot9bbin -> evalcousot9bb2in : [ 0>=A ], cost: 1 6: evalcousot9bb1in -> evalcousot9bb3in : A'=-1+A, [], cost: 1 7: evalcousot9bb2in -> evalcousot9bb3in : A'=C, B'=-1+B, [], cost: 1 8: evalcousot9returnin -> evalcousot9stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalcousot9start 0: evalcousot9start -> evalcousot9entryin : [], cost: 1 1: evalcousot9entryin -> evalcousot9bb3in : A'=free, B'=C, [], cost: 1 2: evalcousot9bb3in -> evalcousot9bbin : [ B>=1 ], cost: 1 4: evalcousot9bbin -> evalcousot9bb1in : [ A>=1 ], cost: 1 5: evalcousot9bbin -> evalcousot9bb2in : [ 0>=A ], cost: 1 6: evalcousot9bb1in -> evalcousot9bb3in : A'=-1+A, [], cost: 1 7: evalcousot9bb2in -> evalcousot9bb3in : A'=C, B'=-1+B, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalcousot9start 9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2 2: evalcousot9bb3in -> evalcousot9bbin : [ B>=1 ], cost: 1 10: evalcousot9bbin -> evalcousot9bb3in : A'=-1+A, [ A>=1 ], cost: 2 11: evalcousot9bbin -> evalcousot9bb3in : A'=C, B'=-1+B, [ 0>=A ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalcousot9start 9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2 12: evalcousot9bb3in -> evalcousot9bb3in : A'=-1+A, [ B>=1 && A>=1 ], cost: 3 13: evalcousot9bb3in -> evalcousot9bb3in : A'=C, B'=-1+B, [ B>=1 && 0>=A ], cost: 3 Accelerating simple loops of location 2. Accelerating the following rules: 12: evalcousot9bb3in -> evalcousot9bb3in : A'=-1+A, [ B>=1 && A>=1 ], cost: 3 13: evalcousot9bb3in -> evalcousot9bb3in : A'=C, B'=-1+B, [ B>=1 && 0>=A ], cost: 3 Accelerated rule 12 with metering function A, yielding the new rule 14. Accelerated rule 13 with metering function B (after strengthening guard), yielding the new rule 15. Nested simple loops 13 (outer loop) and 14 (inner loop) with metering function -1+B, resulting in the new rules: 16, 17. Removing the simple loops: 12 13. Accelerated all simple loops using metering functions (where possible): Start location: evalcousot9start 9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2 14: evalcousot9bb3in -> evalcousot9bb3in : A'=0, [ B>=1 && A>=1 ], cost: 3*A 15: evalcousot9bb3in -> evalcousot9bb3in : A'=C, B'=0, [ B>=1 && 0>=A && 0>=C ], cost: 3*B 16: evalcousot9bb3in -> evalcousot9bb3in : A'=0, B'=1, [ 0>=A && -1+B>=1 && C>=1 ], cost: -3+3*C*(-1+B)+3*B 17: evalcousot9bb3in -> evalcousot9bb3in : A'=0, B'=1, [ A>=1 && -1+B>=1 && C>=1 ], cost: -3+3*C*(-1+B)+3*A+3*B Chained accelerated rules (with incoming rules): Start location: evalcousot9start 9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2 18: evalcousot9start -> evalcousot9bb3in : A'=0, B'=C, [ C>=1 && free>=1 ], cost: 2+3*free 19: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ -1+C>=1 ], cost: -1+3*C+3*C*(-1+C) 20: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ free>=1 && -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)+3*free Removed unreachable locations (and leaf rules with constant cost): Start location: evalcousot9start 18: evalcousot9start -> evalcousot9bb3in : A'=0, B'=C, [ C>=1 && free>=1 ], cost: 2+3*free 19: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ -1+C>=1 ], cost: -1+3*C+3*C*(-1+C) 20: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ free>=1 && -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)+3*free ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalcousot9start 18: evalcousot9start -> evalcousot9bb3in : A'=0, B'=C, [ C>=1 && free>=1 ], cost: 2+3*free 19: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ -1+C>=1 ], cost: -1+3*C+3*C*(-1+C) 20: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ free>=1 && -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)+3*free Computing asymptotic complexity for rule 18 Solved the limit problem by the following transformations: Created initial limit problem: C (+/+!), 2+3*free (+), free (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==1,free==n} resulting limit problem: [solved] Solution: C / 1 free / n Resulting cost 2+3*n has complexity: Unbounded Found new complexity Unbounded. Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Unbounded Cpx degree: Unbounded Solved cost: 2+3*n Rule cost: 2+3*free Rule guard: [ C>=1 && free>=1 ] WORST_CASE(INF,?) ---------------------------------------- (2) BOUNDS(INF, INF)