A1 Refereed original research article in a scientific journal
Nivat's conjecture and pattern complexity in algebraic subshifts
Authors: Kari Jarkko, Moutot Etienne
Publisher: Elsevier B.V.
Publication year: 2019
Journal: Theoretical Computer Science
Journal name in source: Theoretical Computer Science
Volume: 777
First page : 379
Last page: 386
Number of pages: 8
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2018.12.029
Self-archived copy’s web address: https://arxiv.org/pdf/1806.07107.pdf
We study Nivat's conjecture on algebraic subshifts and prove that in some of them every low complexity configuration is periodic. This is the case in the Ledrappier subshift (the 3-dot system) and, more generally, in all two-dimensional algebraic subshifts over defined by a polynomial without line polynomial factors in more than one direction. We also find an algebraic subshift that is defined by a product of two line polynomials that has this property (the 4-dot system) and another one that does not.
Downloadable publication This is an electronic reprint of the original article. |  |
