A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Periods and binary words
Tekijät: Halava V, Harju T, Ilie L
Kustantaja: ACADEMIC PRESS INC
Julkaisuvuosi: 2000
Lehti:: Journal of Combinatorial Theory, Series A
Tietokannassa oleva lehden nimi: JOURNAL OF COMBINATORIAL THEORY SERIES A
Lehden akronyymi: J COMB THEORY A
Vuosikerta: 89
Numero: 2
Aloitussivu: 298
Lopetussivu: 303
Sivujen määrä: 6
ISSN: 0097-3165
DOI: https://doi.org/10.1006/jcta.1999.3014
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali