The Ehrenfeucht-Silberger problem
type: Item
instance of: scholarly article
title: The Ehrenfeucht-Silberger problem
zbMATH Open document ID: 1242.68194
author: Štěpán Holub
author: Dirk Nowotka
published in: Journal of Combinatorial Theory. Series A
publication date: 2012-02-11T00:00:00Z
review text: A factor of a word \(w\) is a block of consecutive letters of \(w\). A factor \(u\) is said to be unbordered if none of its proper prefixes is also a suffix of \(u\); otherwise, \(u\) is said to be bordered. In 1979, \textit{A. Ehrenfeucht} and \textit{D. M. Silberger} [Discrete Math. 26, 101--109 (1979; Zbl 0416.20051)] raised a difficult problem that relates periodicity and unbordered factors of words (this problem is closely related to the so-called critical factorization theorem). Denoting by \(\tau(w)\) the maximum length of unbordered factors of \(w\) and by \(\pi(w)\) the minimal period of \(w\), they asked for a bound on the length of \(w\), bound depending on \(\tau(w)\), that would guarantee the equality \(\tau(w)=\pi(w)\) to hold. In this beautiful paper, the authors finally settle this longstanding problem showing that if \(w\) is a word of length at least \(\frac{7}{3}\tau(w)\), then \(\tau(w)=\pi(w)\). This turns out to be an asymptotically tight bound due to an earlier example of Assous and Pouzet. Holub and Nowotka prove their result, which is independent of the alphabet size, using their notion of \(\alpha\)-critical prefix of a word. This notion becomes useful when finding long unbordered factors in words with large minimal periods. The authors' arguments can also be modified to exhibit an additive constant, i.e., they can show that if the length of \(w\) is at least \(\frac{7}{3}\tau(w)-\frac{8}{3}\) then \(\tau(w)=\pi(w)\). For sake of clarity, the authors did not try to optimize the additive constant.
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6005660
zbMATH Keywords: combinatorics on words
zbMATH Keywords: Ehrenfeucht-Silberger problem
zbMATH Keywords: periodicity
zbMATH Keywords: unbordered words
reviewed by: F. Blanchet-Sadri
MaRDI profile type: Publication
full work available at URL: j.jcta.2011.11.004
OpenAlex ID: W2039842951
cites work: Q4173569
cites work: Periodicity and unbordered segments of words
cites work: Periodes et repetitions des mots du monoide libre
cites work: Relationship between the period of a finite word and the length of its unbordered segments
cites work: A proof of the extended Duval's conjecture
cites work: Periodicity and unbordered words
cites work: Two-way string-matching
cites work: Saving comparisons in the Crochemore-Perrin string-matching algorithm
cites work: Real-Time Streaming String-Matching
cites work: Q3659988
cites work: Une caractérisation des mots périodiques
cites work: A Note on a Conjecture of Duval and Sturmian Words
cites work: Unbordered factors and Lyndon words
cites work: MINIMAL DUVAL EXTENSIONS
cites work: STACS 2004
cites work: Q4200990
DOI: 10.1016/J.JCTA.2011.11.004
Recommended article: The Ehrenfeucht-Silberger Problem
Recommended article: On Eisenstein's problem
Recommended article: On a problem of Eisenstein
Recommended article: Q5717225
Recommended article: On the Rankin-Selberg problem
Recommended article: Q3975941
Recommended article: The Riemann-Hilbert problem
Recommended article: On Siegel's problem for \(E\)-functions
Recommended article: Q2974144
Recommended article: AN ANALOGUE OF THE SCHUR–SIEGEL–SMYTH TRACE PROBLEM
description: scientific article; zbMATH DE number 6005660