Fine and Wilf's theorem for three periods and a generalization of Sturmian words

We extend the theorem of Fine and Wilf to words having three periods. We then define the set 3-PER of words of maximal length for which such result does not apply. We prove that the set 3-PER and the sequences of complexity 2 n + 1, introduced by Arnoux and Rauzy to generalize Sturmian words, have t...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 1999-04, Vol.218 (1), p.83-94
Main Authors: Castelli, M.Gabriella, Mignosi, Filippo, Restivo, Antonio
Format: Article
Language:English
Subjects:
Applied sciences
Combinatorics on words
Computer science
control theory
systems
Data processing. List processing. Character string processing
Euclid's algorithm
Exact sciences and technology
Memory organisation. Data processing
Periodicity
Software
Sturmian words
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:We extend the theorem of Fine and Wilf to words having three periods. We then define the set 3-PER of words of maximal length for which such result does not apply. We prove that the set 3-PER and the sequences of complexity 2 n + 1, introduced by Arnoux and Rauzy to generalize Sturmian words, have the same set of factors.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(98)00251-5