Complexity and palindromic defect of infinite words

DOI10.1016/J.TCS.2010.11.025zbMATH Open1209.68395OpenAlexW2086603341MaRDI QIDQ620969FDOQ620969

Authors: 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

Recommendations

• Proof of the Brlek-Reutenauer conjecture
• On Brlek-Reutenauer conjecture
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• On generalized highly potential words
• A connection between palindromic and factor complexity using return words

zbMATH Keywords

complexitypalindromic defectpalindromic complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Palindrome complexity.
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• Episturmian words and some constructions of de Luca and Rauzy
• On the complexity of infinite sequences
• Enumeration of factors in the Thue-Morse word
• Factor versus palindromic complexity of uniformly recurrent infinite words
• A connection between palindromic and factor complexity using return words
• Combinatorial properties of \(f\)-palindromes in the Thue-Morse sequence
• Rich, Sturmian, and trapezoidal words
• A note on differentiable palindromes.
• Title not available (Why is that?)

Cited In (16)

• On Brlek-Reutenauer conjecture
• Extensions of rich words
• Palindromic complexity of trees
• On highly potential words
• Proof of the Brlek-Reutenauer conjecture
• A note on the paper ``On Brlek-Reutenauer conjecture
• Palindrome complexity.
• A connection between palindromic and factor complexity using return words
• On generalized highly potential words
• On words with the zero palindromic defect
• Palindromes in infinite ternary words
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• On the least number of palindromes contained in an infinite word
• Sturmian numeration systems and decompositions to palindromes
• Languages invariant under more symmetries: overlapping factors versus palindromic richness
• Palindromic richness for languages invariant under more symmetries

This page was built for publication: Complexity and palindromic defect of infinite words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q620969)