/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, 1209 ms] (2) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalfstart(A, B, C, D) -> Com_1(evalfentryin(A, B, C, D)) :|: TRUE evalfentryin(A, B, C, D) -> Com_1(evalfbb7in(0, B, C, D)) :|: TRUE evalfbb7in(A, B, C, D) -> Com_1(evalfbb5in(A, B, 0, D)) :|: B * B * B >= 0 && 0 >= B * B * B && 0 >= 1 + A evalfbb7in(A, B, C, D) -> Com_1(evalfbb5in(A, B, 0, D)) :|: B * B * B >= 1 && E >= 0 && B * B * B >= 2 * E && 1 + 2 * E >= B * B * B && E >= 1 + A evalfbb7in(A, B, C, D) -> Com_1(evalfbb5in(A, B, 0, D)) :|: 0 >= B * B * B + 1 && 0 >= E && E >= 1 + A && 2 * E >= B * B * B && 1 + B * B * B >= 2 * E evalfbb7in(A, B, C, D) -> Com_1(evalfreturnin(A, B, C, D)) :|: B * B * B >= 0 && 0 >= B * B * B && A >= 0 evalfbb7in(A, B, C, D) -> Com_1(evalfreturnin(A, B, C, D)) :|: B * B * B >= 1 && E >= 0 && B * B * B >= 2 * E && 1 + 2 * E >= B * B * B && A >= E evalfbb7in(A, B, C, D) -> Com_1(evalfreturnin(A, B, C, D)) :|: 0 >= B * B * B + 1 && 0 >= E && A >= E && 2 * E >= B * B * B && 1 + B * B * B >= 2 * E evalfbb5in(A, B, C, D) -> Com_1(evalfbb3in(A, B, C, 0)) :|: B >= 1 + C evalfbb5in(A, B, C, D) -> Com_1(evalfbb6in(A, B, C, D)) :|: C >= B evalfbb3in(A, B, C, D) -> Com_1(evalfbb2in(A, B, C, D)) :|: C >= 1 + D evalfbb3in(A, B, C, D) -> Com_1(evalfbb4in(A, B, C, D)) :|: D >= C evalfbb2in(A, B, C, D) -> Com_1(evalfbb3in(A, B, C, D + 1)) :|: TRUE evalfbb4in(A, B, C, D) -> Com_1(evalfbb5in(A, B, C + 1, D)) :|: TRUE evalfbb6in(A, B, C, D) -> Com_1(evalfbb7in(A + 1, B, C, D)) :|: TRUE evalfreturnin(A, B, C, D) -> Com_1(evalfstop(A, B, C, D)) :|: TRUE The start-symbols are:[evalfstart_4] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalfstart 0: evalfstart -> evalfentryin : [], cost: 1 1: evalfentryin -> evalfbb7in : A'=0, [], cost: 1 2: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=0 && 0>=B^3 && 0>=1+A ], cost: 1 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 5: evalfbb7in -> evalfreturnin : [ B^3>=0 && 0>=B^3 && A>=0 ], cost: 1 6: evalfbb7in -> evalfreturnin : [ B^3>=1 && free_2>=0 && B^3>=2*free_2 && 1+2*free_2>=B^3 && A>=free_2 ], cost: 1 7: evalfbb7in -> evalfreturnin : [ 0>=1+B^3 && 0>=free_3 && A>=free_3 && 2*free_3>=B^3 && 1+B^3>=2*free_3 ], cost: 1 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 9: evalfbb5in -> evalfbb6in : [ C>=B ], cost: 1 10: evalfbb3in -> evalfbb2in : [ C>=1+D ], cost: 1 11: evalfbb3in -> evalfbb4in : [ D>=C ], cost: 1 12: evalfbb2in -> evalfbb3in : D'=1+D, [], cost: 1 13: evalfbb4in -> evalfbb5in : C'=1+C, [], cost: 1 14: evalfbb6in -> evalfbb7in : A'=1+A, [], cost: 1 15: evalfreturnin -> evalfstop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalfstart -> evalfentryin : [], cost: 1 Removed unreachable and leaf rules: Start location: evalfstart 0: evalfstart -> evalfentryin : [], cost: 1 1: evalfentryin -> evalfbb7in : A'=0, [], cost: 1 2: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=0 && 0>=B^3 && 0>=1+A ], cost: 1 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 9: evalfbb5in -> evalfbb6in : [ C>=B ], cost: 1 10: evalfbb3in -> evalfbb2in : [ C>=1+D ], cost: 1 11: evalfbb3in -> evalfbb4in : [ D>=C ], cost: 1 12: evalfbb2in -> evalfbb3in : D'=1+D, [], cost: 1 13: evalfbb4in -> evalfbb5in : C'=1+C, [], cost: 1 14: evalfbb6in -> evalfbb7in : A'=1+A, [], cost: 1 Simplified all rules, resulting in: Start location: evalfstart 0: evalfstart -> evalfentryin : [], cost: 1 1: evalfentryin -> evalfbb7in : A'=0, [], cost: 1 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 9: evalfbb5in -> evalfbb6in : [ C>=B ], cost: 1 10: evalfbb3in -> evalfbb2in : [ C>=1+D ], cost: 1 11: evalfbb3in -> evalfbb4in : [ D>=C ], cost: 1 12: evalfbb2in -> evalfbb3in : D'=1+D, [], cost: 1 13: evalfbb4in -> evalfbb5in : C'=1+C, [], cost: 1 14: evalfbb6in -> evalfbb7in : A'=1+A, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalfstart 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 18: evalfbb3in -> evalfbb3in : D'=1+D, [ C>=1+D ], cost: 2 19: evalfbb3in -> evalfbb5in : C'=1+C, [ D>=C ], cost: 2 Accelerating simple loops of location 4. Accelerating the following rules: 18: evalfbb3in -> evalfbb3in : D'=1+D, [ C>=1+D ], cost: 2 Accelerated rule 18 with metering function C-D, yielding the new rule 20. Removing the simple loops: 18. Accelerated all simple loops using metering functions (where possible): Start location: evalfstart 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 19: evalfbb3in -> evalfbb5in : C'=1+C, [ D>=C ], cost: 2 20: evalfbb3in -> evalfbb3in : D'=C, [ C>=1+D ], cost: 2*C-2*D Chained accelerated rules (with incoming rules): Start location: evalfstart 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 21: evalfbb5in -> evalfbb3in : D'=C, [ B>=1+C && C>=1 ], cost: 1+2*C 19: evalfbb3in -> evalfbb5in : C'=1+C, [ D>=C ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalfstart 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 22: evalfbb5in -> evalfbb5in : C'=1+C, D'=0, [ B>=1+C && 0>=C ], cost: 3 23: evalfbb5in -> evalfbb5in : C'=1+C, D'=C, [ B>=1+C && C>=1 ], cost: 3+2*C Accelerating simple loops of location 3. Accelerating the following rules: 22: evalfbb5in -> evalfbb5in : C'=1+C, D'=0, [ B>=1+C && 0>=C ], cost: 3 23: evalfbb5in -> evalfbb5in : C'=1+C, D'=C, [ B>=1+C && C>=1 ], cost: 3+2*C Found no metering function for rule 22. Accelerated rule 23 with metering function -C+B, yielding the new rule 24. Removing the simple loops: 23. Accelerated all simple loops using metering functions (where possible): Start location: evalfstart 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 22: evalfbb5in -> evalfbb5in : C'=1+C, D'=0, [ B>=1+C && 0>=C ], cost: 3 24: evalfbb5in -> evalfbb5in : C'=B, D'=-1+B, [ B>=1+C && C>=1 ], cost: -2*C-2*(C-B)*C+(C-B)^2+2*B Chained accelerated rules (with incoming rules): Start location: evalfstart 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 25: evalfbb7in -> evalfbb5in : C'=1, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && B>=1 ], cost: 4 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalfstart 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 26: evalfbb7in -> evalfbb7in : A'=1+A, C'=0, [ -B^3==0 && 0>=1+A && 0>=B ], cost: 3 27: evalfbb7in -> evalfbb7in : A'=1+A, C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 && 0>=B ], cost: 3 28: evalfbb7in -> evalfbb7in : A'=1+A, C'=1, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && B>=1 && 1>=B ], cost: 6 Accelerating simple loops of location 2. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 26: evalfbb7in -> evalfbb7in : A'=1+A, C'=0, [ -B^3==0 && 0>=1+A && 0>=B ], cost: 3 27: evalfbb7in -> evalfbb7in : A'=1+A, C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 && 0>=B ], cost: 3 28: evalfbb7in -> evalfbb7in : A'=1+A, C'=1, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && 1-B==0 ], cost: 6 Accelerated rule 26 with metering function -A, yielding the new rule 29. During metering: Linearized rule by temporarily substituting {B3==B^3} Accelerated rule 27 with metering function free_1-A, yielding the new rule 30. During metering: Linearized rule by temporarily substituting {B3_1==B^3} Accelerated rule 28 with metering function free-A, yielding the new rule 31. Removing the simple loops: 26 27 28. Accelerated all simple loops using metering functions (where possible): Start location: evalfstart 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 29: evalfbb7in -> evalfbb7in : A'=0, C'=0, [ -B^3==0 && 0>=1+A && 0>=B ], cost: -3*A 30: evalfbb7in -> evalfbb7in : A'=free_1, C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 && 0>=B ], cost: 3*free_1-3*A 31: evalfbb7in -> evalfbb7in : A'=free, C'=1, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && 1-B==0 ], cost: 6*free-6*A Chained accelerated rules (with incoming rules): Start location: evalfstart 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 Removed unreachable locations (and leaf rules with constant cost): Start location: evalfstart ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalfstart 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)