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

1. Thursday, April 4, 11.00
   
      Decidability and complexity of the theory Th(N,*,<p) and the
      undecidability of the theory Th(N,*,<p2)
   
           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.
   

2. Friday, April 5, 11.00
   
      Characterization of integers by finite number of primes
   
   

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