This paper studies the descriptional complexity of (i) sequences over a finite alphabet ; and (ii) subsets of $N$ (the natural numbers). If ${\left(s\left(i\right)\right)}_{i\ge 0}$ is a sequence over a finite alphabet $\Delta$, then we define the $k$-automaticity of $s,A_s^k\left(n\right)$, to be the smallest possible number of states in any deterministic finite automaton that, for all $i$ with $0\le i\le n$, takes $i$ expressed in base $k$ as input and computes $s\left(i\right)$. We give examples of sequences that have high automaticity in all bases $k$ ; for example, we show that the characteristic...

Let $\alpha$ be a real algebraic number of degree $3$ over $\mathbb{Q}$ whose conjugates are not real. There exists an unit $\zeta$ of the ring of integer of $K=\mathbb{Q}\left(\alpha \right)$ for which it is possible to describe the set of all best approximation vectors of $\theta =(\zeta ,{\zeta }^2)$.’

Let $x=x_0{x}_1\cdots$ be a fixed point of a substitution on the alphabet $\left\{a,b\right\},$ and let $U_a=\left(\begin{array}{cc}\hfill -1& \hfill -1\\ \hfill 0& \hfill 1\end{array}\right)$ and $U_b=\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 0& \hfill 1\end{array}\right)$. We give a complete classification of the substitutions $\sigma :{\left\{a,b\right\}}^{☆}$ according to whether the sequence of matrices ${\left(U_{x_0}{U}_{x_1}\cdots U_{x_n}\right)}_{n=0}^{\infty }$ is bounded or unbounded. This corresponds to the boundedness or unboundedness of the oriented walks generated by the substitutions.

The seminal theorem of Cobham has given rise during the last 40 years to a lot of work about non-standard numeration systems and has been extended to many contexts. In this paper, as a result of fifteen years of improvements, we obtain a complete and general version for the so-called substitutive sequences. Let $\alpha$ and $\beta$ be two multiplicatively independent Perron numbers. Then a sequence $x\in A^{\mathbb{N}}$, where $A$ is a finite alphabet, is both $\alpha$-substitutive and $\beta$-substitutive if and only if $x$ is ultimately periodic....

Nous étudions une classe de suites symboliques, les codages de rotations, intervenant dans des problèmes de répartition des suites ${\left(n\alpha \right)}_{n\in \mathbb{N}}$ et représentant une généralisation géométrique des suites sturmiennes. Nous montrons que ces suites peuvent être obtenues par itération de quatre substitutions définies sur un alphabet à trois lettres, puis en appliquant un morphisme de projection. L’ordre d’itération de ces applications est gouverné par un développement bi-dimensionnel de type “fraction continue”...

Nous établissons quelques propriétés des mots sturmiens et classifions, ensuite, les mots infinis qui possèdent, pour tout entier naturel non nul n, exactement n+2 facteurs de longueur n. Nous définissons également la notion d'insertion k à k sur les mots infinis puis nous calculons la complexité des mots obtenus en appliquant cette notion aux mots sturmiens. Enfin nous étudions l'équilibre et la palindromie d'une classe particulière de mots de complexité n+2 que nous appelons mots quasi-sturmiens...

We study some arithmetical and combinatorial properties of β-integers for β being the larger root of the equation x2 = mx - n,m,n ∈ ℵ, m ≥ n +2 ≥ 3. We determine with the accuracy of ± 1 the maximal number of β-fractional positions, which may arise as a result of addition of two β-integers. For the infinite word uβ> coding distances between the consecutive β-integers, we determine precisely also the balance. The word uβ> is the only fixed point of the morphism A → Am-1B and B → Am-n-1B. In...

La complexité d’une suite infinie est définie comme la fonction qui compte le nombre de facteurs de longueur $k$ dans cette suite. Nous prouvons ici que la complexité des suites de Rudin-Shapiro généralisées (qui comptent les occurrences de certains facteurs dans les développements binaires d’entiers) est ultimement affine.

The aim of this paper is to evaluate the growth order of the complexity function (in rectangles) for two-dimensional sequences generated by a linear cellular automaton with coefficients in $\mathbb{Z}/l\mathbb{Z}$, and polynomial initial condition. We prove that the complexity function is quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.

Let $T:x\mapsto x+g$ be an ergodic translation on the compact group $C$ and $M\subseteq C$ a continuity set, i.e. a subset with topological boundary of Haar measure 0. An infinite binary sequence $\mathbf{a}:\mathbb{Z}\mapsto \{0,1\}$ defined by $\mathbf{a}\left(k\right)=1$ if $T^k\left(0_C\right)\in M$ and $\mathbf{a}\left(k\right)=0$ otherwise, is called a Hartman sequence. This paper studies the growth rate of $P_{\mathbf{a}}\left(n\right)$, where $P_{\mathbf{a}}\left(n\right)$ denotes the number of binary words of length $n\in \mathbb{N}$ occurring in $\mathbf{a}$. The growth rate is always subexponential and this result is optimal. If $T$ is an ergodic translation $x\mapsto x+\alpha$$...$

We study the complexity of the infinite word $u_{\beta }$ associated with the Rényi expansion of $1$ in an irrational base $\beta \>1$. When $\beta$ is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity $ℂ\left(n\right)=n+1$. For $\beta$ such that $d_{\beta }\left(1\right)=t_1{t}_2\cdots t_m$ is finite we provide a simple description of the structure of special factors of the word $u_{\beta }$. When $t_m=1$ we show that $ℂ\left(n\right)=(m-1)n+1$. In the cases when $t_1=t_2=\cdots =t_{m-1}$ or $t_1\>max\{t_2,\cdots ,t_{m-1}\}$ we show that the first difference of the complexity function $ℂ(n+1)-ℂ\left(n\right)$ takes value in $\{m-1,m\}$ for every $n$, and consequently we determine...

We study the complexity of the infinite word uβ associated with the Rényi expansion of 1 in an irrational base β > 1. When β is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity C(n) = n + 1. For β such that dβ(1) = t1t2...tm is finite we provide a simple description of the structure of special factors of the word uβ. When tm=1 we show that C(n) = (m - 1)n + 1. In the cases when t1 = t2 = ... tm-1or t1 > max{t2,...,tm-1} we show that the first difference of...