Finding codes on infinite grids automatically
arXiv:2303.005572 citationsh-index: 12
Originality Synthesis-oriented
AI Analysis
This provides a tighter upper bound for a specific coding theory problem on a particular grid, which is an incremental improvement for researchers in that subfield.
The authors use automata theory and Karp's algorithm to find a new upper bound of 53/126 ≈ 0.4206 for the minimum density of an identifying code on the infinite hexagonal grid, improving from the previous bound of 3/7 ≈ 0.4286.
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$.