Article (Scientific journals)
Multidimensional extension of the Morse-Hedlund theorem
Durand, Fabien; Rigo, Michel
2013In European Journal of Combinatorics, 34, p. 391-409
Peer Reviewed verified by ORBi
 

Files


Full Text
complexity-aout2012.pdf
Author preprint (258.43 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
block complexity; Presburger arithmetic; Nivat's conjecture
Abstract :
[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.
Disciplines :
Mathematics
Author, co-author :
Durand, Fabien
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Multidimensional extension of the Morse-Hedlund theorem
Publication date :
2013
Journal title :
European Journal of Combinatorics
ISSN :
0195-6698
eISSN :
1095-9971
Publisher :
Academic Press
Volume :
34
Pages :
391-409
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 26 September 2011

Statistics


Number of views
184 (9 by ULiège)
Number of downloads
137 (3 by ULiège)

Scopus citations®
 
13
Scopus citations®
without self-citations
10
OpenCitations
 
8

Bibliography


Similar publications



Contact ORBi