On Perfect Coverings of Two-Dimensional Grids

Elias Heikkilä; Pyry Herva; Jarkko Kari

doi:10.1007/978-3-031-05578-2_12

On Perfect Coverings of Two-Dimensional Grids

Elias Heikkilä, Pyry Herva^*, Jarkko Kari

^*Corresponding author for this work

Communications Theory

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

Abstract

We study perfect multiple coverings in translation invariant graphs with vertex set Z² 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 language	English
Title of host publication	Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings
Editors	Volker Diekert, Mikhail Volkov
Pages	152-163
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-031-05578-2_12
Publication status	Published - 2022
MoE publication type	A4 Article in a conference publication
Event	International Conference on Developments in Language Theory - Tampa, United States Duration: 9 May 2022 → 13 May 2022

Publication series

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

Conference

Conference	International Conference on Developments in Language Theory
Abbreviated title	DLT
Country/Territory	United States
City	Tampa
Period	09/05/2022 → 13/05/2022

Keywords

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

Access to Document

10.1007/978-3-031-05578-2_12

SFX availability

Full text

Cite this

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 (pp. 152-163). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13257 LNCS). https://doi.org/10.1007/978-3-031-05578-2_12

Heikkilä, Elias ; Herva, Pyry ; Kari, Jarkko. / On Perfect Coverings of Two-Dimensional Grids. Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. editor / Volker Diekert ; Mikhail Volkov. 2022. pp. 152-163 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{68a53741d4d841eda48a84165f8f9134,

title = "On Perfect Coverings of Two-Dimensional Grids",

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.",

keywords = "Formal power series, Laurent polynomials, Perfect multiple coverings, Periodicity, Two-dimensional configurations",

author = "Elias Heikkil{\"a} and Pyry Herva and Jarkko Kari",

note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; International Conference on Developments in Language Theory, DLT ; Conference date: 09-05-2022 Through 13-05-2022",

year = "2022",

doi = "10.1007/978-3-031-05578-2_12",

language = "English",

isbn = "9783031055775",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "152--163",

editor = "Volker Diekert and Mikhail Volkov",

booktitle = "Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings",

}

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

On Perfect Coverings of Two-Dimensional Grids. / Heikkilä, Elias; Herva, Pyry; Kari, Jarkko.

Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. ed. / Volker Diekert; Mikhail Volkov. 2022. p. 152-163 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13257 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - On Perfect Coverings of Two-Dimensional Grids

AU - Heikkilä, Elias

AU - Herva, Pyry

AU - Kari, Jarkko

PY - 2022

Y1 - 2022

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

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

KW - Formal power series

KW - Laurent polynomials

KW - Perfect multiple coverings

KW - Periodicity

KW - Two-dimensional configurations

UR - http://www.scopus.com/inward/record.url?scp=85130252224&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-05578-2_12

DO - 10.1007/978-3-031-05578-2_12

M3 - Conference contribution

AN - SCOPUS:85130252224

SN - 9783031055775

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 152

EP - 163

BT - Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings

A2 - Diekert, Volker

A2 - Volkov, Mikhail

T2 - International Conference on Developments in Language Theory

Y2 - 9 May 2022 through 13 May 2022

ER -

Heikkilä E, Herva P, Kari J. On Perfect Coverings of Two-Dimensional Grids. In Diekert V, Volkov M, editors, Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. 2022. p. 152-163. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-031-05578-2_12