Practical algorithms to rank necklaces,Lyndon words,and de Bruijn sequences

We present practical algorithms for ranking k-ary necklaces and Lyndon words of length n. The algorithms are based on simple counting techniques. By repeatedly applying the ranking algorithms, both necklaces and Lyndon words can be efficiently unranked. Then, explicit details are given to rank and unrank the length n substrings of the lexicographically smallest de Bruijn sequence of order n.     

On the existence of symmetric chain decompositions in a quotient of the Boolean lattice

We highlight a question about binary necklaces, i.e., equivalence classes of binary strings under rotation. Is there a way to choose representatives of the n-bit necklaces so that the subposet of the Boolean lattice induced by those representatives has a symmetric chain decomposition? Alternatively, is the quotient of the Boolean lattice , under the action of the cyclic group Z_n, a symmetric chain order? The answer is known to be yes for all prime n and for composite n≤18, but otherwise the question appears to be open. In this note we describe how it suffices to focus on subposets induced by necklaces with periodic block codes, substantially reducing the size of the problem. We mention a motivating application: determining whether minimum-region rotationally symmetric independent families of n curves exist for all n.     

Necklaces,symmetries and self-reciprocal polynomials

The connection between a certain class of necklaces and self-reciprocal polynomials over finite fields is shown. For n?2, self-reciprocal polynomials of degree 2n arising from monic irreducible polynomials of degree n are shown to be either irreducible or the product or two irreducible factors which are necessarily reciprocal polynomials. Using DeBruijn's method we count the number of necklaces in this class and hence obtain a formula for the number of irreducible self-reciprocal polynomials showing that they exist for every even degree. Thus every extension of a finite field of even degree can be obtained by adjoining a root of an irreducible self-reciprocal polynomial.     

Necklaces of beads in k colors and k-ary de Bruijn sequences

This paper constructs a decreasing lexicographic list of necklaces of length n in beads of k colors. This list, somewhat modified, produces a k-ary de Bruijn sequence of length kⁿ.     

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.     

String overlaps,pattern matching,and nontransitive games

This paper studies several topics concerning the way strings can overlap. The key notion of the correlation of two strings is introduced, which is a representation of how the second string can overlap into the first. This notion is then used to state and prove a formula for the generating function that enumerates the q-ary strings of length n which contain none of a given finite set of patterns. Various generalizations of this basic result are also discussed. This formula is next used to study a wide variety of seemingly unrelated problems. The first application is to the nontransitive dominance relations arising out of a probabilistic coin-tossing game. Another application shows that no algorithm can check for the presence of a given pattern in a text without examining essentially all characters of the text in the worst case. Finally, a class of polynomials arising in connection with the main result are shown to be irreducible.     

How much is that DAWG in the window? a moving window algorithm for the directed acyclic word graph

There is a class of data compression techniques that involve replacing repeating strings by pointers to previous occurrences of those strings. In order to implement these techniques, it would be useful to have an index which can quickly locate repeats within a fixed window of the text seen so far. One such index is the directed acyclic word graph (DAWG). An algorithm is presented which constructs the DAWG for a fixed window of k letters moving from left to right along the input text. It is shown that this algorithm has worst case behavior proportional to nk, where n is the length of the input text and k is the size of the window. This bound is the best possible for a window moving through the DAWG and also for a window moving through the suffix tree, a functionally related structure. The average case for the algorithm is analyzed under the assumption that input strings are random texts constructed from a fixed alphabet where each letter has equal probability. The resulting upper bound is O(nlogk).     

Efficient generation of super condensed neighborhoods

Indexing methods for the approximate string matching problem spend a considerable effort generating condensed neighborhoods. Condensed neighborhoods, however, are not a minimal representation of a pattern neighborhood. Super condensed neighborhoods, proposed in this work, are smaller, provably minimal and can be used to locate approximate matches that can later be extended by on-line search. We present an algorithm for generating Super Condensed Neighborhoods. The algorithm can be implemented either by using dynamic programming or non-deterministic automata. The time complexity is O(ms) for the first case and O(kms) for the second, where m is the pattern size, s is the size of the super condensed neighborhood and k the number of errors. Previous algorithms depended on the size of the condensed neighborhood instead. These algorithms can be implemented using Bit-Parallelism and Increased Bit-Parallelism techniques. Our experimental results show that the resulting algorithms are fast and achieve significant speedups, when compared with the existing proposals that use condensed neighborhoods.     

Lexicographic compositions and deBruijn sequences

In this paper we give an algorithm to generate a new deBruijn sequence. The amount of storage required is only linear in n, the span of the sequence. We make use of the lexicographic compositions of a positive integer which we relate to binary necklaces of beads in two colors. We give a fast algorithm for generating the necklaces. Finally we relate the deBruijn sequence we generate to another sequence.     

A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk²(logn+klogk)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomial-time algorithm with running time O(nk²log²n).     

Counting Finite Lattices

The correct values for the number of all unlabeled lattices on n elements are known for . We present a fast orderly algorithm generating all unlabeled lattices up to a given size n. Using this algorithm, we have computed the number of all unlabeled lattices as well as that of all labeled lattices on an n-element set for each . Received April 4, 2000; accepted in final form November 2, 2001. RID="h1" ID="h1" Presented by R. Freese.     

Fast,Practical Algorithms for Computing All the Repeats in a String

Given a string x = x[1..n] on an alphabet of size α, and a threshold p _min ≥ 1, we describe four variants of an algorithm PSY1 that, using a suffix array, computes all the complete nonextendible repeats in x of length p ≥ p _min . The basic algorithm PSY1–1 and its simple extension PSY1–2 are fast on strings that occur in biological, natural language and other applications (not highly periodic strings), while PSY1–3 guarantees Θ(n) worst-case execution time. The final variant, PSY1–4, also achieves Θ(n) processing time and, over the complete range of strings tested, is the fastest of the four. The space requirement of all four algorithms is about 5n bytes, but all make use of the “longest common prefix” (LCP) array, whose construction requires about 6n bytes. The four algorithms are faster in applications and use less space than a recently-proposed algorithm (Narisawa in Proceedings of 18th Annual Symposium on Combinatorial Pattern Matching, pp. 340–351, 2007) that produces equivalent output. The suffix array is not explicitly used by algorithms PSY1, but may be required for postprocessing; in this case, storage requirements rise to 9n bytes. We also describe two variants of a fast Θ(n)-time algorithm PSY2 for computing all complete supernonextendible repeats in x.     

New constructions for De Bruijn tori

A De Bruijn torus is a periodicd-dimensionalk-ary array such that eachn ₁ × ... ×n _d k-ary array appears exactly once with the same period. We describe two new methods of constructing such arrays. The first is a type of product that constructs ak ₁ k ₂ -ary torus from ak ₁ -ary torus and ak ₂ -ary torus. The second uses a decomposition of ad-dimensional torus to produce ad+1 dimensional torus. Both constructions will produce two dimensionalk-ary tori for which the period is not a power ofk. In particular, for and for all natural numbers (n ₁ , n ₂ ), we construct 2-dimensionalk-ary De Bruijn tori with order n ₁ , n ₂ and period where .Dedicated to the memory of Tony BrewsterPartially supported by NSF grant DMS-9201467Partially supported by a grant from the Reidler Foundation     

Partially Ordered Generalized Patterns and <Emphasis Type="Italic">k</Emphasis>-ary Words

Recently, Kitaev [9] introduced partially ordered generalized patterns (POGPs) in the symmetric group, which further generalize the generalized permutation patterns introduced by Babson and Steingrímsson [1]. A POGP p is a GP some of whose letters are incomparable. In this paper, we study the generating functions (g.f.) for the number of k-ary words avoiding some POGPs. We give analogues, extend and generalize several known results, as well as get some new results. In particular, we give the g.f. for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes (which is allowed to have repetition of letters), provided we know the g.f. for the number of k-ary words that avoid p.AMS Subject Classification: 05A05, 05A15.     

DC-NMF: nonnegative matrix factorization based on divide-and-conquer for fast clustering and topic modeling

The importance of unsupervised clustering and topic modeling is well recognized with ever-increasing volumes of text data available from numerous sources. Nonnegative matrix factorization (NMF) has proven to be a successful method for cluster and topic discovery in unlabeled data sets. In this paper, we propose a fast algorithm for computing NMF using a divide-and-conquer strategy, called DC-NMF. Given an input matrix where the columns represent data items, we build a binary tree structure of the data items using a recently-proposed efficient algorithm for computing rank-2 NMF, and then gather information from the tree to initialize the rank-k NMF, which needs only a few iterations to reach a desired solution. We also investigate various criteria for selecting the node to split when growing the tree. We demonstrate the scalability of our algorithm for computing general rank-k NMF as well as its effectiveness in clustering and topic modeling for large-scale text data sets, by comparing it to other frequently utilized state-of-the-art algorithms. The value of the proposed approach lies in the highly efficient and accurate method for initializing rank-k NMF and the scalability achieved from the divide-and-conquer approach of the algorithm and properties of rank-2 NMF. In summary, we present efficient tools for analyzing large-scale data sets, and techniques that can be generalized to many other data analytics problem domains along with an open-source software library called SmallK.     

A Generalization of n-Ary Algebraic Systems

One of the aims of this article is to extract, whenever possible, the common elements of several seemingly different types of algebraic hypersystems. In achieving this, one discovers general concepts, constructions, and results which not only generalize and unify the known special situations, thus leading to an economy of presentation, but, being at a higher level of abstraction, can also be applied to entirely new situations, yielding significant information and giving rise to new directions. We shall consider a class of algebraic hypersystems which represent a generalization of semigroups, hypersemigroups, and n-ary semigroups. This new class of hypersystems is called n-ary hypersemigroups and properties of such hypersemigroups are investigated. On an n-ary hypersemigroup, we describe the smallest equivalence relation β* whose quotient is an ordinary n-ary semigroup.     

The braid group of a necklace

We show several geometric and algebraic aspects of a necklace: a link composed with a core circle and a series of (unlinked) circles linked to this core. We first prove that the fundamental group of the configuration space of necklaces (that we will call braid group of a necklace) is isomorphic to the braid group over an annulus quotiented by the square of the center. We then define braid groups of necklaces and affine braid groups of type \(\mathcal {A}\) in terms of automorphisms of free groups and characterize these automorphisms among all automorphisms of free groups. In the case of affine braid groups of type \(\mathcal {A}\) such a representation is faithful.     

Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height

In this paper, the author gives the exact counting of unlabeled rigid interval posets regarding or disregarding the height by using generating functions. The counting technique follows those introduced in El-Zahar (1989), Hanlon (Trans Amer Math Soc 272:383?C426, 1982), Khamis (Discrete Math 275:165?C175, 2004). The main advantage of the suggested technique is that a very simple recursive construction of unlabeled rigid interval poset from small ones leads to derive the given generating function for unlabeled rigid interval posets whose coefficients can be easily computed. Moreover, it is proven that the sets of n-element unlabeled rigid interval posets and upper triangular 0?C1 matrices with n ones and no zero rows or columns are in one-to-one correspondence. In addition, n-element unlabeled interval posets are counted for n????1, using the given generating function for rigid ones. Upper and lower bounds for the number of n-element unlabeled rigid interval posets are given. Also, an asymptotic estimate for the required numbers is obtained. Numerical results for unlabeled interval posets coincide with those given in El-Zahar (1989) and Khamis (Discrete Math 275:165?C175, 2004). The exact numbers of n-element unlabeled rigid and general interval posets with and without height k are included, for 1????k????n????15.     

Clique matchings in the <Emphasis Type="Italic">k</Emphasis>-ary <Emphasis Type="Italic">n</Emphasis>-dimensional cube

A clique matching in the k-ary n-dimensional cube (hypercube) is a collection of disjoint one-dimensional faces. A clique matching is called perfect if it covers all vertices of the hypercube. We show that the number of perfect clique matchings in the k-ary n-dimensional cube can be expressed as the k-dimensional permanent of the adjacency array of some hypergraph. We calculate the order of the logarithm of the number of perfect clique matchings in the k-ary n-dimensional cube for an arbitrary positive integer k as n→∞.