A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
An Algebraic Geometric Approach to Nivat's Conjecture
Tekijät: Kari J, Szabados M
Toimittaja: Halldorsson, MM; Iwama, K; Kobayashi, N; Speckmann, B
Konferenssin vakiintunut nimi: International Colloquium on Automata, Languages and Programming
Kustantaja: SPRINGER-VERLAG NEW YORK, MS INGRID CUNNINGHAM, 175 FIFTH AVE, NEW YORK, NY 10010 USA
Kustannuspaikka: Berlin
Julkaisuvuosi: 2015
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Automata, languages, and programming, PT II
Tietokannassa oleva lehden nimi: AUTOMATA, LANGUAGES, AND PROGRAMMING, PT II
Lehden akronyymi: LECT NOTES COMPUT SC
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 9135
Aloitussivu: 273
Lopetussivu: 285
Sivujen määrä: 13
ISBN: 978-3-662-47666-6
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-662-47666-6_22
We study multidimensional configurations (infinite words) and subshifts of low pattern complexity using tools of algebraic geometry. We express the configuration as a multivariate formal power series over integers and investigate the setup when there is a non-trivial annihilating polynomial: a non-zero polynomial whose formal product with the power series is zero. Such annihilator exists, for example, if the number of distinct patterns of some finite shape D in the configuration is at most the size vertical bar D vertical bar of the shape. This is our low pattern complexity assumption. We prove that the configuration must be a sum of periodic configurations over integers, possibly with unbounded values. As a specific application of the method we obtain an asymptotic version of the well-known Nivat's conjecture: we prove that any two-dimensional, non-periodic configuration can satisfy the low pattern complexity assumption with respect to only finitely many distinct rectangular shapes D.
Ladattava julkaisu This is an electronic reprint of the original article. |