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