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