A1 Refereed original research article in a scientific journal

Finding Codes on Infinite Grids Automatically



Authors: Salo, Ville; Törmä, Ilkka

Publisher: IOS Press BV

Publication year: 2024

Journal: Fundamenta Informaticae

Journal name in source: Fundamenta Informaticae

Volume: 191

Issue: 3-4

First page : 331

Last page: 349

eISSN: 1875-8681

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

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

Self-archived copy’s web address: https://arxiv.org/pdf/2303.00557

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


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 ≈ 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.


Funding information in the publication: 
Supported by the Academy of Finland under grant 346566.


Last updated on 2025-03-04 at 13:58