Palindromic length of words and morphisms in class P

We study the palindromic length of factors of infinite words fixed by morphisms of the so-called class P introduced by Hof, Knill and Simon. We show that it grows at most logarithmically with the length of the factor. For the Fibonacci word and the Thue–Morse word we provide explicit bounds on their...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2019-08, Vol.780, p.74-83
Main Authors: Ambrož, Petr, Kadlec, Ondřej, Masáková, Zuzana, Pelantová, Edita
Format: Article
Language:English
Subjects:
Class [formula omitted]
Palindromic length
Palindromic richness
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 study the palindromic length of factors of infinite words fixed by morphisms of the so-called class P introduced by Hof, Knill and Simon. We show that it grows at most logarithmically with the length of the factor. For the Fibonacci word and the Thue–Morse word we provide explicit bounds on their rate of growth. We also construct an infinite word rich in palindromes for which the palindromic length grows as n.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.02.024