A1 Refereed original research article in a scientific journal
Periods and binary words
Authors: Halava V, Harju T, Ilie L
Publisher: ACADEMIC PRESS INC
Publication year: 2000
Journal:: Journal of Combinatorial Theory, Series A
Journal name in source: JOURNAL OF COMBINATORIAL THEORY SERIES A
Journal acronym: J COMB THEORY A
Volume: 89
Issue: 2
First page : 298
Last page: 303
Number of pages: 6
ISSN: 0097-3165
DOI: https://doi.org/10.1006/jcta.1999.3014
Abstract
We give an elementary short proof for a well known theorem of Guibas and Odlyzko stating that thr sets of periods of words are independent of the alphabet size. As a consequence of our constructive proof, we obtain a linear time algorithm which, given a word, computes a binary one with the same periods. We give also a very short proof for the famous Fine Wilf periodicity lemma. (C) 2000 Academic Press.
We give an elementary short proof for a well known theorem of Guibas and Odlyzko stating that thr sets of periods of words are independent of the alphabet size. As a consequence of our constructive proof, we obtain a linear time algorithm which, given a word, computes a binary one with the same periods. We give also a very short proof for the famous Fine Wilf periodicity lemma. (C) 2000 Academic Press.
UTU Research Portal