• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

An Algebraic Geometric Approach to Nivat's Conjecture

Jarkko Kari, Michal Szabados, An Algebraic Geometric Approach to Nivat's Conjecture. In: Automata, languages, and programming, PT II, Lecture Notes in Computer Science 9135, 273–285, SPRINGER-VERLAG NEW YORK, MS INGRID CUNNINGHAM, 175 FIFTH AVE, NEW YORK, NY 10010 USA, 2015.

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

Abstract:

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.

BibTeX entry:

@INPROCEEDINGS{uconv1558782,
  title = {An Algebraic Geometric Approach to Nivat's Conjecture},
  booktitle = {Automata, languages, and programming, PT II},
  author = {Kari, Jarkko and Szabados, Michal},
  volume = {9135},
  series = {Lecture Notes in Computer Science},
  publisher = {SPRINGER-VERLAG NEW YORK, MS INGRID CUNNINGHAM, 175 FIFTH AVE, NEW YORK, NY 10010 USA},
  pages = {273–285},
  year = {2015},
  ISSN = {0302-9743},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication