The Ehrenfeucht-Silberger problem (Q662035): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jcta.2011.11.004 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2039842951 / rank | |||
Normal rank |
Revision as of 20:38, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Ehrenfeucht-Silberger problem |
scientific article |
Statements
The Ehrenfeucht-Silberger problem (English)
0 references
11 February 2012
0 references
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.
0 references
combinatorics on words
0 references
Ehrenfeucht-Silberger problem
0 references
periodicity
0 references
unbordered words
0 references