On Perfect Coverings of Two-Dimensional Grids

Elias Heikkilä, Pyry Herva*, Jarkko Kari

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

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.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 26th International Conference, DLT 2022, Proceedings
EditorsVolker Diekert, Mikhail Volkov
Pages152-163
Number of pages12
DOIs
Publication statusPublished - 2022
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Developments in Language Theory - Tampa, United States
Duration: 9 May 202213 May 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13257 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Developments in Language Theory
Abbreviated titleDLT
Country/TerritoryUnited States
CityTampa
Period09/05/202213/05/2022

Keywords

  • Formal power series
  • Laurent polynomials
  • Perfect multiple coverings
  • Periodicity
  • Two-dimensional configurations

Fingerprint

Dive into the research topics of 'On Perfect Coverings of Two-Dimensional Grids'. Together they form a unique fingerprint.

Cite this