Prof. Bruno Courcelle

          Application for participation in the EIMI program

                      TETE-A-TETE IN RUSSIA



    I. Western participant(s)
       1) last name...........................COURCELLE
       2) given name(s).......................Bruno
       3) citizenship.........................French
       4) degree, title(s). ..................Doctor in mathematics
          ....................................Professor in Computer Science
       5) affiliation.........................Bordeaux-1 University
       6) position............................Professor (permanent position)
       7) mailing address.................... Bordeaux-1 University, LABRI
                    ..........................351  cours de la Liberation,
                                              33 405 TALENCE cedex,  FRANCE
       8) e-mail address:.....................courcell@labri.u-bordeaux.fr
       9) phone number:           (personal:  (33) 5  56 37 53 62
          ...........................office:  (33) 5  56 84 61 00
      10) FAX number                          (33) 5  56 84 66 69


    II. Russian participant(s)
       1) family name        Matiyasevich
       2) given name         Yurii
       3) patronymic         Vladimirovich
       4) degree, title(s)   Dr. Sc.
       5) affiliation        PDMI RAS
       6) position           Head of Laboratory
       7) mailing address    27, Fontanka
                             POMI RAN
                             St.Petersburg
                             191011 Russia
       8) e-mail address     yumat@pdmi.ras.ru
       9) phone number       7(812)1174392
      10) FAX number         7(812)3105377


   III. Subject and form of proposed joint work (a few phrases):


General topic: Work on power of monadic second order logic for expressing
properties of finite graphs and for defining graph transformations.
Specific problem:
In some cases, equipping the given graph with an arbitrary linear
order helps for expressing its properties. Among such properties are
cardinality of sets modulo fixed integers.
Question is: Are there other
properties requiring auxiliary linear order. Conjecture by Courcelle is YES.


    IV. Desired duration  6  days in the period
        from July 5  to  July 10, 1997