On theta-palindromic richness

DOI10.1016/J.TCS.2010.12.011zbMATH Open1211.68302arXiv1005.0722OpenAlexW2047842237MaRDI QIDQ631773FDOQ631773

Authors: Štěpán Starosta 

Publication date: 14 March 2011

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

Abstract: In this paper we study generalization of the reversal mapping realized by an arbitrary involutory antimorphism $Theta$. It generalizes the notion of a palindrome into a $Theta$-palindrome -- a word invariant under $Theta$. For languages closed under $Theta$ we give the relation between $Theta$-palindromic complexity and factor complexity. We generalize the notion of richness to $Theta$-richness and we prove analogous characterizations of words that are $Theta$-rich, especially in the case of set of factors invariant under $Theta$. A criterion for $Theta$-richness of $Theta$-episturmian words is given together with other examples of $Theta$-rich words.

Full work available at URL: https://arxiv.org/abs/1005.0722

Recommendations

• Infinite words rich and almost rich in generalized palindromes
• ALMOST RICH WORDS AS MORPHIC IMAGES OF RICH WORDS
• Palindromic richness for languages invariant under more symmetries
• Generalized Thue-Morse words and palindromic richness
• Pseudopalindrome closure operators in free monoids

zbMATH Keywords

combinatorics on wordsrich wordspseudopalindrometheta-episturmian wordstheta-palindrome

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Palindromic richness
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• Episturmian words and some constructions of de Luca and Rauzy
• Sturmian and Episturmian Words
• Palindromes and Sturmian words
• A new characteristic property of rich words
• Palindromic complexity of infinite words associated with simple Parry numbers
• Factor versus palindromic complexity of uniformly recurrent infinite words
• A connection between palindromic and factor complexity using return words
• On different generalizations of episturmian words
• Episturmian words: a survey
• Sturmian jungle (or garden?) On multiliteral alphabets
• On \(\theta\)-episturmian words

Cited In (12)

• Enumeration of two dimensional palindromes
• Twin-roots of words and their properties
• Infinite words rich and almost rich in generalized palindromes
• A relation by palindromic subwords
• Theta palindromes in theta conjugates
• Pseudopalindrome closure operators in free monoids
• Generalized Thue-Morse words and palindromic richness
• Reconstructing words from a \(\sigma\)-palindromic language
• ALMOST RICH WORDS AS MORPHIC IMAGES OF RICH WORDS
• Languages invariant under more symmetries: overlapping factors versus palindromic richness
• Palindromic richness for languages invariant under more symmetries
• Palindromic closures using multiple antimorphisms

This page was built for publication: On theta-palindromic richness

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