We address the problem to know whether the relation induced by a one-rule length-preserving rewrite system is rational. We partially answer to a conjecture of Éric Lilin who conjectured in 1991 that a one-rule length-preserving rewrite system is a rational transduction if and only if the left-hand side u and the right-hand side v of the rule of the system are not quasi-conjugate or are equal, that means if u and v are distinct, there do not exist words x, y and z such that u = xyz and v = zyx. We...

We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case sufficient...

We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case sufficient...

On peut définir la pente d'un mot écrit avec des 0 et des 1 comme le nombre de 1 divisé par le nombre de 0, et généraliser cette définition aux mots de longueur infinie. Considérant le lien entre les mots de Christoffel et les fractions continues, on se propose d'étudier le comportement de tels mots lorsqu'on additionne leurs pentes, ou qu'on les multiplie par un entier positif. Après un bref exposé des différentes notions liées aux mots de Christoffel, l'étude de la somme et de la multiplication...

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.