We show a connection between a recent conjecture of Shallit and an older conjecture of Rauzy for infinite words on a finite alphabet. More precisely we show that a Rauzy-like conjecture is equivalent to Shallit's. In passing we correct a misprint in Rauzy's conjecture.

The repetition threshold is a measure of the extent to which there need to be consecutive (partial) repetitions of finite words within infinite words over alphabets of various sizes. Dejean's Conjecture, which has been recently proven, provides this threshold for all alphabet sizes. Motivated by a question of Krieger, we deal here with the analogous threshold when the infinite word is restricted to be a D0L word. Our main result is that, asymptotically, this threshold does not exceed the unrestricted...

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids....

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In 1991, Klarner, Birget and Satterfield proved the undecidability...

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids....

For any finite word $w$ on a finite alphabet, we consider the basic parameters $R_w$ and $K_w$ of $w$ defined as follows: $R_w$ is the minimal natural number for which $w$ has no right special factor of length $R_w$ and $K_w$ is the minimal natural number for which $w$ has no repeated suffix of length $K_w$. In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.

For any finite word w on a finite alphabet, we consider the basic parameters Rw and Kw of w defined as follows: Rw is the minimal natural number for which w has no right special factor of length Rw and Kw is the minimal natural number for which w has no repeated suffix of length Kw. In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.

The characteristic parameters $K_w$ and $R_w$ of a word $w$ over a finite alphabet are defined as follows: $K_w$ is the minimal natural number such that $w$ has no repeated suffix of length $K_w$ and $R_w$ is the minimal natural number such that $w$ has no right special factor of length $R_w$. In a previous paper, published on this journal, we have studied the distributions of these parameters, as well as the distribution of the maximal length of a repetition, among the words of each length on a given alphabet. In this paper...

The characteristic parameters Kw and Rw of a word w over a finite alphabet are defined as follows: Kw is the minimal natural number such that w has no repeated suffix of length Kw and Rw is the minimal natural number such that w has no right special factor of length Rw. In a previous paper, published on this journal, we have studied the distributions of these parameters, as well as the distribution of the maximal length of a repetition, among the words of each length on a given alphabet....

Threshold languages, which are the (k/(k–1))+-free languages over k-letter alphabets with k ≥ 5, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over k letters tends to a constant $\widehat{\alpha }\approx 1.242$ as k tends to infinity.

For each $m\ge 2,$ we consider the $m$-bonacci numbers defined by $F_k=2^k$ for $0\le k\le m-1$ and $F_k=F_{k-1}+F_{k-2}+\cdots +F_{k-m}$ for $k\ge m.$ When $m=2,$ these are the usual Fibonacci numbers. Every positive integer $n$ may be expressed as a sum of distinct $m$-bonacci numbers in one or more different ways. Let $R_m\left(n\right)$ be the number of partitions of $n$ as a sum of distinct $m$-bonacci numbers. Using a theorem of Fine and Wilf, we obtain a formula for $R_m\left(n\right)$ involving sums of binomial coefficients modulo $2.$ In addition we show that this formula may be used to determine the number of partitions...

The theorem of Fraenkel and Simpson states that the maximum number of distinct squares that a word w of length n can contain is less than 2n. This is based on the fact that no more than two squares can have their last occurrences starting at the same position. In this paper we show that the maximum number of the last occurrences of squares per position in a partial word containing one hole is 2k, where k is the size of the alphabet. Moreover, we prove that the number of distinct squares in a partial...

The product w = u ⊗ v of two sequences u and v is a naturally defined sequence on the alphabet of pairs of symbols. Here, we study when the product w of two balanced sequences u,v is balanced too. In the case u and v are binary sequences, we prove, as a main result, that, if such a product w is balanced and deg(w) = 4, then w is an ultimately periodic sequence of a very special form. The case of arbitrary alphabets is approached in the last section. The partial results obtained and the problems...

The product w = u ⊗ v of two sequences u and v is a naturally defined sequence on the alphabet of pairs of symbols. Here, we study when the product w of two balanced sequences u,v is balanced too. In the case u and v are binary sequences, we prove, as a main result, that, if such a product w is balanced and deg(w) = 4, then w is an ultimately periodic sequence of a very special form. The case of arbitrary alphabets is approached in the last section. The partial results obtained and the problems...

Given a finite alphabet Σ and a language L ⊆ ∑+, the centralizer of L is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of L (with respect to a lexicographic order) is prefix distinguishable in L then the centralizer of L is as simple as possible, that is, the submonoid L*. This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.