Complexity and palindromic defect of infinite words

DOI10.1016/j.tcs.2010.11.025zbMath1209.68395MaRDI QIDQ620969

Christophe Reutenauer, Srečko Brlek

Publication date: 2 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.025

zbMATH Keywords

complexity; palindromic defect; palindromic complexity

Mathematics Subject Classification ID

68R15: Combinatorics on words

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Languages invariant under more symmetries: overlapping factors versus palindromic richness, Palindromic richness for languages invariant under more symmetries, Extensions of rich words, On Brlek-Reutenauer conjecture, On highly potential words, Palindromic Complexity of Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rich, Sturmian, and trapezoidal words
• On the complexity of infinite sequences
• A note on differentiable palindromes.
• Enumeration of factors in the Thue-Morse word
• Palindrome complexity.
• Factor versus palindromic complexity of uniformly recurrent infinite words
• A connection between palindromic and factor complexity using return words
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• Episturmian words and some constructions of de Luca and Rauzy