Some answer to Nivat's conjecture: A characterization of periodicity with respect to block complexity
Preprint
Abstract
Nivat's conjecture is about the link between the pure periodicity of a subset $M$ of $\ZZ^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\ge 2$. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of $\ZZ^d$ definable by a first order formula in the Presburger arithmetic $<\ZZ;<,+>$. With this latter notion and using a powerful criterion due to Muchnik, we solve an analogue of Nivat's conjecture and characterize sets of $\ZZ^d$ definable in $<\ZZ;<,+>$ in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- On a conjecture on bidimensional wordsTheoretical Computer Science, 2003
- The definable criterion for definability in Presburger arithmetic and its applicationsTheoretical Computer Science, 2003
- The rectangle complexity of functions on two-dimensional latticesTheoretical Computer Science, 2002
- Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequencesDiscrete Mathematics, 2000
- Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theoremsAnnals of Pure and Applied Logic, 1996
- Logic and {$p$}-recognizable sets of integersBulletin of the Belgian Mathematical Society - Simon Stevin, 1994
- On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operationHistory and Philosophy of Logic, 1991
- On the base-dependence of sets of numbers recognizable by finite automataTheory of Computing Systems, 1969