4.86/2.26 WORST_CASE(NON_POLY, ?) 4.86/2.26 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 4.86/2.26 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.86/2.26 4.86/2.26 4.86/2.26 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 4.86/2.26 4.86/2.26 (0) CpxIntTrs 4.86/2.26 (1) Loat Proof [FINISHED, 513 ms] 4.86/2.26 (2) BOUNDS(INF, INF) 4.86/2.26 4.86/2.26 4.86/2.26 ---------------------------------------- 4.86/2.26 4.86/2.26 (0) 4.86/2.26 Obligation: 4.86/2.26 Complexity Int TRS consisting of the following rules: 4.86/2.26 f21(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) -> Com_1(f29(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O)) :|: 0 >= A 4.86/2.26 f41(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) -> Com_1(f41(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O)) :|: TRUE 4.86/2.26 f43(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) -> Com_1(f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O)) :|: TRUE 4.86/2.26 f29(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) -> Com_1(f41(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O)) :|: A >= 1 4.86/2.26 f29(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) -> Com_1(f41(A, B, P, 0, P, P, G, H, I, J, K, L, M, N, O)) :|: 0 >= A && 999 + B >= P 4.86/2.27 f29(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) -> Com_1(f41(1, B, P, 0, P, P, G, H, I, J, K, L, M, N, O)) :|: 0 >= A && P >= B + 1000 4.86/2.27 f21(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) -> Com_1(f29(0, P, P, D, E, F, 0, P, I, J, K, L, M, N, O)) :|: A >= 1 4.86/2.27 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) -> Com_1(f21(1, B, C, D, E, F, G, H, P, P, K, L, M, N, O)) :|: 0 >= P 4.86/2.27 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) -> Com_1(f21(1, B, C, D, E, F, G, H, P, 0, 1, Q, Q, Q, Q)) :|: P >= 1 && Q >= 1 4.86/2.27 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) -> Com_1(f41(1, B, C, D, E, F, G, H, P, 0, 1, Q, Q, Q, Q)) :|: P >= 1 && 0 >= Q 4.86/2.27 4.86/2.27 The start-symbols are:[f0_15] 4.86/2.27 4.86/2.27 4.86/2.27 ---------------------------------------- 4.86/2.27 4.86/2.27 (1) Loat Proof (FINISHED) 4.86/2.27 4.86/2.27 4.86/2.27 ### Pre-processing the ITS problem ### 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Initial linear ITS problem 4.86/2.27 4.86/2.27 Start location: f0 4.86/2.27 4.86/2.27 0: f21 -> f29 : [ 0>=A ], cost: 1 4.86/2.27 4.86/2.27 6: f21 -> f29 : A'=0, B'=free_2, C'=free_2, G'=0, H'=free_2, [ A>=1 ], cost: 1 4.86/2.27 4.86/2.27 1: f41 -> f41 : [], cost: 1 4.86/2.27 4.86/2.27 2: f43 -> f46 : [], cost: 1 4.86/2.27 4.86/2.27 3: f29 -> f41 : [ A>=1 ], cost: 1 4.86/2.27 4.86/2.27 4: f29 -> f41 : C'=free, D'=0, E'=free, F'=free, [ 0>=A && 999+B>=free ], cost: 1 4.86/2.27 4.86/2.27 5: f29 -> f41 : A'=1, C'=free_1, D'=0, E'=free_1, F'=free_1, [ 0>=A && free_1>=1000+B ], cost: 1 4.86/2.27 4.86/2.27 7: f0 -> f21 : A'=1, Q'=free_3, J'=free_3, [ 0>=free_3 ], cost: 1 4.86/2.27 4.86/2.27 8: f0 -> f21 : A'=1, Q'=free_4, J'=0, K'=1, L'=free_5, M'=free_5, N'=free_5, O'=free_5, [ free_4>=1 && free_5>=1 ], cost: 1 4.86/2.27 4.86/2.27 9: f0 -> f41 : A'=1, Q'=free_6, J'=0, K'=1, L'=free_7, M'=free_7, N'=free_7, O'=free_7, [ free_6>=1 && 0>=free_7 ], cost: 1 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Removed unreachable and leaf rules: 4.86/2.27 4.86/2.27 Start location: f0 4.86/2.27 4.86/2.27 0: f21 -> f29 : [ 0>=A ], cost: 1 4.86/2.27 4.86/2.27 6: f21 -> f29 : A'=0, B'=free_2, C'=free_2, G'=0, H'=free_2, [ A>=1 ], cost: 1 4.86/2.27 4.86/2.27 1: f41 -> f41 : [], cost: 1 4.86/2.27 4.86/2.27 3: f29 -> f41 : [ A>=1 ], cost: 1 4.86/2.27 4.86/2.27 4: f29 -> f41 : C'=free, D'=0, E'=free, F'=free, [ 0>=A && 999+B>=free ], cost: 1 4.86/2.27 4.86/2.27 5: f29 -> f41 : A'=1, C'=free_1, D'=0, E'=free_1, F'=free_1, [ 0>=A && free_1>=1000+B ], cost: 1 4.86/2.27 4.86/2.27 7: f0 -> f21 : A'=1, Q'=free_3, J'=free_3, [ 0>=free_3 ], cost: 1 4.86/2.27 4.86/2.27 8: f0 -> f21 : A'=1, Q'=free_4, J'=0, K'=1, L'=free_5, M'=free_5, N'=free_5, O'=free_5, [ free_4>=1 && free_5>=1 ], cost: 1 4.86/2.27 4.86/2.27 9: f0 -> f41 : A'=1, Q'=free_6, J'=0, K'=1, L'=free_7, M'=free_7, N'=free_7, O'=free_7, [ free_6>=1 && 0>=free_7 ], cost: 1 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 ### Simplification by acceleration and chaining ### 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Accelerating simple loops of location 1. 4.86/2.27 4.86/2.27 Accelerating the following rules: 4.86/2.27 4.86/2.27 1: f41 -> f41 : [], cost: 1 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Accelerated rule 1 with NONTERM, yielding the new rule 10. 4.86/2.27 4.86/2.27 Removing the simple loops: 1. 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Accelerated all simple loops using metering functions (where possible): 4.86/2.27 4.86/2.27 Start location: f0 4.86/2.27 4.86/2.27 0: f21 -> f29 : [ 0>=A ], cost: 1 4.86/2.27 4.86/2.27 6: f21 -> f29 : A'=0, B'=free_2, C'=free_2, G'=0, H'=free_2, [ A>=1 ], cost: 1 4.86/2.27 4.86/2.27 10: f41 -> [6] : [], cost: INF 4.86/2.27 4.86/2.27 3: f29 -> f41 : [ A>=1 ], cost: 1 4.86/2.27 4.86/2.27 4: f29 -> f41 : C'=free, D'=0, E'=free, F'=free, [ 0>=A && 999+B>=free ], cost: 1 4.86/2.27 4.86/2.27 5: f29 -> f41 : A'=1, C'=free_1, D'=0, E'=free_1, F'=free_1, [ 0>=A && free_1>=1000+B ], cost: 1 4.86/2.27 4.86/2.27 7: f0 -> f21 : A'=1, Q'=free_3, J'=free_3, [ 0>=free_3 ], cost: 1 4.86/2.27 4.86/2.27 8: f0 -> f21 : A'=1, Q'=free_4, J'=0, K'=1, L'=free_5, M'=free_5, N'=free_5, O'=free_5, [ free_4>=1 && free_5>=1 ], cost: 1 4.86/2.27 4.86/2.27 9: f0 -> f41 : A'=1, Q'=free_6, J'=0, K'=1, L'=free_7, M'=free_7, N'=free_7, O'=free_7, [ free_6>=1 && 0>=free_7 ], cost: 1 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Chained accelerated rules (with incoming rules): 4.86/2.27 4.86/2.27 Start location: f0 4.86/2.27 4.86/2.27 0: f21 -> f29 : [ 0>=A ], cost: 1 4.86/2.27 4.86/2.27 6: f21 -> f29 : A'=0, B'=free_2, C'=free_2, G'=0, H'=free_2, [ A>=1 ], cost: 1 4.86/2.27 4.86/2.27 3: f29 -> f41 : [ A>=1 ], cost: 1 4.86/2.27 4.86/2.27 4: f29 -> f41 : C'=free, D'=0, E'=free, F'=free, [ 0>=A && 999+B>=free ], cost: 1 4.86/2.27 4.86/2.27 5: f29 -> f41 : A'=1, C'=free_1, D'=0, E'=free_1, F'=free_1, [ 0>=A && free_1>=1000+B ], cost: 1 4.86/2.27 4.86/2.27 11: f29 -> [6] : [ A>=1 ], cost: INF 4.86/2.27 4.86/2.27 12: f29 -> [6] : C'=free, D'=0, E'=free, F'=free, [ 0>=A && 999+B>=free ], cost: INF 4.86/2.27 4.86/2.27 13: f29 -> [6] : A'=1, C'=free_1, D'=0, E'=free_1, F'=free_1, [ 0>=A && free_1>=1000+B ], cost: INF 4.86/2.27 4.86/2.27 7: f0 -> f21 : A'=1, Q'=free_3, J'=free_3, [ 0>=free_3 ], cost: 1 4.86/2.27 4.86/2.27 8: f0 -> f21 : A'=1, Q'=free_4, J'=0, K'=1, L'=free_5, M'=free_5, N'=free_5, O'=free_5, [ free_4>=1 && free_5>=1 ], cost: 1 4.86/2.27 4.86/2.27 9: f0 -> f41 : A'=1, Q'=free_6, J'=0, K'=1, L'=free_7, M'=free_7, N'=free_7, O'=free_7, [ free_6>=1 && 0>=free_7 ], cost: 1 4.86/2.27 4.86/2.27 14: f0 -> [6] : A'=1, Q'=free_6, J'=0, K'=1, L'=free_7, M'=free_7, N'=free_7, O'=free_7, [ free_6>=1 && 0>=free_7 ], cost: INF 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Removed unreachable locations (and leaf rules with constant cost): 4.86/2.27 4.86/2.27 Start location: f0 4.86/2.27 4.86/2.27 0: f21 -> f29 : [ 0>=A ], cost: 1 4.86/2.27 4.86/2.27 6: f21 -> f29 : A'=0, B'=free_2, C'=free_2, G'=0, H'=free_2, [ A>=1 ], cost: 1 4.86/2.27 4.86/2.27 11: f29 -> [6] : [ A>=1 ], cost: INF 4.86/2.27 4.86/2.27 12: f29 -> [6] : C'=free, D'=0, E'=free, F'=free, [ 0>=A && 999+B>=free ], cost: INF 4.86/2.27 4.86/2.27 13: f29 -> [6] : A'=1, C'=free_1, D'=0, E'=free_1, F'=free_1, [ 0>=A && free_1>=1000+B ], cost: INF 4.86/2.27 4.86/2.27 7: f0 -> f21 : A'=1, Q'=free_3, J'=free_3, [ 0>=free_3 ], cost: 1 4.86/2.27 4.86/2.27 8: f0 -> f21 : A'=1, Q'=free_4, J'=0, K'=1, L'=free_5, M'=free_5, N'=free_5, O'=free_5, [ free_4>=1 && free_5>=1 ], cost: 1 4.86/2.27 4.86/2.27 14: f0 -> [6] : A'=1, Q'=free_6, J'=0, K'=1, L'=free_7, M'=free_7, N'=free_7, O'=free_7, [ free_6>=1 && 0>=free_7 ], cost: INF 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Eliminated locations (on tree-shaped paths): 4.86/2.27 4.86/2.27 Start location: f0 4.86/2.27 4.86/2.27 11: f29 -> [6] : [ A>=1 ], cost: INF 4.86/2.27 4.86/2.27 12: f29 -> [6] : C'=free, D'=0, E'=free, F'=free, [ 0>=A && 999+B>=free ], cost: INF 4.86/2.27 4.86/2.27 13: f29 -> [6] : A'=1, C'=free_1, D'=0, E'=free_1, F'=free_1, [ 0>=A && free_1>=1000+B ], cost: INF 4.86/2.27 4.86/2.27 14: f0 -> [6] : A'=1, Q'=free_6, J'=0, K'=1, L'=free_7, M'=free_7, N'=free_7, O'=free_7, [ free_6>=1 && 0>=free_7 ], cost: INF 4.86/2.27 4.86/2.27 15: f0 -> f29 : A'=0, B'=free_2, C'=free_2, G'=0, H'=free_2, Q'=free_3, J'=free_3, [ 0>=free_3 ], cost: 2 4.86/2.27 4.86/2.27 16: f0 -> f29 : A'=0, B'=free_2, C'=free_2, G'=0, H'=free_2, Q'=free_4, J'=0, K'=1, L'=free_5, M'=free_5, N'=free_5, O'=free_5, [ free_4>=1 && free_5>=1 ], cost: 2 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Eliminated locations (on tree-shaped paths): 4.86/2.27 4.86/2.27 Start location: f0 4.86/2.27 4.86/2.27 14: f0 -> [6] : A'=1, Q'=free_6, J'=0, K'=1, L'=free_7, M'=free_7, N'=free_7, O'=free_7, [ free_6>=1 && 0>=free_7 ], cost: INF 4.86/2.27 4.86/2.27 17: f0 -> [6] : A'=0, B'=free_2, C'=free, D'=0, E'=free, F'=free, G'=0, H'=free_2, Q'=free_3, J'=free_3, [ 0>=free_3 && 999+free_2>=free ], cost: INF 4.86/2.27 4.86/2.27 18: f0 -> [6] : A'=1, B'=free_2, C'=free_1, D'=0, E'=free_1, F'=free_1, G'=0, H'=free_2, Q'=free_3, J'=free_3, [ 0>=free_3 && free_1>=1000+free_2 ], cost: INF 4.86/2.27 4.86/2.27 19: f0 -> [6] : A'=0, B'=free_2, C'=free, D'=0, E'=free, F'=free, G'=0, H'=free_2, Q'=free_4, J'=0, K'=1, L'=free_5, M'=free_5, N'=free_5, O'=free_5, [ free_4>=1 && free_5>=1 && 999+free_2>=free ], cost: INF 4.86/2.27 4.86/2.27 20: f0 -> [6] : A'=1, B'=free_2, C'=free_1, D'=0, E'=free_1, F'=free_1, G'=0, H'=free_2, Q'=free_4, J'=0, K'=1, L'=free_5, M'=free_5, N'=free_5, O'=free_5, [ free_4>=1 && free_5>=1 && free_1>=1000+free_2 ], cost: INF 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 ### Computing asymptotic complexity ### 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Fully simplified ITS problem 4.86/2.27 4.86/2.27 Start location: f0 4.86/2.27 4.86/2.27 14: f0 -> [6] : A'=1, Q'=free_6, J'=0, K'=1, L'=free_7, M'=free_7, N'=free_7, O'=free_7, [ free_6>=1 && 0>=free_7 ], cost: INF 4.86/2.27 4.86/2.27 17: f0 -> [6] : A'=0, B'=free_2, C'=free, D'=0, E'=free, F'=free, G'=0, H'=free_2, Q'=free_3, J'=free_3, [ 0>=free_3 && 999+free_2>=free ], cost: INF 4.86/2.27 4.86/2.27 18: f0 -> [6] : A'=1, B'=free_2, C'=free_1, D'=0, E'=free_1, F'=free_1, G'=0, H'=free_2, Q'=free_3, J'=free_3, [ 0>=free_3 && free_1>=1000+free_2 ], cost: INF 4.86/2.27 4.86/2.27 19: f0 -> [6] : A'=0, B'=free_2, C'=free, D'=0, E'=free, F'=free, G'=0, H'=free_2, Q'=free_4, J'=0, K'=1, L'=free_5, M'=free_5, N'=free_5, O'=free_5, [ free_4>=1 && free_5>=1 && 999+free_2>=free ], cost: INF 4.86/2.27 4.86/2.27 20: f0 -> [6] : A'=1, B'=free_2, C'=free_1, D'=0, E'=free_1, F'=free_1, G'=0, H'=free_2, Q'=free_4, J'=0, K'=1, L'=free_5, M'=free_5, N'=free_5, O'=free_5, [ free_4>=1 && free_5>=1 && free_1>=1000+free_2 ], cost: INF 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Computing asymptotic complexity for rule 14 4.86/2.27 4.86/2.27 Resulting cost INF has complexity: Nonterm 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Found new complexity Nonterm. 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 Obtained the following overall complexity (w.r.t. the length of the input n): 4.86/2.27 4.86/2.27 Complexity: Nonterm 4.86/2.27 4.86/2.27 Cpx degree: Nonterm 4.86/2.27 4.86/2.27 Solved cost: INF 4.86/2.27 4.86/2.27 Rule cost: INF 4.86/2.27 4.86/2.27 Rule guard: [ free_6>=1 && 0>=free_7 ] 4.86/2.27 4.86/2.27 4.86/2.27 4.86/2.27 NO 4.86/2.27 4.86/2.27 4.86/2.27 ---------------------------------------- 4.86/2.27 4.86/2.27 (2) 4.86/2.27 BOUNDS(INF, INF) 4.86/2.29 EOF