Reference : Multidimensional extension of the Morse-Hedlund theorem
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Multidimensional extension of the Morse-Hedlund theorem
Durand, Fabien [> >]
Rigo, Michel mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
European Journal of Combinatorics
Academic Press
Yes (verified by ORBi)
[en] block complexity ; Presburger arithmetic ; Nivat's conjecture
[en] Nivat's conjecture is about the link between the pure periodicity of a subset M of Z^2, i.e., invariance under translation by a fixed vector, and some upper bound on the function counting the number of different rectangular blocks occurring in $M$. Attempts to solve this conjecture have been considered during the last fifteen years. Let d>1. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of Z^d definable by a first order formula in the Presburger arithmetic <Z;<,+>. With this latter notion and using a powerful criterion due to Muchnik, we solve an analogue of Nivat's conjecture and characterize sets of Z^d definable in <Z;<,+> in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.

File(s) associated to this reference

Fulltext file(s):

Open access
complexity-aout2012.pdfAuthor preprint252.37 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.