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).

Язык оригиналаанглийский
Номер статьиP4.15
ЖурналElectronic Journal of Combinatorics
Том26
Номер выпуска4
СостояниеОпубликовано - 11 окт 2019

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Геометрия и топология
  • Дискретная математика и комбинаторика
  • Математика и теория расчета
  • Прикладная математика

ID: 48985690