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.     

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.     

The coolest way to generate combinations

We present a practical and elegant method for generating all (s,t)-combinations (binary strings with s zeros and t ones): Identify the shortest prefix ending in 010 or 011 (or the entire string if no such prefix exists), and rotate it by one position to the right. This iterative rule gives an order to (s,t)-combinations that is circular and genlex. Moreover, the rotated portion of the string always contains at most four contiguous runs of zeros and ones, so every iteration can be achieved by transposing at most two pairs of bits. This leads to an efficient loopless and branchless implementation that consists only of two variables and six assignment statements. The order also has a number of striking similarities to colex order, especially its recursive definition and ranking algorithm. In the light of these similarities we have named our order cool-lex!     

Prefix and suffix transreversals on binary and ternary strings

The problem of sorting by a genome rearrangement event asks for the minimum number of that event required to sort the elements of a given permutation. In this paper, we study a variant of the rearrangement event called prefix and suffix transreversal. A transreversal is an operation which reverses the first block before exchanging two adjacent blocks in a permutation. A prefix (suffix) transreversal always reverses and moves a prefix (suffix) of the permutation to another location. Interestingly, we will apply transreversal not on permutations but on strings over an alphabet of fixed size. We determine the minimum number of prefix and suffix transreversals required to sort the binary and ternary strings, with polynomial time algorithms for these sorting problems.     

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

Circular-imperfection of triangle-free graphs

Circular-perfect graphs form a natural superclass of the well-known perfect graphs by means of a more general coloring concept.For perfect graphs, a characterization by means of forbidden subgraphs was recently settled by Chudnovsky et al. [Chudnovsky, M., N. Robertson, P. Seymour, and R. Thomas, The Strong Perfect Graph Theorem, Annals of Mathematics 164 (2006) 51–229]. It is, therefore, natural to ask for an analogous characterization for circular-perfect graphs or, equivalently, for a characterization of all minimally circular-imperfect graphs.Our focus is the circular-(im)perfection of triangle-free graphs. We exhibit several different new infinite families of minimally circular-imperfect triangle-free graphs. This shows that a characterization of circular-perfect graphs by means of forbidden subgraphs is a difficult task, even if restricted to the class of triangle-free graphs. This is in contrary to the perfect case where it is long-time known that the only minimally imperfect triangle-free graphs are the odd holes [Tucker, A., Critical Perfect Graphs and Perfect 3-chromatic Graphs, J. Combin. Theory (B) 23 (1977) 143–149].     

A combinatorial approach to binary positional number systems

Although the representation of the real numbers in terms of a base and a set of digits has a long history, new questions arise even in the binary case – digits 0 and 1. A binary positional number system (binary radix system) with base equal to the golden ratio \((1+\sqrt{5}\,)/2\) is fairly well known. The main result of this paper is a construction of infinitely many binary radix systems, each one constructed combinatorially from a single pair of binary strings. Every binary radix system that satisfies even a minimal set of conditions that would be expected of a positional number system, can be constructed in this way.     

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.     

Clique-perfectness of complements of line graphs

The clique-transversal number τ_c(G) of a graph G is the minimum size of a set of vertices meeting all the cliques. The clique-independence number α_c(G) of G is the maximum size of a collection of vertex-disjoint cliques. A graph is clique-perfect if these two numbers are equal for every induced subgraph of G. Unlike perfect graphs, the class of clique-perfect graphs is not closed under graph complementation nor is a characterization by forbidden induced subgraphs known. Nevertheless, partial results in this direction have been obtained. For instance, in [Bonomo, F., M. Chudnovsky and G. Durán, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Discrete Appl. Math. 156 (2008), pp. 1058–1082], a characterization of those line graphs that are clique-perfect is given in terms of minimal forbidden induced subgraphs. Our main result is a characterization of those complements of line graphs that are clique-perfect, also by means of minimal forbidden induced subgraphs. This implies an O(n²) time algorithm for deciding the clique-perfectness of complements of line graphs and, for those that are clique-perfect, finding α_c and τ_c.     

On the Enumeration of Non-Crossing Pairings of Well-Balanced Binary Strings

A non-crossing pairing on a binary string pairs ones and zeroes such that the arcs representing the pairings are non-crossing. A binary string is well-balanced if it is of the form ${1^{a_1} 0^{a_1}1^{a_2} 0^{a_2} . . .1^{a_r} 0^{a_r}}$ . In this paper we establish connections between non-crossing pairings of well-balanced binary strings and various lattice paths in plane. We show that for well-balanced binary strings with a ₁ ≤ a ₂ ≤  . . . ≤  a _r , the number of non-crossing pairings is equal to the number of lattice paths on the plane with certain right boundary, and hence can be enumerated by differential Goncarov polynomials. For the regular binary strings S =  (1 ^k 0 ^k ) ⁿ , the number of non-crossing pairings is given by the (k + 1)-Catalan numbers. We present a simple bijective proof for this case.     

Are binary codings universal?

It is common sense to notice that one needs fewer digits to code numbers in ternary than in binary; new names are about log₃2 times shorter. Is this trade-off a consequence of the special coding scheme? The answer is negative. More generally, we argue that the answer to the question, stated in the title and formulated to the first author by C. Rackhoff, is in fact negative. The conclusion will be achieved by studying the role of the size of the alphabet in constructing instantaneous codes for all natural numbers, and defining random strings and sequences. We show that there is no optimal instantaneous code for all positive integers, and the binary is the worst possible. Codes over a fixed alphabet can be indefinitely improved themselves, but only “slightly”; in contrast, changing the size of the alphabet determines a significant, not linear, improvement. The key relation describing the above phenomenon can be expressed in terms of Chaitin complexity: changing the size of the coding alphabet from q to Q, 2 ≤ q < Q, results in an improvement of the complexity by a factor og log q. As a consequence, a string avoiding consistently a fixed letter is not random. In binary, this corresponds to a trivial situation. In the nonbinary case the distinction is relevant: more than 3.2ⁿ ternary strings of length n are not random (many of these strings are binary random). This phenomenon is even sharper for infinite sequences.     

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.     

Minimal string difference encodings

Given two strings s and t, a difference encoding is a third string that contains sufficient information to derivet t from s. An algorithm is presented which derives a difference encoding that can be represented in the fewest number of bits relative to the string edit operators insert, delete, replace, and skip. This algorithm has practical significance for distributed text processing applications.     

An Iterative Approach to Determining the Length of the Longest Common Subsequence of Two Strings

This paper concerns the longest common subsequence (LCS) shared by two sequences (or strings) of length N, whose elements are chosen at random from a finite alphabet. The exact distribution and the expected value of the length of the LCS, k say, between two random sequences is still an open problem in applied probability. While the expected value E(N) of the length of the LCS of two random strings is known to lie within certain limits, the exact value of E(N) and the exact distribution are unknown. In this paper, we calculate the length of the LCS for all possible pairs of binary sequences from N=1 to 14. The length of the LCS and the Hamming distance are represented in color on two all-against-all arrays. An iterative approach is then introduced in which we determine the pairs of sequences whose LCS lengths increased by one upon the addition of one letter to each sequence. The pairs whose score did increase are shown in black and white on an array, which has an interesting fractal-like structure. As the sequence length increases, R(N) (the proportion of sequences whose score increased) approaches the Chvátal–Sankoff constant a _c (the proportionality constant for the linear growth of the expected length of the LCS with sequence length). We show that R(N) is converging more rapidly to a _c than E(N)/N.     

Pure elements and intertwining classes of simple strata in local central simple algebras

Let S be a semigroup of words over an alphabet ∑ . Suppose tliar every two words u and e over ∑ are equal in S if (1) the sets of subwords of length k of the words a and b coincide and are non-empty. (2) the prefix (suffix) of u of length k1 is equal to the prefix (suffix) of e. Then S is called k-testable. A semigroup is locally testable if it is k-testable for some k > 0.

We present a finite basis of identities of the variety of A'-testable semigroups. The structure of k-testable semigroup is studied. Necessarv and sufficient conditions for local testability will be given. A solution to one problem from the survey of Shevrin and Sukhanov (1985) will be presented.     

Odd and even hamming spheres also have minimum boundary

Combinatorial problems with a geometric flavor arise if the set of all binary sequences of a fixed length n, is provided with the Hamming distance. The Hamming distance of any two binary sequences is the number of positions in which they differ. The (outer) boundary of a set A of binary sequences is the set of all sequences outside A that are at distance 1 from some sequence in A. Harper [6] proved that among all the sets of a prescribed volume, the ‘sphere’ has minimum boundary.We show that among all the sets in which no pair of sequences have distance 1, the set of all the sequences with an even (odd) number of 1's in a Hamming ‘sphere’ has the same minimizing property. Some related results are obtained. Sets with more general extremal properties of this kind yield good error-correcting codes for multi-terminal channels.     

Two-pattern strings II—frequency of occurrence and substring complexity

The previous paper in this series introduced a class of infinite binary strings, called two-pattern strings, that constitute a significant generalization of, and include, the much-studied Sturmian strings. The class of two-pattern strings is a union of a sequence of increasing (with respect to inclusion) subclasses T_λ of two-pattern strings of scope λ, λ=1,2,…. Prefixes of two-pattern strings are interesting from the algorithmic point of view (their recognition, generation, and computation of repetitions and near-repetitions) and since they include prefixes of the Fibonacci and the Sturmian strings, they merit investigation of how many finite two-pattern strings of a given size there are among all binary strings of the same length. In this paper we first consider the frequency f_λ(n) of occurrence of two-pattern strings of length n and scope λ among all strings of length n on {a,b}: we show that lim_n→∞f_λ(n)=0, but that for strings of lengths n2λ, two-pattern strings of scope λ constitute more than one-quarter of all strings. Since the class of Sturmian strings is a subset of two-pattern strings of scope 1, it was natural to focus the study of the substring complexity of two-pattern strings to those of scope 1. Though preserving the aperiodicity of the Sturmian strings, the generalization to two-pattern strings greatly relaxes the constrained substring complexity (the number of distinct substrings of the same length) of the Sturmian strings. We derive upper and lower bounds on C₁(k) (the number of distinct substring of length k) of two-pattern strings of scope 1, and we show that it can be considerably greater than that of a Sturmian string. In fact, we describe circumstances in which lim_k→∞(C₁(k)−k)=∞.     

The Euler circuit theorem for binary matroids

It is proved that, if M is a binary matroid, then every cocircuit of M has even cardinality if and only if M can be obtained by contracting some other binary matroid M⁺ onto a single circuit. This is the natural analog of the Euler circuit theorem for graphs. It is also proved that every coloop-free matroid can be obtained by contracting some other matroid (not in general binary) onto a single circuit.     

Spectral boundary controllability of networks of strings

In this Note we give a necessary and sufficient condition for the spectral controllability from one simple node of a general network of strings that undergoes transversal vibrations in a sufficiently large time. This condition asserts that no eigenfunction vanishes identically on the string that contains the controlled node. The proof combines the Beurling–Malliavin's theorem and an asymptotic formula for the eigenvalues of the network. The optimal control time may be characterized as twice the sum of the lengths of all the strings of the network. To cite this article: R. Dáger, E. Zuazua, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 545–550.     

The lexicographically smallest universal cycle for binary strings with minimum specified weight

H. Fredricksen, I.J. Kessler and J. Maiorana discovered a simple but elegant construction of a universal cycle for binary strings of length n: Concatenate the aperiodic prefixes of length n binary necklaces in lexicographic order. We generalize their construction to binary strings of length n whose weights are in the range $c,c+1,\dots ,n$ by simply omitting the necklaces with weight less than c. We also provide an efficient algorithm that generates the universal cycles in constant amortized time per bit using $O(n)$ space. Our universal cycles have the property of being the lexicographically smallest universal cycle for the set of binary strings of length n with weight ≥c.