8.35/4.93 WORST_CASE(Omega(n^1), ?) 8.35/4.94 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 8.35/4.94 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.35/4.94 8.35/4.94 8.35/4.94 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, INF). 8.35/4.94 8.35/4.94 (0) CpxIntTrs 8.35/4.94 (1) Loat Proof [FINISHED, 3221 ms] 8.35/4.94 (2) BOUNDS(n^1, INF) 8.35/4.94 8.35/4.94 8.35/4.94 ---------------------------------------- 8.35/4.94 8.35/4.94 (0) 8.35/4.94 Obligation: 8.35/4.94 Complexity Int TRS consisting of the following rules: 8.35/4.94 f6(A, B, C, D) -> Com_1(f7(A, B, C, D)) :|: 0 >= A + 1 8.35/4.94 f6(A, B, C, D) -> Com_1(f7(A, B, C, D)) :|: A >= 1 8.35/4.94 f0(A, B, C, D) -> Com_1(f4(A, B, C, B + 1)) :|: B >= 0 && C >= B 8.35/4.94 f4(A, B, C, D) -> Com_1(f6(E, B, C, D)) :|: B >= D + 1 8.35/4.94 f4(A, B, C, D) -> Com_1(f6(E, B, C, D)) :|: D >= 1 + B 8.35/4.94 f7(A, B, C, D) -> Com_1(f4(A, B, C, D + 1)) :|: C >= D 8.35/4.94 f7(A, B, C, D) -> Com_1(f4(A, B, C, 0)) :|: D >= 1 + C 8.35/4.94 f6(A, B, C, D) -> Com_1(f14(0, B, C, D)) :|: A >= 0 && A <= 0 8.35/4.94 f4(A, B, C, D) -> Com_1(f14(A, B, C, B)) :|: B >= D && B <= D 8.35/4.94 8.35/4.94 The start-symbols are:[f0_4] 8.35/4.94 8.35/4.94 8.35/4.94 ---------------------------------------- 8.35/4.94 8.35/4.94 (1) Loat Proof (FINISHED) 8.35/4.94 8.35/4.94 8.35/4.94 ### Pre-processing the ITS problem ### 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Initial linear ITS problem 8.35/4.94 8.35/4.94 Start location: f0 8.35/4.94 8.35/4.94 0: f6 -> f7 : [ 0>=1+A ], cost: 1 8.35/4.94 8.35/4.94 1: f6 -> f7 : [ A>=1 ], cost: 1 8.35/4.94 8.35/4.94 7: f6 -> f14 : A'=0, [ A==0 ], cost: 1 8.35/4.94 8.35/4.94 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 8.35/4.94 8.35/4.94 3: f4 -> f6 : A'=free, [ B>=1+D ], cost: 1 8.35/4.94 8.35/4.94 4: f4 -> f6 : A'=free_1, [ D>=1+B ], cost: 1 8.35/4.94 8.35/4.94 8: f4 -> f14 : D'=B, [ B==D ], cost: 1 8.35/4.94 8.35/4.94 5: f7 -> f4 : D'=1+D, [ C>=D ], cost: 1 8.35/4.94 8.35/4.94 6: f7 -> f4 : D'=0, [ D>=1+C ], cost: 1 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Removed unreachable and leaf rules: 8.35/4.94 8.35/4.94 Start location: f0 8.35/4.94 8.35/4.94 0: f6 -> f7 : [ 0>=1+A ], cost: 1 8.35/4.94 8.35/4.94 1: f6 -> f7 : [ A>=1 ], cost: 1 8.35/4.94 8.35/4.94 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 8.35/4.94 8.35/4.94 3: f4 -> f6 : A'=free, [ B>=1+D ], cost: 1 8.35/4.94 8.35/4.94 4: f4 -> f6 : A'=free_1, [ D>=1+B ], cost: 1 8.35/4.94 8.35/4.94 5: f7 -> f4 : D'=1+D, [ C>=D ], cost: 1 8.35/4.94 8.35/4.94 6: f7 -> f4 : D'=0, [ D>=1+C ], cost: 1 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 ### Simplification by acceleration and chaining ### 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Eliminated locations (on tree-shaped paths): 8.35/4.94 8.35/4.94 Start location: f0 8.35/4.94 8.35/4.94 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 8.35/4.94 8.35/4.94 9: f4 -> f7 : A'=free, [ B>=1+D && 0>=1+free ], cost: 2 8.35/4.94 8.35/4.94 10: f4 -> f7 : A'=free, [ B>=1+D && free>=1 ], cost: 2 8.35/4.94 8.35/4.94 11: f4 -> f7 : A'=free_1, [ D>=1+B && 0>=1+free_1 ], cost: 2 8.35/4.94 8.35/4.94 12: f4 -> f7 : A'=free_1, [ D>=1+B && free_1>=1 ], cost: 2 8.35/4.94 8.35/4.94 5: f7 -> f4 : D'=1+D, [ C>=D ], cost: 1 8.35/4.94 8.35/4.94 6: f7 -> f4 : D'=0, [ D>=1+C ], cost: 1 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Eliminated locations (on tree-shaped paths): 8.35/4.94 8.35/4.94 Start location: f0 8.35/4.94 8.35/4.94 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 8.35/4.94 8.35/4.94 13: f4 -> f4 : A'=free, D'=1+D, [ B>=1+D && 0>=1+free && C>=D ], cost: 3 8.35/4.94 8.35/4.94 14: f4 -> f4 : A'=free, D'=0, [ B>=1+D && 0>=1+free && D>=1+C ], cost: 3 8.35/4.94 8.35/4.94 15: f4 -> f4 : A'=free, D'=1+D, [ B>=1+D && free>=1 && C>=D ], cost: 3 8.35/4.94 8.35/4.94 16: f4 -> f4 : A'=free, D'=0, [ B>=1+D && free>=1 && D>=1+C ], cost: 3 8.35/4.94 8.35/4.94 17: f4 -> f4 : A'=free_1, D'=1+D, [ D>=1+B && 0>=1+free_1 && C>=D ], cost: 3 8.35/4.94 8.35/4.94 18: f4 -> f4 : A'=free_1, D'=0, [ D>=1+B && 0>=1+free_1 && D>=1+C ], cost: 3 8.35/4.94 8.35/4.94 19: f4 -> f4 : A'=free_1, D'=1+D, [ D>=1+B && free_1>=1 && C>=D ], cost: 3 8.35/4.94 8.35/4.94 20: f4 -> f4 : A'=free_1, D'=0, [ D>=1+B && free_1>=1 && D>=1+C ], cost: 3 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Accelerating simple loops of location 2. 8.35/4.94 8.35/4.94 Accelerating the following rules: 8.35/4.94 8.35/4.94 13: f4 -> f4 : A'=free, D'=1+D, [ B>=1+D && 0>=1+free && C>=D ], cost: 3 8.35/4.94 8.35/4.94 14: f4 -> f4 : A'=free, D'=0, [ B>=1+D && 0>=1+free && D>=1+C ], cost: 3 8.35/4.94 8.35/4.94 15: f4 -> f4 : A'=free, D'=1+D, [ B>=1+D && free>=1 && C>=D ], cost: 3 8.35/4.94 8.35/4.94 16: f4 -> f4 : A'=free, D'=0, [ B>=1+D && free>=1 && D>=1+C ], cost: 3 8.35/4.94 8.35/4.94 17: f4 -> f4 : A'=free_1, D'=1+D, [ D>=1+B && 0>=1+free_1 && C>=D ], cost: 3 8.35/4.94 8.35/4.94 18: f4 -> f4 : A'=free_1, D'=0, [ D>=1+B && 0>=1+free_1 && D>=1+C ], cost: 3 8.35/4.94 8.35/4.94 19: f4 -> f4 : A'=free_1, D'=1+D, [ D>=1+B && free_1>=1 && C>=D ], cost: 3 8.35/4.94 8.35/4.94 20: f4 -> f4 : A'=free_1, D'=0, [ D>=1+B && free_1>=1 && D>=1+C ], cost: 3 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Accelerated rule 13 with backward acceleration, yielding the new rule 21. 8.35/4.94 8.35/4.94 Accelerated rule 13 with backward acceleration, yielding the new rule 22. 8.35/4.94 8.35/4.94 Accelerated rule 14 with NONTERM (after strengthening guard), yielding the new rule 23. 8.35/4.94 8.35/4.94 Accelerated rule 15 with backward acceleration, yielding the new rule 24. 8.35/4.94 8.35/4.94 Accelerated rule 15 with backward acceleration, yielding the new rule 25. 8.35/4.94 8.35/4.94 Accelerated rule 16 with NONTERM (after strengthening guard), yielding the new rule 26. 8.35/4.94 8.35/4.94 Accelerated rule 17 with metering function 1+C-D, yielding the new rule 27. 8.35/4.94 8.35/4.94 Accelerated rule 18 with NONTERM (after strengthening guard), yielding the new rule 28. 8.35/4.94 8.35/4.94 Accelerated rule 19 with metering function 1+C-D, yielding the new rule 29. 8.35/4.94 8.35/4.94 Accelerated rule 20 with NONTERM (after strengthening guard), yielding the new rule 30. 8.35/4.94 8.35/4.94 Nested simple loops 14 (outer loop) and 22 (inner loop) with NONTERM, resulting in the new rules: 31, 32. 8.35/4.94 8.35/4.94 Nested simple loops 16 (outer loop) and 25 (inner loop) with NONTERM, resulting in the new rules: 33, 34. 8.35/4.94 8.35/4.94 Nested simple loops 18 (outer loop) and 27 (inner loop) with NONTERM, resulting in the new rules: 35, 36. 8.35/4.94 8.35/4.94 Nested simple loops 20 (outer loop) and 29 (inner loop) with NONTERM, resulting in the new rules: 37, 38. 8.35/4.94 8.35/4.94 Removing the simple loops: 13 14 15 16 17 18 19 20. 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Accelerated all simple loops using metering functions (where possible): 8.35/4.94 8.35/4.94 Start location: f0 8.35/4.94 8.35/4.94 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 8.35/4.94 8.35/4.94 21: f4 -> f4 : A'=free, D'=B, [ B>=1+D && 0>=1+free && C>=D && C>=-1+B ], cost: -3*D+3*B 8.35/4.94 8.35/4.94 22: f4 -> f4 : A'=free, D'=1+C, [ B>=1+D && 0>=1+free && C>=D && B>=1+C ], cost: 3+3*C-3*D 8.35/4.94 8.35/4.94 23: f4 -> [5] : [ B>=1+D && 0>=1+free && D>=1+C && B>=1 && 0>=1+C ], cost: INF 8.35/4.94 8.35/4.94 24: f4 -> f4 : A'=free, D'=B, [ B>=1+D && free>=1 && C>=D && C>=-1+B ], cost: -3*D+3*B 8.35/4.94 8.35/4.94 25: f4 -> f4 : A'=free, D'=1+C, [ B>=1+D && free>=1 && C>=D && B>=1+C ], cost: 3+3*C-3*D 8.35/4.94 8.35/4.94 26: f4 -> [5] : [ B>=1+D && free>=1 && D>=1+C && B>=1 && 0>=1+C ], cost: INF 8.35/4.94 8.35/4.94 27: f4 -> f4 : A'=free_1, D'=1+C, [ D>=1+B && 0>=1+free_1 && C>=D ], cost: 3+3*C-3*D 8.35/4.94 8.35/4.94 28: f4 -> [5] : [ D>=1+B && 0>=1+free_1 && D>=1+C && 0>=1+B && 0>=1+C ], cost: INF 8.35/4.94 8.35/4.94 29: f4 -> f4 : A'=free_1, D'=1+C, [ D>=1+B && free_1>=1 && C>=D ], cost: 3+3*C-3*D 8.35/4.94 8.35/4.94 30: f4 -> [5] : [ D>=1+B && free_1>=1 && D>=1+C && 0>=1+B && 0>=1+C ], cost: INF 8.35/4.94 8.35/4.94 31: f4 -> [5] : [ B>=1+D && 0>=1+free && D>=1+C && B>=1 && C>=0 && B>=1+C && 6+3*C>=1 ], cost: INF 8.35/4.94 8.35/4.94 32: f4 -> [5] : A'=free, D'=1+C, [ B>=1+D && 0>=1+free && C>=D && B>=2+C && B>=1 && C>=0 && 6+3*C>=1 ], cost: INF 8.35/4.94 8.35/4.94 33: f4 -> [5] : [ B>=1+D && free>=1 && D>=1+C && B>=1 && C>=0 && B>=1+C && 6+3*C>=1 ], cost: INF 8.35/4.94 8.35/4.94 34: f4 -> [5] : A'=free, D'=1+C, [ B>=1+D && free>=1 && C>=D && B>=2+C && B>=1 && C>=0 && 6+3*C>=1 ], cost: INF 8.35/4.94 8.35/4.94 35: f4 -> [5] : [ D>=1+B && 0>=1+free_1 && D>=1+C && 0>=1+B && C>=0 && 6+3*C>=1 ], cost: INF 8.35/4.94 8.35/4.94 36: f4 -> [5] : A'=free_1, D'=1+C, [ D>=1+B && 0>=1+free_1 && C>=D && 1+C>=1+B && 0>=1+B && C>=0 && 6+3*C>=1 ], cost: INF 8.35/4.94 8.35/4.94 37: f4 -> [5] : [ D>=1+B && free_1>=1 && D>=1+C && 0>=1+B && C>=0 && 6+3*C>=1 ], cost: INF 8.35/4.94 8.35/4.94 38: f4 -> [5] : A'=free_1, D'=1+C, [ D>=1+B && free_1>=1 && C>=D && 1+C>=1+B && 0>=1+B && C>=0 && 6+3*C>=1 ], cost: INF 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Chained accelerated rules (with incoming rules): 8.35/4.94 8.35/4.94 Start location: f0 8.35/4.94 8.35/4.94 2: f0 -> f4 : D'=1+B, [ B>=0 && C>=B ], cost: 1 8.35/4.94 8.35/4.94 39: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && 0>=1+free_1 && C>=1+B ], cost: 1+3*C-3*B 8.35/4.94 8.35/4.94 40: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && free_1>=1 && C>=1+B ], cost: 1+3*C-3*B 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Removed unreachable locations (and leaf rules with constant cost): 8.35/4.94 8.35/4.94 Start location: f0 8.35/4.94 8.35/4.94 39: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && 0>=1+free_1 && C>=1+B ], cost: 1+3*C-3*B 8.35/4.94 8.35/4.94 40: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && free_1>=1 && C>=1+B ], cost: 1+3*C-3*B 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 ### Computing asymptotic complexity ### 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Fully simplified ITS problem 8.35/4.94 8.35/4.94 Start location: f0 8.35/4.94 8.35/4.94 39: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && 0>=1+free_1 && C>=1+B ], cost: 1+3*C-3*B 8.35/4.94 8.35/4.94 40: f0 -> f4 : A'=free_1, D'=1+C, [ B>=0 && free_1>=1 && C>=1+B ], cost: 1+3*C-3*B 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Computing asymptotic complexity for rule 39 8.35/4.94 8.35/4.94 Solved the limit problem by the following transformations: 8.35/4.94 8.35/4.94 Created initial limit problem: 8.35/4.94 8.35/4.94 1+3*C-3*B (+), 1+B (+/+!), C-B (+/+!), -free_1 (+/+!) [not solved] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 applying transformation rule (C) using substitution {B==0} 8.35/4.94 8.35/4.94 resulting limit problem: 8.35/4.94 8.35/4.94 1 (+/+!), C (+/+!), 1+3*C (+), -free_1 (+/+!) [not solved] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 applying transformation rule (C) using substitution {C==1+B} 8.35/4.94 8.35/4.94 resulting limit problem: 8.35/4.94 8.35/4.94 1 (+/+!), 1+B (+/+!), -free_1 (+/+!), 4+3*B (+) [not solved] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 applying transformation rule (B), deleting 1 (+/+!) 8.35/4.94 8.35/4.94 resulting limit problem: 8.35/4.94 8.35/4.94 1+B (+/+!), -free_1 (+/+!), 4+3*B (+) [not solved] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 applying transformation rule (D), replacing 1+B (+/+!) by B (+) 8.35/4.94 8.35/4.94 resulting limit problem: 8.35/4.94 8.35/4.94 -free_1 (+/+!), 4+3*B (+), B (+) [not solved] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 applying transformation rule (D), replacing 4+3*B (+) by 3*B (+) 8.35/4.94 8.35/4.94 resulting limit problem: 8.35/4.94 8.35/4.94 -free_1 (+/+!), 3*B (+), B (+) [not solved] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 applying transformation rule (C) using substitution {free_1==-1} 8.35/4.94 8.35/4.94 resulting limit problem: 8.35/4.94 8.35/4.94 1 (+/+!), 3*B (+), B (+) [not solved] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 applying transformation rule (B), deleting 1 (+/+!) 8.35/4.94 8.35/4.94 resulting limit problem: 8.35/4.94 8.35/4.94 3*B (+), B (+) [not solved] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 applying transformation rule (A), replacing 3*B (+) by B (+) and 3 (+!) using + limit vector (+,+!) 8.35/4.94 8.35/4.94 resulting limit problem: 8.35/4.94 8.35/4.94 3 (+!), B (+) [not solved] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 applying transformation rule (B), deleting 3 (+!) 8.35/4.94 8.35/4.94 resulting limit problem: 8.35/4.94 8.35/4.94 B (+) [solved] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Solution: 8.35/4.94 8.35/4.94 C / 1+n 8.35/4.94 8.35/4.94 free_1 / -1 8.35/4.94 8.35/4.94 B / 0 8.35/4.94 8.35/4.94 Resulting cost 4+3*n has complexity: Poly(n^1) 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Found new complexity Poly(n^1). 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 Obtained the following overall complexity (w.r.t. the length of the input n): 8.35/4.94 8.35/4.94 Complexity: Poly(n^1) 8.35/4.94 8.35/4.94 Cpx degree: 1 8.35/4.94 8.35/4.94 Solved cost: 4+3*n 8.35/4.94 8.35/4.94 Rule cost: 1+3*C-3*B 8.35/4.94 8.35/4.94 Rule guard: [ B>=0 && 0>=1+free_1 && C>=1+B ] 8.35/4.94 8.35/4.94 8.35/4.94 8.35/4.94 WORST_CASE(Omega(n^1),?) 8.35/4.94 8.35/4.94 8.35/4.94 ---------------------------------------- 8.35/4.94 8.35/4.94 (2) 8.35/4.94 BOUNDS(n^1, INF) 8.35/4.97 EOF