/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 1736 ms] (2) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f6(A, B, C, D) -> Com_1(f7(A, B, C, D)) :|: 0 >= A + 1 f6(A, B, C, D) -> Com_1(f7(A, B, C, D)) :|: A >= 1 f0(A, B, C, D) -> Com_1(f4(A, B, C, B + 1)) :|: B >= 0 && C >= B f4(A, B, C, D) -> Com_1(f6(E, B, C, D)) :|: B >= D + 1 f4(A, B, C, D) -> Com_1(f6(E, B, C, D)) :|: D >= 1 + B f7(A, B, C, D) -> Com_1(f4(A, B, C, D + 1)) :|: C >= D f7(A, B, C, D) -> Com_1(f4(A, B, C, 0)) :|: D >= 1 + C f6(A, B, C, D) -> Com_1(f14(0, B, C, D)) :|: A >= 0 && A <= 0 f4(A, B, C, D) -> Com_1(f14(A, B, C, B)) :|: B >= D && B <= D The start-symbols are:[f0_4] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f6 -> f7 : [ 0>=1+A ], cost: 1 1: f6 -> f7 : [ A>=1 ], cost: 1 7: f6 -> f14 : A'=0, [ A==0 ], cost: 1 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 3: f4 -> f6 : A'=free, [ B>=1+D ], cost: 1 4: f4 -> f6 : A'=free_1, [ D>=1+B ], cost: 1 8: f4 -> f14 : D'=B, [ B==D ], cost: 1 5: f7 -> f4 : D'=1+D, [ C>=D ], cost: 1 6: f7 -> f4 : D'=0, [ D>=1+C ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 Removed unreachable and leaf rules: Start location: f0 0: f6 -> f7 : [ 0>=1+A ], cost: 1 1: f6 -> f7 : [ A>=1 ], cost: 1 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 3: f4 -> f6 : A'=free, [ B>=1+D ], cost: 1 4: f4 -> f6 : A'=free_1, [ D>=1+B ], cost: 1 5: f7 -> f4 : D'=1+D, [ C>=D ], cost: 1 6: f7 -> f4 : D'=0, [ D>=1+C ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on tree-shaped paths): Start location: f0 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 9: f4 -> f7 : A'=free, [ B>=1+D && 0>=1+free ], cost: 2 10: f4 -> f7 : A'=free, [ B>=1+D && free>=1 ], cost: 2 11: f4 -> f7 : A'=free_1, [ D>=1+B && 0>=1+free_1 ], cost: 2 12: f4 -> f7 : A'=free_1, [ D>=1+B && free_1>=1 ], cost: 2 5: f7 -> f4 : D'=1+D, [ C>=D ], cost: 1 6: f7 -> f4 : D'=0, [ D>=1+C ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: f0 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 13: f4 -> f4 : A'=free, D'=1+D, [ B>=1+D && 0>=1+free && C>=D ], cost: 3 14: f4 -> f4 : A'=free, D'=0, [ B>=1+D && 0>=1+free && D>=1+C ], cost: 3 15: f4 -> f4 : A'=free, D'=1+D, [ B>=1+D && free>=1 && C>=D ], cost: 3 16: f4 -> f4 : A'=free, D'=0, [ B>=1+D && free>=1 && D>=1+C ], cost: 3 17: f4 -> f4 : A'=free_1, D'=1+D, [ D>=1+B && 0>=1+free_1 && C>=D ], cost: 3 18: f4 -> f4 : A'=free_1, D'=0, [ D>=1+B && 0>=1+free_1 && D>=1+C ], cost: 3 19: f4 -> f4 : A'=free_1, D'=1+D, [ D>=1+B && free_1>=1 && C>=D ], cost: 3 20: f4 -> f4 : A'=free_1, D'=0, [ D>=1+B && free_1>=1 && D>=1+C ], cost: 3 Accelerating simple loops of location 2. Accelerating the following rules: 13: f4 -> f4 : A'=free, D'=1+D, [ B>=1+D && 0>=1+free && C>=D ], cost: 3 14: f4 -> f4 : A'=free, D'=0, [ B>=1+D && 0>=1+free && D>=1+C ], cost: 3 15: f4 -> f4 : A'=free, D'=1+D, [ B>=1+D && free>=1 && C>=D ], cost: 3 16: f4 -> f4 : A'=free, D'=0, [ B>=1+D && free>=1 && D>=1+C ], cost: 3 17: f4 -> f4 : A'=free_1, D'=1+D, [ D>=1+B && 0>=1+free_1 && C>=D ], cost: 3 18: f4 -> f4 : A'=free_1, D'=0, [ D>=1+B && 0>=1+free_1 && D>=1+C ], cost: 3 19: f4 -> f4 : A'=free_1, D'=1+D, [ D>=1+B && free_1>=1 && C>=D ], cost: 3 20: f4 -> f4 : A'=free_1, D'=0, [ D>=1+B && free_1>=1 && D>=1+C ], cost: 3 Found no metering function for rule 13. Accelerated rule 14 with NONTERM (after strengthening guard), yielding the new rule 21. Found no metering function for rule 15. Accelerated rule 16 with NONTERM (after strengthening guard), yielding the new rule 22. Accelerated rule 17 with metering function 1+C-D, yielding the new rule 23. Accelerated rule 18 with NONTERM (after strengthening guard), yielding the new rule 24. Accelerated rule 19 with metering function 1+C-D, yielding the new rule 25. Accelerated rule 20 with NONTERM (after strengthening guard), yielding the new rule 26. Nested simple loops 18 (outer loop) and 23 (inner loop) with NONTERM, resulting in the new rules: 27, 28. Nested simple loops 20 (outer loop) and 25 (inner loop) with NONTERM, resulting in the new rules: 29, 30. Removing the simple loops: 17 18 19 20. Accelerated all simple loops using metering functions (where possible): Start location: f0 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 13: f4 -> f4 : A'=free, D'=1+D, [ B>=1+D && 0>=1+free && C>=D ], cost: 3 14: f4 -> f4 : A'=free, D'=0, [ B>=1+D && 0>=1+free && D>=1+C ], cost: 3 15: f4 -> f4 : A'=free, D'=1+D, [ B>=1+D && free>=1 && C>=D ], cost: 3 16: f4 -> f4 : A'=free, D'=0, [ B>=1+D && free>=1 && D>=1+C ], cost: 3 21: f4 -> [5] : [ B>=1+D && 0>=1+free && D>=1+C && B>=1 && 0>=1+C ], cost: NONTERM 22: f4 -> [5] : [ B>=1+D && free>=1 && D>=1+C && B>=1 && 0>=1+C ], cost: NONTERM 23: f4 -> f4 : A'=free_1, D'=1+C, [ D>=1+B && 0>=1+free_1 && C>=D ], cost: 3+3*C-3*D 24: f4 -> [5] : [ D>=1+B && 0>=1+free_1 && D>=1+C && 0>=1+B && 0>=1+C ], cost: NONTERM 25: f4 -> f4 : A'=free_1, D'=1+C, [ D>=1+B && free_1>=1 && C>=D ], cost: 3+3*C-3*D 26: f4 -> [5] : [ D>=1+B && free_1>=1 && D>=1+C && 0>=1+B && 0>=1+C ], cost: NONTERM 27: f4 -> [5] : [ D>=1+B && 0>=1+free_1 && D>=1+C && 0>=1+B && C>=0 && 6+3*C>=1 ], cost: NONTERM 28: f4 -> [5] : A'=free_1, D'=1+C, [ D>=1+B && 0>=1+free_1 && C>=D && 1+C>=1+B && 0>=1+B && C>=0 && 6+3*C>=1 ], cost: NONTERM 29: f4 -> [5] : [ D>=1+B && free_1>=1 && D>=1+C && 0>=1+B && C>=0 && 6+3*C>=1 ], cost: NONTERM 30: f4 -> [5] : A'=free_1, D'=1+C, [ D>=1+B && free_1>=1 && C>=D && 1+C>=1+B && 0>=1+B && C>=0 && 6+3*C>=1 ], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: f0 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 31: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && 0>=1+free_1 && C>=1+B ], cost: 1+3*C-3*B 32: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && free_1>=1 && C>=1+B ], cost: 1+3*C-3*B Removed unreachable locations (and leaf rules with constant cost): Start location: f0 31: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && 0>=1+free_1 && C>=1+B ], cost: 1+3*C-3*B 32: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && free_1>=1 && C>=1+B ], cost: 1+3*C-3*B ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 31: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && 0>=1+free_1 && C>=1+B ], cost: 1+3*C-3*B 32: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && free_1>=1 && C>=1+B ], cost: 1+3*C-3*B Computing asymptotic complexity for rule 31 Solved the limit problem by the following transformations: Created initial limit problem: C-B (+/+!), -free_1 (+/+!), 1+3*C-3*B (+), 1+B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==2*n,free_1==-n,B==n} resulting limit problem: [solved] Solution: C / 2*n free_1 / -n B / n Resulting cost 1+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: 1+3*n Rule cost: 1+3*C-3*B Rule guard: [ B>=0 && 0>=1+free_1 && C>=1+B ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (2) BOUNDS(n^1, INF)