A note about words which coincide except in one position

DOI10.1016/J.TCS.2019.04.005MaRDI QIDQ2272406zbMATH OpenOpenAlexWikidataFDO

Authors Margot Bruneaux

Publication date 10 September 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.02430

zbMATH Keywords

combinatorics on words Fine-Wilf theorem periods

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: In this short note, we show that a result about words which coincide except in one position given as an exercise in Lothaire's Algebraic Combinatorics on Words is false. Moreover, we derive a modified statement which allows us to fix the proof of a theorem which originally used the result of this exercise.

Review text

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.

Recommendations

Cited in

(2)

This page was built for publication: A note about words which coincide except in one position

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272406)