Ville Salo ; Ilkka Törmä - Finding codes on infinite grids automatically

fi:11012 - Fundamenta Informaticae, November 10, 2024, Volume 191, Issues 3-4: Iiro Honkala's 60 Birthday - https://doi.org/10.46298/fi.11012
Finding codes on infinite grids automaticallyArticle

Authors: Ville Salo ; Ilkka Törmä

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

Comment: 19 pages, 5 figures

https://doi.org/10.46298/fi.11012
Source: arXiv.org:2303.00557
Volume: Volume 191, Issues 3-4: Iiro Honkala's 60 Birthday
Published on: November 10, 2024
Accepted on: October 26, 2023
Submitted on: March 2, 2023
Keywords: Mathematics - Combinatorics, Computer Science - Discrete Mathematics, Computer Science - Formal Languages and Automata Theory, Mathematics - Dynamical Systems, G.2.1
Licence: arXiv.org - Non-exclusive license to distribute

Share and export

Consultation statistics

This page has been seen 289 times.
This article's PDF has been downloaded 195 times.