Aperiodic two-dimensional words of small abelian complexity
The electronic journal of combinatorics, Tome 26 (2019) no. 4
In this paper we prove an abelian analog of the famous Nivat's conjecture linking complexity and periodicity for two-dimensional words: We show that if a two-dimensional recurrent word contains at most two abelian factors for each pair $(n,m)$ of integers, then it has a periodicity vector. Moreover, we show that a two-dimensional aperiodic recurrent word must have more than two abelian factors infinitely often. On the other hand, there exist aperiodic recurrent words with abelian complexity bounded by $3$, as well as aperiodic words having abelian complexity $1$ for some pairs $(m,n)$.
DOI :
10.37236/8580
Classification :
68R15
Mots-clés : abelian complexity, Nivat conjecture, two-dimensional word
Mots-clés : abelian complexity, Nivat conjecture, two-dimensional word
Affiliations des auteurs :
Svetlana Puzynina 1
@article{10_37236_8580,
author = {Svetlana Puzynina},
title = {Aperiodic two-dimensional words of small abelian complexity},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {4},
doi = {10.37236/8580},
zbl = {1423.68374},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8580/}
}
Svetlana Puzynina. Aperiodic two-dimensional words of small abelian complexity. The electronic journal of combinatorics, Tome 26 (2019) no. 4. doi: 10.37236/8580
Cité par Sources :