Article ID Journal Published Year Pages File Type
435281 Theoretical Computer Science 2011 11 Pages PDF
Abstract

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

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics