Finding codes on infinite grids automatically

Abstract

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\approx 0.4206$ for the minimum density of an identifying code on the infinite hexagonal grid, down from the previous record of $3/7\approx 0.4286$.

arXiv comment19 pages, 5 figures