Complexity and palindromic defect of infinite words

DOI10.1016/J.TCS.2010.11.025MaRDI QIDQ620969zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)