Counting minimal semi-Sturmian words

A finite Sturmian   word w$w$ is a balanced word over the binary alphabet {a,b}$\{a,b\}$, that is, for all subwords u$u$ and v$v$ of w$w$ of equal length, |_|u|a−_|v|a|≤1$|{\left|u\right|}_a-{\left|v\right|}_a|\le 1$, where _|u|a${\left|u\right|}_a$ and _|v|a${\left|v\right|}_a$ denote the number of occurrences of the letter a$a$ in u$u$ and v$v$, respectively. There are several other characterizations, some leading to efficient algorithms for testing whether a finite word is Sturmian. These algorithms find important applications in areas such as pattern recognition, image processing, and computer graphics. Recently, Blanchet-Sadri and Lensmire considered finite semi-Sturmian words of minimal length and provided an algorithm for generating all of them using techniques from graph theory. In this paper, we exploit their approach in order to count the number of minimal semi-Sturmian words. We also present some other results that come from applying this graph theoretical framework to subword complexity.     

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.     

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 the permutations generated by Sturmian words

Infinite permutations of use in this article were introduced in [1]. Here we distinguish the class of infinite permutations that are generated by the Sturmian words and inherit their properties. We find the combinatorial complexity of these permutations, describe their Rauzy graphs, frequencies of subpermutations, and recurrence functions. We also find their arithmetic complexity and Kamae complexity.     

Marcus contextual languages consisting of primitive words

In this paper we prove that the language of all primitive (strongly primitive) words over a nontrivial alphabet can be generated by certain types of Marcus contextual grammars.     

Testing primitivity on partial words

Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or not a word is primitive can be done in linear time in the length of the word. Indeed, a word is primitive if and only if it is not an inside factor of its square. In this paper, we describe a linear time algorithm to test primitivity on partial words which are strings that may contain a number of “do not know” symbols. Our algorithm is based on the combinatorial result that under some condition, a partial word is primitive if and only if it is not compatible with an inside factor of its square. The concept of special, related to commutativity on partial words, is foundational in the design of our algorithm. A World Wide Web server interface at http://www.uncg.edu/mat/primitive/ has been established for automated use of the program.     

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.     

Computing the partial word avoidability indices of ternary patterns

We study pattern avoidance in the context of partial words. The problem of classifying the avoidable binary patterns has been solved, so we move on to ternary and more general patterns. Our results, which are based on morphisms (iterated or not), determine all the ternary patternsʼ avoidability indices or at least give bounds for them.     

Generalized periodicity and primitivity for words

Starting from six kinds of periodicity of words we define six sets of words which are primitive in different senses and we investigate their relationships. We show that only three of the sets are external Marcus contextual languages with choice but none of them is an external contextual language without choice or an internal contextual language. For the time complexity of deciding any of our sets by one-tape Turing machines, n ² is a lower bound and this is optimal in two cases. The notions of roots and degrees of words and languages, which are strongly connected to periodicity and primitivity, are also considered, and we show that there can be an arbitrarily large gap between the complexity of a language and that of its roots. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)