/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, 436 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f18(3, 3, 0, 3, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: TRUE f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: 0 >= A && A >= C f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f10(A, B + A, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: A >= 1 && A >= C f18(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f25(A, B, C, D, D, D, -(3), 4, 0, J, K, L, M, N, O, P, Q, R)) :|: TRUE f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: 0 >= G && G >= I f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f25(A, B, C, D, E, F, G, H + G, I, J, K, L, M, N, O, P, Q, R)) :|: G >= 1 && G >= I f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f40(A, B, C, D, E, F, G, H, I, K, K, K, 3, -(6), 0, P, Q, R)) :|: TRUE f40(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f40(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: 0 >= M && M >= O f40(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f40(A, B, C, D, E, F, G, H, I, J, K, L, M, N + M, O, P, Q, R)) :|: M >= 1 && M >= O f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, Q, Q, Q)) :|: 4 >= F f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, Q, Q, Q)) :|: F >= 5 f40(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f48(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, N, R)) :|: O >= 1 + M f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f33(A, B, C, D, E, F, G, H, I, J, H, L, M, N, O, P, Q, R)) :|: I >= 1 + G f10(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f18(A, B, C, B, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: C >= 1 + A The start-symbols are:[f0_18] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1 1: f10 -> f10 : [ 0>=A && A>=C ], cost: 1 2: f10 -> f10 : B'=A+B, [ A>=1 && A>=C ], cost: 1 13: f10 -> f18 : D'=B, [ C>=1+A ], cost: 1 3: f18 -> f25 : E'=D, F'=D, G'=-3, H'=4, Q'=0, [], cost: 1 4: f25 -> f25 : [ 0>=G && G>=Q ], cost: 1 5: f25 -> f25 : H'=G+H, [ G>=1 && G>=Q ], cost: 1 12: f25 -> f33 : K'=H, [ Q>=1+G ], cost: 1 6: f33 -> f40 : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: 1 7: f40 -> f40 : [ 0>=M && M>=O ], cost: 1 8: f40 -> f40 : N'=M+N, [ M>=1 && M>=O ], cost: 1 11: f40 -> f48 : Q_1'=N, [ O>=1+M ], cost: 1 9: f48 -> f52 : P'=Q_1, R'=Q_1, [ 4>=F ], cost: 1 10: f48 -> f52 : P'=Q_1, R'=Q_1, [ F>=5 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1 Removed unreachable and leaf rules: Start location: f0 0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1 3: f18 -> f25 : E'=D, F'=D, G'=-3, H'=4, Q'=0, [], cost: 1 4: f25 -> f25 : [ 0>=G && G>=Q ], cost: 1 5: f25 -> f25 : H'=G+H, [ G>=1 && G>=Q ], cost: 1 12: f25 -> f33 : K'=H, [ Q>=1+G ], cost: 1 6: f33 -> f40 : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: 1 7: f40 -> f40 : [ 0>=M && M>=O ], cost: 1 8: f40 -> f40 : N'=M+N, [ M>=1 && M>=O ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 3. Accelerating the following rules: 4: f25 -> f25 : [ 0>=G && G>=Q ], cost: 1 5: f25 -> f25 : H'=G+H, [ G>=1 && G>=Q ], cost: 1 Accelerated rule 4 with NONTERM, yielding the new rule 14. Accelerated rule 5 with NONTERM, yielding the new rule 15. Removing the simple loops: 4 5. Accelerating simple loops of location 5. Accelerating the following rules: 7: f40 -> f40 : [ 0>=M && M>=O ], cost: 1 8: f40 -> f40 : N'=M+N, [ M>=1 && M>=O ], cost: 1 Accelerated rule 7 with NONTERM, yielding the new rule 16. Accelerated rule 8 with NONTERM, yielding the new rule 17. Removing the simple loops: 7 8. Accelerated all simple loops using metering functions (where possible): Start location: f0 0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1 3: f18 -> f25 : E'=D, F'=D, G'=-3, H'=4, Q'=0, [], cost: 1 12: f25 -> f33 : K'=H, [ Q>=1+G ], cost: 1 14: f25 -> [8] : [ 0>=G && G>=Q ], cost: NONTERM 15: f25 -> [8] : [ G>=1 && G>=Q ], cost: NONTERM 6: f33 -> f40 : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: 1 16: f40 -> [9] : [ 0>=M && M>=O ], cost: NONTERM 17: f40 -> [9] : [ M>=1 && M>=O ], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: f0 0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1 3: f18 -> f25 : E'=D, F'=D, G'=-3, H'=4, Q'=0, [], cost: 1 12: f25 -> f33 : K'=H, [ Q>=1+G ], cost: 1 6: f33 -> f40 : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: 1 18: f33 -> [9] : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: f0 0: f0 -> f18 : A'=3, B'=3, C'=0, D'=3, [], cost: 1 3: f18 -> f25 : E'=D, F'=D, G'=-3, H'=4, Q'=0, [], cost: 1 12: f25 -> f33 : K'=H, [ Q>=1+G ], cost: 1 18: f33 -> [9] : J'=K, L'=K, M'=3, N'=-6, O'=0, [], cost: NONTERM Eliminated locations (on linear paths): Start location: f0 21: f0 -> [9] : A'=3, B'=3, C'=0, D'=3, E'=3, F'=3, G'=-3, H'=4, Q'=0, J'=4, K'=4, L'=4, M'=3, N'=-6, O'=0, [], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 21: f0 -> [9] : A'=3, B'=3, C'=0, D'=3, E'=3, F'=3, G'=-3, H'=4, Q'=0, J'=4, K'=4, L'=4, M'=3, N'=-6, O'=0, [], cost: NONTERM Computing asymptotic complexity for rule 21 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)