Finding Codes on Infinite Grids Automatically

: Salo, Ville; Törmä, Ilkka

Publisher: IOS Press BV

: 2024

: Fundamenta Informaticae

: 191

: 3-4

: 331

: 349

: 1875-8681

DOI: https://doi.org/10.3233/FI-242186

: https://doi.org/10.3233/FI-242186

: https://arxiv.org/pdf/2303.00557

: https://arxiv.org/abs/2303.00557

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.

:
Supported by the Academy of Finland under grant 346566.