Enumerating words with forbidden factors

This presentation is an exposition of an application of the theory of recurrence relations to enumerating strings over an alphabet with a forbidden factor (consecutive substring). As an illustration we examine the case of binary strings with a forbidden factor of k consecutive symbols 1 for given k, using generating function techniques that deserve to be better known.This allows us to derive a known upper bound for the number of prefix normal binary words: words with the property that no factor has more occurrences of the symbol 1 than the prefix of the same length. Such words arise in the context of indexed binary jumbled pattern matching.     

Congruence preserving functions of Wilke’s tree algebras

As a framework for characterizing families of regular languages of binary trees, Wilke introduced a formalism for defining binary trees that uses six many-sorted operations involving letters, trees and contexts. In this paper a completeness property of these operations is studied. It is shown that all functions involving letters, binary trees and binary contexts which preserve congruence relations of the free tree algebra over an alphabet, are generated by Wilke’s functions, if the alphabet contains at least seven letters. That is to say, the free tree algebra over an alphabet with at least seven letters is affine-complete. The proof yields also a version of the theorem for ordinary one-sorted term algebras: congruence preserving functions on contexts and members of a term algebra are substitution functions, provided that the signature consists of constant and binary function symbols only, and contains at least seven symbols of each rank. Moreover, term algebras over signatures with at least seven constant symbols are affine-complete.Received March 18, 2004; accepted in final form October 8, 2004.     

A stabilization law for two semi-infinite interacting strings of characters

We consider a Markov chain that describes the evolution of two interacting strings of symbols. The transitions probalitities of this Markov chain depend only on the rightmost symbols of both strings. The main goal of the present paper is to prove a limit theorem (stabilization law): the distribution of the rightmost symbols converges to some limit correlation function.1 Partially supported by FAPESP (2002/01501-9) and RFBR (02-01-00415)2 Partially supported by RFBR (02-01-00415)     

一类特殊非齐次树上马氏链的若干强大数定律

首先给出了一类特殊非齐次树上可数状态马氏链的局部收敛定理,作为推论,得到了此类树上可数状态马氏链关于状态与状态序偶出现频率的若干极限性质,最后得到了这类特殊非齐次树上有限状态马氏链关于状态与状态序偶出现频率的强大数定律.     

Hardness results for the center and median string problems under the weighted and unweighted edit distances

Given a finite set of strings, the Median String problem consists in finding a string that minimizes the sum of the edit distances to the strings in the set. Approximations of the median string are used in a very broad range of applications where one needs a representative string that summarizes common information to the strings of the set. It is the case in classification, in speech and pattern recognition, and in computational biology. In the latter, Median String is related to the key problem of multiple alignment. In the recent literature, one finds a theorem stating the NP-completeness of the Median String for unbounded alphabets. However, in the above mentioned areas, the alphabet is often finite. Thus, it remains a crucial question whether the Median String problem is NP-complete for bounded and even binary alphabets. In this work, we provide an answer to this question and also give the complexity of the related Center String problem. Moreover, we study the parameterized complexity of both problems with respect to the number of input strings. In addition, we provide an algorithm to compute an optimal center under a weighted edit distance in polynomial time when the number of input strings is fixed.     

Prefix-primitivity-preserving homomorphisms

This paper aims to investigate homomorphisms which preserve p-primitive languages. A characterization of p-primitivity-preserving homomorphisms can be detected within finite steps. Also the set of square-freeness-preserving homomorphisms is shown to be a proper subfamily of the set of p-primitivity-preserving homomorphisms. For homomorphisms over an alphabet X with |X|=2, it is also shown that the set of p-primitivity-preserving homomorphisms is a proper subfamily of the set of primitivity-preserving homomorphisms. But it is conjectured to also hold for homomorphisms over an alphabet with more than two letters.     

Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)

Many applications call for exhaustive lists of strings subject to various constraints, such as inequivalence under group actions. A k-ary necklace is an equivalence class of k-ary strings under rotation (the cyclic group). A k-ary unlabeled necklace is an equivalence class of k-ary strings under rotation and permutation of alphabet symbols. We present new, fast, simple, recursive algorithms for generating (i.e., listing) all necklaces and binary unlabeled necklaces. These algorithms have optimal running times in the sense that their running times are proportional to the number of necklaces produced. The algorithm for generating necklaces can be used as the basis for efficiently generating many other equivalence classes of strings under rotation and has been applied to generating bracelets, fixed density necklaces, and chord diagrams. As another application, we describe the implementation of a fast algorithm for listing all degree n irreducible and primitive polynomials over GF(2).     

Bethe树和Cayley树上奇偶马尔可夫链场的强极限定理

本文介绍了N元Bethe树TB,N(N元Cayley树TC,N)上的奇偶马尔可夫链场的定义,并通过构造两个非负鞅证得了随机变量序列的强极限定理,应用此强极限定理获得了奇偶马尔可夫链场上的一个强极限定理,作为它的推论得到了状态和状态序偶出现频率的一类强极限定理及其估计,从而推广了关于N元Bethe树上马氏链场和二进树上奇偶马氏链场的部分强极限定理.     

On cyclic strings avoiding a pattern

We count the number of cyclic strings over an alphabet that avoid a single pattern under two different assumptions. In the first case, we assume that the symbols of the alphabet are on numbered positions on a circle, while in the second case we assume that the symbols can be freely rotated on the circle (i.e., we deal with necklaces). In each case, we provide a generating function, and we explain how these two cases are related. For the situation of avoiding more than one pattern, we formulate a general conjecture for the first case, and a conditional result for the second case. We also explain the differences between our theory and the theory of Edlin and Zeilberger (2000) by emphasizing how we modified the definition of the enumeration of cyclic strings that avoid one or more patterns when their lengths are less than the length of the longest pattern.     

Strong laws of large numbers for asymptotic even–odd Markov chains indexed by a homogeneous tree

In this paper, we are going to study the strong laws of large numbers for asymptotic even–odd Markov chains indexed by a homogeneous tree. First, the definition of the asymptotic even–odd Markov chain is introduced. Then the strong limit theorem for asymptotic even–odd Markov chains indexed by a homogeneous tree is established. Next, the strong laws of large numbers for the frequencies of occurrence of states and ordered couple of states for asymptotic even–odd Markov chains indexed by a homogeneous tree are obtained. Finally, we prove the asymptotic equipartition property (AEP) for these Markov chains.     

齐次树上三次循环树指标马氏链的强极限定理

首先给出齐次树上三次循环树指标马氏链的定义,利用构造鞅的方法,研究齐次树上三次循环树指标马氏链的强极限定理,并给出其状态及状态序偶发生频率的强大数定律.     

Upper Limitation of Kolmogorov Complexity and Universal P. Martin-Löf Tests

In this paper we study the Kolmogorov complexity of initial strings in infinite sequences (being inspired by [9]), and we relate it with the theory of P. Martin-Lof random sequences. Working with partial recursive functions instead of recursive functions we can localize on an apriori given recursive set the points where the complexity is small. The relation between Kolmogorov's complexity and P. Martin-Lof's universal tests enables us to show that the randomness theories for finite strings and infinite sequences are not compatible (e.g.because no universal test is sequential).We lay stress upon the fact that we work within the general framework of a non-necessarily binary alphabet.     

Approximating Probability Distributions Using Small Sample Spaces

We formulate the notion of a "good approximation" to a probability distribution over a finite abelian group ?. The quality of the approximating distribution is characterized by a parameter ɛ which is a bound on the difference between corresponding Fourier coefficients of the two distributions. It is also required that the sample space of the approximating distribution be of size polynomial in and 1/ɛ. Such approximations are useful in reducing or eliminating the use of randomness in certain randomized algorithms. We demonstrate the existence of such good approximations to arbitrary distributions. In the case of n random variables distributed uniformly and independently over the range , we provide an efficient construction of a good approximation. The approximation constructed has the property that any linear combination of the random variables (modulo d) has essentially the same behavior under the approximating distribution as it does under the uniform distribution over . Our analysis is based on Weil's character sum estimates. We apply this result to the construction of a non-binary linear code where the alphabet symbols appear almost uniformly in each non-zero code-word. Received: September 22, 1990/Revised: First revision November 11, 1990; last revision November 10, 1997     

广义Bethe树指标可列马氏链场关于广义随机选择系统的一类局部极限定理

研究任意广义Bethe树指标马尔可夫链场二元泛函关于广义随机选择系统的一类局部极限定理.作为推论得到了广义随机选择系统中任意Cayley树上状态频率和状态序偶的一类极限定理.证明中采用了一种研究马尔可夫链场的较新颖的分析方法.     

树上路径过程的随机路径条件概率的极限性质

本文研究了树上路径过程的极限性质.利用构造鞅的方法得到了树上路径过程的条件概率调和平均的极限性质.所得结果推广了树上非齐次马氏链随机转移概率和任意随机变量序列随机条件概率的调和平均极限性质.     

An algebraic approach to the prefix model analysis of binary trie structures and set intersection algorithms

The trie, or digital tree, is a standard data structure for representing sets of strings over a given finite alphabet. Since Knuth's original work (1973), these data structures have been extensively studied and analyzed. In this paper, we present an algebraic approach to the analysis of average storage and average time required by the retrieval algorithms of trie structures under the prefix model. This approach extends the work of Flajolet et al. for other models which, unlike the prefix model, assume that no key in a sample set is the prefix of another. As the main application, we analyze the average running time of two algorithms for computing set intersections.     

Short permutation strings

A permutation string is a string of symbols over the numerals 1, 2, …, n such that all permutations of the string 1 2 … n are subsequences. The search for short permutation strings arose out of studies into the complexity of shortest path algorithms by Karp and others. The results in the sequel are presented independent of such studies because they are felt to be of intrinsic combinatorial interest [1]. An algorithm for constructing permutation strings of length n²−2n+4 is given.     

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.