On Perfect Coverings of Two-Dimensional Grids

No Thumbnail Available
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
Date
2022
Major/Subject
Mcode
Degree programme
Language
en
Pages
12
152-163
Series
Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volume 13257 LNCS
Abstract
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.
Description
Publisher Copyright: © 2022, Springer Nature Switzerland AG.
Keywords
Formal power series, Laurent polynomials, Perfect multiple coverings, Periodicity, Two-dimensional configurations
Other note
Citation
Heikkilä , E , Herva , P & Kari , J 2022 , On Perfect Coverings of Two-Dimensional Grids . in V Diekert & M Volkov (eds) , Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , vol. 13257 LNCS , Springer , pp. 152-163 , International Conference on Developments in Language Theory , Tampa , Florida , United States , 09/05/2022 . https://doi.org/10.1007/978-3-031-05578-2_12