A4 Vertaisarvioitu artikkeli konferenssijulkaisussa

On Perfect Coverings of Two-Dimensional Grids




TekijätHeikkilä Elias, Herva Pyry, Kari Jarkko

ToimittajaVolker Diekert, Mikhail Volkov

Konferenssin vakiintunut nimiInternational Conference on Developments in Language Theory

KustannuspaikkaCham

Julkaisuvuosi2022

JournalLecture Notes in Computer Science

Kokoomateoksen nimiDevelopments in Language Theory: 26th International Conference, DLT 2022, Tampa, FL, USA, May 9–13, 2022, Proceedings

Sarjan nimiLecture Notes in Computer Science

Vuosikerta13257

Aloitussivu152

Lopetussivu163

ISBN978-3-031-05577-5

eISBN978-3-031-05578-2

ISSN0302-9743

eISSN1611-3349

DOIhttps://doi.org/10.1007/978-3-031-05578-2_12

Verkko-osoitehttps://link.springer.com/chapter/10.1007/978-3-031-05578-2_12

Preprintin osoitehttps://arxiv.org/abs/2301.04987


Tiivistelmä

We study perfect multiple coverings in translation invariant graphs with vertex set Z2 using an algebraic approach. In this approach we consider any such covering as a two-dimensional binary configuration which we then express as a two-variate formal power series. Using known results, we conclude that any perfect multiple covering has a non-trivial periodizer, that is, there exists a non-zero polynomial whose formal product with the power series presenting the covering is a two-periodic configuration. If a non-trivial periodizer has line polynomial factors in at most one direction, then the configuration is known to be periodic. Using this result we find many setups where perfect multiple coverings of infinite grids are necessarily periodic. We also consider some algorithmic questions on finding perfect multiple coverings.



Last updated on 2024-26-11 at 20:44