66.68/38.53 MAYBE 66.68/38.54 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 66.68/38.54 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 66.68/38.54 66.68/38.54 66.68/38.54 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, INF). 66.68/38.54 66.68/38.54 (0) CpxIntTrs 66.68/38.54 (1) Loat Proof [FINISHED, 17.8 s] 66.68/38.54 (2) BOUNDS(1, INF) 66.68/38.54 66.68/38.54 66.68/38.54 ---------------------------------------- 66.68/38.54 66.68/38.54 (0) 66.68/38.54 Obligation: 66.68/38.54 Complexity Int TRS consisting of the following rules: 66.68/38.54 f5(A, B, C, D, E, F) -> Com_1(f7(A, B, C, D, E, F)) :|: 0 >= A 66.68/38.54 f5(A, B, C, D, E, F) -> Com_1(f7(A, B, C, D, E, F)) :|: A >= 2 66.68/38.54 f7(A, B, C, D, E, F) -> Com_1(f9(A, 0, C, D, E, F)) :|: B >= 0 && B <= 0 66.68/38.54 f16(A, B, C, D, E, F) -> Com_1(f5(A, B, C, G, E, F)) :|: 255 >= C 66.68/38.54 f25(A, B, C, D, E, F) -> Com_1(f5(A, B, C, G, E, F)) :|: C >= 0 66.68/38.54 f0(A, B, C, D, E, F) -> Com_1(f5(4, 0, C, G, 0, F)) :|: TRUE 66.68/38.54 f7(A, B, C, D, E, F) -> Com_1(f9(A - 1, B, C, D, E, F)) :|: 0 >= B + 1 66.68/38.54 f7(A, B, C, D, E, F) -> Com_1(f9(A - 1, B, C, D, E, F)) :|: B >= 1 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f16(A, B, C + A, D, 2, F)) :|: 0 >= E && D >= 1 + F 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f16(A, B, C + A, D, 2, F)) :|: E >= 2 && D >= 1 + F 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f16(A, B, C + A, D, 2, F)) :|: 0 >= B + 1 && D >= 1 + F && E >= 1 && E <= 1 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f16(A, B, C + A, D, 2, F)) :|: B >= 1 && D >= 1 + F && E >= 1 && E <= 1 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f16(A - 1, 1, C + A - 1, D, 2, F)) :|: D >= 1 + F && B >= 0 && B <= 0 && E >= 1 && E <= 1 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f25(A, B, C - A, D, 1, F)) :|: 1 >= E && F >= D + 1 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f25(A, B, C - A, D, 1, F)) :|: E >= 3 && F >= D + 1 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f25(A, B, C - A, D, 1, F)) :|: 0 >= B + 1 && F >= D + 1 && E >= 2 && E <= 2 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f25(A, B, C - A, D, 1, F)) :|: B >= 1 && F >= D + 1 && E >= 2 && E <= 2 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f25(A - 1, 1, C - A + 1, D, 1, F)) :|: F >= D + 1 && B >= 0 && B <= 0 && E >= 2 && E <= 2 66.68/38.54 f5(A, B, C, D, E, F) -> Com_1(f30(1, B, C, D, E, F)) :|: A >= 1 && A <= 1 66.68/38.54 f16(A, B, C, D, E, F) -> Com_1(f30(A, B, C, D, E, F)) :|: C >= 256 66.68/38.54 f25(A, B, C, D, E, F) -> Com_1(f30(A, B, C, D, E, F)) :|: 0 >= C + 1 66.68/38.54 f9(A, B, C, D, E, F) -> Com_1(f30(A, B, C, D, E, D)) :|: D >= F && D <= F 66.68/38.54 66.68/38.54 The start-symbols are:[f0_6] 66.68/38.54 66.68/38.54 66.68/38.54 ---------------------------------------- 66.68/38.54 66.68/38.54 (1) Loat Proof (FINISHED) 66.68/38.54 66.68/38.54 66.68/38.54 ### Pre-processing the ITS problem ### 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Initial linear ITS problem 66.68/38.54 66.68/38.54 Start location: f0 66.68/38.54 66.68/38.54 0: f5 -> f7 : [ 0>=A ], cost: 1 66.68/38.54 66.68/38.54 1: f5 -> f7 : [ A>=2 ], cost: 1 66.68/38.54 66.68/38.54 18: f5 -> f30 : A'=1, [ A==1 ], cost: 1 66.68/38.54 66.68/38.54 2: f7 -> f9 : B'=0, [ B==0 ], cost: 1 66.68/38.54 66.68/38.54 6: f7 -> f9 : A'=-1+A, [ 0>=1+B ], cost: 1 66.68/38.54 66.68/38.54 7: f7 -> f9 : A'=-1+A, [ B>=1 ], cost: 1 66.68/38.54 66.68/38.54 3: f16 -> f5 : D'=free, [ 255>=C ], cost: 1 66.68/38.54 66.68/38.54 19: f16 -> f30 : [ C>=256 ], cost: 1 66.68/38.54 66.68/38.54 4: f25 -> f5 : D'=free_1, [ C>=0 ], cost: 1 66.68/38.54 66.68/38.54 20: f25 -> f30 : [ 0>=1+C ], cost: 1 66.68/38.54 66.68/38.54 5: f0 -> f5 : A'=4, B'=0, D'=free_2, E'=0, [], cost: 1 66.68/38.54 66.68/38.54 8: f9 -> f16 : C'=C+A, E'=2, [ 0>=E && D>=1+F ], cost: 1 66.68/38.54 66.68/38.54 9: f9 -> f16 : C'=C+A, E'=2, [ E>=2 && D>=1+F ], cost: 1 66.68/38.54 66.68/38.54 10: f9 -> f16 : C'=C+A, E'=2, [ 0>=1+B && D>=1+F && E==1 ], cost: 1 66.68/38.54 66.68/38.54 11: f9 -> f16 : C'=C+A, E'=2, [ B>=1 && D>=1+F && E==1 ], cost: 1 66.68/38.54 66.68/38.54 12: f9 -> f16 : A'=-1+A, B'=1, C'=-1+C+A, E'=2, [ D>=1+F && B==0 && E==1 ], cost: 1 66.68/38.54 66.68/38.54 13: f9 -> f25 : C'=C-A, E'=1, [ 1>=E && F>=1+D ], cost: 1 66.68/38.54 66.68/38.54 14: f9 -> f25 : C'=C-A, E'=1, [ E>=3 && F>=1+D ], cost: 1 66.68/38.54 66.68/38.54 15: f9 -> f25 : C'=C-A, E'=1, [ 0>=1+B && F>=1+D && E==2 ], cost: 1 66.68/38.54 66.68/38.54 16: f9 -> f25 : C'=C-A, E'=1, [ B>=1 && F>=1+D && E==2 ], cost: 1 66.68/38.54 66.68/38.54 17: f9 -> f25 : A'=-1+A, B'=1, C'=1+C-A, E'=1, [ F>=1+D && B==0 && E==2 ], cost: 1 66.68/38.54 66.68/38.54 21: f9 -> f30 : F'=D, [ D==F ], cost: 1 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Removed unreachable and leaf rules: 66.68/38.54 66.68/38.54 Start location: f0 66.68/38.54 66.68/38.54 0: f5 -> f7 : [ 0>=A ], cost: 1 66.68/38.54 66.68/38.54 1: f5 -> f7 : [ A>=2 ], cost: 1 66.68/38.54 66.68/38.54 2: f7 -> f9 : B'=0, [ B==0 ], cost: 1 66.68/38.54 66.68/38.54 6: f7 -> f9 : A'=-1+A, [ 0>=1+B ], cost: 1 66.68/38.54 66.68/38.54 7: f7 -> f9 : A'=-1+A, [ B>=1 ], cost: 1 66.68/38.54 66.68/38.54 3: f16 -> f5 : D'=free, [ 255>=C ], cost: 1 66.68/38.54 66.68/38.54 4: f25 -> f5 : D'=free_1, [ C>=0 ], cost: 1 66.68/38.54 66.68/38.54 5: f0 -> f5 : A'=4, B'=0, D'=free_2, E'=0, [], cost: 1 66.68/38.54 66.68/38.54 8: f9 -> f16 : C'=C+A, E'=2, [ 0>=E && D>=1+F ], cost: 1 66.68/38.54 66.68/38.54 9: f9 -> f16 : C'=C+A, E'=2, [ E>=2 && D>=1+F ], cost: 1 66.68/38.54 66.68/38.54 10: f9 -> f16 : C'=C+A, E'=2, [ 0>=1+B && D>=1+F && E==1 ], cost: 1 66.68/38.54 66.68/38.54 11: f9 -> f16 : C'=C+A, E'=2, [ B>=1 && D>=1+F && E==1 ], cost: 1 66.68/38.54 66.68/38.54 12: f9 -> f16 : A'=-1+A, B'=1, C'=-1+C+A, E'=2, [ D>=1+F && B==0 && E==1 ], cost: 1 66.68/38.54 66.68/38.54 13: f9 -> f25 : C'=C-A, E'=1, [ 1>=E && F>=1+D ], cost: 1 66.68/38.54 66.68/38.54 14: f9 -> f25 : C'=C-A, E'=1, [ E>=3 && F>=1+D ], cost: 1 66.68/38.54 66.68/38.54 15: f9 -> f25 : C'=C-A, E'=1, [ 0>=1+B && F>=1+D && E==2 ], cost: 1 66.68/38.54 66.68/38.54 16: f9 -> f25 : C'=C-A, E'=1, [ B>=1 && F>=1+D && E==2 ], cost: 1 66.68/38.54 66.68/38.54 17: f9 -> f25 : A'=-1+A, B'=1, C'=1+C-A, E'=1, [ F>=1+D && B==0 && E==2 ], cost: 1 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 ### Simplification by acceleration and chaining ### 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Eliminated locations (on tree-shaped paths): 66.68/38.54 66.68/38.54 Start location: f0 66.68/38.54 66.68/38.54 22: f5 -> f9 : B'=0, [ 0>=A && B==0 ], cost: 2 66.68/38.54 66.68/38.54 23: f5 -> f9 : A'=-1+A, [ 0>=A && 0>=1+B ], cost: 2 66.68/38.54 66.68/38.54 24: f5 -> f9 : A'=-1+A, [ 0>=A && B>=1 ], cost: 2 66.68/38.54 66.68/38.54 25: f5 -> f9 : B'=0, [ A>=2 && B==0 ], cost: 2 66.68/38.54 66.68/38.54 26: f5 -> f9 : A'=-1+A, [ A>=2 && 0>=1+B ], cost: 2 66.68/38.54 66.68/38.54 27: f5 -> f9 : A'=-1+A, [ A>=2 && B>=1 ], cost: 2 66.68/38.54 66.68/38.54 5: f0 -> f5 : A'=4, B'=0, D'=free_2, E'=0, [], cost: 1 66.68/38.54 66.68/38.54 28: f9 -> f5 : C'=C+A, D'=free, E'=2, [ 0>=E && D>=1+F && 255>=C+A ], cost: 2 66.68/38.54 66.68/38.54 29: f9 -> f5 : C'=C+A, D'=free, E'=2, [ E>=2 && D>=1+F && 255>=C+A ], cost: 2 66.68/38.54 66.68/38.54 30: f9 -> f5 : C'=C+A, D'=free, E'=2, [ 0>=1+B && D>=1+F && E==1 && 255>=C+A ], cost: 2 66.68/38.54 66.68/38.54 31: f9 -> f5 : C'=C+A, D'=free, E'=2, [ B>=1 && D>=1+F && E==1 && 255>=C+A ], cost: 2 66.68/38.54 66.68/38.54 32: f9 -> f5 : A'=-1+A, B'=1, C'=-1+C+A, D'=free, E'=2, [ D>=1+F && B==0 && E==1 && 255>=-1+C+A ], cost: 2 66.68/38.54 66.68/38.54 33: f9 -> f5 : C'=C-A, D'=free_1, E'=1, [ 1>=E && F>=1+D && C-A>=0 ], cost: 2 66.68/38.54 66.68/38.54 34: f9 -> f5 : C'=C-A, D'=free_1, E'=1, [ E>=3 && F>=1+D && C-A>=0 ], cost: 2 66.68/38.54 66.68/38.54 35: f9 -> f5 : C'=C-A, D'=free_1, E'=1, [ 0>=1+B && F>=1+D && E==2 && C-A>=0 ], cost: 2 66.68/38.54 66.68/38.54 36: f9 -> f5 : C'=C-A, D'=free_1, E'=1, [ B>=1 && F>=1+D && E==2 && C-A>=0 ], cost: 2 66.68/38.54 66.68/38.54 37: f9 -> f5 : A'=-1+A, B'=1, C'=1+C-A, D'=free_1, E'=1, [ F>=1+D && B==0 && E==2 && 1+C-A>=0 ], cost: 2 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Eliminated locations (on tree-shaped paths): 66.68/38.54 66.68/38.54 Start location: f0 66.68/38.54 66.68/38.54 38: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ 0>=A && B==0 && 0>=E && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 39: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ 0>=A && B==0 && E>=2 && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 40: f5 -> f5 : A'=-1+A, B'=1, C'=-1+C+A, D'=free, E'=2, [ 0>=A && B==0 && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 41: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ 0>=A && B==0 && 1>=E && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 42: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ 0>=A && B==0 && E>=3 && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 43: f5 -> f5 : A'=-1+A, B'=1, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && B==0 && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 44: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && 0>=1+B && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 45: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && 0>=1+B && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 46: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && 0>=1+B && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 47: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && 0>=1+B && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 48: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && 0>=1+B && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 49: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && 0>=1+B && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 50: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && B>=1 && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 51: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && B>=1 && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 52: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && B>=1 && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 53: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && B>=1 && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 54: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && B>=1 && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 55: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && B>=1 && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 56: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ A>=2 && B==0 && 0>=E && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 57: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ A>=2 && B==0 && E>=2 && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 58: f5 -> f5 : A'=-1+A, B'=1, C'=-1+C+A, D'=free, E'=2, [ A>=2 && B==0 && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 59: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ A>=2 && B==0 && 1>=E && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 60: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ A>=2 && B==0 && E>=3 && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 61: f5 -> f5 : A'=-1+A, B'=1, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && B==0 && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 62: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && 0>=1+B && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 63: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && 0>=1+B && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 64: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && 0>=1+B && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 65: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && 0>=1+B && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 66: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && 0>=1+B && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 67: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && 0>=1+B && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 68: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && B>=1 && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 69: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && B>=1 && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 70: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && B>=1 && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 71: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && B>=1 && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 72: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && B>=1 && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 73: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && B>=1 && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 5: f0 -> f5 : A'=4, B'=0, D'=free_2, E'=0, [], cost: 1 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Accelerating simple loops of location 0. 66.68/38.54 66.68/38.54 Accelerating the following rules: 66.68/38.54 66.68/38.54 38: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ 0>=A && B==0 && 0>=E && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 39: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ 0>=A && B==0 && E>=2 && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 40: f5 -> f5 : A'=-1+A, B'=1, C'=-1+C+A, D'=free, E'=2, [ 0>=A && B==0 && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 41: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ 0>=A && B==0 && 1>=E && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 42: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ 0>=A && B==0 && E>=3 && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 43: f5 -> f5 : A'=-1+A, B'=1, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && B==0 && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 44: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && 0>=1+B && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 45: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && 0>=1+B && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 46: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && 0>=1+B && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 47: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && 0>=1+B && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 48: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && 0>=1+B && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 49: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && 0>=1+B && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 50: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && B>=1 && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 51: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && B>=1 && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 52: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && B>=1 && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 53: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && B>=1 && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 54: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && B>=1 && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 55: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && B>=1 && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 56: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ A>=2 && B==0 && 0>=E && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 57: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ A>=2 && B==0 && E>=2 && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 58: f5 -> f5 : A'=-1+A, B'=1, C'=-1+C+A, D'=free, E'=2, [ A>=2 && B==0 && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 59: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ A>=2 && B==0 && 1>=E && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 60: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ A>=2 && B==0 && E>=3 && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 61: f5 -> f5 : A'=-1+A, B'=1, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && B==0 && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 62: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && 0>=1+B && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 63: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && 0>=1+B && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 64: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && 0>=1+B && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 65: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && 0>=1+B && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 66: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && 0>=1+B && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 67: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && 0>=1+B && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 68: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && B>=1 && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 69: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && B>=1 && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 70: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && B>=1 && D>=1+F && E==1 && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 71: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && B>=1 && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 72: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && B>=1 && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 73: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && B>=1 && F>=1+D && E==2 && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Found no metering function for rule 38. 66.68/38.54 66.68/38.54 Accelerated rule 39 with NONTERM (after strengthening guard), yielding the new rule 74. 66.68/38.54 66.68/38.54 Accelerated rule 40 with metering function meter (where 2*meter==1-E-B), yielding the new rule 75. 66.68/38.54 66.68/38.54 Accelerated rule 41 with NONTERM (after strengthening guard), yielding the new rule 76. 66.68/38.54 66.68/38.54 Found no metering function for rule 42. 66.68/38.54 66.68/38.54 Accelerated rule 43 with metering function meter_1 (where 2*meter_1==-2+E-B), yielding the new rule 77. 66.68/38.54 66.68/38.54 Found no metering function for rule 44. 66.68/38.54 66.68/38.54 Accelerated rule 45 with NONTERM (after strengthening guard), yielding the new rule 78. 66.68/38.54 66.68/38.54 Accelerated rule 46 with metering function 1-E, yielding the new rule 79. 66.68/38.54 66.68/38.54 Accelerated rule 47 with NONTERM (after strengthening guard), yielding the new rule 80. 66.68/38.54 66.68/38.54 Found no metering function for rule 48. 66.68/38.54 66.68/38.54 Accelerated rule 49 with metering function -2+E, yielding the new rule 81. 66.68/38.54 66.68/38.54 Found no metering function for rule 50. 66.68/38.54 66.68/38.54 Accelerated rule 51 with NONTERM (after strengthening guard), yielding the new rule 82. 66.68/38.54 66.68/38.54 Accelerated rule 52 with metering function 1-E, yielding the new rule 83. 66.68/38.54 66.68/38.54 Accelerated rule 53 with NONTERM (after strengthening guard), yielding the new rule 84. 66.68/38.54 66.68/38.54 Found no metering function for rule 54. 66.68/38.54 66.68/38.54 Accelerated rule 55 with metering function -2+E, yielding the new rule 85. 66.68/38.54 66.68/38.54 Found no metering function for rule 56. 66.68/38.54 66.68/38.54 Found no metering function for rule 57. 66.68/38.54 66.68/38.54 Accelerated rule 58 with metering function meter_2 (where 2*meter_2==1-E-B), yielding the new rule 86. 66.68/38.54 66.68/38.54 Found no metering function for rule 59. 66.68/38.54 66.68/38.54 Found no metering function for rule 60. 66.68/38.54 66.68/38.54 Accelerated rule 61 with metering function meter_3 (where 2*meter_3==-2+E-B), yielding the new rule 87. 66.68/38.54 66.68/38.54 Found no metering function for rule 62. 66.68/38.54 66.68/38.54 Found no metering function for rule 63. 66.68/38.54 66.68/38.54 Accelerated rule 64 with metering function 1-E, yielding the new rule 88. 66.68/38.54 66.68/38.54 Found no metering function for rule 65. 66.68/38.54 66.68/38.54 Found no metering function for rule 66. 66.68/38.54 66.68/38.54 Accelerated rule 67 with metering function -2+E, yielding the new rule 89. 66.68/38.54 66.68/38.54 Found no metering function for rule 68. 66.68/38.54 66.68/38.54 Found no metering function for rule 69. 66.68/38.54 66.68/38.54 Accelerated rule 70 with metering function 1-E, yielding the new rule 90. 66.68/38.54 66.68/38.54 Found no metering function for rule 71. 66.68/38.54 66.68/38.54 Found no metering function for rule 72. 66.68/38.54 66.68/38.54 Accelerated rule 73 with metering function -2+E, yielding the new rule 91. 66.68/38.54 66.68/38.54 Removing the simple loops: 40 43 46 49 52 55 58 61 64 67 70 73. 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Accelerated all simple loops using metering functions (where possible): 66.68/38.54 66.68/38.54 Start location: f0 66.68/38.54 66.68/38.54 38: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ 0>=A && B==0 && 0>=E && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 39: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ 0>=A && B==0 && E>=2 && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 41: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ 0>=A && B==0 && 1>=E && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 42: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ 0>=A && B==0 && E>=3 && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 44: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && 0>=1+B && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 45: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && 0>=1+B && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 47: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && 0>=1+B && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 48: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && 0>=1+B && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 50: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && B>=1 && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 51: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ 0>=A && B>=1 && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 53: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && B>=1 && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 54: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ 0>=A && B>=1 && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 56: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ A>=2 && B==0 && 0>=E && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 57: f5 -> f5 : B'=0, C'=C+A, D'=free, E'=2, [ A>=2 && B==0 && E>=2 && D>=1+F && 255>=C+A ], cost: 4 66.68/38.54 66.68/38.54 59: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ A>=2 && B==0 && 1>=E && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 60: f5 -> f5 : B'=0, C'=C-A, D'=free_1, E'=1, [ A>=2 && B==0 && E>=3 && F>=1+D && C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 62: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && 0>=1+B && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 63: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && 0>=1+B && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 65: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && 0>=1+B && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 66: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && 0>=1+B && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 68: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && B>=1 && 0>=E && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 69: f5 -> f5 : A'=-1+A, C'=-1+C+A, D'=free, E'=2, [ A>=2 && B>=1 && E>=2 && D>=1+F && 255>=-1+C+A ], cost: 4 66.68/38.54 66.68/38.54 71: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && B>=1 && 1>=E && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 72: f5 -> f5 : A'=-1+A, C'=1+C-A, D'=free_1, E'=1, [ A>=2 && B>=1 && E>=3 && F>=1+D && 1+C-A>=0 ], cost: 4 66.68/38.54 66.68/38.54 74: f5 -> [7] : [ 0>=A && B==0 && E>=2 && D>=1+F && 255>=C+A && free>=1+F ], cost: INF 66.68/38.54 66.68/38.54 75: f5 -> f5 : A'=-meter+A, B'=1, C'=1+meter*A-3/2*meter+C-1/2*meter^2, D'=free, E'=2, [ 0>=A && B==0 && D>=1+F && E==1 && 255>=-1+C+A && 2*meter==1-E-B && meter>=1 ], cost: 4*meter 66.68/38.54 66.68/38.54 76: f5 -> [7] : [ 0>=A && B==0 && 1>=E && F>=1+D && C-A>=0 && F>=1+free_1 ], cost: INF 66.68/38.54 66.68/38.54 77: f5 -> f5 : A'=-meter_1+A, B'=1, C'=-1+C+1/2*meter_1^2-meter_1*A+3/2*meter_1, D'=free_1, E'=1, [ 0>=A && B==0 && F>=1+D && E==2 && 1+C-A>=0 && 2*meter_1==-2+E-B && meter_1>=1 ], cost: 4*meter_1 66.68/38.54 66.68/38.54 78: f5 -> [7] : [ 0>=A && 0>=1+B && E>=2 && D>=1+F && 255>=-1+C+A && free>=1+F ], cost: INF 66.68/38.54 66.68/38.54 79: f5 -> f5 : A'=-1+A+E, C'=-1/2+C-A*(-1+E)+3/2*E-1/2*(-1+E)^2, D'=free, E'=2, [ 0>=A && 0>=1+B && D>=1+F && E==1 && 255>=-1+C+A && 1-E>=1 ], cost: 4-4*E 66.68/38.54 66.68/38.54 80: f5 -> [7] : [ 0>=A && 0>=1+B && 1>=E && F>=1+D && 1+C-A>=0 && F>=1+free_1 ], cost: INF 66.68/38.54 66.68/38.54 81: f5 -> f5 : A'=2+A-E, C'=-4+1/2*(-2+E)^2+C-(-2+E)*A+3/2*E, D'=free_1, E'=1, [ 0>=A && 0>=1+B && F>=1+D && E==2 && 1+C-A>=0 && -2+E>=1 ], cost: -8+4*E 66.68/38.54 66.68/38.54 82: f5 -> [7] : [ 0>=A && B>=1 && E>=2 && D>=1+F && 255>=-1+C+A && free>=1+F ], cost: INF 66.68/38.54 66.68/38.54 83: f5 -> f5 : A'=-1+A+E, C'=-1/2+C-A*(-1+E)+3/2*E-1/2*(-1+E)^2, D'=free, E'=2, [ 0>=A && B>=1 && D>=1+F && E==1 && 255>=-1+C+A && 1-E>=1 ], cost: 4-4*E 66.68/38.54 66.68/38.54 84: f5 -> [7] : [ 0>=A && B>=1 && 1>=E && F>=1+D && 1+C-A>=0 && F>=1+free_1 ], cost: INF 66.68/38.54 66.68/38.54 85: f5 -> f5 : A'=2+A-E, C'=-4+1/2*(-2+E)^2+C-(-2+E)*A+3/2*E, D'=free_1, E'=1, [ 0>=A && B>=1 && F>=1+D && E==2 && 1+C-A>=0 && -2+E>=1 ], cost: -8+4*E 66.68/38.54 66.68/38.54 86: f5 -> f5 : A'=-meter_2+A, B'=1, C'=1+C+meter_2*A-3/2*meter_2-1/2*meter_2^2, D'=free, E'=2, [ A>=2 && B==0 && D>=1+F && E==1 && 255>=-1+C+A && 2*meter_2==1-E-B && meter_2>=1 ], cost: 4*meter_2 66.68/38.54 66.68/38.54 87: f5 -> f5 : A'=-meter_3+A, B'=1, C'=-1-meter_3*A+C+1/2*meter_3^2+3/2*meter_3, D'=free_1, E'=1, [ A>=2 && B==0 && F>=1+D && E==2 && 1+C-A>=0 && 2*meter_3==-2+E-B && meter_3>=1 ], cost: 4*meter_3 66.68/38.54 66.68/38.54 88: f5 -> f5 : A'=-1+A+E, C'=-1/2+C-A*(-1+E)+3/2*E-1/2*(-1+E)^2, D'=free, E'=2, [ A>=2 && 0>=1+B && D>=1+F && E==1 && 255>=-1+C+A && 1-E>=1 ], cost: 4-4*E 66.68/38.54 66.68/38.54 89: f5 -> f5 : A'=2+A-E, C'=-4+1/2*(-2+E)^2+C-(-2+E)*A+3/2*E, D'=free_1, E'=1, [ A>=2 && 0>=1+B && F>=1+D && E==2 && 1+C-A>=0 && -2+E>=1 ], cost: -8+4*E 66.68/38.54 66.68/38.54 90: f5 -> f5 : A'=-1+A+E, C'=-1/2+C-A*(-1+E)+3/2*E-1/2*(-1+E)^2, D'=free, E'=2, [ A>=2 && B>=1 && D>=1+F && E==1 && 255>=-1+C+A && 1-E>=1 ], cost: 4-4*E 66.68/38.54 66.68/38.54 91: f5 -> f5 : A'=2+A-E, C'=-4+1/2*(-2+E)^2+C-(-2+E)*A+3/2*E, D'=free_1, E'=1, [ A>=2 && B>=1 && F>=1+D && E==2 && 1+C-A>=0 && -2+E>=1 ], cost: -8+4*E 66.68/38.54 66.68/38.54 5: f0 -> f5 : A'=4, B'=0, D'=free_2, E'=0, [], cost: 1 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Chained accelerated rules (with incoming rules): 66.68/38.54 66.68/38.54 Start location: f0 66.68/38.54 66.68/38.54 5: f0 -> f5 : A'=4, B'=0, D'=free_2, E'=0, [], cost: 1 66.68/38.54 66.68/38.54 92: f0 -> f5 : A'=4, B'=0, C'=4+C, D'=free, E'=2, [ 255>=4+C ], cost: 5 66.68/38.54 66.68/38.54 93: f0 -> f5 : A'=4, B'=0, C'=-4+C, D'=free_1, E'=1, [ -4+C>=0 ], cost: 5 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Removed unreachable locations (and leaf rules with constant cost): 66.68/38.54 66.68/38.54 Start location: f0 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 ### Computing asymptotic complexity ### 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Fully simplified ITS problem 66.68/38.54 66.68/38.54 Start location: f0 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 Obtained the following overall complexity (w.r.t. the length of the input n): 66.68/38.54 66.68/38.54 Complexity: Unknown 66.68/38.54 66.68/38.54 Cpx degree: ? 66.68/38.54 66.68/38.54 Solved cost: 0 66.68/38.54 66.68/38.54 Rule cost: 0 66.68/38.54 66.68/38.54 Rule guard: [] 66.68/38.54 66.68/38.54 66.68/38.54 66.68/38.54 WORST_CASE(Omega(0),?) 66.68/38.54 66.68/38.54 66.68/38.54 ---------------------------------------- 66.68/38.54 66.68/38.54 (2) 66.68/38.54 BOUNDS(1, INF) 66.68/38.55 EOF