A4 Vertaisarvioitu artikkeli konferenssijulkaisussa

An Algebraic Geometric Approach to Nivat's Conjecture




TekijätKari J, Szabados M

ToimittajaHalldorsson, MM; Iwama, K; Kobayashi, N; Speckmann, B

Konferenssin vakiintunut nimiInternational Colloquium on Automata, Languages and Programming

KustantajaSPRINGER-VERLAG NEW YORK, MS INGRID CUNNINGHAM, 175 FIFTH AVE, NEW YORK, NY 10010 USA

KustannuspaikkaBerlin

Julkaisuvuosi2015

JournalLecture Notes in Computer Science

Kokoomateoksen nimiAutomata, languages, and programming, PT II

Tietokannassa oleva lehden nimiAUTOMATA, LANGUAGES, AND PROGRAMMING, PT II

Lehden akronyymiLECT NOTES COMPUT SC

Sarjan nimiLecture Notes in Computer Science

Vuosikerta9135

Aloitussivu273

Lopetussivu285

Sivujen määrä13

ISBN978-3-662-47666-6

ISSN0302-9743

DOIhttps://doi.org/10.1007/978-3-662-47666-6_22


Tiivistelmä

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.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 22:44