Previous Next Contents

6   Année 1999-2000

Groupe de travail géré par par D. Janin

   


* 4 octobre D. Janin
  Sur la complexité monadique du mu-calcul


* 18 octobre P. Weil
  Automates et rationalité pour les langages série-paralléle et d'autres structures
  Résumé : [résultats obtenus conjointement avec Kamal Lodaya (I. M. Sc., Chennai)]

Dans un travail antérieur, nous avions abordé l'étude des langages de pomsets série-parallèle à l'aide de la notion classique de reconnaissabilité, et en introduisant un modèle d'automates adapté à la manipulation de ces pomsets. Il s'était avéré que la classe des langages acceptés par des automates et celle des langages reconnaissables coïncident sous l'hypothèse de largeur bornée, mais que cela n'est pas le cas en général.

Les résultats qui seront présentés au groupe de travail se situent dans la continuité de ceux qui viennent d'être rappelés. Pour élucider le lien entre reconnaissabilité et automates, nous passons des pomsets série-parallèle aux ``
sS-langages'', c'est-à-dire que nous nous plaçons dans une structure algébrique où coexistent un produit binaire associatif, dit produit séquentiel, et d'autres opérations, dans une signature S fixée, qui ne sont soumises à aucun axiome.

Les automates introduits pour les langages série-parallèle sont étendus à ce cadre plus général et plus libre, et on y démontre l'équivalence entre reconnaissabilité et acceptation par un automate. Une caractérisation par expressions rationnelles peut également être donnée.

L'application de ces résultats aux langages série-parallèle montre d'une part que tout langage série-parallèle reconnaissable est accepté par un automate, et d'autre part que les langages série-parallèle acceptés par des automates sont caractérisés par certaines expressions rationnelles. La question de la clôture par complément des langages série-parallèle acceptés par automate reste ouverte.


* 25 octobre O. Ly
  Problème des bouts pour les graphes automatiques et générations de graphes par substitution
  Résumé : On montre que le nombre de bouts d'un graphe automatique n'est pas calculable. La preuve utilise les notions de machine auto-stabilisante et de graphes des configuration d'une machine de Turing. On établit par ailleurs un lien entre les graphes automatiques et les systèmes de substitution de graphes finis. De façon plus précise, la suite des sphères d'un graphe automatique est générée en itérant une substitution de graphe. On en déduit que le probléme de la connexité des graphes produits en itérant une substitution est indécidable. Nous verrons aussi que le type de substitution considéré ici permet l'émulation des systémes de remplacement d'hyperarcs pour lesquels le problème de la connexité est décidable.


* 8 novembre M. Ykhlef
  Soutenance de thèse


* 29 novembre G. Lenzi
  Une characterization au second ordre des automates de Buchi
  Résumé : Nous considérons la logique monadique du second ordre avec deux fonctions de successeurs, interprétée sur l'arbre binaire. Nous montrons que une propriété est définissable dans le fragment S2 de cette logique si et seulement si elle est définissable par un automate de Büchi. En plus nous montrons que toute propriété définissable dans S2 avec égalité est définissable dans S2 sans égalité aussi.


* 13 decembre B. Courcelle et R. Vanicat
  Representations efficaces de graphes pour l'adjacence et la distance


* 10 janvier V. Dussaux
  Autour des spécifications partielles de dessins plannaires


* 17 janvier B. Courcelle et J. Makowsi
  Operations sur les hypergraphes compatibles avec la logique monadique du 2nd ordre: complementations et fusions de sommets


* 21 février M. Jurdzinski - Varsovie/Aarhus(BRICS)
  On the model-checking problem


* 28 février N. Bonichon
  Algorithme de dessin de graphe planaire en couches


* 6 mars D. janin
  Vers une théorie algébrique des langages d'arbres infinis


* 14 mars Décomposition orthogonale de graphes
  F. Carrere


* 27 mars Logique temporelle avec compteurs et automates
  Hubert COMON (LSV, Cachan)


* 17 avril E. Gioan
  Correspondance entre les orientations et les arbres maximaux d'un graphe : generalisation aux regions et simplexes d'un arrangement d'hyperplans, et aux matroides orientes.
  Résumé : Il s'agit en general d'une correspondance canonique entre les reorientations et les bases d'un matroide oriente, compatible avec les activites. Dans le cas d'un arrangement d'hyperplans (ensemble d'hyperplans d'un espace vectoriel reel), elle se traduit geometriquement par une correspondance entre les regions et les simplexes (par exemple pour un ensemble de droites du plan affine, c'est une correspondance entre les regions et les triangles de la configuration). Plus particulierement dans le cas d'un graphe, on obtient une correspondance entre les orientations et les arbres maximaux. Les activites sont un modele d'etat du polynome de Tutte (ce polynome fondamental a deux variables generalise le polynome chromatique et le polynome des flots de la theorie des graphes, et est lie aussi a l'enumeration des cellules d'un arrangement d'hyperplans).


* 29 mai About graphical control structures for graph grammars
  S. Gruner (Berlin)


* 30 mai (Mardi) Independence: logics and concurrency
  J. Bradfield (Edimburg)
  Résumé : The idea of Henkin's branching quantifiers, in which quantified variables depend on only some of the previous variables, has in recent years been taken up again in logic by Hintikka and Sandu. I will introduce this logic, and then suggest that there is a natural associated modal logic that gives some account of independence in concurrency, but without invoking true concurrent models. I will give examples, define some associated fixpoint logics, and consider some problems of more general fixpoint extensions.


* 5 juin From Atjai-Fagin game to Erenfeucht-Fraissé games and back
  J. Marcinkowski (Wroclav)


* 19 juin Largeur de clique des graphes dénombrables: un résultat de compacité
  B. Courcelle


Previous Next Contents