A note about words which coincide except in one position (Q2272406)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A note about words which coincide except in one position |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note about words which coincide except in one position |
scientific article |
Statements
A note about words which coincide except in one position (English)
0 references
10 September 2019
0 references
The paper corrects the statement of a proposition left as an exercise in the famous monograph [Algebraic combinatorics on words. Cambridge: Cambridge University Press (2002; Zbl 1001.68093)] by \textit{M. Lothaire}. As stated, the proposition is false, which is shown by the following counter-example: two words \(w = ababab\) and \(v = abaaab\) of length \(6\) differ only in one position, \(w\) is \(2\)-periodic, \(v\) is \(4\)-periodic, \(2+4=6\), but \(w \neq v\). So, to make the respective statement true, we have to add the condition for both periods to be not greater than the common length of both words divided by two: then two words with respective periods which differ in at most one position have to be equal. The corrected statement still allows one to prove the theorem on periods of a word from Lothaire's monograph in which the exercise was initially used.
0 references
combinatorics on words
0 references
periods
0 references
Fine-Wilf theorem
0 references