Given two strings, text t of length n, and pattern p = p1 : : : pk of length k, and given a natural number w, the subsequence matching problem consists in finding the number of size w windows of text t which contain pattern p as a subsequence, i.e. the letters p1 ; : : : ; pk occur in the window, in the same order as in p, but not necessarily consecutively (they may be interleaved with other letters). Subsequence matching is used for finding frequent patterns and association rules in databases. We generalize the Knuth-Morris-Pratt (KMP) pattern matching algorithm; we define a non-conventional kind of RAM, the MP--RAMs which model more closely the microprocessor operations; we design an O(n) on-line algorithm for solving the subsequence matching problem on MP--RAMs. Keywords: Subsequence matching, algorithms, frequent patterns, episode matching, datamining. 1 Introduction We address the following problem. Given a text t of length n and a pattern p = p 1 \\Delta \\Delta \\Delta p k of l...

The purpose of the paper is to present the implications of a new definition of context-free languages. The main interests of this approach are first to allow full formal proofs and second to enlight the crucial role of rational closures. The proposed formalism is based on a theorem of Wechler. It is very near to the “radical algebras” of Conway.

With every language L we associate an increasing function called its rational index. We obtain this function by comparing L with rational languages of increasing complexity. We show that the rational indices of two languages related by a rational transduction are polynomially related. From this, we can define new rational cones of languages in terms of rational indices. We then focus our attention on the rational index of context-free languages and raise several questions closely related to the open problems concerning the subcones of the family of context-free languages.

We give a definition of one-counter languages. We show that the smallest full AFL containing this family is principal with full generator D'@@@@ @@@@, the semi-Dyck language on two letters. We then give without the proof, which shall be published elsewhere, our main result: an iteration theorem for one-counter languages that yields several corollaries.