The palindromization map

The iterated palindromic closure is an injective map mapping arbitrary words to palindromes. It has been introduced by Aldo de Luca in [9]. This map is used to define a representation of Sturmian words by means of a directive word and is related to a transformation introduced by Rauzy (see [20, 3]). The iterated palindromic closure has been shown in [18] to be extendable, in the case of two letters, to a map (not anymore injective) from the free group into itself and to have many interesting properties.

In this article, we study the extension of the iterated palindrome closure to a map from the free group on more than two letters to itself. We show that some of the features appearing with two letters remain valid while some others do not hold anymore. In particular, we show that the map is continuous for the profinite topology (Proposition 4.1). We were not able to characterise the kernel of the map as it is done in [18], where it is related to the braid group. We also discuss the relation with noncommutative cohomology evidenced in [18] but we show that, on more than two letters, the cocycle corresponding to the iterated palindromization map is not trivial.

In Section 5, we describe the suffix automaton of a word of the form $\operatorname{Pal}(w)$, that is the minimal automaton of the set of suffixes of this word. We extend to arbitrary alphabets results concerning the suffix automaton; the corresponding results for binary alphabets are from [13].

In Section 6, we develop study compact automata. These automata have already been studied in the case of suffix automata (see the chapter by Maxime Crochemore in [19]), but they do not seem to have been considered before in the general case of automata. We fill this gap and present a direct definition of a minimal compact automaton, which is shown to be unique (Corollary 6.6), together with two other results related to the notion of reduction of automaton (Propositions 6.5 and 6.7).

This will apply in Section 7 to the construction of the minimal compact suffix automaton of $\operatorname{Pal}(u)$. In that section, we construct directly the minimal compact automaton of the set of suffixes of $\operatorname{Pal}(w)$. The construction extends the known construction in the binary alphabet case due to Epifanio, Mignosi, Shallit and Venturini [13] (see also [7]). It consists in computing the automaton for $\operatorname{Pal}(ua)$ from the automaton of $\operatorname{Pal}(u)$, by adjoining one state, and several transitions from the first automaton to this state. From this, we deduce the exact form of the automaton (Theorem 7.1) and several of its properties (Corollaries 7.6 and 7.7)

We denote by $A^{*}$ the free monoid on the alphabet $A$ and by $1$ the empty word. We denote by $\tilde{w}=a_{n}\cdots a_{2}a_{1}$ the reversal of the word $w=a_{1}a_{2}\cdots a_{n}$ with $a_{i}\in A$. The word $w$ is a palindrome if $\tilde{w}=w$.

We denote by $FG(A)$ the free group on $A$. If $w$ is in $F(A)$ and $a$ in $A$, we denote by $|w|_{a}$ the number of occurrences of $a$ in $w$, where one counts with -1 the occurrences of $a^{-1}$; this is well defined and does not depend on the chosen expression for $w$; we call it the $a$-degree of $w$. Moreover, define $|w|=\sum_{a\in A}|w|_{a}$, the algebraic length of $w$. In particular, if $w\in A^{*}$, then $|w|$ is the length of $w$.

The reversal of the element $w=a_{1}a_{2}\cdots a_{n}$ with $a_{i}\in A\cup A^{-1}$ is the element $\tilde{w}=a_{n}\cdots a_{2}a_{1}$. This does not depend on the chosen expression for $w$. The map $w\mapsto\tilde{w}$ is an antimorphism, that is, it satisfies $\widetilde{uv}=\tilde{v}\tilde{u}$. We also say that an element $w$ of $FG(A)$ is a palindrome if $\tilde{w}=w$.

Let us define two morphisms $L\colon u\mapsto L_{u}$ and $R\colon u\mapsto R_{u}$ from $FG(A)$ into its group of automorphisms as follows. For $a,b\in A$, we set

The map $L_{a}$ is an automorphism of $FG(A)$ since its inverse is the map

Symmetrically, for $a,b\in A$, we set $R_{a}(b)=\widetilde{L_{a}(b)}$.

Thus, for example, $L_{a}(ab^{-1})=aL_{a}(b)^{-1}=ab^{-1}a^{-1}$ and $R_{a}(ab^{-1})=aR_{a}(b)^{-1}=aa^{-1}b^{-1}=b^{-1}$.

Note that $L,R$ are related by two identities. The first one is

for every $a\in A\cup A^{-1}$ and $u\in FG(A)$. Indeed, this is true when $u$ is a letter; by rewriting equivalently $R_{a}(u)=a^{-1}L_{a}(u)a$, this equality follows since both sides are the image of $u$ under an automorphism of $FG(A)$.

The second one is

for every $u,v\in FG(A)$. Indeed, this is true when $u$ is a letter and the general case follows similarly.

Every word $w\in A^{*}$ is a prefix of some palindrome since $w\tilde{w}$ is always a palindrome. Thus, there exists a palindrome of shortest length which has $w$ as a prefix. Actually, this palindrome is unique. It is called the palindromic closure of $w$ and denoted $w^{(+)}$. One has $w^{(+})=yz\tilde{y}$ where $z$ is the longest palindrome suffix of $w=yz$ (for these results, due to Aldo de Luca, see for example [21] Proposition 12.1.1).

For example, $(abaa)^{(+)}=abaaba$, since the longest palindromic suffix of $abaa$ is $z=aa$, and $y=ab$.

Let $\operatorname{Pal}$ be the unique map from $A^{*}$ to $A^{*}$ such that $\operatorname{Pal}(1)=1$, and for $w\in A^{*}$ and $a\in A$

For a word $w$, $\operatorname{Pal}(w)$ is called the iterated palindromic closure of $w$. The iterated palindromic closure has been introduced by Aldo de Luca [9] who has shown that it is injective (see for example [21] p. 102, where the injectivity is proved by an algorithm).

For example $\operatorname{Pal}(aba)=abaaba$, since $\operatorname{Pal}(a)=a$, $\operatorname{Pal}(ab)=(ab)^{(+)}=aba$, and finally $\operatorname{Pal}(aba)=(abaa)^{(+)}=abaaba$.

The mapping $\operatorname{Pal}$ may be extended to infinite words, since when $u$ is a proper prefix of $v$, $\operatorname{Pal}(u)$ is a proper prefix of $\operatorname{Pal}(v)$.

An important property of $\operatorname{Pal}$ is the following functional equation, known as Justin’s Formula [17]. For all $u,v\in A^{*}$,

A dual form of (2.3) (which is the one actually given in [17, Lemma 2.1]) is

Indeed, assuming (2.4), we have using (2.2),

Hence (2.4) implies (2.3). The reverse implication is true, too, as is similarly verified.

We want to prove the following result, extending the construction of [18] to arbitrary alphabets.

We will still denote by $\operatorname{Pal}$ the extension of the iterated palindromic closure to the free group and call it the palindromization map. We will see below that the extension also satisfies (2.4), for any $u,v\in FG(A)$.

The statement follows directly from the following property.

We now verify the following property of the palindromization map.

It follows from Proposition 2.3, using the same argument as in (2.6), that the map $\operatorname{Pal}$ satisfies also (2.4) for every $u,v\in FG(A)$.

As an example, we have $Pal(b^{-1})=b^{-1}$ and $\operatorname{Pal}(ab^{-1})=\operatorname{Pal}(a)R_{a}(Pal(b^{-1}))=aR_{a}(b^{-1})=a(ba)^{-1}=b^{-1}$. This shows that the extension of $\operatorname{Pal}$ to $FG(A)$ is not injective. In the case of a binary alphabet, one can characterize the kernel of $\operatorname{Pal}$ as follows.

Let $B_{3}$ be the braid group on three strands defined as

Let $\beta:FG(a,b)\to B_{3}$ be the morphism $\beta:a\mapsto\sigma_{1},b\mapsto\sigma_{2}$. For any $u,v\in FG(a,b)$, one has $\operatorname{Pal}(u)=\operatorname{Pal}(v)$ if and only if $\beta(u^{-1}v)\in\langle\sigma_{1}\sigma_{2}^{-1}\sigma_{1}^{-1}\rangle$ (see [18, Proposition 5.2]). No such characterization is known on more than two letters.

We discuss now several interpretations of Justin’s Formula.

The profinite topology on the free group $FG(A)$ is the topology generated by the inverse images of subsets of a finite group $F$ by a morphism $\varphi:FG(A)\to F$. Equivalently, it is the coarsest topology such that every morphism to a finite discrete group is continuous. This topology on the free group was introduced by Hall (see [16]). It is a particular case of a more general notion which extends to varieties of groups and also of semigroups (see [22] and [1]).

The following is proved in [18] for the case of a binary alphabet.

Actually we shall prove a slightly more general result. Following [1] p. 57, we define the profinite distance $d$ on $FG(A)$ by the formula

where $u,v$ are distinct, and where $r(u,v)$ is the minimal cardinality of a group $G$ such that, for some morphism $\varphi:FG(A)\to G$, $\varphi(u)\neq\varphi(v)$. Since $FG(A)$ is residually finite, $r(u,v)$ is a finite integer for each pair $u,v$ of distinct elements in $FG(A)$. It is easy to prove that $r(u,w)\geq\min(r(u,v),r(v,w))$, hence

which means that $d$ is an ultrametric distance.

The topology of $FG(A)$ induced by $d$ is precisely the profinite topology.

Proposition 4.1 follows from the next result, since each uniformly continuous function is continuous.

We need in the proof the following characterizations of uniformly continuous functions.

1. A function $P:FG(A)\to FG(A)$ is uniformly continuous if and only if for any morphism $\varphi:FG(A)\to G$, the function $\varphi\circ P:FG(A)\to G$ is uniformly continuous, where $G$ has the discrete distance.

2. A function $P^{\prime}:FG(A)\to G$, with $G$ a finite group with discrete distance, is uniformly continuous if and only if it factorizes as $P^{\prime}=h\circ\psi$, where $\psi:FG(A)\to S$ is a morphism into a finite group, and $h:S\to G$ is some function.

Since $A^{*}$ is dense in $FG(A)$ for the profinite topology (see [1] or [2] for example), we deduce from Proposition 4.1 the following statement.

Though $\operatorname{Pal}$ is continuous for the profinite topology, it is not continuous for the pro-$p$ topology on the free group $F_{2}$ of rank $2$, where $p$ is a prime number. Recall that the pro-$p$ topology is the coarsest topology such that every group homomorphism from $F_{2}$ into a finite $p$-group is continuous (see [18, Remark 6.3]).

The minimal automaton of the set of suffixes of a word $w$ is called the suffix automaton of $w$. These automata has been extensively studied (see [19, Chapter 2]) A striking property (originally due to [4]) is that its number of states is at most $2|w|-1$.

Let $u$ be a word over an arbitrary alphabet $A$. We denote by $\mathcal{S}(u)$ the suffix automaton of $\operatorname{Pal}(u)$.

Part (i) of the following result is not new, but we give a proof for sake of completeness.

This result, for a binary alphabet, is due to  [13] ((i) in the binary case also follows from Theorem 1 in [24], which characterizes the binary words whose suffix automaton has $|w|+1$ states); see also [13], [12], [7]. Moreover, for general alphabets, Part (i) of the theorem is a consequence of the remark in Section 5 in Fici’s article [14]. Note that that characterizations of the words $w$ such that the suffix automaton of $w$ has $|w|+1$ states have been given by Fici [14] and Richomme [23].

A factor $w$ of a word $u$ (resp. an infinite word $s$) is left-special if there are at least two letters $a$ such that $aw$ is a factor of $u$ (resp. $s$).

The following is from [10, Proposition 5] (see also [11, Proposition 1.5.11]). Recall that for any infinite word $x$, the infinite word $\operatorname{Pal}(x)$ is well-defined.

We will use the following consequence.

Note that not all prefixes of $\operatorname{Pal}(u)$ need to be left-special. For example, if $u=ab$, the factor $ab$ is not a left-special factor of $\operatorname{Pal}(u)=aba$.

Given a language $L$, a residual of $L$ is set of the form $u^{-1}L=\{v\in A^{*}\mid uv\in L\}$. It is well-known that the minimal automaton of a language $L$, denoted $\mathcal{A}(L)$, has the set of nonempty residuals of $L$ as set of states.

Let us show now that $\alpha$ is surjective. Let $q$ be a state of the automaton $\mathcal{S}(u)$. Let $w$ be a word such that $1\cdot w=q$. Since the automaton is co-accessible, there is some word $s$ such that $1\cdot ws$ is a terminal state, and thus $ws$ is a suffix of $\operatorname{Pal}(u)$. Hence the word $w$ is a factor of $\operatorname{Pal}(u)$. Let $p$ be the shortest prefix of $\operatorname{Pal}(u)$ such that $pw$ is a prefix of $\operatorname{Pal}(u)$. Let us show by induction on the length of $p^{\prime}$ that for every suffix $p^{\prime}$ of $p$, one has $1\cdot p^{\prime}w=q$. It is true if $p^{\prime}=1$. Otherwise, set $p^{\prime}=ap^{\prime\prime}$. We have $1\cdot p^{\prime\prime}w=q$ by induction hypothesis.

Let $s$ be an arbitrary word such that $ws$ belongs to the set $S$ of suffixes of $\operatorname{Pal}(u)$. Since $1\cdot p^{\prime\prime}w=1\cdot w$, and since the automaton $\mathcal{S}(u)$ is the minimal automaton of $S$, so that $(p^{\prime\prime}w)^{-1}S=w^{-1}S$, and $s\in w^{-1}S$, we have $p^{\prime\prime}ws\in S$. We cannot have $p^{\prime\prime}ws=\operatorname{Pal}(u)$, since otherwise $p^{\prime\prime}w$ is a prefix of $\operatorname{Pal}(u)$ with $p^{\prime\prime}$ shorter than $p$.

Thus there is some $b\in A$ such that $bp^{\prime\prime}ws\in S$ . Since $ap^{\prime\prime}w=p^{\prime}w$ is a factor of $\operatorname{Pal}(u)$ and since, by Corollary 5.3, $p^{\prime\prime}w$ is not left-special (because $p^{\prime\prime}w$ is not a prefix of $\operatorname{Pal}(u)$ for the same reason as above), we have $a=b$. This shows that $ws\in S\Rightarrow p^{\prime}ws\in S$. The converse is also true and thus that $w^{-1}S=(p^{\prime}w)^{-1}S$, that is $1\cdot p^{\prime}w=1\cdot w=q$, since the automaton is minimal.

We conclude that $1\cdot pw=q$. This shows that $\alpha$ is surjective and proves property (i). Next, if $p$ is a prefix of $\operatorname{Pal}(u)$ which is also a suffix, then $p$ is a palindrome and thus property (ii) is true.         

Note that the automaton $\mathcal{S}(u)$ has the additional property

1. (iii)

   The label of an edge depends only on its end.

Actually, this property holds for any suffix automaton, as is well-known. Indeed, if $p,q$ are two states of the suffix automaton of a word $w$ such that $p\cdot a=q\cdot b=r$, let $u,v,t$ be such that $1\stackrel{{\scriptstyle u}}{{\rightarrow}}p\stackrel{{\scriptstyle a}}{{\rightarrow}}r\stackrel{{\scriptstyle t}}{{\rightarrow}}s$ and $1\stackrel{{\scriptstyle v}}{{\rightarrow}}q\stackrel{{\scriptstyle b}}{{\rightarrow}}r\stackrel{{\scriptstyle t}}{{\rightarrow}}s$ with $s$ a terminal state. Then $uat$ and $vbt$ are suffixes of $w$, which implies $a=b$.

We explore the notion of compact automaton in which the edges can be labeled by nonempty words instead of letters. This version of automata appears, in the case of compact suffix automata, in [6] or [8]. It is also presented in the chapter by Maxime Crochemore in [19]. In particular, the construction of a minimal compact suffix automaton is described (see also [5]). We will show here that it is possible to define in complete generality a minimal compact automaton for every language.

A compact automaton $\mathcal{A}=(Q,E,I,T)$ is given by a set of states $Q$, a set of edges $E\subset Q\times A^{+}\times Q$, a set initial states $I\subset Q$ and a set of terminal states $T\subset Q$. A path $p_{0}\stackrel{{\scriptstyle u_{0}}}{{\rightarrow}}p_{1}\stackrel{{\scriptstyle u_{1}}}{{\rightarrow}}p_{2}\ldots\stackrel{{\scriptstyle u_{n-1}}}{{\rightarrow}}p_{n}$ is a sequence of consecutive edges. Its label is $u_{0}u_{1}\cdots u_{n-1}$. The language recognized by $\mathcal{A}$, denoted $L(\mathcal{A})$, is the set of labels od successful paths, that is paths from $I$ to $T$.

An ordinary automaton is clearly a particular case of a compact automaton.

A compact automaton is deterministic if $\operatorname{Card}(I)=1$ and if for every state $p$, the labels of the edges starting at $p$ begin with distinct letters.

Again, an ordinary deterministic automaton is deterministic as a compact automaton.

The set of special states of a compact automaton $\mathcal{A}=(Q,E,I,T)$ is the set $Q_{s}$ of states $q$ which either belong to $I\cup T$ or such that there are edges going out of $q$ with labels beginning with distinct letters.

Let $p,q$ be special states. A path $p\stackrel{{\scriptstyle w}}{{\rightarrow}}q$ is special if the only special states on the path are its origin and its end.

A reduction from a deterministic compact automaton $\mathcal{A}=(Q,E,i,T)$ onto a deterministic compact automaton $\mathcal{A}^{\prime}=(Q^{\prime},E^{\prime},i^{\prime},T^{\prime})$ is a map $\varphi$ from $Q_{s}$ onto $Q^{\prime}_{s}$ such that