/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, 317 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f0(A, B, C, D) -> Com_1(f10001(A, B, C, D)) :|: TRUE f2(A, B, C, D) -> Com_1(f2(A, B, C, D)) :|: TRUE f2(A, B, C, D) -> Com_1(f10001(A, B, C, D)) :|: TRUE f2(A, B, C, D) -> Com_1(f1200(B, B, C, D)) :|: TRUE f2200(A, B, C, D) -> Com_1(f10000(A, B, 0, D)) :|: C >= 0 && C <= 0 f12(A, B, C, D) -> Com_1(f12(A, B, C, D)) :|: TRUE f100(A, B, C, D) -> Com_1(f110(A, 1, C, D)) :|: TRUE f110(A, B, C, D) -> Com_1(f120(A, 2, C, D)) :|: TRUE f120(A, B, C, D) -> Com_1(f120(A, B, C, D)) :|: TRUE f1200(A, B, C, D) -> Com_1(f1200(A, B, C, D)) :|: TRUE f0(A, B, C, D) -> Com_1(f2(A, 2, C, D)) :|: TRUE f0(A, B, C, D) -> Com_1(f10001(A, 1, C, D)) :|: TRUE f0(A, B, C, D) -> Com_1(f110(1, 1, C, D)) :|: TRUE f0(A, B, C, D) -> Com_1(f12(B, 2, C, D)) :|: TRUE f12(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE f0(A, B, C, D) -> Com_1(f10001(B, B, C, 1)) :|: TRUE f0(A, B, C, D) -> Com_1(f10001(B, 1, C, 1)) :|: TRUE f100(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE f110(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE f120(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE f1000(A, B, C, D) -> Com_1(f1200(A, 2, C, D)) :|: TRUE f1000(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE f1200(A, B, C, D) -> Com_1(f10001(A, B, C, 1)) :|: TRUE f1000(A, B, C, D) -> Com_1(f10001(A, 1, C, 1)) :|: TRUE The start-symbols are:[f0_4] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f0 -> f10001 : [], cost: 1 10: f0 -> f2 : B'=2, [], cost: 1 11: f0 -> f10001 : B'=1, [], cost: 1 12: f0 -> f110 : A'=1, B'=1, [], cost: 1 13: f0 -> f12 : A'=B, B'=2, [], cost: 1 15: f0 -> f10001 : A'=B, D'=1, [], cost: 1 16: f0 -> f10001 : A'=B, B'=1, D'=1, [], cost: 1 1: f2 -> f2 : [], cost: 1 2: f2 -> f10001 : [], cost: 1 3: f2 -> f1200 : A'=B, [], cost: 1 4: f2200 -> f10000 : C'=0, [ C==0 ], cost: 1 5: f12 -> f12 : [], cost: 1 14: f12 -> f10001 : D'=1, [], cost: 1 6: f100 -> f110 : B'=1, [], cost: 1 17: f100 -> f10001 : D'=1, [], cost: 1 7: f110 -> f120 : B'=2, [], cost: 1 18: f110 -> f10001 : D'=1, [], cost: 1 8: f120 -> f120 : [], cost: 1 19: f120 -> f10001 : D'=1, [], cost: 1 9: f1200 -> f1200 : [], cost: 1 22: f1200 -> f10001 : D'=1, [], cost: 1 20: f1000 -> f1200 : B'=2, [], cost: 1 21: f1000 -> f10001 : D'=1, [], cost: 1 23: f1000 -> f10001 : B'=1, D'=1, [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: f0 -> f10001 : [], cost: 1 Removed unreachable and leaf rules: Start location: f0 10: f0 -> f2 : B'=2, [], cost: 1 12: f0 -> f110 : A'=1, B'=1, [], cost: 1 13: f0 -> f12 : A'=B, B'=2, [], cost: 1 1: f2 -> f2 : [], cost: 1 3: f2 -> f1200 : A'=B, [], cost: 1 5: f12 -> f12 : [], cost: 1 7: f110 -> f120 : B'=2, [], cost: 1 8: f120 -> f120 : [], cost: 1 9: f1200 -> f1200 : [], cost: 1 Removed unreachable and leaf rules: Start location: f0 10: f0 -> f2 : B'=2, [], cost: 1 12: f0 -> f110 : A'=1, B'=1, [], cost: 1 13: f0 -> f12 : A'=B, B'=2, [], cost: 1 1: f2 -> f2 : [], cost: 1 3: f2 -> f1200 : A'=B, [], cost: 1 5: f12 -> f12 : [], cost: 1 7: f110 -> f120 : B'=2, [], cost: 1 8: f120 -> f120 : [], cost: 1 9: f1200 -> f1200 : [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: f2 -> f2 : [], cost: 1 Accelerated rule 1 with NONTERM, yielding the new rule 24. Removing the simple loops: 1. Accelerating simple loops of location 3. Accelerating the following rules: 5: f12 -> f12 : [], cost: 1 Accelerated rule 5 with NONTERM, yielding the new rule 25. Removing the simple loops: 5. Accelerating simple loops of location 6. Accelerating the following rules: 8: f120 -> f120 : [], cost: 1 Accelerated rule 8 with NONTERM, yielding the new rule 26. Removing the simple loops: 8. Accelerating simple loops of location 7. Accelerating the following rules: 9: f1200 -> f1200 : [], cost: 1 Accelerated rule 9 with NONTERM, yielding the new rule 27. Removing the simple loops: 9. Accelerated all simple loops using metering functions (where possible): Start location: f0 10: f0 -> f2 : B'=2, [], cost: 1 12: f0 -> f110 : A'=1, B'=1, [], cost: 1 13: f0 -> f12 : A'=B, B'=2, [], cost: 1 3: f2 -> f1200 : A'=B, [], cost: 1 24: f2 -> [11] : [], cost: NONTERM 25: f12 -> [12] : [], cost: NONTERM 7: f110 -> f120 : B'=2, [], cost: 1 26: f120 -> [13] : [], cost: NONTERM 27: f1200 -> [14] : [], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: f0 10: f0 -> f2 : B'=2, [], cost: 1 12: f0 -> f110 : A'=1, B'=1, [], cost: 1 13: f0 -> f12 : A'=B, B'=2, [], cost: 1 28: f0 -> [11] : B'=2, [], cost: NONTERM 29: f0 -> [12] : A'=B, B'=2, [], cost: NONTERM 3: f2 -> f1200 : A'=B, [], cost: 1 31: f2 -> [14] : A'=B, [], cost: NONTERM 7: f110 -> f120 : B'=2, [], cost: 1 30: f110 -> [13] : B'=2, [], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: f0 10: f0 -> f2 : B'=2, [], cost: 1 12: f0 -> f110 : A'=1, B'=1, [], cost: 1 28: f0 -> [11] : B'=2, [], cost: NONTERM 29: f0 -> [12] : A'=B, B'=2, [], cost: NONTERM 31: f2 -> [14] : A'=B, [], cost: NONTERM 30: f110 -> [13] : B'=2, [], cost: NONTERM Eliminated locations (on linear paths): Start location: f0 28: f0 -> [11] : B'=2, [], cost: NONTERM 29: f0 -> [12] : A'=B, B'=2, [], cost: NONTERM 32: f0 -> [14] : A'=2, B'=2, [], cost: NONTERM 33: f0 -> [13] : A'=1, B'=2, [], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 33: f0 -> [13] : A'=1, B'=2, [], cost: NONTERM Computing asymptotic complexity for rule 33 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: [] NO ---------------------------------------- (2) BOUNDS(INF, INF)