We study infinite words u over an alphabet $𝒜$ satisfying the property $𝒫:𝒫\left(n\right)+𝒫(n+1)=1+\#𝒜\mathrm{for}\mathrm{any}n\in \mathbb{N}$, where $𝒫\left(n\right)$ denotes the number of palindromic factors of length n occurring in the language of u. We study also infinite words satisfying a stronger property $\mathrm{𝒫ℰ}$: every palindrome of u has exactly one palindromic extension in u. For binary words, the properties $𝒫$ and $\mathrm{𝒫ℰ}$ coincide and these properties characterize Sturmian words, i.e., words with the complexity C(n) = n + 1 for any $n\in \mathbb{N}$. In this paper, we focus on ternary infinite...

We study the palindromic complexity of infinite words $u_{\beta }$, the fixed points of the substitution over a binary alphabet, $\varphi \left(0\right)=0^{a}1$, $\varphi \left(1\right)=0^{b}1$, with $a-1\ge b\ge 1$, which are canonically associated with quadratic non-simple Parry numbers $\beta$.

We study the palindromic complexity of infinite words uβ, the fixed points of the substitution over a binary alphabet, φ(0) = 0a1, φ(1) = 0b1, with a - 1 ≥ b ≥ 1, which are canonically associated with quadratic non-simple Parry numbers β.

A simple Parry number is a real number $\beta \>1$ such that the Rényi expansion of $1$ is finite, of the form $d_{\beta }\left(1\right)=t_1\cdots t_m$. We study the palindromic structure of infinite aperiodic words $u_{\beta }$ that are the fixed point of a substitution associated with a simple Parry number $\beta$. It is shown that the word $u_{\beta }$ contains infinitely many palindromes if and only if $t_1=t_2=\cdots =t_{m-1}\ge t_m$. Numbers $\beta$ satisfying this condition are the so-called confluent Pisot numbers. If $t_m=1$ then $u_{\beta }$ is an Arnoux-Rauzy word. We show that if $\beta$ is a confluent Pisot number then...

In the present work, we investigate real numbers whose sequence of partial quotients enjoys some combinatorial properties involving the notion of palindrome. We provide three new transendence criteria, that apply to a broad class of continued fraction expansions, including expansions with unbounded partial quotients. Their proofs heavily depend on the Schmidt Subspace Theorem.

A set T ⊆ L is a Parikh test set of L if c(T) is a test set of c(L). We give a characterization of Parikh test sets for arbitrary language in terms of its Parikh basis, and the coincidence graph of letters.

Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with m distinct variables and of length at least 2m is avoidable over a ternary alphabet and if the length is at least 3 2m−1 it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words - sequences, in which some characters are left “blank”. Using method of entropy compression, we obtain the partial words version of the theorem for ternary words

This contribution extends the notions of roots and periodicity to strings of transfinite lengths. It shows that given a transfinite string, either it possesses a unique root or the set of its roots are equivalent in a strong way.

This contribution extends the notions of roots and periodicity to strings of transfinite lengths. It shows that given a transfinite string, either it possesses a unique root or the set of its roots are equivalent in a strong way.

In this paper, we characterize the substitutions over a three-letter alphabet which generate a ultimately periodic sequence.

In this paper, we characterize the substitutions over a three-letter alphabet which generate a ultimately periodic sequence.

We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.

We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.

Cet article est probablement le dernier texte de mathématiques écrit en vue de sa publication par M. P. Schützenberger, décédé en juillet 1996. Il était offert par son auteur en hommage à André Lentin, à l'occasion d'un colloque tenu en l'honneur de celui-ci le 23 février 1996 ; M. P. Schützenberger, déjà très malade, n'avait pu participer à cette rencontre, mais avait tenu à rédiger, non sans souffrances, une contribution scientifique qui témoignât de son amitié pour A. Lentin. Lorsque je lui dis...