A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Finding Codes on Infinite Grids Automatically
Tekijät: Salo, Ville; Törmä, Ilkka
Kustantaja: IOS Press BV
Julkaisuvuosi: 2024
Journal: Fundamenta Informaticae
Tietokannassa oleva lehden nimi: Fundamenta Informaticae
Vuosikerta: 191
Numero: 3-4
Aloitussivu: 331
Lopetussivu: 349
eISSN: 1875-8681
DOI: https://doi.org/10.3233/FI-242186
Verkko-osoite: https://doi.org/10.3233/FI-242186
Rinnakkaistallenteen osoite: https://arxiv.org/pdf/2303.00557
Preprintin osoite: https://arxiv.org/abs/2303.00557
Tiivistelmä
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.
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.
Julkaisussa olevat rahoitustiedot:
Supported by the Academy of Finland under grant 346566.