Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.

A compatibility relation on letters induces a reflexive and symmetric relation on words of equal length. We consider these word relations with respect to the theory of variable length codes and free monoids. We define an (R,S)-code and an (R,S)-free monoid for arbitrary word relations R and S. Modified Sardinas-Patterson algorithm is presented for testing whether finite sets of words are (R,S)-codes. Coding capabilities of relational codes are measured algorithmically by finding minimal and maximal relations....

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...

We analyze an algorithm that decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in $𝒪(m·n)$, where $n$ is the length of the word and $m$ the size of the alphabet.

Rauzy fractals are compact sets with fractal boundary that can be associated with any unimodular Pisot irreducible substitution. These fractals can be defined as the Hausdorff limit of a sequence of compact sets, where each set is a renormalized projection of a finite union of faces of unit cubes. We exploit this combinatorial definition to prove the connectedness of the Rauzy fractal associated with any finite product of three-letter Arnoux–Rauzy substitutions.

A deterministic automaton recognizing a given ω-regular language is constructed from an ω-regular expression with the help of derivatives. The construction is related to Safra's algorithm, in about the same way as the classical derivative method is related to the subset construction.

The main purpose of this work is to present new families of transcendental continued fractions with bounded partial quotients. Our results are derived thanks to combinatorial transcendence criteria recently obtained by the first two authors in [3].

We add a sufficient condition for validity of Propo- sition 4.10 in the paper Frougny et al. (2004). This condition is not a necessary one, it is nevertheless convenient, since anyway most of the statements in the paper Frougny et al. (2004) use it.