The palindromization map
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.
- A characterization of infinite LSP words
- A noncommutative extension of Mahler's interpolation theorem
- A palindromization map for the free group
- A topology for free groups and related groups
- Average sizes of suffix trees and DAWGs
- Combinatorial pattern matching. 8th annual symposium, CPM '97, Aarhus, Denmark, June 30 -- July 2, 1997. Proceedings
- Complete inverted files for efficient text retrieval and analysis
- Deterministic generalized automata
- Dimension groups and dynamical systems. Substitutions, Bratteli diagrams and Cantor systems
- Elements of automata theory. Translated from the French by Reuben Thomas
- Episturmian morphisms and a Galois theorem on continued fractions
- Episturmian words and some constructions of de Luca and Rauzy
- From Christoffel Words to Markoff Numbers
- scientific article; zbMATH DE number 1577999 (Why is no real title available?)
- scientific article; zbMATH DE number 3991618 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 2183071 (Why is no real title available?)
- On Sturmian graphs
- On-line construction of compact directed acyclic word graphs
- Profinite groups.
- Profinite semigroups and applications.
- Profinite semigroups and symbolic dynamics
- Représentation géométrique de suites de complexité 2n+1
- Special factors and the combinatorics of suffix and factor automata
- Sturmian graphs and integer representations over numeration systems
- Sturmian numeration systems and decompositions to palindromes
- Sturmian words: structure, combinatorics, and their arithmetics
- Suffix Automata and Standard Sturmian Words
- The smallest automaton recognizing the subwords of a text
This page was built for publication: The palindromization map
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6048431)
