Professor Denis Richard 
Laboratoire de Logique,
Algoritmique et Informatique (LLAIC) from Clermont-Ferrand,
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
            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).