A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
On the Periodic Decompositions of Multidimensional Configurations
Tekijät: Herva, Pyry; Kari, Jarkko
Toimittaja: Královič, Rastislav; Kůrková, Věra
Konferenssin vakiintunut nimi: International Conference on Current Trends in Theory and Practice of Computer Science
Kustantaja: Springer Nature Switzerland
Julkaisuvuosi: 2025
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: SOFSEM 2025: Theory and Practice of Computer Science: 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Bratislava, Slovak Republic, January 20–23, 2025, Proceedings, Part II
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta: 15539
Aloitussivu: 45
Lopetussivu: 57
ISBN: 978-3-031-82696-2
eISBN: 978-3-031-82697-9
ISSN: 0302-9743
eISSN: 1611-3349
DOI: https://doi.org/10.1007/978-3-031-82697-9_4
Verkko-osoite: https://doi.org/10.1007/978-3-031-82697-9_4
We consider d-dimensional configurations, that is, colorings of the d-dimensional integer grid Zd with finitely many colors. Moreover, we interpret the colors as integers so that configurations are functions Zd→Z of finite range. We say that such function is k-periodic if it is invariant under translations in k linearly independent directions. It is known that if a configuration has a non-trivial annihilator, that is, if some non-trivial linear combination of its translations is the zero function, then it is a sum of finitely many periodic functions. This result is known as the periodic decomposition theorem. We prove two different improvements of it. The first improvement gives a characterization on annihilators of a configuration to guarantee the k-periodicity of the functions in its periodic decomposition—for any k. The periodic decomposition theorem is then a special case of this result with k=1. The second improvement concerns so called sparse configurations for which the number of non-zero values in patterns grows at most linearly with respect to the diameter of the pattern. We prove that a sparse configuration with a non-trivial annihilator is a sum of finitely many periodic fibers where a fiber means a function whose non-zero values lie on a unique line.
Julkaisussa olevat rahoitustiedot:
This research was supported by the Academy of Finland grant 354965.
