Patrick Cegielski

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 . Subsequence matching is used for finding frequent patterns and association rules in databases. We generalize the Knuth–Morris–Pratt 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 on-line algorithm for solving the subsequence matching problem on MP-RAMs

Let M be a first-order structure; we denote by DEF(M) the set of all first-order definable relations and functions within M. Let π be any one-to-one function from N into the set of prime integers. Let ∣ and $\bullet$ be respectively the divisibility relation and multiplication as function. We show that the sets DEF(N,π,∣) and $\mathrm{DEF}(\mathbb{N},\pi,\bullet)$ are equal. However there exists function π such that the set DEF(N,π,∣), or, equivalently, $\mathrm{DEF}(\mathbb{N},\pi,\bullet)$ is not equal to $\mathrm{DEF}(\mathbb{N},+,\bullet)$ . Nevertheless, in all cases there is an $\{\pi,\bullet\}$ -definable and hence also {π,∣}-definable structure over N which is isomorphic to $\langle\mathbb{N},+,\bullet\rangle$ . Hence theories TH(N,π,∣) and $\mathrm{TH}(\mathbb{N},\pi,\bullet)$ are undecidable. The binary relation of equipotence between two positive integers saying that they have equal number of prime divisors is not definable within the divisibility lattice over positive integers. We prove it first by comparing the lower bound of the computational complexity of the additive theory of positive integers and of the upper bound of the computational complexity of the theory of the mentioned lattice. The last section provides a self-contained alternative proof of this latter result based on a decision method linked to an elimination of quantifiers via specific tables