On periodic properties of circular words

The conjugacy relation defines a partition of words into equivalence classes. We call these classes circular words. Periodic properties of circular words are investigated in this article. The Periodicity Theorem of Fine and Wilf does not hold for weak periods of circular words; instead we give a str...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2016-03, Vol.339 (3), p.1189-1197
Main Authors: Hegedüs, László, Nagy, Benedek
Format: Article
Language:English
Subjects:
Circular words
Combinatorics on words
Weak period
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The conjugacy relation defines a partition of words into equivalence classes. We call these classes circular words. Periodic properties of circular words are investigated in this article. The Periodicity Theorem of Fine and Wilf does not hold for weak periods of circular words; instead we give a strict upper bound on the length of a non-unary circular word that has two given relatively prime weak periods. Weak periods also lead to a way of representing circular words in a more compact form. We investigate in which cases are these representations unique or minimal. We will also analyze weak periods of circular Thue–Morse, Fibonacci and Christoffel words.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2015.10.043