/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 223 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 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: INF 25: f12 -> [12] : [], cost: INF 7: f110 -> f120 : B'=2, [], cost: 1 26: f120 -> [13] : [], cost: INF 27: f1200 -> [14] : [], cost: INF 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: INF 29: f0 -> [12] : A'=B, B'=2, [], cost: INF 3: f2 -> f1200 : A'=B, [], cost: 1 31: f2 -> [14] : A'=B, [], cost: INF 7: f110 -> f120 : B'=2, [], cost: 1 30: f110 -> [13] : B'=2, [], cost: INF 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: INF 29: f0 -> [12] : A'=B, B'=2, [], cost: INF 31: f2 -> [14] : A'=B, [], cost: INF 30: f110 -> [13] : B'=2, [], cost: INF Eliminated locations (on linear paths): Start location: f0 28: f0 -> [11] : B'=2, [], cost: INF 29: f0 -> [12] : A'=B, B'=2, [], cost: INF 32: f0 -> [14] : A'=2, B'=2, [], cost: INF 33: f0 -> [13] : A'=1, B'=2, [], cost: INF ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 33: f0 -> [13] : A'=1, B'=2, [], cost: INF Computing asymptotic complexity for rule 33 Resulting cost INF 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: INF Rule cost: INF Rule guard: [] NO ---------------------------------------- (2) BOUNDS(INF, INF)