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

    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 166 times.
    This article's PDF has been downloaded 136 times.