A well known result of Fraenkel and Simpson
states that the number of distinct squares in a word of length is bounded by since at each position there are at most two distinct squares whose last occurrence starts.
In this paper, we investigate squares in partial words with one hole,
or sequences over a finite alphabet that have a “do not know” symbol or “hole”.
A square in a partial word over a given alphabet has the form where is with , and consequently, such square is compatible with a...
It is well-known that some of the most basic properties of words, like the commutativity () and the conjugacy (), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation has only periodic solutions in a free monoid, that is, if holds with integers , then there exists a word such that are powers of . This result, which received a lot of attention, was first proved by Lyndon and...
Recently, Constantinescu and Ilie proved a variant of the well-known periodicity theorem of Fine and Wilf in the case of two relatively prime abelian periods and conjectured a result for the case of two non-relatively prime abelian periods. In this paper, we answer some open problems they suggested. We show that their conjecture is false but we give bounds, that depend on the two abelian periods, such that the conjecture is true for all words having length at least those bounds and show that some...
Most of the constructions of infinite words having polynomial subword complexity are quite complicated, , sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words over a binary alphabet { } with polynomial subword complexity
. Assuming contains an infinite number of ’s, our method is based on the gap function which gives the distances between consecutive ’s. It is known that if the gap...
It is well-known that some of the most basic properties of words, like the
commutativity () and the conjugacy (), can be expressed
as solutions of word equations. An important problem is to decide whether
or not a given equation on words has a solution. For instance,
the equation has only periodic solutions in a free
monoid, that is, if holds with integers ,
then there exists a word such that are powers of .
This result, which received a lot of attention, was first proved
by Lyndon and Schützenberger...
Download Results (CSV)