Extremal square-free words

Jarosław Grytczuk , Hubert Kordulewski , A. Niewiadomski


A word is square-free if it does not contain nonempty factors of the form XX. In 1906 Thue proved that there exist arbitrarily long square-free words over a 3-letter alphabet. We consider a new type of square-free words with additional property. A square-free word is called extremal if it cannot be extended to a new square-free word by inserting a single letter at any position. We prove that there exist infinitely many square-free extremal words over a 3-letter alphabet. Some parts of our construction relies on computer verifications. It is not known if there exist any extremal square-free words over a 4-letter alphabet.
Author Jarosław Grytczuk (FMIS / DAC)
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Hubert Kordulewski (FMIS)
Hubert Kordulewski,,
- Faculty of Mathematics and Information Science
, A. Niewiadomski
A. Niewiadomski,,
Journal seriesElectronic Journal of Combinatorics, ISSN 1077-8926
Issue year2020
Publication size in sheets0.5
Keywords in PolishEkstremalne słowa bez repetycji
Keywords in EnglishExtremal square-free words
ASJC Classification1703 Computational Theory and Mathematics; 2608 Geometry and Topology; 2614 Theoretical Computer Science
Abstract in PolishPraca dowodzi istnienia nieskończenie wielu słów ekstremalnych nad alfabetem 3-literowym.
URL https://https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p48/8036
Languageen angielski
Score (nominal)100
Score sourcejournalList
ScoreMinisterial score = 100.0, 26-06-2020, ArticleFromJournal
Publication indicators Scopus Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 0.922; WoS Impact Factor: 2018 = 0.762 (2) - 2018=0.764 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?