/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: 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, 1829 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f4(A, B) -> Com_1(f5(A, B)) :|: 0 >= A + 1 f4(A, B) -> Com_1(f5(A, B)) :|: A >= 1 f0(A, B) -> Com_1(f4(C, 0)) :|: TRUE f5(A, B) -> Com_1(f4(C, B + 1)) :|: 3 >= B f5(A, B) -> Com_1(f4(C, B + 1)) :|: B >= 5 f5(A, B) -> Com_1(f4(C, 1)) :|: B >= 4 && B <= 4 f4(A, B) -> Com_1(f12(0, B)) :|: A >= 0 && A <= 0 The start-symbols are:[f0_2] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f4 -> f5 : [ 0>=1+A ], cost: 1 1: f4 -> f5 : [ A>=1 ], cost: 1 6: f4 -> f12 : A'=0, [ A==0 ], cost: 1 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 3: f5 -> f4 : A'=free_1, B'=1+B, [ 3>=B ], cost: 1 4: f5 -> f4 : A'=free_2, B'=1+B, [ B>=5 ], cost: 1 5: f5 -> f4 : A'=free_3, B'=1, [ B==4 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 Removed unreachable and leaf rules: Start location: f0 0: f4 -> f5 : [ 0>=1+A ], cost: 1 1: f4 -> f5 : [ A>=1 ], cost: 1 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 3: f5 -> f4 : A'=free_1, B'=1+B, [ 3>=B ], cost: 1 4: f5 -> f4 : A'=free_2, B'=1+B, [ B>=5 ], cost: 1 5: f5 -> f4 : A'=free_3, B'=1, [ B==4 ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on tree-shaped paths): Start location: f0 7: f4 -> f4 : A'=free_1, B'=1+B, [ 0>=1+A && 3>=B ], cost: 2 8: f4 -> f4 : A'=free_2, B'=1+B, [ 0>=1+A && B>=5 ], cost: 2 9: f4 -> f4 : A'=free_3, B'=1, [ 0>=1+A && B==4 ], cost: 2 10: f4 -> f4 : A'=free_1, B'=1+B, [ A>=1 && 3>=B ], cost: 2 11: f4 -> f4 : A'=free_2, B'=1+B, [ A>=1 && B>=5 ], cost: 2 12: f4 -> f4 : A'=free_3, B'=1, [ A>=1 && B==4 ], cost: 2 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 Accelerating simple loops of location 0. Accelerating the following rules: 7: f4 -> f4 : A'=free_1, B'=1+B, [ 0>=1+A && 3>=B ], cost: 2 8: f4 -> f4 : A'=free_2, B'=1+B, [ 0>=1+A && B>=5 ], cost: 2 9: f4 -> f4 : A'=free_3, B'=1, [ 0>=1+A && B==4 ], cost: 2 10: f4 -> f4 : A'=free_1, B'=1+B, [ A>=1 && 3>=B ], cost: 2 11: f4 -> f4 : A'=free_2, B'=1+B, [ A>=1 && B>=5 ], cost: 2 12: f4 -> f4 : A'=free_3, B'=1, [ A>=1 && B==4 ], cost: 2 Accelerated rule 7 with metering function 4-B (after strengthening guard), yielding the new rule 13. Accelerated rule 8 with NONTERM (after strengthening guard), yielding the new rule 14. Accelerated rule 9 with metering function meter (where 3*meter==-4+B), yielding the new rule 15. Accelerated rule 10 with metering function 4-B (after strengthening guard), yielding the new rule 16. Accelerated rule 11 with NONTERM (after strengthening guard), yielding the new rule 17. Accelerated rule 12 with metering function meter_1 (where 3*meter_1==-4+B), yielding the new rule 18. Nested simple loops 9 (outer loop) and 13 (inner loop) with NONTERM, resulting in the new rules: 19, 20. Nested simple loops 12 (outer loop) and 16 (inner loop) with NONTERM, resulting in the new rules: 21, 22. Removing the simple loops: 9 12. Accelerated all simple loops using metering functions (where possible): Start location: f0 7: f4 -> f4 : A'=free_1, B'=1+B, [ 0>=1+A && 3>=B ], cost: 2 8: f4 -> f4 : A'=free_2, B'=1+B, [ 0>=1+A && B>=5 ], cost: 2 10: f4 -> f4 : A'=free_1, B'=1+B, [ A>=1 && 3>=B ], cost: 2 11: f4 -> f4 : A'=free_2, B'=1+B, [ A>=1 && B>=5 ], cost: 2 13: f4 -> f4 : A'=free_1, B'=4, [ 0>=1+A && 3>=B && 0>=1+free_1 ], cost: 8-2*B 14: f4 -> [4] : [ 0>=1+A && B>=5 && 0>=1+free_2 ], cost: NONTERM 15: f4 -> f4 : A'=free_3, B'=1, [ 0>=1+A && B==4 && 3*meter==-4+B && meter>=1 ], cost: 2*meter 16: f4 -> f4 : A'=free_1, B'=4, [ A>=1 && 3>=B && free_1>=1 ], cost: 8-2*B 17: f4 -> [4] : [ A>=1 && B>=5 && free_2>=1 ], cost: NONTERM 18: f4 -> f4 : A'=free_3, B'=1, [ A>=1 && B==4 && 3*meter_1==-4+B && meter_1>=1 ], cost: 2*meter_1 19: f4 -> [4] : [ 0>=1+A && B==4 && 0>=1+free_1 ], cost: NONTERM 20: f4 -> [4] : A'=free_1, B'=4, [ 0>=1+A && 3>=B && 0>=1+free_1 ], cost: NONTERM 21: f4 -> [4] : [ A>=1 && B==4 && free_1>=1 ], cost: NONTERM 22: f4 -> [4] : A'=free_1, B'=4, [ A>=1 && 3>=B && free_1>=1 ], cost: NONTERM 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: f0 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 23: f0 -> f4 : A'=free_1, B'=1, [], cost: 3 24: f0 -> f4 : A'=free_1, B'=1, [], cost: 3 25: f0 -> f4 : A'=free_1, B'=4, [ 0>=1+free_1 ], cost: 9 26: f0 -> f4 : A'=free_1, B'=4, [ free_1>=1 ], cost: 9 27: f0 -> [4] : A'=free_1, B'=4, [ 0>=1+free_1 ], cost: NONTERM 28: f0 -> [4] : A'=free_1, B'=4, [ free_1>=1 ], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: f0 27: f0 -> [4] : A'=free_1, B'=4, [ 0>=1+free_1 ], cost: NONTERM 28: f0 -> [4] : A'=free_1, B'=4, [ free_1>=1 ], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 27: f0 -> [4] : A'=free_1, B'=4, [ 0>=1+free_1 ], cost: NONTERM 28: f0 -> [4] : A'=free_1, B'=4, [ free_1>=1 ], cost: NONTERM Computing asymptotic complexity for rule 27 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: [ 0>=1+free_1 ] NO ---------------------------------------- (2) BOUNDS(INF, INF)