A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. An algebra is said to be affine complete if every congruence preserving function is a polynomial function. We show that the algebra of (possibly empty) binary trees whose leaves are labeled by letters of an alphabet containing at least one letter, and the free monoid on an alphabet containing at least two letters are affine complete.

1LIAFA (Université Paris 7) and Université Paris 6, France. E-mail: [email protected]

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

We give a sufficient condition under which the least fixpoint of the equation X=a+f(X)X equals the least fixpoint of the equation X=a+f(a)X. We then apply that condition to recursive logic programs containing chain rules: we translate it into a sufficient condition under which a recursive logic program containing n/spl ges/2 recursive calls in the bodies of the rules is equivalent to a linear program containing at most one recursive call in the bodies of the rules. We conclude with a discussion comparing our condition with the other approaches to linearization studied in the literature.>

We prove that boundedness is decidable for uniformly connected Datalog programs. We study various semantics (cumulative, non-deterministic, well-founded and stratified) for Datalogneg programs. We compare the various boundedness notions for Datalogneg programs according to these semantics and we show that boundedness is undecidable for Datalogneg programs.

The equationally complete proof system for “if-then-else” of Bloom and Tindell (this Journal, 12(1983), pp. 677–707) is extended to a complete proof system for many-sorted algebras with extra operations, predicates and equations among those. We give similar completeness results for continuous algebras and program schemes (infinite trees) by the methods of algebraic semantics. These extensions provide a purely equational proof system to prove properties of functional programs over user-definable data types.