|
|
* 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) |