296.59/291.57 KILLED 296.59/291.58 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 296.59/291.58 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 296.59/291.58 296.59/291.58 296.59/291.58 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, INF). 296.59/291.58 296.59/291.58 (0) CpxIntTrs 296.59/291.58 (1) Loat Proof [FINISHED, 895 ms] 296.59/291.58 (2) BOUNDS(1, INF) 296.59/291.58 296.59/291.58 296.59/291.58 ---------------------------------------- 296.59/291.58 296.59/291.58 (0) 296.59/291.58 Obligation: 296.59/291.58 Complexity Int TRS consisting of the following rules: 296.59/291.58 f15(A, B, C, D, E) -> Com_1(f16(A, B, C, D, E)) :|: A >= B + 1 296.59/291.58 f15(A, B, C, D, E) -> Com_1(f16(A, B, C, D, E)) :|: B >= 1 + A 296.59/291.58 f0(A, B, C, D, E) -> Com_1(f7(F, B, F, D, E)) :|: 0 >= F 296.59/291.58 f0(A, B, C, D, E) -> Com_1(f7(F, B, F, D, E)) :|: F >= 101 296.59/291.58 f0(A, B, C, D, E) -> Com_1(f15(F, 0, F, G, E)) :|: 100 >= F && F >= 1 296.59/291.58 f16(A, B, C, D, E) -> Com_1(f15(A, B + 1, C, D, E)) :|: TRUE 296.59/291.58 f23(A, B, C, D, E) -> Com_1(f23(A, B, C, D, E + 1)) :|: B >= E + 1 296.59/291.58 f23(A, B, C, D, E) -> Com_1(f7(A, B, C, D, E)) :|: E >= B 296.59/291.58 f15(A, B, C, D, E) -> Com_1(f23(A, A - 1, C, D, 0)) :|: A >= B && A <= B 296.59/291.58 f16(A, B, C, D, E) -> Com_1(f23(A, B - 1, C, D, 0)) :|: TRUE 296.59/291.58 296.59/291.58 The start-symbols are:[f0_5] 296.59/291.58 296.59/291.58 296.59/291.58 ---------------------------------------- 296.59/291.58 296.59/291.58 (1) Loat Proof (FINISHED) 296.59/291.58 296.59/291.58 296.59/291.58 ### Pre-processing the ITS problem ### 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Initial linear ITS problem 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 0: f15 -> f16 : [ A>=1+B ], cost: 1 296.59/291.58 296.59/291.58 1: f15 -> f16 : [ B>=1+A ], cost: 1 296.59/291.58 296.59/291.58 8: f15 -> f23 : B'=-1+A, E'=0, [ A==B ], cost: 1 296.59/291.58 296.59/291.58 2: f0 -> f7 : A'=free, C'=free, [ 0>=free ], cost: 1 296.59/291.58 296.59/291.58 3: f0 -> f7 : A'=free_1, C'=free_1, [ free_1>=101 ], cost: 1 296.59/291.58 296.59/291.58 4: f0 -> f15 : A'=free_2, B'=0, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1 296.59/291.58 296.59/291.58 5: f16 -> f15 : B'=1+B, [], cost: 1 296.59/291.58 296.59/291.58 9: f16 -> f23 : B'=-1+B, E'=0, [], cost: 1 296.59/291.58 296.59/291.58 6: f23 -> f23 : E'=1+E, [ B>=1+E ], cost: 1 296.59/291.58 296.59/291.58 7: f23 -> f7 : [ E>=B ], cost: 1 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Removed unreachable and leaf rules: 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 0: f15 -> f16 : [ A>=1+B ], cost: 1 296.59/291.58 296.59/291.58 1: f15 -> f16 : [ B>=1+A ], cost: 1 296.59/291.58 296.59/291.58 8: f15 -> f23 : B'=-1+A, E'=0, [ A==B ], cost: 1 296.59/291.58 296.59/291.58 4: f0 -> f15 : A'=free_2, B'=0, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1 296.59/291.58 296.59/291.58 5: f16 -> f15 : B'=1+B, [], cost: 1 296.59/291.58 296.59/291.58 9: f16 -> f23 : B'=-1+B, E'=0, [], cost: 1 296.59/291.58 296.59/291.58 6: f23 -> f23 : E'=1+E, [ B>=1+E ], cost: 1 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 ### Simplification by acceleration and chaining ### 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Accelerating simple loops of location 3. 296.59/291.58 296.59/291.58 Accelerating the following rules: 296.59/291.58 296.59/291.58 6: f23 -> f23 : E'=1+E, [ B>=1+E ], cost: 1 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Accelerated rule 6 with metering function -E+B, yielding the new rule 10. 296.59/291.58 296.59/291.58 Removing the simple loops: 6. 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Accelerated all simple loops using metering functions (where possible): 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 0: f15 -> f16 : [ A>=1+B ], cost: 1 296.59/291.58 296.59/291.58 1: f15 -> f16 : [ B>=1+A ], cost: 1 296.59/291.58 296.59/291.58 8: f15 -> f23 : B'=-1+A, E'=0, [ A==B ], cost: 1 296.59/291.58 296.59/291.58 4: f0 -> f15 : A'=free_2, B'=0, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1 296.59/291.58 296.59/291.58 5: f16 -> f15 : B'=1+B, [], cost: 1 296.59/291.58 296.59/291.58 9: f16 -> f23 : B'=-1+B, E'=0, [], cost: 1 296.59/291.58 296.59/291.58 10: f23 -> f23 : E'=B, [ B>=1+E ], cost: -E+B 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Chained accelerated rules (with incoming rules): 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 0: f15 -> f16 : [ A>=1+B ], cost: 1 296.59/291.58 296.59/291.58 1: f15 -> f16 : [ B>=1+A ], cost: 1 296.59/291.58 296.59/291.58 8: f15 -> f23 : B'=-1+A, E'=0, [ A==B ], cost: 1 296.59/291.58 296.59/291.58 11: f15 -> f23 : B'=-1+A, E'=-1+A, [ A==B && -1+A>=1 ], cost: A 296.59/291.58 296.59/291.58 4: f0 -> f15 : A'=free_2, B'=0, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1 296.59/291.58 296.59/291.58 5: f16 -> f15 : B'=1+B, [], cost: 1 296.59/291.58 296.59/291.58 9: f16 -> f23 : B'=-1+B, E'=0, [], cost: 1 296.59/291.58 296.59/291.58 12: f16 -> f23 : B'=-1+B, E'=-1+B, [ -1+B>=1 ], cost: B 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Removed unreachable locations (and leaf rules with constant cost): 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 0: f15 -> f16 : [ A>=1+B ], cost: 1 296.59/291.58 296.59/291.58 1: f15 -> f16 : [ B>=1+A ], cost: 1 296.59/291.58 296.59/291.58 11: f15 -> f23 : B'=-1+A, E'=-1+A, [ A==B && -1+A>=1 ], cost: A 296.59/291.58 296.59/291.58 4: f0 -> f15 : A'=free_2, B'=0, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1 296.59/291.58 296.59/291.58 5: f16 -> f15 : B'=1+B, [], cost: 1 296.59/291.58 296.59/291.58 12: f16 -> f23 : B'=-1+B, E'=-1+B, [ -1+B>=1 ], cost: B 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Eliminated locations (on tree-shaped paths): 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 11: f15 -> f23 : B'=-1+A, E'=-1+A, [ A==B && -1+A>=1 ], cost: A 296.59/291.58 296.59/291.58 13: f15 -> f15 : B'=1+B, [ A>=1+B ], cost: 2 296.59/291.58 296.59/291.58 14: f15 -> f23 : B'=-1+B, E'=-1+B, [ A>=1+B && -1+B>=1 ], cost: 1+B 296.59/291.58 296.59/291.58 15: f15 -> f15 : B'=1+B, [ B>=1+A ], cost: 2 296.59/291.58 296.59/291.58 16: f15 -> f23 : B'=-1+B, E'=-1+B, [ B>=1+A && -1+B>=1 ], cost: 1+B 296.59/291.58 296.59/291.58 4: f0 -> f15 : A'=free_2, B'=0, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Accelerating simple loops of location 0. 296.59/291.58 296.59/291.58 Accelerating the following rules: 296.59/291.58 296.59/291.58 13: f15 -> f15 : B'=1+B, [ A>=1+B ], cost: 2 296.59/291.58 296.59/291.58 15: f15 -> f15 : B'=1+B, [ B>=1+A ], cost: 2 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Accelerated rule 13 with metering function A-B, yielding the new rule 17. 296.59/291.58 296.59/291.58 Accelerated rule 15 with NONTERM, yielding the new rule 18. 296.59/291.58 296.59/291.58 Removing the simple loops: 13 15. 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Accelerated all simple loops using metering functions (where possible): 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 11: f15 -> f23 : B'=-1+A, E'=-1+A, [ A==B && -1+A>=1 ], cost: A 296.59/291.58 296.59/291.58 14: f15 -> f23 : B'=-1+B, E'=-1+B, [ A>=1+B && -1+B>=1 ], cost: 1+B 296.59/291.58 296.59/291.58 16: f15 -> f23 : B'=-1+B, E'=-1+B, [ B>=1+A && -1+B>=1 ], cost: 1+B 296.59/291.58 296.59/291.58 17: f15 -> f15 : B'=A, [ A>=1+B ], cost: 2*A-2*B 296.59/291.58 296.59/291.58 18: f15 -> [6] : [ B>=1+A ], cost: INF 296.59/291.58 296.59/291.58 4: f0 -> f15 : A'=free_2, B'=0, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Chained accelerated rules (with incoming rules): 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 11: f15 -> f23 : B'=-1+A, E'=-1+A, [ A==B && -1+A>=1 ], cost: A 296.59/291.58 296.59/291.58 14: f15 -> f23 : B'=-1+B, E'=-1+B, [ A>=1+B && -1+B>=1 ], cost: 1+B 296.59/291.58 296.59/291.58 16: f15 -> f23 : B'=-1+B, E'=-1+B, [ B>=1+A && -1+B>=1 ], cost: 1+B 296.59/291.58 296.59/291.58 4: f0 -> f15 : A'=free_2, B'=0, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1 296.59/291.58 296.59/291.58 19: f0 -> f15 : A'=free_2, B'=free_2, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1+2*free_2 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Removed unreachable locations (and leaf rules with constant cost): 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 11: f15 -> f23 : B'=-1+A, E'=-1+A, [ A==B && -1+A>=1 ], cost: A 296.59/291.58 296.59/291.58 14: f15 -> f23 : B'=-1+B, E'=-1+B, [ A>=1+B && -1+B>=1 ], cost: 1+B 296.59/291.58 296.59/291.58 16: f15 -> f23 : B'=-1+B, E'=-1+B, [ B>=1+A && -1+B>=1 ], cost: 1+B 296.59/291.58 296.59/291.58 4: f0 -> f15 : A'=free_2, B'=0, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1 296.59/291.58 296.59/291.58 19: f0 -> f15 : A'=free_2, B'=free_2, C'=free_2, D'=free_3, [ 100>=free_2 && free_2>=1 ], cost: 1+2*free_2 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Eliminated locations (on tree-shaped paths): 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 20: f0 -> f23 : A'=free_2, B'=-1+free_2, C'=free_2, D'=free_3, E'=-1+free_2, [ 100>=free_2 && -1+free_2>=1 ], cost: 1+3*free_2 296.59/291.58 296.59/291.58 21: f0 -> [7] : [ 100>=free_2 && free_2>=1 ], cost: 1+2*free_2 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 ### Computing asymptotic complexity ### 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Fully simplified ITS problem 296.59/291.58 296.59/291.58 Start location: f0 296.59/291.58 296.59/291.58 20: f0 -> f23 : A'=free_2, B'=-1+free_2, C'=free_2, D'=free_3, E'=-1+free_2, [ 100>=free_2 && -1+free_2>=1 ], cost: 1+3*free_2 296.59/291.58 296.59/291.58 21: f0 -> [7] : [ 100>=free_2 && free_2>=1 ], cost: 1+2*free_2 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Computing asymptotic complexity for rule 20 296.59/291.58 296.59/291.58 Could not solve the limit problem. 296.59/291.58 296.59/291.58 Resulting cost 0 has complexity: Unknown 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Computing asymptotic complexity for rule 21 296.59/291.58 296.59/291.58 Could not solve the limit problem. 296.59/291.58 296.59/291.58 Resulting cost 0 has complexity: Unknown 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 Obtained the following overall complexity (w.r.t. the length of the input n): 296.59/291.58 296.59/291.58 Complexity: Unknown 296.59/291.58 296.59/291.58 Cpx degree: ? 296.59/291.58 296.59/291.58 Solved cost: 0 296.59/291.58 296.59/291.58 Rule cost: 0 296.59/291.58 296.59/291.58 Rule guard: [] 296.59/291.58 296.59/291.58 296.59/291.58 296.59/291.58 WORST_CASE(Omega(0),?) 296.59/291.58 296.59/291.58 296.59/291.58 ---------------------------------------- 296.59/291.58 296.59/291.58 (2) 296.59/291.58 BOUNDS(1, INF) 296.59/291.59 EOF