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