4.15/1.93 WORST_CASE(NON_POLY, ?) 4.15/1.94 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 4.15/1.94 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.15/1.94 4.15/1.94 4.15/1.94 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 4.15/1.94 4.15/1.94 (0) CpxIntTrs 4.15/1.94 (1) Loat Proof [FINISHED, 318 ms] 4.15/1.94 (2) BOUNDS(INF, INF) 4.15/1.94 4.15/1.94 4.15/1.94 ---------------------------------------- 4.15/1.94 4.15/1.94 (0) 4.15/1.94 Obligation: 4.15/1.94 Complexity Int TRS consisting of the following rules: 4.15/1.94 f2(A, B, C, D, E, F) -> Com_1(f2(1 + A, G, G, D, E, F)) :|: G >= 1 && A >= 1 4.15/1.94 f2(A, B, C, D, E, F) -> Com_1(f2(1 + A, G, G, D, E, F)) :|: 0 >= G + 1 && A >= 1 4.15/1.94 f2(A, B, C, D, E, F) -> Com_1(f0(A, 0, 0, G, E, F)) :|: TRUE 4.15/1.94 f3(A, B, C, D, E, F) -> Com_1(f2(1 + A, G, G, D, E, F)) :|: G >= 1 && A >= 1 4.15/1.94 f3(A, B, C, D, E, F) -> Com_1(f2(1 + A, G, G, D, E, F)) :|: 0 >= G + 1 && A >= 1 4.15/1.94 f3(A, B, C, D, E, F) -> Com_1(f0(A, 0, 0, G, E, F)) :|: TRUE 4.15/1.94 f4(A, B, C, D, E, F) -> Com_1(f2(1 + H, G, G, D, H, H)) :|: G >= 1 && H >= 1 4.15/1.94 f4(A, B, C, D, E, F) -> Com_1(f2(1 + H, G, G, D, H, H)) :|: 0 >= G + 1 && H >= 1 4.15/1.94 f4(A, B, C, D, E, F) -> Com_1(f0(G, 0, 0, H, G, G)) :|: TRUE 4.15/1.94 4.15/1.94 The start-symbols are:[f4_6] 4.15/1.94 4.15/1.94 4.15/1.94 ---------------------------------------- 4.15/1.94 4.15/1.94 (1) Loat Proof (FINISHED) 4.15/1.94 4.15/1.94 4.15/1.94 ### Pre-processing the ITS problem ### 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Initial linear ITS problem 4.15/1.94 4.15/1.94 Start location: f4 4.15/1.94 4.15/1.94 0: f2 -> f2 : A'=1+A, B'=free, C'=free, [ free>=1 && A>=1 ], cost: 1 4.15/1.94 4.15/1.94 1: f2 -> f2 : A'=1+A, B'=free_1, C'=free_1, [ 0>=1+free_1 && A>=1 ], cost: 1 4.15/1.94 4.15/1.94 2: f2 -> f0 : B'=0, C'=0, D'=free_2, [], cost: 1 4.15/1.94 4.15/1.94 3: f3 -> f2 : A'=1+A, B'=free_3, C'=free_3, [ free_3>=1 && A>=1 ], cost: 1 4.15/1.94 4.15/1.94 4: f3 -> f2 : A'=1+A, B'=free_4, C'=free_4, [ 0>=1+free_4 && A>=1 ], cost: 1 4.15/1.94 4.15/1.94 5: f3 -> f0 : B'=0, C'=0, D'=free_5, [], cost: 1 4.15/1.94 4.15/1.94 6: f4 -> f2 : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: 1 4.15/1.94 4.15/1.94 7: f4 -> f2 : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: 1 4.15/1.94 4.15/1.94 8: f4 -> f0 : A'=free_10, B'=0, C'=0, D'=free_11, E'=free_10, F'=free_10, [], cost: 1 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Removed unreachable and leaf rules: 4.15/1.94 4.15/1.94 Start location: f4 4.15/1.94 4.15/1.94 0: f2 -> f2 : A'=1+A, B'=free, C'=free, [ free>=1 && A>=1 ], cost: 1 4.15/1.94 4.15/1.94 1: f2 -> f2 : A'=1+A, B'=free_1, C'=free_1, [ 0>=1+free_1 && A>=1 ], cost: 1 4.15/1.94 4.15/1.94 6: f4 -> f2 : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: 1 4.15/1.94 4.15/1.94 7: f4 -> f2 : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: 1 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 ### Simplification by acceleration and chaining ### 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Accelerating simple loops of location 0. 4.15/1.94 4.15/1.94 Accelerating the following rules: 4.15/1.94 4.15/1.94 0: f2 -> f2 : A'=1+A, B'=free, C'=free, [ free>=1 && A>=1 ], cost: 1 4.15/1.94 4.15/1.94 1: f2 -> f2 : A'=1+A, B'=free_1, C'=free_1, [ 0>=1+free_1 && A>=1 ], cost: 1 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Accelerated rule 0 with NONTERM, yielding the new rule 9. 4.15/1.94 4.15/1.94 Accelerated rule 1 with NONTERM, yielding the new rule 10. 4.15/1.94 4.15/1.94 Removing the simple loops: 0 1. 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Accelerated all simple loops using metering functions (where possible): 4.15/1.94 4.15/1.94 Start location: f4 4.15/1.94 4.15/1.94 9: f2 -> [4] : [ free>=1 && A>=1 ], cost: INF 4.15/1.94 4.15/1.94 10: f2 -> [4] : [ 0>=1+free_1 && A>=1 ], cost: INF 4.15/1.94 4.15/1.94 6: f4 -> f2 : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: 1 4.15/1.94 4.15/1.94 7: f4 -> f2 : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: 1 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Chained accelerated rules (with incoming rules): 4.15/1.94 4.15/1.94 Start location: f4 4.15/1.94 4.15/1.94 6: f4 -> f2 : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: 1 4.15/1.94 4.15/1.94 7: f4 -> f2 : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: 1 4.15/1.94 4.15/1.94 11: f4 -> [4] : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: INF 4.15/1.94 4.15/1.94 12: f4 -> [4] : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: INF 4.15/1.94 4.15/1.94 13: f4 -> [4] : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: INF 4.15/1.94 4.15/1.94 14: f4 -> [4] : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: INF 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Removed unreachable locations (and leaf rules with constant cost): 4.15/1.94 4.15/1.94 Start location: f4 4.15/1.94 4.15/1.94 11: f4 -> [4] : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: INF 4.15/1.94 4.15/1.94 12: f4 -> [4] : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: INF 4.15/1.94 4.15/1.94 13: f4 -> [4] : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: INF 4.15/1.94 4.15/1.94 14: f4 -> [4] : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: INF 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 ### Computing asymptotic complexity ### 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Fully simplified ITS problem 4.15/1.94 4.15/1.94 Start location: f4 4.15/1.94 4.15/1.94 13: f4 -> [4] : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: INF 4.15/1.94 4.15/1.94 14: f4 -> [4] : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: INF 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Computing asymptotic complexity for rule 13 4.15/1.94 4.15/1.94 Resulting cost INF has complexity: Nonterm 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Found new complexity Nonterm. 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 Obtained the following overall complexity (w.r.t. the length of the input n): 4.15/1.94 4.15/1.94 Complexity: Nonterm 4.15/1.94 4.15/1.94 Cpx degree: Nonterm 4.15/1.94 4.15/1.94 Solved cost: INF 4.15/1.94 4.15/1.94 Rule cost: INF 4.15/1.94 4.15/1.94 Rule guard: [ free_7>=1 && free_6>=1 ] 4.15/1.94 4.15/1.94 4.15/1.94 4.15/1.94 NO 4.15/1.94 4.15/1.94 4.15/1.94 ---------------------------------------- 4.15/1.94 4.15/1.94 (2) 4.15/1.94 BOUNDS(INF, INF) 4.15/1.96 EOF