Greedy Palindromic Lengths

In [A. Frid, S. Puzynina and L. Q. Zamboni, On palindromic factorization of words, Adv. in Appl. Math. 50 (2013) 737–748], it was conjectured that any infinite word whose palindromic lengths of factors are bounded is ultimately periodic. We introduce variants of this conjecture and prove this conjec...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2018-04, Vol.29 (3), p.331-356
Main Authors: Bucci, Michelangelo, Richomme, Gwenaël
Format: Article
Language:English
Subjects:
Computer Science
Discrete Mathematics
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:In [A. Frid, S. Puzynina and L. Q. Zamboni, On palindromic factorization of words, Adv. in Appl. Math. 50 (2013) 737–748], it was conjectured that any infinite word whose palindromic lengths of factors are bounded is ultimately periodic. We introduce variants of this conjecture and prove this conjecture when the bound is 2. Especially we introduce left and right greedy palindromic lengths. These lengths are always greater than or equals to the initial palindromic length. When the greedy left (or right) palindromic lengths of prefixes of a word are bounded then this word is ultimately periodic.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054118500077