The palindromization map (Q6048431): Difference between revisions

A palindrome is a word which remains the same when read from left to right and from right to left. Given a finite word \(w\), its palindromic closure \(w^{(+)}\) is the smallest palindrome having \(w\) as a prefix. \textit{A. de Luca} [Theor. Comput. Sci. 183, No. 1, 45--82 (1997; Zbl 0911.68098)] introduced the iterated palindromic closure Pal, a map sending the empty word to itself and \(wa\) to \((\operatorname{Pal}(w)a)^{(+)}\) for every finite word \(w\) and letter \(a\). Such a map Pal can be generalized to infinite words -- since when \(u\) is a prefix of \(v\) then \(\operatorname{Pal}(u)\) is a prefix of \(\operatorname{Pal}(v)\), for all finite words \(u\), \(v\) -- and also to free groups, where it takes the name of \emph{palindromization map}. This has been done first for free groups of rank two by the second author with Kassel in [\textit{C. Kassel} and \textit{C. Reutenauer}, Theor. Comput. Sci. 409, No. 3, 461--470 (2008; Zbl 1155.68066)] and now here for free groups over arbitrary alphabets. Several properties of the map are given in this article, as well as its connections with topics in algebra, profinite topology, automata and transducer theory, with a particular focus on compact automata and suffix automata.