RUS  ENG
Full version
JOURNALS // Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya // Archive

Izv. RAN. Ser. Mat., 2004 Volume 68, Issue 2, Pages 191–214 (Mi im480)

This article is cited in 13 papers

Partial words and the interaction property of periods

A. M. Shur, Yu. V. Gamzova


Abstract: A theorem of Fine and Wilf expresses the interaction property of periods, which is a basic property of periodic words. An arbitrary word with given periods $p$ and $q$ also has a “derived” period $\operatorname{gcd}(p,q)$ if the length of the word is greater than some critical value called the length of interaction. In this paper we consider a similar property for arbitrary periodic partial words and give a sharp linear bound for the length of interaction.

UDC: 512.532.2+519.11

MSC: 68R15, 68Q45

Received: 08.01.2003

DOI: 10.4213/im480


 English version:
Izvestiya: Mathematics, 2004, 68:2, 405–428

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024