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.     

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.     

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.     

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.

A cyclic binary morphism avoiding Abelian fourth powers

We exhibit a cyclic binary morphism avoiding Abelian fourth powers.     

Optimal parallel detection of squares in strings

A stringw isprimitive if it is not a power of another string (i.e., writingw =v ^k impliesk = 1. Conversely,w is asquare ifw =vv, withv a primitive string. A stringx issquare-free if it has no nonempty substring of the formww. It is shown that the square-freedom of a string ofn symbols over an arbitrary alphabet can be tested by a CRCW PRAM withn processors inO(logn) time and linear auxiliary space. If the cardinality of the input alphabet is bounded by a constant independent of the input size, then the number of processors can be reduced ton/logn without affecting the time complexity of this strategy. The fastest sequential algorithms solve this problemO(n logn) orO(n) time, depending on whether the cardinality of the input alphabet is unbounded or bounded, and either performance is known to be optimal within its class. More elaborate constructions lead to a CRCW PRAM algorithm for detecting, within the samen-processors bounds, all positioned squares inx in timeO(logn) and using linear auxiliary space. The fastest sequential algorithms solve this problem inO(n logn) time, and such a performance is known to be optimal.This research was supported, through the Leonardo Fibonacci Institute, by the Istituto Trentino di Cultura, Trento, Italy. Additional support was provided by the French and Italian Ministries of Education, by the National Research Council of Italy, by the British Research Council Grant SERC-E76797, by NSF Grant CCR-89-00305, by NIH Library of Medicine Grant ROI LM05118, by AFOSR Grant 90-0107, and by NATO Grant CRG900293.     

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.     

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.     

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.     

A note on the condition number of the scaled total least squares problem

In this paper, we show that the normwise condition number of the scaled total least squares problem can be transformed into a new and compact form. Considering the relationship between the scaled total least squares problem and the total least squares problem, we obtain something new on the normwise condition number of the total least squares problem. The new forms of the normwise condition number are of particular interest in the following two aspects. Firstly, it is easy to use for the practitioners from applied disciplines. Secondly, the new forms enjoy great computational efficiency and require very little storage space compared with its original forms. Numerical examples are given to illustrate the results.     

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

A Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences

We present in this article a linear time and space method for the computation of the length of a repeated suffix for each prefix of a given word p . Our method is based on the utilization of the factor oracle of p which is a new and very compact structure introduced in [1], used for representing all the factors of p . We exhibit applications where our method really speeds up the computation of repetitions in words.     

Long binary patterns are Abelian 2-avoidable

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

A fast algorithm for finding the positions of all squares in a run-length encoded string

Squares are strings of the form ww where w is any nonempty string. Main and Lorentz proposed an O(nlogn)-time algorithm for finding the positions of all squares in a string of length n. Based on their result, we show how to find the positions of all squares in a run-length encoded string in time O(NlogN) where N is the number of runs in this string, provided that we do not explicitly compute at all “trivial squares” occurring within runs. The algorithm is optimal and its time complexity is independent of the length of the original uncompressed string.