On Repetitiveness Measures of Thue-Morse Words

Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)


We show that the size of the smallest string attractor of the n-th Thue-Morse word is 4 for any, disproving the conjecture by Mantaci et al. [ICTCS 2019] that it is n. We also show that for, where is the maximum over all, the number of distinct substrings of length k in w divided by k, which is a measure of repetitiveness recently studied by Kociumaka et al. [LATIN 2020]. Furthermore, we show that the number of factors in the self-referencing Lempel-Ziv factorization of is exactly 2n.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings
EditorsChristina Boucher, Sharma V. Thankachan
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages8
ISBN (Print)9783030592110
Publication statusPublished - 2020
Event27th International Symposium on String Processing and Information Retrieval, SPIRE 2020 - Orlando, United States
Duration: Oct 13 2020Oct 15 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12303 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Symposium on String Processing and Information Retrieval, SPIRE 2020
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On Repetitiveness Measures of Thue-Morse Words'. Together they form a unique fingerprint.

Cite this