Long binary patterns are Abelian 2-avoidable

We show that every long binary pattern is Abelian 2-avoidable.     

Abelian combinatorics on words: A survey

We survey known results and open problems in abelian combinatorics on words. Abelian combinatorics on words is the extension to the commutative setting of the classical theory of combinatorics on words. The extension is based on abelian equivalence, which is the equivalence relation defined in the set of words by having the same Parikh vector, that is, the same number of occurrences of each letter of the alphabet. In the past few years, there was a lot of research on abelian analogues of classical definitions and properties in combinatorics on words. This survey aims to gather these results.     

Fewest repetitions versus maximal-exponent powers in infinite binary words

A square is the concatenation of a nonempty word with itself. A word has period p if its letters at distance p match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give some new results on the trade-off between the number of squares and the number of maximal-exponent powers in infinite binary words, in the three cases where the maximal exponent is 7/3, 5/2, and 3. These are the only threshold values related to the question.     

Some characterizations of Parikh matrix equivalent binary words

We state different characterizations of pair of words having the same Parikh matrix.     

A note on the number of squares in a word

Fraenkel and Simpson [A.S. Fraenkel, J. Simpson, How many squares can a string contain? J. Combin. Theory Ser. A 82 (1998) 112–120] proved that the number of squares in a word of length n$n$ is bounded by 2n$2n$. In this note we improve this bound to 2n−Θ(logn)$2n-\Theta (logn)$. Based on the numerical evidence, the conjectured bound is n$n$.     

Reconstruction of a word from a multiset of its factors

Let be the multiset containing all factors of w of length k including repetitions. One of the main results is that if for all , then w=v. The bound is optimal; however we will also show that if for all , then w and v are structurally similar.     

Unavoidable Sets of Partial Words

The notion of an unavoidable set of words appears frequently in the fields of mathematics and theoretical computer science, in particular with its connection to the study of combinatorics on words. The theory of unavoidable sets has seen extensive study over the past twenty years. In this paper we extend the definition of unavoidable sets of words to unavoidable sets of partial words. Partial words, or finite sequences that may contain a number of “do not know” symbols or “holes,” appear naturally in several areas of current interest such as molecular biology, data communication, and DNA computing. We demonstrate the utility of the notion of unavoidability of sets of partial words by making use of it to identify several new classes of unavoidable sets of full words. Along the way we begin work on classifying the unavoidable sets of partial words of small cardinality. We pose a conjecture, and show that affirmative proof of this conjecture gives a sufficient condition for classifying all the unavoidable sets of partial words of size two. We give a result which makes the conjecture easy to verify for a significant number of cases. We characterize many forms of unavoidable sets of partial words of size three over a binary alphabet, and completely characterize such sets over a ternary alphabet. Finally, we extend our results to unavoidable sets of partial words of size k over a k-letter alphabet. This material is based upon work supported by the National Science Foundation under Grant No. DMS-0452020. Part of this paper was presented at DLT’07 [4]. We thank the referees as well as Robert Mercaş and Geoffrey Scott for very valuable comments and suggestions. World Wide Web server interfaces have been established at and for automated use of the programs.     

Abelian complexity of infinite words associated with quadratic Parry numbers

We derive an explicit formula for the Abelian complexity of infinite words associated with quadratic Parry numbers.     

Avoiding large squares in partial words

Well-known results on the avoidance of large squares in (full) words include the following: (1) Fraenkel and Simpson showed that we can construct an infinite binary word containing at most three distinct squares; (2) Entringer, Jackson and Schatz showed that there exists an infinite binary word avoiding all squares of the form xx such that |x|≥3, and that the bound 3 is optimal; (3) Dekking showed that there exists an infinite cube-free binary word that avoids all squares xx with |x|≥4, and that the bound of 4 is best possible. In this paper, we investigate these avoidance results in the context of partial words, or sequences that may have some undefined symbols called holes. Here, a square has the form uv with u and v compatible, and consequently, such a square is compatible with a number of full words that are squares over the given alphabet. We show that (1) holds for partial words with at most two holes. We prove that (2) extends to partial words having infinitely many holes. Regarding (3), we show that there exist binary partial words with infinitely many holes that avoid cubes and have only eleven full word squares compatible with factors of it. Moreover, this number is optimal, and all such squares xx satisfy |x|≤4.     

On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters

We give lower bounds on the growth rate of Dejean words, i.e. minimally repetitive words, over a k-letter alphabet, for 5≤k≤10. Put together with the known upper bounds, we estimate these growth rates with the precision of 0.005. As a consequence, we establish the exponential growth of the number of Dejean words over a k-letter alphabet, for 5≤k≤10.     

Covering numbers of rotations

For an irrational rotation, we use the symbolic dynamics on the sturmian coding to compute explicitly, according to the continued fraction approximation of the argument, the measure of the largest Rokhlin stack made with intervals, and the measure of the largest Rokhlin stack whose levels have one name for the coding. Each one of these measures is equal to one if and only if the argument has unbounded partial quotients.     

On two-sided infinite fixed points of morphisms

Let Σ be a finite alphabet, and let h:Σ^* → Σ^* be a morphism. Finite and infinite fixed points of morphisms—i.e., those words w such that h(w)=w—play an important role in formal language theory. Head characterized the finite fixed points of h, and later, Head and Lando characterized the one-sided infinite fixed points of h. Our paper has two main results. First, we complete the characterization of fixed points of morphisms by describing all two-sided infinite fixed points of h, for both the “pointed” and “unpointed” cases. Second, we completely characterize the solutions to the equation h(xy)=yx in finite words.     

Some non finitely generated monoids of repetition-free endomorphisms

We answer a question raised by Mitrana in Information Processing Letters 64 about primitive morphisms, that is, morphisms that preserve primitiveness of words. Given an alphabet A with Card(A)?2, the monoid of primitive endomorphisms on A and the monoid of primitive uniform endomorphisms on A are not finitely generated. Moreover we show that it is also the case for the following monoids: the monoid of overlap-free (uniform) endomorphisms on A (when Card(A)?3), the monoid of k-power-free (uniform) endomorphisms on A (when Card(A)?2 and k?3).     

Balancing and clustering of words in the Burrows-Wheeler transform

Compression algorithms based on Burrows-Wheeler transform (BWT) take advantage of the fact that the word output of BWT shows a local similarity and then turns out to be highly compressible. The aim of the present paper is to study such “clustering effect” by using notions and methods from Combinatorics on Words.The notion of balance of a word plays a central role in our investigation. Empirical observations suggest that balance is actually the combinatorial property of input word that ensure optimal BWT compression. Moreover, it is reasonable to assume that the more balanced the input word is, the more local similarity we have after BWT (and therefore the better the compression is). This hypothesis is here corroborated by experiments on “real” text, by using local entropy as a measure of the degree of balance of a word.In the setting of Combinatorics on Words, a sound confirmation of previous hypothesis is given by a result of Mantaci et al. (2003) [27], which states that, in the case of a binary alphabet, there is an equivalence between circularly balanced words, words having a clusterized BWT, and the conjugates of standard words. In the case of alphabets of size greater than two, there is no more equivalence. The last section of the present paper is devoted to investigate the relationships between these notions, and other related ones (as, for instance, palindromic richness) in the case of a general alphabet.     

On systems of word equations with simple loop sets

Consider the infinite system S of word equations

For each , let T_k be the subsystem of S given by i{k,k+1,k+2}. We prove two properties of the above system.

(1) Let k≥1. If φ is a solution of T_k such that primitive roots of are of equal length, as well as primitive roots of , then φ is a solution of the whole S.

(2) If n=1 then, for any k≥2, a solution φ of T_k is also a solution of S.

Minimal forbidden subwords

Motivated by a study of similar problems stated for factors of words, we study forbidden subwords of a language or a word. A procedure for obtaining the set of all words avoiding a given set of subwords is presented. On the other hand, an algorithm for computing the set of minimal forbidden subwords for a word is given. The case of a two-letter alphabet appears to be particularly interesting and it is considered separately.     

Computation of words satisfying the “rhythmic oddity property” (after Simha Arom's works)

This paper addresses the problem of enumerating all words having a combinatoric property called “rhythmic oddity property”. This enumeration is motivated by the fact that this property is satisfied by many rhythmic patterns used in traditional Central African music.