Nivat's conjecture and pattern complexity in algebraic subshifts

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 Fp defined by a polynomial withou...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2019-07, Vol.777, p.379-386
Main Authors: Kari, Jarkko, Moutot, Etienne
Format: Article
Language:English
Subjects:
Algebraic subshift
Computer Science
Discrete Mathematics
Ledrappier subshift
Low complexity configurations
Multidimensional symbolic dynamics
Nivat's conjecture
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Fp 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2018.12.029