6.07/3.43 WORST_CASE(NON_POLY, ?) 6.07/3.44 proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat 6.07/3.44 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.07/3.44 6.07/3.44 6.07/3.44 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 6.07/3.44 6.07/3.44 (0) CpxIntTrs 6.07/3.44 (1) Loat Proof [FINISHED, 1798 ms] 6.07/3.44 (2) BOUNDS(INF, INF) 6.07/3.44 6.07/3.44 6.07/3.44 ---------------------------------------- 6.07/3.44 6.07/3.44 (0) 6.07/3.44 Obligation: 6.07/3.44 Complexity Int TRS consisting of the following rules: 6.07/3.44 f4(A, B) -> Com_1(f5(A, B)) :|: 0 >= A + 1 6.07/3.44 f4(A, B) -> Com_1(f5(A, B)) :|: A >= 1 6.07/3.44 f0(A, B) -> Com_1(f4(C, 0)) :|: TRUE 6.07/3.44 f5(A, B) -> Com_1(f4(C, B + 1)) :|: 3 >= B 6.07/3.44 f5(A, B) -> Com_1(f4(C, B + 1)) :|: B >= 5 6.07/3.44 f5(A, B) -> Com_1(f4(C, 1)) :|: B >= 4 && B <= 4 6.07/3.44 f4(A, B) -> Com_1(f12(0, B)) :|: A >= 0 && A <= 0 6.07/3.44 6.07/3.44 The start-symbols are:[f0_2] 6.07/3.44 6.07/3.44 6.07/3.44 ---------------------------------------- 6.07/3.44 6.07/3.44 (1) Loat Proof (FINISHED) 6.07/3.44 6.07/3.44 6.07/3.44 ### Pre-processing the ITS problem ### 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Initial linear ITS problem 6.07/3.44 6.07/3.44 Start location: f0 6.07/3.44 6.07/3.44 0: f4 -> f5 : [ 0>=1+A ], cost: 1 6.07/3.44 6.07/3.44 1: f4 -> f5 : [ A>=1 ], cost: 1 6.07/3.44 6.07/3.44 6: f4 -> f12 : A'=0, [ A==0 ], cost: 1 6.07/3.44 6.07/3.44 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 6.07/3.44 6.07/3.44 3: f5 -> f4 : A'=free_1, B'=1+B, [ 3>=B ], cost: 1 6.07/3.44 6.07/3.44 4: f5 -> f4 : A'=free_2, B'=1+B, [ B>=5 ], cost: 1 6.07/3.44 6.07/3.44 5: f5 -> f4 : A'=free_3, B'=1, [ B==4 ], cost: 1 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Removed unreachable and leaf rules: 6.07/3.44 6.07/3.44 Start location: f0 6.07/3.44 6.07/3.44 0: f4 -> f5 : [ 0>=1+A ], cost: 1 6.07/3.44 6.07/3.44 1: f4 -> f5 : [ A>=1 ], cost: 1 6.07/3.44 6.07/3.44 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 6.07/3.44 6.07/3.44 3: f5 -> f4 : A'=free_1, B'=1+B, [ 3>=B ], cost: 1 6.07/3.44 6.07/3.44 4: f5 -> f4 : A'=free_2, B'=1+B, [ B>=5 ], cost: 1 6.07/3.44 6.07/3.44 5: f5 -> f4 : A'=free_3, B'=1, [ B==4 ], cost: 1 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 ### Simplification by acceleration and chaining ### 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Eliminated locations (on tree-shaped paths): 6.07/3.44 6.07/3.44 Start location: f0 6.07/3.44 6.07/3.44 7: f4 -> f4 : A'=free_1, B'=1+B, [ 0>=1+A && 3>=B ], cost: 2 6.07/3.44 6.07/3.44 8: f4 -> f4 : A'=free_2, B'=1+B, [ 0>=1+A && B>=5 ], cost: 2 6.07/3.44 6.07/3.44 9: f4 -> f4 : A'=free_3, B'=1, [ 0>=1+A && B==4 ], cost: 2 6.07/3.44 6.07/3.44 10: f4 -> f4 : A'=free_1, B'=1+B, [ A>=1 && 3>=B ], cost: 2 6.07/3.44 6.07/3.44 11: f4 -> f4 : A'=free_2, B'=1+B, [ A>=1 && B>=5 ], cost: 2 6.07/3.44 6.07/3.44 12: f4 -> f4 : A'=free_3, B'=1, [ A>=1 && B==4 ], cost: 2 6.07/3.44 6.07/3.44 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Accelerating simple loops of location 0. 6.07/3.44 6.07/3.44 Accelerating the following rules: 6.07/3.44 6.07/3.44 7: f4 -> f4 : A'=free_1, B'=1+B, [ 0>=1+A && 3>=B ], cost: 2 6.07/3.44 6.07/3.44 8: f4 -> f4 : A'=free_2, B'=1+B, [ 0>=1+A && B>=5 ], cost: 2 6.07/3.44 6.07/3.44 9: f4 -> f4 : A'=free_3, B'=1, [ 0>=1+A && B==4 ], cost: 2 6.07/3.44 6.07/3.44 10: f4 -> f4 : A'=free_1, B'=1+B, [ A>=1 && 3>=B ], cost: 2 6.07/3.44 6.07/3.44 11: f4 -> f4 : A'=free_2, B'=1+B, [ A>=1 && B>=5 ], cost: 2 6.07/3.44 6.07/3.44 12: f4 -> f4 : A'=free_3, B'=1, [ A>=1 && B==4 ], cost: 2 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Accelerated rule 7 with metering function 4-B (after strengthening guard), yielding the new rule 13. 6.07/3.44 6.07/3.44 Accelerated rule 8 with NONTERM (after strengthening guard), yielding the new rule 14. 6.07/3.44 6.07/3.44 Accelerated rule 9 with metering function meter (where 3*meter==-4+B), yielding the new rule 15. 6.07/3.44 6.07/3.44 Accelerated rule 10 with metering function 4-B (after strengthening guard), yielding the new rule 16. 6.07/3.44 6.07/3.44 Accelerated rule 11 with NONTERM (after strengthening guard), yielding the new rule 17. 6.07/3.44 6.07/3.44 Accelerated rule 12 with metering function meter_1 (where 3*meter_1==-4+B), yielding the new rule 18. 6.07/3.44 6.07/3.44 Nested simple loops 9 (outer loop) and 13 (inner loop) with NONTERM, resulting in the new rules: 19, 20. 6.07/3.44 6.07/3.44 Nested simple loops 12 (outer loop) and 16 (inner loop) with NONTERM, resulting in the new rules: 21, 22. 6.07/3.44 6.07/3.44 Removing the simple loops: 9 12. 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Accelerated all simple loops using metering functions (where possible): 6.07/3.44 6.07/3.44 Start location: f0 6.07/3.44 6.07/3.44 7: f4 -> f4 : A'=free_1, B'=1+B, [ 0>=1+A && 3>=B ], cost: 2 6.07/3.44 6.07/3.44 8: f4 -> f4 : A'=free_2, B'=1+B, [ 0>=1+A && B>=5 ], cost: 2 6.07/3.44 6.07/3.44 10: f4 -> f4 : A'=free_1, B'=1+B, [ A>=1 && 3>=B ], cost: 2 6.07/3.44 6.07/3.44 11: f4 -> f4 : A'=free_2, B'=1+B, [ A>=1 && B>=5 ], cost: 2 6.07/3.44 6.07/3.44 13: f4 -> f4 : A'=free_1, B'=4, [ 0>=1+A && 3>=B && 0>=1+free_1 ], cost: 8-2*B 6.07/3.44 6.07/3.44 14: f4 -> [4] : [ 0>=1+A && B>=5 && 0>=1+free_2 ], cost: INF 6.07/3.44 6.07/3.44 15: f4 -> f4 : A'=free_3, B'=1, [ 0>=1+A && B==4 && 3*meter==-4+B && meter>=1 ], cost: 2*meter 6.07/3.44 6.07/3.44 16: f4 -> f4 : A'=free_1, B'=4, [ A>=1 && 3>=B && free_1>=1 ], cost: 8-2*B 6.07/3.44 6.07/3.44 17: f4 -> [4] : [ A>=1 && B>=5 && free_2>=1 ], cost: INF 6.07/3.44 6.07/3.44 18: f4 -> f4 : A'=free_3, B'=1, [ A>=1 && B==4 && 3*meter_1==-4+B && meter_1>=1 ], cost: 2*meter_1 6.07/3.44 6.07/3.44 19: f4 -> [4] : [ 0>=1+A && B==4 && 0>=1+free_1 ], cost: INF 6.07/3.44 6.07/3.44 20: f4 -> [4] : A'=free_1, B'=4, [ 0>=1+A && 3>=B && 0>=1+free_1 ], cost: INF 6.07/3.44 6.07/3.44 21: f4 -> [4] : [ A>=1 && B==4 && free_1>=1 ], cost: INF 6.07/3.44 6.07/3.44 22: f4 -> [4] : A'=free_1, B'=4, [ A>=1 && 3>=B && free_1>=1 ], cost: INF 6.07/3.44 6.07/3.44 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Chained accelerated rules (with incoming rules): 6.07/3.44 6.07/3.44 Start location: f0 6.07/3.44 6.07/3.44 2: f0 -> f4 : A'=free, B'=0, [], cost: 1 6.07/3.44 6.07/3.44 23: f0 -> f4 : A'=free_1, B'=1, [], cost: 3 6.07/3.44 6.07/3.44 24: f0 -> f4 : A'=free_1, B'=1, [], cost: 3 6.07/3.44 6.07/3.44 25: f0 -> f4 : A'=free_1, B'=4, [ 0>=1+free_1 ], cost: 9 6.07/3.44 6.07/3.44 26: f0 -> f4 : A'=free_1, B'=4, [ free_1>=1 ], cost: 9 6.07/3.44 6.07/3.44 27: f0 -> [4] : A'=free_1, B'=4, [ 0>=1+free_1 ], cost: INF 6.07/3.44 6.07/3.44 28: f0 -> [4] : A'=free_1, B'=4, [ free_1>=1 ], cost: INF 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Removed unreachable locations (and leaf rules with constant cost): 6.07/3.44 6.07/3.44 Start location: f0 6.07/3.44 6.07/3.44 27: f0 -> [4] : A'=free_1, B'=4, [ 0>=1+free_1 ], cost: INF 6.07/3.44 6.07/3.44 28: f0 -> [4] : A'=free_1, B'=4, [ free_1>=1 ], cost: INF 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 ### Computing asymptotic complexity ### 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Fully simplified ITS problem 6.07/3.44 6.07/3.44 Start location: f0 6.07/3.44 6.07/3.44 27: f0 -> [4] : A'=free_1, B'=4, [ 0>=1+free_1 ], cost: INF 6.07/3.44 6.07/3.44 28: f0 -> [4] : A'=free_1, B'=4, [ free_1>=1 ], cost: INF 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Computing asymptotic complexity for rule 27 6.07/3.44 6.07/3.44 Resulting cost INF has complexity: Nonterm 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Found new complexity Nonterm. 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 Obtained the following overall complexity (w.r.t. the length of the input n): 6.07/3.44 6.07/3.44 Complexity: Nonterm 6.07/3.44 6.07/3.44 Cpx degree: Nonterm 6.07/3.44 6.07/3.44 Solved cost: INF 6.07/3.44 6.07/3.44 Rule cost: INF 6.07/3.44 6.07/3.44 Rule guard: [ 0>=1+free_1 ] 6.07/3.44 6.07/3.44 6.07/3.44 6.07/3.44 NO 6.07/3.44 6.07/3.44 6.07/3.44 ---------------------------------------- 6.07/3.44 6.07/3.44 (2) 6.07/3.44 BOUNDS(INF, INF) 6.07/3.46 EOF