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