In this paper we will deal with the balance properties of the infinite binary words associated to β-integers when β is a quadratic simple Pisot number. Those words are the fixed points of the morphisms of the type $\varphi \left(A\right)=A^{p}B$, $\varphi \left(B\right)=A^q$ for $p\in \mathbb{N}$, $q\in \mathbb{N}$, $p\ge q$, where $\beta =\frac{p+\sqrt{p^2+4q}}{2}$. We will prove that such word is t-balanced with $t=1+\left[(p-1)/(p+1-q)\right]$. Finally, in the case that p < q it is known [B. Adamczewski, Theoret. Comput. Sci.273 (2002) 197–224] that the fixed point of the substitution $\varphi \left(A\right)=A^{p}B$, $\varphi \left(B\right)=A^q$ is not m-balanced for any m. We exhibit an infinite sequence...

A word u defined over an alphabet $𝒜$ is c-balanced (c∈$\mathbb{N}$) if for all pairs of factors v, w of u of the same length and for all letters a∈$𝒜$, the difference between the number of letters a in v and w is less or equal to c. In this paper we consider a ternary alphabet $𝒜$ = {L, S, M} and a class of substitutions ${\varphi }_p$ defined by ${\varphi }_p$(L) = LpS, ${\varphi }_p$(S) = M, ${\varphi }_p$(M) = Lp–1S where p> 1. We prove that the fixed point of ${\varphi }_p$, formally written as ${\varphi }_p^{\infty }$(L), is 3-balanced and that its Abelian complexity is bounded above by...

Deciding whether a given word is an equality word of two nonperiodic morphisms is also known as the dual Post correspondence problem. Although the problem is decidable, there is no practical decision algorithm. Already in the binary case, the classification is a large project dating back to 1980s. In this paper we give a full classification of binary equality words in which one of the letters has two occurrences.

The avoidability of binary patterns by binary cube-free words is investigated and the exact bound between unavoidable and avoidable patterns is found. All avoidable patterns are shown to be D0L-avoidable. For avoidable patterns, the growth rates of the avoiding languages are studied. All such languages, except for the overlap-free language, are proved to have exponential growth. The exact growth rates of languages avoiding minimal avoidable patterns are approximated through computer-assisted upper...

We show that there are three types of infinite words over the two-letter alphabet {0,1} that avoid the pattern AABBCABBA. These types, P, E0, and E1, differ by the factor complexity and the asymptotic frequency of the letter 0. Type P has polynomial factor complexity and letter frequency $\frac{1}{2}$. Type E0 has exponential factor complexity and the frequency of the letter 0 is at least 0.45622 and at most 0.48684. Type E1 is obtained from type E0 by exchanging 0 and 1.

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.

Laminations are classic sets of disjoint and non-self-crossing curves on surfaces. Lamination languages are languages of two-way infinite words which code laminations by using associated labeled embedded graphs, and which are subshifts. Here, we characterize the possible exact affine factor complexities of these languages through bouquets of circles, i.e. graphs made of one vertex, as representative coding graphs. We also show how to build families of laminations together with corresponding lamination...