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