Finding codes on infinite grids automatically

03/01/2023
by   Ville Salo, et al.
0

We apply automata theory and Karp's minimum mean weight cycle algorithm to minimum density problems in coding theory. Using this method, we find the new upper bound 53/126 ≈ 0.4206 for the minimum density of an identifying code on the infinite hexagonal grid, down from the previous record of 3/7 ≈ 0.4286.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset