Previous Next Contents

5   Année 2000-2001

   


* 11 septembre An automaton model for user-controlled navigation of the web
  K. Lodaya (The Institute of Mathematical Sciences, Chennai)
  Résumé : We present a simple theoretical model of web navigation, in which each WWW user creates style specifications which constrain web browsing, search and navigation using the user's own judgement of the quality of visited sites. A finite state automaton is associated with each specification, which is presented in a two-level modal logic making up the acceptance condition for the automaton. We show that many interesting queries regarding the user's web search can be answered using standard automata theory.

This is joint work with my colleague R. Ramanujam, and was presented at the Conference on Implementation and Application of Automata (CIAA '00), London, Canada, in July this year.


* 2 Octobre Introduction aux Messages séquences Charts (titre provisoire)
  Pascal Weil


* 5 Octobre (Jeudi 16h -17h30) Méthodes logiques en algorithmique
  Janos Makowski (Haifa)
  Résumé : Définissabilité logique et calculabilité sur les objets finis:
Structures finies, langages logiques du premier et du second ordre; Jeux de Ehrenfeucht et Fraïssé: résultats de non-définissabilité; Définissabilité des langages rationnels; Classe NP et théorème de Fagin.


* 9 Octobre (Lundi 14h - 15h30) Méthodes logiques en algorithmique
  Janos Makowski (Haifa)
  Résumé : Polynômes sur les graphes et leur complexité:
Complexité du calcul du permanent d'une matrice et classe #P; Largeur arborescente, Evaluation efficace du permanent; Applications aux noeuds; Polynômes de Tutte et de Kauffman.


* 12 Octobre (Jeudi 16h-17h30) Méthodes logiques en algorithmique
  Janos Makowski (Haifa)
  Résumé : Décomposition des graphes et des structures, et inductivité de la vérification:
Théorèmes de Fefermann, Vaught et Shelah pour les logiques du premier ordre et du second-ordre monadique; Applications aux structures relationnelles de largeur arborescente bornée; Généralisations et problèmes.


* 23 Octobre Décomposition arborescentes locales - d'aprés M. Grohe
  Bruno Courcelle


* 13 Novembre "Tilling system et hierarchie monadique" d'aprés Matz et Thomas
  David Janin


* 20 Novembre Evaluation exhaustive des requetes en logique monadique du second ordre monadique, d'après Grohe et Flum
  Bruno Courcelle


* 27 Novembre Jeux d'Ehrenfeucht-Fraissé et hierarchie d'alternance de quantificateurs de la logique monadique faible du second-ordre
  Olivier Ly


* 4 Decembre Arbres de Schnyder d'un graphe planaire maximal. Opérations, propriétés et dessins
  Nicolas Bonichon


* 18 Decembre "Tilling system et hierarchie monadique" (suite et fin)
  David Janin


* 8 janvier Décompositions arborescentes de formules du premier ordre d'après M. Grohe
  Bruno Courcelle


* 22 janvier Résolution des jeux de parité par améliorations successives de stratégies
  Aymeric Vincent
  Résumé : Dans un article présenté à CAV'2000, Vöge et Jurdzinski proposent un algorithme permettant de trouver l'ensemble des positions gagnantes pour un joueur dans un jeu de parité en améliorant par étapes une stratégie choisie au départ arbitrairement.

La méthode utilisée fait intervenir des étiquetages de positions sur lesquels existe une relation d'ordre qui permet d'assurer la terminaison de l'algorithme.

Le but de cet exposé est de présenter intuitivement les idées sous-jacentes au papier, afin de pouvoir le lire plus facilement.

L'intérêt pour cet article est motivé par le fait que le problème est dans UP inter co-UP, et que la complexité d'une étape de l'algorithme est polynomiale. La question (ouverte) est donc de savoir si le nombre d'étapes nécessaires pour aboutir à la solution est polynomial ou non.


* 29 janvier Une approche algébrique pour le calcul efficace des positions gagnantes dans les jeux de parité.
  David Janin
  Résumé : Les jeux de parité se trouvent au coeur de la théorie des automates d'arbres infinis et du mu-calcul propositionnel. Cet exposé se propose d'étudier le problème fondamentale encore ouvert sur les jeux de parité : la complexité du calcul des positions gagnantes.

En définissant une relation d'ordre appropriée sur les positions dans les jeux de parité, je montrerais qu'il existe un jeu de parité canonique, dont toutes les positions sont gagnantes, dans lequel se plonge (via l'ordre ci-dessus) toutes les positions gagnantes de tous les jeux de parités.

La relation d'ordre préservant les positions gagnantes et le graphe canonique étant de taille n^d (pour tous jeux à n positions et 2d indices de parité), ce résultat induit un algorithme de calcul des positions gagnantes au moins aussi bon, en termes de complexité, que tous les algorithmes (dont la complexité a été analysé) connus à ce jour.

L'algorithme présenté est-il polynomial de degré borné ? cette question est (actuellement) ouverte.

Par ailleurs, cette approche nouvelle pourrait aussi offrir des critères de décision pour des problèmes classiques du mu-calcul ou de la logique monadique du second ordre sur les arbres (et les graphes modulo dépliage).


* 5 février Logique et Compression
  Michel de Rougemont


* 12 février Dépliages partiels, arbres hyperalgébriques et logique du second-ordre monadique, Travail en cours avec T. Knapik (La Réunion).
  Bruno Courcelle


* 5 mars Dépliages partiels, arbres hyperalgébriques et logique du second-ordre monadique, Travail en cours avec T. Knapik (La Réunion) - La suite.
  Bruno Courcelle


* 12 mars Prédicats morphiques et extensions - Travail en collaboration avec W. Thomas
  Olivier Carton
  Résumé : Nous considérons la structure (N,<,P) des entiers naturels munis de l'ordre, étendue par un prédicat unaire P. Nous montrons que pour un prédicat morphique P, la théorie monadique du second ordre associée MTh(N,<,P) est décidable. Ce résultat étend les résultats précédents de Elgot et Rabin (1966) et Maes (1999). La solution est obtenue par des méthodes de théorie des semigroupes, qui sont reliées à l'approche par automates de Elgot et Rabin. Finalement, nous montrons comment ces méthodes permettent d'obtenir une large classe de prédicats P pour lesquels la théorie MTh(N,<,P) est décidable.


* 19 mars Reconnaissance de graphes par calculs locaux
  Emmanuel Godard
  Résumé : Les calculs locaux sont utilisés pour décrire les algorithmes distribués et consistent en des systèmes de réécriture de graphes. Dans le cadre de l'étude de la puissance et des limitations de ces calculs locaux, on s'intéresse au problème de la reconnaissance qui consiste, pour un réseau, à calculer certaines propriétés topologiques du graphe sous-jacent (être un arbre, planarité, ...). On présentera une caractérisation complète des propriétés reconnaissables par calculs locaux en fonction du degré de connaissance que peut avoir a priori le réseau sur lui-même (nombre de sommets, ...). Cette caractérisation est basée sur l'utilisation de revêtements (morphismes de graphes préservant les propriétés locales) et d'un algorithme d'énumération de sommets proposé par A. Mazurkievicz.


* 26 mars Modularité de l'appel par nécessité pour les systèmes de réécriture de termes orthogonaux.
  Irène Durand
  Résumé : On se place dans le cadre des systèmes de réécritures de termes orthogonaux. Précedemment a été définie une hiérarchie de classes de systèmes de réécriture de termes orthogonaux telle que pour chaque classe:

1- on a une stratégie de réécriture séquentielle optimale et calculable (valable pour tous les systèmes de la classe)
2- on peut décider si un système appartient à la classe

La complexité de décider si un système appartient à une de ces classes étant élevée (exponentielle en bas de la hiérarchie, doublement exponentielle en haut), il est intéressant d´étudier la modularité de l'appartenance à ces classes: "si deux systèmes R1 et R2 appartiennent à la classe C, leur union appartient-t'elle aussi à C?". On montre que ce n'est pas toujours le cas et on donne des conditions suffisantes pour que ce soit le cas.


* 23 avril Graphes infinis et Logique monadique du second ordre
  Téodore Knapik (La Réunion)


Previous Next Contents