Combinatorics on partial word correlations

Partial words are strings over a finite alphabet that may contain a number of “do not know” symbols. In this paper, we consider the period and weak period sets of partial words of length n over a finite alphabet, and study the combinatorics of specific representations of them, called correlations, which are binary and ternary vectors of length n indicating the periods and weak periods. We characterize precisely which vectors represent the period and weak period sets of partial words and prove that all valid correlations may be taken over the binary alphabet. We show that the sets of all such vectors of a given length form distributive lattices under suitably defined partial orderings. We show that there is a well-defined minimal set of generators for any binary correlation of length n and demonstrate that these generating sets are the primitive subsets of {1,2,…,n−1}. We also investigate the number of partial word correlations of length n. Finally, we compute the population size, that is, the number of partial words sharing a given correlation, and obtain recurrences to compute it. Our results generalize those of Guibas, Odlyzko, Rivals and Rahmann.     

Unbordered partial words

An unbordered word is a string over a finite alphabet such that none of its proper prefixes is one of its suffixes. In this paper, we extend the results on unbordered words to unbordered partial words. Partial words are strings that may have a number of “do not know” symbols. We extend a result of Ehrenfeucht and Silberger which states that if a word u can be written as a concatenation of nonempty prefixes of a word v, then u can be written as a unique concatenation of nonempty unbordered prefixes of v. We study the properties of the longest unbordered prefix of a partial word, investigate the relationship between the minimal weak period of a partial word and the maximal length of its unbordered factors, and also investigate some of the properties of an unbordered partial word and how they relate to its critical factorizations (if any).     

Unbordered factors and Lyndon words

A primitive word w is a Lyndon word if w is minimal among all its conjugates with respect to some lexicographic order. A word w is bordered if there is a nonempty word u such that w=uvu for some word v. A right extension of a word w of length n is a word wu where all factors longer than n are bordered. A right extension wu of w is called trivial if there exists a positive integer k such that w^k=uv for some word v.We prove that Lyndon words have only trivial right extensions. Moreover, we give a conjecture which characterizes a property of every word w which has a nontrivial right extension of length 2|w|-2.     

On minimal Sturmian partial words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that p_w(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form aⁱ?a^jba^l, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(a^N−1?)^h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2.     

Sorting and generating reduced words

We introduce a partial order on the set of all reduced words of a given permutation ω, called directed-braid poset of ω. This poset enables us to produce two algorithms: One is a sorting algorithm applied to any reduced word of ω and aims to obtain the natural word (i.e. lexicographically largest reduced word); the other one is a generation algorithm applied to the natural word and returns the set of all reduced words of ω.     

On highly potential words

We introduce a class of infinite words, called highly potential words because of their seemingly high potential of being a good supply of examples and counterexamples regarding various problems on words. We prove that they are all aperiodic words of finite positive defect, and having their set of factors closed under reversal, thus giving examples Brlek and Reutenauer were looking for. We prove that they indeed satisfy the Brlek–Reutenauer conjecture. We observe that each highly potential word is recurrent, but not uniformly recurrent. Considering a theorem from the paper of Balková, Pelantová and Starosta, later found to be incorrect, we show that highly potential words constitute an infinite family of counterexamples to that theorem. Finally, we construct a highly potential word which is a fixed point of a nonidentical morphism, thus showing that a stronger version of a conjecture by Blondin-Massé et al., as stated by Brlek and Reutenauer, is false.     

Morse and Hedlund’s Skew Sturmian Words Revisited

For any infinite word r over A = {a, b} we associate two infinite words min(r), max(r) such that any prefix of min(r) (max(r), respectively) is the lexicographically smallest (greatest, respectively) among the factors of r of the same length. We prove that (min(r); max(r)) = (as, bs) for some infinite word s if and only if r is a proper Sturmian word or an ultimately periodic word of a particular form. This result is based on a lemma concerning sequences of infinite words. Received July 11, 2005     

The sequence of open and closed prefixes of a Sturmian word

A finite word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We are interested in the oc-sequence of a word, which is the binary sequence whose n-th element is 0 if the prefix of length n of the word is open, or 1 if it is closed. We exhibit results showing that this sequence is deeply related to the combinatorial and periodic structure of a word. In the case of Sturmian words, we show that these are uniquely determined (up to renaming letters) by their oc-sequence. Moreover, we prove that the class of finite Sturmian words is a maximal element with this property in the class of binary factorial languages. We then discuss several aspects of Sturmian words that can be expressed through this sequence. Finally, we provide a linear-time algorithm that computes the oc-sequence of a finite word, and a linear-time algorithm that reconstructs a finite Sturmian word from its oc-sequence.     

Avoiding abelian squares in partial words

Erd?s raised the question whether there exist infinite abelian square-free words over a given alphabet, that is, words in which no two adjacent subwords are permutations of each other. It can easily be checked that no such word exists over a three-letter alphabet. However, infinite abelian square-free words have been constructed over alphabets of sizes as small as four. In this paper, we investigate the problem of avoiding abelian squares in partial words, or sequences that may contain some holes. In particular, we give lower and upper bounds for the number of letters needed to construct infinite abelian square-free partial words with finitely or infinitely many holes. Several of our constructions are based on iterating morphisms. In the case of one hole, we prove that the minimal alphabet size is four, while in the case of more than one hole, we prove that it is five. We also investigate the number of partial words of length n with a fixed number of holes over a five-letter alphabet that avoid abelian squares and show that this number grows exponentially with n.     

On G-locally primitive graphs of locally Twisted Wreath type and a conjecture of Weiss

Let Γ be a connected G-vertex-transitive graph and let v be a vertex of Γ. The graph Γ is said to be G-locally primitive if the action of the vertex-stabiliser Gv on the neighbourhood Γ(v) of v is primitive. Furthermore, Γ is said to be of locally Twisted Wreath type if Gv is a primitive group of Twisted Wreath type in its action on Γ(v).Richard Weiss conjectured in 1978 that, there exists a function f:N→N such that if Γ is a connected G-vertex-transitive locally primitive graph of valency d and v is a vertex of Γ, then |Gv|?f(d). In this paper we prove this conjecture when Γ is of locally Twisted Wreath type.     

k-Abelian pattern matching

Two words are called k-abelian equivalent, if they share the same multiplicities for all factors of length at most k. We present an optimal linear time algorithm for identifying all occurrences of factors in a text that are k-abelian equivalent to some pattern P. Moreover, an optimal algorithm for finding the largest k for which two words are k-abelian equivalent is given. Solutions for online versions of the k-abelian pattern matching problem are also proposed.     

Locally Periodic Versus Globally Periodic Infinite Words

We call a one-way infinite word w over a finite alphabet (ρ,l)-repetitive if all long enough prefixes of w contain as a suffix a ρth power (or more generally a repetition of order ρ) of a word of length at most l. We show that each (2,4)-repetitive word is ultimately periodic, as well as that there exist continuum many, and hence also nonultimately periodic, (2,5)-repetitive words. Further, we characterize nonultimately periodic (2,5)-repetitive words both structurally and algebraically.     

A new statistic on Dyck paths for counting 3-dimensional Catalan words

A 3-dimensional Catalan word is a word on three letters so that the subword on any two letters is a Dyck path. For a given Dyck path D, a recently defined statistic counts the number of Catalan words with the property that any subword on two letters is exactly D. In this paper, we enumerate Dyck paths with this statistic equal to certain values, including all primes. The formulas obtained are in terms of Motzkin numbers and Motzkin ballot numbers.     

Binary bubble languages and cool-lex order

A bubble language is a set of binary strings with a simple closure property: The first 01 of any string can be replaced by 10 to obtain another string in the set. Natural representations of many combinatorial objects are bubble languages. Examples include binary string representations of k-ary trees, unit interval graphs, linear-extensions of B-posets, binary necklaces and Lyndon words, and feasible solutions to knapsack problems. In co-lexicographic order, fixed-weight binary strings are ordered so that their suffixes of the form i¹⁰ occur (recursively) in the order i=max,max−1,…,min+1,min for some values of max and min. In cool-lex order the suffixes occur (recursively) in the order max−1,…,min+1,min,max. This small change has significant consequences. We prove that the strings in any bubble language appear in a Gray code order when listed in cool-lex order. This Gray code may be viewed from two different perspectives. On one hand, successive binary strings differ by one or two transpositions, and on the other hand, they differ by a shift of some substring one position to the right. This article also provides the theoretical foundation for many efficient generation algorithms, as well as the first construction of fixed-weight binary de Bruijn sequences; results that will appear in subsequent articles.     

Clifford-algebraic random walks on the hypercube

The n-dimensional hypercube is a simple graph on 2ⁿ vertices labeled by binary strings, or words, of length n. Pairs of vertices are adjacent if and only if they differ in exactly one position as binary words; i.e., the Hamming distance between the words is one. A discrete-time random walk is easily defined on the hypercube by “flipping” a randomly selected digit from 0 to 1 or vice-versa at each time step. By associating the words as blades in a Clifford algebra of particular signature, combinatorial properties of the geometric product can be used to represent this random walk as a sequence within the algebra. A closed-form formula is revealed which yields probability distributions on the vertices of the hypercube at any time k ≥ 0 by a formal power series expansion of elements in the algebra. Furthermore, by inducing a walk on a larger Clifford algebra, probabilities of self-avoiding walks and expected first hitting times of specific vertices are recovered. Moreover, because the Clifford algebras used in the current work are canonically isomorphic to fermion algebras, everything appearing here can be rewritten using fermion creation/annihilation operators, making the discussion relevant to quantum mechanics and/or quantum computing.     

An O(n log n) algorithm for finding all repetitions in a string

Any nonempty string of the form xx is called a repetition. An O(n log n) algorithm is presented to find all repetitions in a string of lenght n. The algorithm is based on a linear algorithm to find all the new repetitions formed when two strings are concatenated. This linear algorithm is possible because new repetitions of equal length must occur in blocks with consecutive starting positions. The linear algorithm uses a variation of the Knuth-Morris-Pratt algorithm to find all partial occurrences of a pattern within a text string. It is also shown that no algorithm based on comparisons of symbols can improve O(n log n). Finally, some open problems and applications are suggested.     

An algorithm for rescaling a matrix positive definite

For a given square real matrix M, we present a general algorithm which decides the existence of a positive diagonal matrix D such that DM is positive definite and which constructs the D if it exists. It is shown that solving this matrix rescaling problem is equivalent to finding a solution of an infinite system of linear inequalities. The algorithm solves this infinite system of linear inequalities by generating and solving a sequence of linear programs.     

The standard factorization of Lyndon words: an average point of view

A non-empty word w is a Lyndon word if and only if it is strictly smaller for the lexicographical order than any of its proper suffixes. Such a word w is either a letter or admits a standard factorization uv where v is its smallest proper suffix. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is regular and compute explicitly the associated generating function. Next, considering the Lyndon words of length n over a two-letter alphabet, we establish that, for the uniform distribution, the average length of the right factor v of the standard factorization is asymptotically 3n/4.     

On the finite basis problem for certain 2-limited words

Let X* be a free monoid over an alphabet X and W be a finite language over X. Let S(W) be the Rees quotient X*/I(W), where I(W) is the ideal of X* consisting of all elements of X* that are not subwords of W. Then S(W) is a finite monoid with zero and is called the discrete syntactic monoid of W. W is called finitely based if the monoid S(W) is finitely based. In this paper, we give some sufficient conditions for a monoid to be non-finitely based. Using these conditions and other results, we describe all finitely based 2-limited words over a three-element alphabet. Furthermore, an explicit algorithm is given to decide that whether or not a 2-limited word in which there are exactly two non-linear letters is finitely based.