/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(NON_POLY, ?) 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(INF, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 525 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_speedFails2_start(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb0_in(v_i_0, v_n, v_x)) :|: TRUE eval_speedFails2_bb0_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_0(v_i_0, v_n, v_x)) :|: TRUE eval_speedFails2_0(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_1(v_i_0, v_n, v_x)) :|: TRUE eval_speedFails2_1(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_2(v_i_0, v_n, v_x)) :|: TRUE eval_speedFails2_2(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_3(v_i_0, v_n, v_x)) :|: TRUE eval_speedFails2_3(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_4(v_i_0, v_n, v_x)) :|: TRUE eval_speedFails2_4(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb1_in(v_x, v_n, v_x)) :|: TRUE eval_speedFails2_bb1_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb2_in(v_i_0, v_n, v_x)) :|: v_i_0 < v_n eval_speedFails2_bb1_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb2_in(v_i_0, v_n, v_x)) :|: v_i_0 > v_n eval_speedFails2_bb1_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb3_in(v_i_0, v_n, v_x)) :|: v_i_0 >= v_n && v_i_0 <= v_n eval_speedFails2_bb2_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb1_in(v_i_0 + 1, v_n, v_x)) :|: TRUE eval_speedFails2_bb3_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_stop(v_i_0, v_n, v_x)) :|: TRUE The start-symbols are:[eval_speedFails2_start_3] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalspeedFails2start 0: evalspeedFails2start -> evalspeedFails2bb0in : [], cost: 1 1: evalspeedFails2bb0in -> evalspeedFails20 : [], cost: 1 2: evalspeedFails20 -> evalspeedFails21 : [], cost: 1 3: evalspeedFails21 -> evalspeedFails22 : [], cost: 1 4: evalspeedFails22 -> evalspeedFails23 : [], cost: 1 5: evalspeedFails23 -> evalspeedFails24 : [], cost: 1 6: evalspeedFails24 -> evalspeedFails2bb1in : A'=B, [], cost: 1 7: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ C>=1+A ], cost: 1 8: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ A>=1+C ], cost: 1 9: evalspeedFails2bb1in -> evalspeedFails2bb3in : [ A==C ], cost: 1 10: evalspeedFails2bb2in -> evalspeedFails2bb1in : A'=1+A, [], cost: 1 11: evalspeedFails2bb3in -> evalspeedFails2stop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalspeedFails2start -> evalspeedFails2bb0in : [], cost: 1 Removed unreachable and leaf rules: Start location: evalspeedFails2start 0: evalspeedFails2start -> evalspeedFails2bb0in : [], cost: 1 1: evalspeedFails2bb0in -> evalspeedFails20 : [], cost: 1 2: evalspeedFails20 -> evalspeedFails21 : [], cost: 1 3: evalspeedFails21 -> evalspeedFails22 : [], cost: 1 4: evalspeedFails22 -> evalspeedFails23 : [], cost: 1 5: evalspeedFails23 -> evalspeedFails24 : [], cost: 1 6: evalspeedFails24 -> evalspeedFails2bb1in : A'=B, [], cost: 1 7: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ C>=1+A ], cost: 1 8: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ A>=1+C ], cost: 1 10: evalspeedFails2bb2in -> evalspeedFails2bb1in : A'=1+A, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalspeedFails2start 17: evalspeedFails2start -> evalspeedFails2bb1in : A'=B, [], cost: 7 7: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ C>=1+A ], cost: 1 8: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ A>=1+C ], cost: 1 10: evalspeedFails2bb2in -> evalspeedFails2bb1in : A'=1+A, [], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalspeedFails2start 17: evalspeedFails2start -> evalspeedFails2bb1in : A'=B, [], cost: 7 18: evalspeedFails2bb1in -> evalspeedFails2bb1in : A'=1+A, [ C>=1+A ], cost: 2 19: evalspeedFails2bb1in -> evalspeedFails2bb1in : A'=1+A, [ A>=1+C ], cost: 2 Accelerating simple loops of location 7. Accelerating the following rules: 18: evalspeedFails2bb1in -> evalspeedFails2bb1in : A'=1+A, [ C>=1+A ], cost: 2 19: evalspeedFails2bb1in -> evalspeedFails2bb1in : A'=1+A, [ A>=1+C ], cost: 2 Accelerated rule 18 with metering function C-A, yielding the new rule 20. Accelerated rule 19 with NONTERM, yielding the new rule 21. Removing the simple loops: 18 19. Accelerated all simple loops using metering functions (where possible): Start location: evalspeedFails2start 17: evalspeedFails2start -> evalspeedFails2bb1in : A'=B, [], cost: 7 20: evalspeedFails2bb1in -> evalspeedFails2bb1in : A'=C, [ C>=1+A ], cost: 2*C-2*A 21: evalspeedFails2bb1in -> [11] : [ A>=1+C ], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: evalspeedFails2start 17: evalspeedFails2start -> evalspeedFails2bb1in : A'=B, [], cost: 7 22: evalspeedFails2start -> evalspeedFails2bb1in : A'=C, [ C>=1+B ], cost: 7+2*C-2*B 23: evalspeedFails2start -> [11] : A'=B, [ B>=1+C ], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: evalspeedFails2start 22: evalspeedFails2start -> evalspeedFails2bb1in : A'=C, [ C>=1+B ], cost: 7+2*C-2*B 23: evalspeedFails2start -> [11] : A'=B, [ B>=1+C ], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalspeedFails2start 22: evalspeedFails2start -> evalspeedFails2bb1in : A'=C, [ C>=1+B ], cost: 7+2*C-2*B 23: evalspeedFails2start -> [11] : A'=B, [ B>=1+C ], cost: NONTERM Computing asymptotic complexity for rule 22 Solved the limit problem by the following transformations: Created initial limit problem: C-B (+/+!), 7+2*C-2*B (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==0,B==-n} resulting limit problem: [solved] Solution: C / 0 B / -n Resulting cost 7+2*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 23 Guard is satisfiable, yielding nontermination Resulting cost NONTERM has complexity: Nonterm Found new complexity Nonterm. Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Nonterm Cpx degree: Nonterm Solved cost: NONTERM Rule cost: NONTERM Rule guard: [ B>=1+C ] NO ---------------------------------------- (2) BOUNDS(INF, INF)