Fundamentals of Computing and Discrete Mathematics

Aldo de Luca

University of Naples Federico II - Italy

October 2012

Distinguished Lecture Colloquium

A palindromization map on free monoids and its generalizations

This talk is a survey of several results of combinatorial nature which have been obtained starting from a palindromization map $\psi$ on a free monoid $A^*$ introduced by the author in 1997 in the case of a binary alphabet, and successively generalized by other authors for arbitrary finite alphabets. If one extends the action of the palindromization map to infinite words, one can generate the class of all standard episturmian words, introduced by Droubay, Justin and Pirillo in 2001, which includes standard Sturmian words and Arnoux-Rauzy words. A noteworthy generalization of the palindromization map is obtained starting with a given code $X$ over $A$. The new operator $\psi_X$ maps $X^*$ to the set of palindromes of $A^*$; some properties of $\psi$ are lost and some are saved in a weak form. When $X$ has a finite deciphering delay one can extend $\psi_X$ to $X^\omega$, generating a class of infinite words much wider than standard episturmian words. For a finite and maximal code $X$ over $A$, a suitable generalization of standard Arnoux-Rauzy words is obtained. Finally, one can generalize further $\psi_X$ by replacing palindromic closure with $\theta$-palindromic closure, where $\theta$ is any involutory antimorphism of $A^*$. This yields an extension of the class of $\theta$-standard words introduced by the author and Alessandro De Luca in 2006.

Additional Material

A PDF version of the abstract can be downloaded here.

Last modified: Tuesday October 07, 2014