Palindromic complexity

When studying a given symbolic sequence, it is of particular interest to concentrate on its palindromic factors, i.e. words that read the same backward and forward. Examples of palindromes in French are "ressasser" and "radar". In discrete geometry, palindromes correspond to objects having symmetric properties, such as being invariant under a rotation of angle π or under some reflection.

In [1], Brlek, Hamel, Nivat and Reutenauer introduced the concept of palindromic defect, a statistic on words indicating whether they are full (or rich) in palindromes or not. More precisely, let w be a finite word. It is easy to show that w contains at most |w| + 1 distinct palindromes (including the empty palindrome ε). The defect of w is then defined by

A word is called full if D(w) = 0. It is well-known that Sturmian and Episturmian words are full. Moreover, the Thue-Morse sequence is not full and the exact positions where the palindromes are missed are described in [2]. More recently, we have shown that codings of rotations, a natural generalization of Sturmian words, are full as well [3].

An interesting operator acting on palindromes is the iterated palindromic closure. Let w be some finite word. One defines the palindromic closure of a w as the shortest palindrome having w as a prefix. It is denoted by w^( + ). For instance,

since baab is the longest palindromic suffix of abaab. Another remarkable property of the Fibonacci word is that it might be constructed by applying over and over the palindromic closure and adding alternatively the letters a and b on the word:

(a)^( + )  =  a       (ab)^( + )  =  aba       (abaa)^( + )  =  abaaba       (abaabab)^( + )  =  abaababaaba       (abaababaabaa)^( + )  =  abaababaabaababaaba       ⋮

Many different generalizations of the iterated palindromic closure have been studied. One of them focuses on pseudopalindromes or f-palindromes, i.e. a classical generalization of palindromes. Let f be some involution on an alphabet. Then w is called f-palindrome if f(w) = w̃, where ⋅̃ denotes the reversal of a word (the letters are written in reverse order). As an example, the word ACGT is a f-palindrome, where f is defined by A↔T and C↔G. The combinatorics of f-palindrome is widely studied in bio-informatics. The reader interested in the matter might take a look at [5] for further details on my work on f-palindromes and iterated palindromic closure.

Tilings

Combinatorics on words provide useful tools to study discrete objects such as polyominoes. In particular, it allows one to characterize those which tile periodically the Euclidean plane ℝ² by translation. Let P be some polyomino. Beauquier and Nivat proved in [6] that P tiles periodically the plane if it admits some boundary word w (a word on the alphabet {a, a, b, b} coding the moves right, left, up and down respectively) such that

where ^⋅ denote the discrete path traveled in the opposite direction and at most one word among A, B and C is empty. Such polyominoes are called tiles. For example, the two following polyominoes are tiles:

The left polyomino is called square tile, since the word C is empty. On the other hand, the right polyomino is called hexagon tile as all words A, B and C are nonempty.

In the last years, I have restricted my attention on the families of square tiles, more precisely on polyominoes that admit multiple square tilings. For instance, the following Fibonacci tile is called 2-square tiles (or double square tile):

since it admits two distinct square tilings (marked by red and blue dots). In 2008, it was conjectured in [7] that there exists no 3-square tilings. We proved that the conjecture indeed holds in [8]. Finally, we studied in details the enumeration of double square tiles in [9]. The figure below enumerates the first 100 double square tiles:

Some open problems still remain for students wishing to be introduced to discrete geometry and combinatorics on words (see for instance [9]).

References