We describe a multiple string pattern matching algorithm which is well-suited for approximate search and dictionaries composed of words of different lengths. We prove that this algorithm has optimal complexity rate up to a multiplicative constant, for arbitrary dictionaries. This extends to arbitrary dictionaries the classical results of Yao [SIAM J. Comput. 8, 1979], and Chang and Marr [Proc. CPM94, 1994].

Optimal prefix codes are studied for pairs of independent, integer-valued symbols emitted by a source with a geometric probability distribution of parameterq, 0qqcannot be optimal for any other value ofq. This is in sharp contrast to the one-dimensional (1-D) case, where codes are optimal for positive-length intervals of the parameterq. Thus, in the 2-D case, it is infeasible to give a compact characterization of optimal codes for all values of the parameterq, as was done in the 1-D case. Instead, optimal codes are characterized for a discrete sequence of values ofqthat provides good coverage of the unit interval. Specifically, optimal prefix codes are described forq= 2-1/k(k≥ 1), covering the rangeq≥ [1/2], andq= 2-k(k> 1), covering the rangeq<; [1/2]. The described codes produce the expected reduction in redundancy with respect to the 1-D case, while maintaining low-complexity coding operations.

We determine the asymptotic proportion of minimal automata, within n-state accessible deterministic complete automata over a k-letter alphabet, with the uniform distribution over the possible transition structures, and a binomial distribution over terminal states, with arbitrary parameter b. It turns out that a fraction ~ 1-C(k,b) n^{-k+2} of automata is minimal, with C(k,b) a function, explicitly determined, involving the solution of a transcendental equation.

In this article, we provide the multivariate generating function counting texts according to their length and to the number of occurrences of words from a finite set. The application of the inclusion-exclusion principle to word counting due to Goulden and Jackson [1979, 1983] is used to derive the result. Unlike some other techniques which suppose that the set of words is reduced (i.e., where no two words are factor of one another), the finite set can be chosen arbitrarily. Noonan and Zeilberger [1999] already provided a Maple package treating the nonreduced case, without giving an expression of the generating function or a detailed proof. We provide a complete proof validating the use of the inclusion-exclusion principle. Some formulæ for expected values, variance, and covariance for number of occurrences when considering two arbitrary sets of finite words are given as an application of our methodology.

We prove that, for any arbitrary finite alphabet and for the uniform distribution over deterministic and accessible automata with $n$ states, the average complexity of Moore's state minimization algorithm is in $\mathcal{O}(n \log n)$. Moreover this bound is tight in the case of unary automata.

Lossless compression is studied for pairs of independent integer-valued symbols emitted by a source with a geometric probability distribution of parameter q /spl isin/ (0,1). Optimal prefix codes are described for q = 1/2/sup k/ (k > 1) and q = 1/k/spl radic/2 (k > 0). The codes described differ from previously characterized cases related to the geometric distribution in that their corresponding trees are of unbounded width, and in that an infinite set of distinct optimal codes is required to cover any interval (0, /spl epsi/), /spl epsi/ > 0, of values of q.

Lossless compression is studied for pairs of independent, integer-valued symbols emitted by a source with a geometric probability distribution of parameter q, 0k(k > 1) and q = 1/knthroot2 (k > 0). These codes retain some of the low-complexity and low-latency advantage of symbol by symbol coding of geometric distributions, which is widely used in practice, while improving on the inherent redundancy of the approach. From a combinatorial standpoint, the codes described differ from previously characterized cases related to the geometric distribution in that their corresponding trees are of unbounded width, and in that an infinite set of distinct optimal codes is required to cover any interval (0,epsi), epsi > 0, of values of q

The main result is a finite-state version of the Kraft--McMillan theorem characterizing the generating sequence of a k-ary regular tree. The proof uses a new construction called the multiset construction, which is a version with multiplicities of the well-known subset construction of automata theory.