ProfessorDenis RichardLaboratoire de Logique, Algoritmique et Informatique (LLAIC) from Clermont-Ferrand, France visited St.Peterburg from 3 to 9 April 1996 and gave the following lectures:

**Thursday, April 4, 11.00 Decidability and complexity of the theory Th(N,*,<**In a paper to appear in the JSL, F. MAURIN proved that the elementary theory of the structure of the natural integers with multiplication and the natural order restricted to primes, is decidable. Also, of course, the elementary theory of multiplication and natural order is undecidable. A natural question which arises from the above results is to determine, among fragments of order "richer" than order restricted to primes, those which, associated with multiplication, lead to undecibable theories. In particular, F.MAURIN asked whether the structure of integers with multiplica- tion and order restricted to powers of primes has a decidable theory. We show that even more restrictive fragments of order (order is restricted to squares of primes for instance) lead to undecidable theory. It means that, surprisingly, there exist two (a priori) very close theory from the point of view of definability (but not a posteriori) which are extending SKOLEM Arithmetic, one being decidable and the other undecidable. At last,we can prove that the structures of integers with divisibility (or multiplication) and order restricted to powers of primes of one hand , and on the other hand, the usual arithmetic (with plus and times) are interdefinable._{p}) and the undecidability of the theory Th(N,*,<_{p2})**Friday, April 5, 11.00 Characterization of integers by finite number of primes****Monday, April 8, 14.00 New algorithms of decidability in weak arithmetics : the NEZONDET p-destinies. Applications and connections with number-theory.**ABSTRACT. One can try to obtain a decision procedure in a theory of sentences expressed in a finite signature of relational symbols and having a bounded number of quantifiers by describing all possible relational configurations (up to isomorphisms). For such a purpose, Francis NEZONDET introduces a special kind of trees : the p-destinies. We shall define them and show how they contain an algorithm of decision for sentences with p quantifiers in a given relational signature. Then we shall present some examples, and specially the theory of sentences with 3 quantifiers in the language of successor and coprimeness. The decision is reduced to 5 questions of number theory attacked both by theoretical means and computer science (namely MAPLE).