Nivat's conjecture and pattern complexity in algebraic subshifts




Kari Jarkko, Moutot Etienne

PublisherElsevier B.V.

2019

Theoretical Computer Science

Theoretical Computer Science

777

379

386

8

0304-3975

DOIhttps://doi.org/10.1016/j.tcs.2018.12.029

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.


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