/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: 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, 598 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_catmouse_start(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb0_in(v_m, v_n, v_x_0)) :|: TRUE eval_catmouse_bb0_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_0(v_m, v_n, v_x_0)) :|: TRUE eval_catmouse_0(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_1(v_m, v_n, v_x_0)) :|: TRUE eval_catmouse_1(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_2(v_m, v_n, v_x_0)) :|: TRUE eval_catmouse_2(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_3(v_m, v_n, v_x_0)) :|: TRUE eval_catmouse_3(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_4(v_m, v_n, v_x_0)) :|: TRUE eval_catmouse_4(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_5(v_m, v_n, v_x_0)) :|: TRUE eval_catmouse_5(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb1_in(v_m, v_n, 0)) :|: TRUE eval_catmouse_bb1_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb2_in(v_m, v_n, v_x_0)) :|: v_x_0 <= v_n eval_catmouse_bb1_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb3_in(v_m, v_n, v_x_0)) :|: v_x_0 > v_n eval_catmouse_bb2_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb1_in(v_m, v_n, v_x_0 + 1)) :|: v_x_0 <= v_m eval_catmouse_bb2_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb1_in(v_m, v_n, v_x_0 - 1)) :|: v_x_0 > v_m eval_catmouse_bb3_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_stop(v_m, v_n, v_x_0)) :|: TRUE The start-symbols are:[eval_catmouse_start_3] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalcatmousestart 0: evalcatmousestart -> evalcatmousebb0in : [], cost: 1 1: evalcatmousebb0in -> evalcatmouse0 : [], cost: 1 2: evalcatmouse0 -> evalcatmouse1 : [], cost: 1 3: evalcatmouse1 -> evalcatmouse2 : [], cost: 1 4: evalcatmouse2 -> evalcatmouse3 : [], cost: 1 5: evalcatmouse3 -> evalcatmouse4 : [], cost: 1 6: evalcatmouse4 -> evalcatmouse5 : [], cost: 1 7: evalcatmouse5 -> evalcatmousebb1in : A'=0, [], cost: 1 8: evalcatmousebb1in -> evalcatmousebb2in : [ B>=A ], cost: 1 9: evalcatmousebb1in -> evalcatmousebb3in : [ A>=1+B ], cost: 1 10: evalcatmousebb2in -> evalcatmousebb1in : A'=1+A, [ C>=A ], cost: 1 11: evalcatmousebb2in -> evalcatmousebb1in : A'=-1+A, [ A>=1+C ], cost: 1 12: evalcatmousebb3in -> evalcatmousestop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalcatmousestart -> evalcatmousebb0in : [], cost: 1 Removed unreachable and leaf rules: Start location: evalcatmousestart 0: evalcatmousestart -> evalcatmousebb0in : [], cost: 1 1: evalcatmousebb0in -> evalcatmouse0 : [], cost: 1 2: evalcatmouse0 -> evalcatmouse1 : [], cost: 1 3: evalcatmouse1 -> evalcatmouse2 : [], cost: 1 4: evalcatmouse2 -> evalcatmouse3 : [], cost: 1 5: evalcatmouse3 -> evalcatmouse4 : [], cost: 1 6: evalcatmouse4 -> evalcatmouse5 : [], cost: 1 7: evalcatmouse5 -> evalcatmousebb1in : A'=0, [], cost: 1 8: evalcatmousebb1in -> evalcatmousebb2in : [ B>=A ], cost: 1 10: evalcatmousebb2in -> evalcatmousebb1in : A'=1+A, [ C>=A ], cost: 1 11: evalcatmousebb2in -> evalcatmousebb1in : A'=-1+A, [ A>=1+C ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalcatmousestart 19: evalcatmousestart -> evalcatmousebb1in : A'=0, [], cost: 8 8: evalcatmousebb1in -> evalcatmousebb2in : [ B>=A ], cost: 1 10: evalcatmousebb2in -> evalcatmousebb1in : A'=1+A, [ C>=A ], cost: 1 11: evalcatmousebb2in -> evalcatmousebb1in : A'=-1+A, [ A>=1+C ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalcatmousestart 19: evalcatmousestart -> evalcatmousebb1in : A'=0, [], cost: 8 20: evalcatmousebb1in -> evalcatmousebb1in : A'=1+A, [ B>=A && C>=A ], cost: 2 21: evalcatmousebb1in -> evalcatmousebb1in : A'=-1+A, [ B>=A && A>=1+C ], cost: 2 Accelerating simple loops of location 8. Accelerating the following rules: 20: evalcatmousebb1in -> evalcatmousebb1in : A'=1+A, [ B>=A && C>=A ], cost: 2 21: evalcatmousebb1in -> evalcatmousebb1in : A'=-1+A, [ B>=A && A>=1+C ], cost: 2 Found no metering function for rule 20. Accelerated rule 21 with metering function -C+A, yielding the new rule 22. Nested simple loops 20 (outer loop) and 22 (inner loop) with NONTERM, resulting in the new rules: 23, 24. Removing the simple loops: 20 21. Accelerated all simple loops using metering functions (where possible): Start location: evalcatmousestart 19: evalcatmousestart -> evalcatmousebb1in : A'=0, [], cost: 8 22: evalcatmousebb1in -> evalcatmousebb1in : A'=C, [ B>=A && A>=1+C ], cost: -2*C+2*A 23: evalcatmousebb1in -> [12] : [ B>=A && A>=1+C && B>=C && 2-2*C+2*A>=1 ], cost: NONTERM 24: evalcatmousebb1in -> [12] : A'=1+A, [ C>=A && B>=1+A && 1+A>=1+C && B>=C && 4-2*C+2*A>=1 ], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: evalcatmousestart 19: evalcatmousestart -> evalcatmousebb1in : A'=0, [], cost: 8 25: evalcatmousestart -> evalcatmousebb1in : A'=C, [ B>=0 && 0>=1+C ], cost: 8-2*C 26: evalcatmousestart -> [12] : A'=0, [ B>=0 && 0>=1+C && B>=C && 2-2*C>=1 ], cost: NONTERM 27: evalcatmousestart -> [12] : A'=1, [ -C==0 && B>=1 && B>=C && 4-2*C>=1 ], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: evalcatmousestart 25: evalcatmousestart -> evalcatmousebb1in : A'=C, [ B>=0 && 0>=1+C ], cost: 8-2*C 26: evalcatmousestart -> [12] : A'=0, [ B>=0 && 0>=1+C && B>=C && 2-2*C>=1 ], cost: NONTERM 27: evalcatmousestart -> [12] : A'=1, [ -C==0 && B>=1 && B>=C && 4-2*C>=1 ], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalcatmousestart 25: evalcatmousestart -> evalcatmousebb1in : A'=C, [ B>=0 && 0>=1+C ], cost: 8-2*C 26: evalcatmousestart -> [12] : A'=0, [ B>=0 && 0>=1+C && B>=C && 2-2*C>=1 ], cost: NONTERM 27: evalcatmousestart -> [12] : A'=1, [ -C==0 && B>=1 && B>=C && 4-2*C>=1 ], cost: NONTERM Computing asymptotic complexity for rule 25 Solved the limit problem by the following transformations: Created initial limit problem: 8-2*C (+), 1+B (+/+!), -C (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==-n,B==n} resulting limit problem: [solved] Solution: C / -n B / n Resulting cost 8+2*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 26 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>=0 && 0>=1+C ] NO ---------------------------------------- (2) BOUNDS(INF, INF)