A4 Refereed article in a conference publication
On Perfect Coverings of Two-Dimensional Grids
Authors: Heikkilä Elias, Herva Pyry, Kari Jarkko
Editors: Volker Diekert, Mikhail Volkov
Conference name: International Conference on Developments in Language Theory
Publishing place: Cham
Publication year: 2022
Journal: Lecture Notes in Computer Science
Book title : Developments in Language Theory: 26th International Conference, DLT 2022, Tampa, FL, USA, May 9–13, 2022, Proceedings
Series title: Lecture Notes in Computer Science
Volume: 13257
First page : 152
Last page: 163
ISBN: 978-3-031-05577-5
eISBN: 978-3-031-05578-2
ISSN: 0302-9743
eISSN: 1611-3349
DOI: https://doi.org/10.1007/978-3-031-05578-2_12
Web address : https://link.springer.com/chapter/10.1007/978-3-031-05578-2_12
Preprint address: https://arxiv.org/abs/2301.04987
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.