SIF
Séminaire d'Informatique Fondamentale



VENDREDI 15 AVRIL à 15 h 15
Salle 200 - batiment A33

(batiment de Mathématiques)



Fabien Jourdan

(LIRMM - Université Montpellier)


Visualisation d'information : dessin, indices structuraux et navigation.

RESUME:

L'objectif des méthodes de visualisation d'information est d'aider l'utilisateur dans son exploration ou analyse des données. Pour cela, la visualisation exploite les capacités de traitement du système visuel humain, en proposant des représentations interactives de l'information. La recherche de nouvelles méthodes et techniques de représentation et d'interaction est d'autant plus nécessaire que le flux de nouvelles données à analyser et comprendre va croissant. Notamment en biologie, où le séquençage du génome et la systématisation des expérimentations automatiques fournissent des centaines de milliers d'éléments de données.

La visualisation de données mutli-dimensionnelles est un problème très étudié en visualisation d'information. Dans ces données, chaque élément est associé à un ensemble d'attributs numériques (par exemple des données financières : débit, crédit ...). L'objectif des méthodes dites de mise à l'échelle (Multi Dimensional Scaling) est de plonger ces données dans un espace en deux ou trois dimensions. Plus précisément les méthodes MDS visent à corréler les similarités entre les éléments (proximité des attributs) avec des distances dans l'espace de plongement. Pour intégrer ce calcul à un outil de visualisation il faut pouvoir trouver un plongement satisfaisant dans des temps raisonables (moins que quadratiques). Nous verrons comment réduire ce temps de calcul dans des heuristiques basées sur une analogie physique.

Cette approche MDS a été utilisée dans de nombreux domaines, notamment pour l'analyse financière. Actuellement les applications à la biologie se multiplient, notamment dans des outils de visualisation dédiés à la classification. En particulier quand une ditance peut être caculée entre chaque paire d'éléments (par exemple pour des abres phylogénétiques).

Pour tout renseignement sur le SIF:
hanusse@labri.u-bordeaux.fr

Programme


Résumé des exposés

Fabien Jourdan (LIRMM - Université Montpellier) Visualisation d'information : dessin, indices structuraux et navigation.

L'objectif des méthodes de visualisation d'information est d'aider l'utilisateur dans son exploration ou analyse des données. Pour cela, la visualisation exploite les capacités de traitement du système visuel humain, en proposant des représentations interactives de l'information. La recherche de nouvelles méthodes et techniques de représentation et d'interaction est d'autant plus nécessaire que le flux de nouvelles données à analyser et comprendre va croissant. Notamment en biologie, où le séquençage du génome et la systématisation des expérimentations automatiques fournissent des centaines de milliers d'éléments de données.

La visualisation de données mutli-dimensionnelles est un problème très étudié en visualisation d'information. Dans ces données, chaque élément est associé à un ensemble d'attributs numériques (par exemple des données financières : débit, crédit ...). L'objectif des méthodes dites de mise à l'échelle (Multi Dimensional Scaling) est de plonger ces données dans un espace en deux ou trois dimensions. Plus précisément les méthodes MDS visent à corréler les similarités entre les éléments (proximité des attributs) avec des distances dans l'espace de plongement. Pour intégrer ce calcul à un outil de visualisation il faut pouvoir trouver un plongement satisfaisant dans des temps raisonables (moins que quadratiques). Nous verrons comment réduire ce temps de calcul dans des heuristiques basées sur une analogie physique.

Cette approche MDS a été utilisée dans de nombreux domaines, notamment pour l'analyse financière. Actuellement les applications à la biologie se multiplient, notamment dans des outils de visualisation dédiés à la classification. En particulier quand une ditance peut être caculée entre chaque paire d'éléments (par exemple pour des abres phylogénétiques).


Arnaud Durand (LACL - Université Paris XII - Créteil) Évaluation de requêtes sur structures fonctionnelles

Travail en commun avec Etienne Grandjean (Caen)
Dans cet exposé, on s'intéresse à la complexité de l'évaluation de requêtes dans les bases de données. On commencera par rappeler la problématique générale et des résultats du domaine. Puis, on introduira un langage de requêtes basé sur la logique du premier-ordre utilisant des fonctions unaires. Les formules de ce langage peuvent-être vues (entre autres mais pas seulement) comme exprimant des contraintes avec l'égalité ('='), l'inégalité ('!=') ou des comparaisons ('<' ou '>') sur les attributs (i.e. fonctions de projection) d'un ensemble de tuples.
On exhibe ensuite une notion de requêtes acycliques analogue à celle introduite dans les BD relationnelles dans les années 80 mais basée sur des notions de graphes et plus d'hypergraphes. Puis, on montre que toute requête acyclique est évaluable en temps f(|Q|).|BD|.|Q(BD)| où f(|Q|) est une fonction en la taille de la requête, |BD| est la taille de la base de données et |Q(BD)| la taille du résultat de la requête (la valeur précise de la fonction 'f' dépendant du fragment du langage considéré).
Ces résultats ont deux applications principales. La première est, qu'en se replaçant dans le contexte des BD "classiques" on améliore quelque peu les bornes de complexité prouvées pour les analogues relationnelles de ces classes de requêtes. La seconde applications est que ce langage fournit un cadre uniforme pour exprimer un certain nombre de problèmes algorithmiques classiques : problème du sous-graphe acyclique, couplage multi-dimensionnel, etc... Là aussi, dans certains cas, les résultats permettent de retrouver ou améliorer les bornes existantes.
Enfin on discutera des extensions possibles de ce travail aux requêtes de largeurs d'arborescence bornées ainsi qu'à l'interrogation de document XML.

Gwenael Richomme (LaRIA - Université de Picardie) Morphismes et mots de Lyndon

Les mots (finis ou infinis) de Lyndon sont les mots plus petits dans l'ordre lexicographique que leurs suffixes propres. Plusieurs études autour de ces mots font usage de morphismes de monoïdes libres ayant des propriétés particulières comme la préservation des mots de Lyndon ou de l'ordre lexicographique. Nous présentons des caractérisations de ces morphismes et montrons des relations entre ces différents morphismes. Quelques applications sont également abordées en particulier pour la décomposition en mots de Lyndon de certains mots infinis.

Christian Toinard (LIFO - Université d'Orléans) Sécurité des systèmes à large échelle et intérêt des approches formelles

L'exposé présentera les travaux menés à Bourges en sécurité dans le cadre du LIFO. Il présentera les solutions mises en oeuvre et les perspectives en matière d'approches formelles.
Le contexte du travail est la sécurité des systèmes à très large échelle et à très haut débit notamment celle des clusters de calcul. Nous présentons d'abord une solution de gestion d'une politique de sécurité qui permet des mises à jour entièrement réparties de la politique. Cette solution est basée sur une méthode de déploiement pour des systèmes permettant du Mandatory Access Control. Cette technique est ouverte sur des techniques de preuves de propriétés qui sont développées dans le cadre de l'ACI SATIN. Ensuite, nous exposons une nouvelle architecture de détection d'intrusion qui se base sur une politique répartie et permet de détecter des attaques potentielles de la politique. Cette solution permet une intégration d'outils classiques de détection d'intrusion. Elle offre des perspectives en matière de preuves et de techniques statistiques d'apprentissage et de fouille de données.

Emeric Gioan (Université de Nice) Dessins de graphes et codage des perspectives sur les graphes spatiaux

D'abord, il s'agit d'etudier les dessins de graphes avec une structure logique concise intermediaire entre la carte (qui determine le dessin d'un graphe planaire) et le sketch de Bruno Courcelle (qui determine le dessin en general). Ici on retient quelles aretes se coupent mais pas l'ordre des croisements. Pour un graphe complet cela determine le dessin a une suite de mutations de triangles pres que l'on sait calculer.
En particulier, cela s'applique aux projections de graphes spatiaux codes par des matroides orientes (un m.o. est une structure combinatoire qui donne les positions relatives des points, sans tenir compte des distances). L'inconvenient de ce codage est son volume (n4 signes de determinants au pire) mais son avantage est que, une fois la structure memorisee, de nombreuses informations s'en deduisent et des modifications s'y font tres simplement.
Finalement on a un codage combinatoire a deux niveaux de la visualisation en perspective des graphes spatiaux : lorsque le point de vue est coince dans les plans de la configuration, le m.o. ne change pas et seuls des triangles mutent, et lorsque le point de vue traverse un plan, seuls certains signes changent dans le m.o.

Frédéric Mazoit (Université de Nantes) Décompositions en branches et graphes planaires

Dans leur longue série d'articles sur les mineurs de graphes, Robertson et Seymour on défini une nouvelle classe de décompositions des graphes -- les décompositions en branches -- pour obtenir une obstruction aux décompositions arborescente. Cette obstruction a permis à Seymour et Thomas, en calculant exactement la largeur de branches des graphes planaires, de donner la meilleure approximation de la largeur arborescente des graphes planaires.
Je montrerai comment unifier ces deux types de décompositions à l'aide d'un nouvel objet combinatoire: les matriochkas. Ces matriochkas permettent de mieux comprendre les liens mais aussi les différences entre les décompositions arborescentes et les décompositions en branches. En les utilisant, il est aussi possible de transférer des résultats d'une des décompositions à l'autre. Je présenterai une nouvelle démonstration du fait que la largeur arborescente d'un graphe planaire et celle de son dual diffèrent au plus d'un, démonstration que j'ai obtenue de cette façon.

Dominique Perrin (IGM - Université de Marne-la-vallée) Codes et systèmes sofiques

Cet expose cherche a montrer comment on peut généraliser au cas des sytèmes dynamiques symboliques la plupart des notions et résultats de la combinatoire des mots. On rappellera d'abord la terminologie de la dynamique symbolique. Nous établissons d'abord une généralisation de l'inégalité de Kraft-McMillan pour des codes dans des systèmes sofiques. Le cas d'égalité correspond à des codes qui sont complets au sens que tout bloc admissible admet une interprétation. Ce résultat est utilisé pour montrer que le polynome naturellement associé à un code complet fini dans un système sofique est factorisable par le polynome de l'alphabet. Ceci résoud un problème soulevé par Christophe Reutenauer qui a prouvé le même résultat avec des hypothèses plus fortes.

Andre Nies (Université d'Auckland) FA-presentable structures: richness and limitations

To be finite automaton (FA)-presentable seems to be a rather strong restriction on a countable structure in a finite signature: the domain can be represented by a regular set, in a way that finite automata can also verify that the atomic relations hold (where the strings representing elements are written one below the other, using symbols in a power alphabet). For instance, the additive group of integers is FA-presentable: numbers are represented in binary, and the correctness of the usual carry bit addition algorithm can be verified by a finite automaton. This notion was introduced by Khoussainov and Nerode, 1995. (There and elsewhere, FA-presentable structures are called automatic structures, however, for groups, the term ``automatic'' refers to a different concept.)
For each FA-presentable structure one can also give an FA-representation of all definable relations, effectively in the defining formula. So FA-presentable structures are closed under interpretations, and each one has a decidable theory.
When considering an elementary class of effectively given structures, a good measure for its richness is the complexity of the isomorphism problem. For instance, Khoussainov, Nies, Rubin and Stephan (LICS 2004) have proved that for FA-presentable graphs or even successor trees, isomorphism is as complex as possible ($Sigma1_1$-complete), so the class is quite rich after all. With little effort, the result carries over to partial orders, lattices, and commutative semigroups.
One the other hand, the class of FA-presentable infinite Boolean algebras is very limited: Khoussainov, Nies, Rubin and Stephan have shown that they are just the finite powers of the Boolean algebra of finite or cofinite subsets of a countable set.
The general program is to locate each interesting class somewhere between those two possibilities. I discuss some new results for abelian groups and groups in general, mostly on the limiting side.
Groups: Examples of non-abelian FA-presentable groups include infinite direct powers of a finite non-abelian group, and GL_n(R) for some FA-presentable ring, e.g. the Boolean algebra mentioned before, viewed as a ring. Each finitely generated FA-presentable group is abelian-by-finite (Oliver and Thomas). A recent improvement of this (Nies and Thomas): if G is ANY FA-presentable group, then each f.g. subgroup of G is abelian-by-finite. Using similar methods, each FA- presentable commutative ring with 1 is locally finite.
Abelian groups: Known examples are (Z,+), the Prufer groups, and Z[1/p] for a prime p, and the obvious derived examples (like finite direct products). While the multiplicative group of rationals is not FA-presentable (Khoussainov e.a.), it is a major open question whether the additive rationals are FA-presentable.

Stéphane Messika (ENS Cachan - LSV) Couplage et auto-stabilisation

Un système probabiliste est dit ``auto-stabilisant'' lorsque, quelle que soit sa configuration de départ, il atteint (presque sûrement) le sous-ensemble donné des configurations légales. Cette propriété fournit notamment un intéressant modèle de résistance aux pannes. Il est essentiel de pouvoir non seulement garantir la propriété d'auto-stabilisation d'un algorithme donné, mais également d'estimer le temps d'auto-stabilisation. Nous montrons ici comment des méthodes mathématiques, telles que le "coupling", développées pour simuler des chaines de Markov, donnent de nouveaux critères d'auto-stabilisation, ainsi qu'une meilleure analyse de la vitesse de convergence. Nous donnons quelques exemples de telles méthodes et diverses applications, comme l'analyse de l'algorithme du dilemme du prisonnier itéré.

Carole Delporte (Université Paris 7 - LIAFA) Election de leader ultime, systèmes partiellement synchrones et détecteurs de défaillances

Omega est un détecteur de défaillances qui réalise une élection ultime de leader. Omega est particulièrement intéressant car dans un système asynchrone avec des pannes de processus par arrêt définitif, en présence d'une majorité de processus corrects, il est le plus faible détecteur de défaillances qui permet de réaliser le consensus. Dans cet exposé, on présente des systèmes partiellement synchrones avec des hypothèses très faibles de synchronisme et de fiabilité. On montre comment, dans ces systèmes, on peut réaliser des implémentations efficaces de Omega. Les travaux présentés ont été réalisés en collaboration avec Marcos Aguilera, Hugues Fauconnier et Sam Toueg.

Martin Skoviera (Université Bratislava - Slovaquie) Factorisation of Snarks

A snark is a "non-trivial" cubic graph which has no 3-edge-colouring. Snarks are related to several important and long-standing conjectures such as the Cycle-Double Cover Conjecture, 5-Flow Conjecture, Grunbaum's Conjecture and others. In spite of their simple definition and over a century lasting investigation their properties and structure are largely unknown. In this talk we concentrate on highly non-trivial snarks such as irreducible snarks. Their characteristic property is that the removal of any non-trivial edge-cut results in a 3-edge-colourable graph. We show that every irreducible snark G can be decomposed into a collection {H1,H2,...,Hn} of cyclically 5-connected irreducible snarks such that G can be reconstructed from them as a repeated dot-product. Moreover every irreducible snark has only one such collection up to isomorphism and ordering. This fact suggests that the role of cyclically 5-connected irreducible snarks can be compared to that of the prime numbers in the factorisation of integers.

Antonio Machi (Université de Rome) Choisir aléatoirement des éléments dans un groupe: est-ce justifié ?

On considère la probabilité que deux entiers choisis au hazard soient premiers entre eux. A partir de cet exemple, on se pose le problème de savoir dans quels groupes le choix d`un élément a un sens. Ceux groupes sont importants dans plusieurs domaines, par exemple dans la théorie des automates cellulaires.

Madiagne Diallo (PRISM - Université Versailles) Applications de Problèmes de flots : Analyse de sensibilité et gestion de la congestion dans un réseau

le sujet de mon exposé porte sur des applications des problèmes de flots dans des réseaux modélisant des réseaux de distribution de fluide ou d'énergie et des réseaux de télécommunication ou de transports.
*La première application* consiste en une analyse de sensibilité des flots sur les réseaux, c'est à dire, l'étude de l'impact de la variation de la capacité d'une ou de plusieurs arêtes sur l'ensemble des valeurs de flot maximum entre toutes les paires de sommets du réseau. Nous montrons comment détecter en temps réel l'ensemble des flots dont la valeur est affectée par les différentes variations de capacités dans le réseau. Nos études sont basées sur les arbres de coupes de Gomory et Hu (De tels arbres reflétent les valeurs de flot maximum entre toutes les paires de sommets dans un réseau non orienté.)
*La deuxième application* concerne l'allocation de ressources dans un réseau de télécommunication pour la satisfaction de requête d'utilisateurs. Pour ce faire, nous étudions ce problème par le biais de la tarification pour gérer la congestion tout en tenant compte du comportement des utilisateurs et de la volonté de profit de l'opérateur. Nous avons utilisé une approche bi-niveaux pour résoudre le problème. Par la méthode du Lagragien augmenté, nous résolvons le problème d'allocation de ressources en associant les multiplicateurs de Lagrange aux prix sur les liens du réseaux. Nous utilisons ensuite les conditions d'optimalité de Karush-Kuhn-Tucker pour vérifier si les multiplicateurs (prix) sont uniques ou pas. Au cas de non unicité nous montrons comment on peut résoudre un deuxième problème d'optimisation juste sur ces multiplicateurs (prix) afin d'améliorer le revenu sur le réseau.
*Mots Clès 1 * : réseaux de flots, flots paramétrés, analyse de sensibilité, capacité critique, arc vital
*Mots Clès 2 * : programmation bi-niveaux, affectation du traffic, tarification, contrôle de congestion

Jean Mairesse (LIAFA - Université Paris 6 et 7) Marches aleatoires sur certains groupes et monoides

On definit une famille de groupes discrets qui contient les groupes finis, les groupes libres et qui est stable par produit libre. On montre que toute marche aleatoire transiente et au plus proche voisin sur le (graphe de Cayley du) groupe admet une mesure harmonique Markovienne. Cette mesure est entierement determine par la resolution d'un systeme d'equations polynomiales. Une consequence est que la derive (vitesse de fuite) ou encore l'entropie de la marche aleatoire est `explicitement' calculable. Ainsi, si les probabilites de transition sont rationnelles, la vitesse de fuite est un nombre algebrique. Le resultat s'etend, modulo quelques amenagements, au cas des monoides. Dans le cas du groupe libre, on retrouve des resultats classiques essentiellement dus Dynkin et Malyutov (1961). Ensuite, on montre l'effectivite du resultat en calculant explicitement les vitesses de fuite sur certains groupes interessants: le groupe modulaire (Z/2Z*Z/3Z) ou les groupes d'Artin a 2 generateurs. On s'interesse egalement au calcul explicite de l'entropie et au lien entre entropie, derive et volume logarithmique du groupe. Travail commun avec F. Matheus (U. Bretagne-Sud).

James Martin (LIAFA - Université Paris 6 et 7) Introduction au modèle des particules dures

Un "ensemble indepéndant" dans un graphe est un ensemble de sommets tel qu'aucun de ces sommets ne sont voisins l'un de l'autre dans le graphe.
Quelles propriétés possède un ensemble indépendant "typique" d'un graphe donné? Par typique on veut dire choisi uniformément parmi tous ces ensembles. Comment généraliser au cas d'un graphe infini, où il y a infiniment d'ensembles indépendants?
Ces questions nous conduisent à considerer le "hard-body model" (modèle des particules dures), qui trouve sa motivation aussi bien en informatique qu'en physique statistique.
Je donnerai une introduction à ce modèle, en me concentrant sur les cas où le graphe est un trellis carré ou un arbre.

Jean-Marc Petit (Université Clermont-Ferrand) Recherche adaptative de bordures en fouille de données

De nombreux problèmes de fouille de données tels la recherche des motifs fréquents maximaux, des dépendances fonctionnelles ou d'inclusion dans les bases de données peuvent se formuler dans un cadre théorique général [Mannila et al,DMKD,1/3, 1997]: Etant donné un langage fini $\cal L$, une base de données $d$, un ordre partiel $\preceq$ sur l'ensemble des phrases du langage et un prédicat anti-monotone $Q$, trouver les phrases les plus specifiques qui vérifient le prédicat $Q$ dans $d$, aussi appelé \emph{bordure positive}.
Deux types de parcours de l'espace des solutions seront abordés. Le premier est dit par niveaux, des éléments les plus généraux (de petite taille) aux éléments les plus spécifiques (de grande taille). Par anti-monotonie, dès qu'un élément ne vérifie pas $Q$, toutes ses spécialisations ne le vérifient pas non plus. Ce type de stratégie est néanmoins mis en échec dès lors que la bordure positive possède au moins un élément de grande taille.
Nous présenterons une alternative à ce type d'approche qui consiste à : 1) appliquer une stratégie par niveaux jusqu'à un niveau k, fixé par ailleurs. 2) caractériser la \emph{bordure positive optimiste} à partir des éléments qui n'ont pas vérifier $Q$ jusqu'au niveau $k$. 3) estimer l'erreur commise en calculant une distance entre les éléments de la bordure optimiste et ceux de la bordure à découvrir. 4) proposer un mode de parcours adaptatif en fonction de cette erreur : soit "top-down", i.e. l'erreur commise n'est pas trop grande, soit "bottom-up", i.e. en repartant au niveau $k+1$.
Une application de cette stratégie a été menée pour la découverte des dépendances d'inclusion. De part le coût d'un accès à la base de données et d'une propriété d'interaction entre DF et DI qui permet de justifier les "sauts optimistes" dans l'espace des solutions, les résultats expérimentaux sur des bases de données réelles et synthétiques montrent que les temps de réponse sont toujours meilleurs que les autres approches testées, même pour les bordures positives composés d'éléments de petite taille. Quelques points ouverts seront donnés pour conclure cet exposé.

Michel Koskas (LAMFA - Université d'Amiens) Radix trees et recherche opérationnelle

Les radix trees, utilisés en combinatoire des mots pour stocker des langages, peuvent servir à des algorithmes de recherche opérationnelle puissants. On peut les utiliser en effet pour la recherche de plus court chemin dans un graphe dirigé et valué par des entiers, la gestion de bases de données, la recherche de motifs dans des images, une aide à la traduction automatique, la recherche sophistiquée de mots dans un texte, les calculs de maillages et d'efforts dans des représentations de surfaces, des problèmes d'optimisation de flots. Ils peuvent en outre aussi servir à un problème classique de combinatoire des mots : le calcul de complexité de facteurs. L'objet de cet exposé est de présenter quelques uns de ces algorithmes et leurs performances.

Pierre Fraigniaud (CNRS - LRI - Université d'Orsay) Tables de hachage distribuees pour reseaux pair-a-pair.


Jean Berstel (Institut Gaspard Monde, Université Marne-la-vallée) Répétitions dans les mots: résultats récents et problèmes ouverts

Dans une première partie de cet exposé de synthèse, on passe en revue divers mécanismes de génération de mots infinis. Ensuite, on decrit quelques résultqts plus ou moins récents concernant les répétitions, au sens de puissances de mots, qui peuvent être évitées ou non. Enfin, on mentionne quelques problèmes ouverts.

Juhani Karhumaki (Université Turku, Finland) Combinatorics on words: a new challenging research topic.

Motivated by a rapidly growing interest in Combinatorics on Words, as shown, for example, by the fact that in the latest classification of Mathematical Reviews the topic is a topic of its own, we give a survey on several highlights of the theory, as well as point out some challenging problems. Some of the problems are amazingly simple looking. Rather than trying to be exhaustive we concentrate to a few problems according to the taste of the speaker; After considering some aspects of repetition-free words, we then concentrate to periodicity from different perspectives. For exmample, we look for local peirodity conditions which would imply the global periodicity, that is the fact that the word is ultimately periodic. We also consider questions connected to word equations.Finally, a few words about extensions of the theory of words into that of finite sets of words are said.

Jean-Louis Giavitto (LAMI - Université d'Evry) Système de réécriture et modélisation de processus biologiques.

Un système de réécriture est, pour un informaticien, un modèle de calcul qui indique comment remplacer certains objets par d'autres dans une certaine structure S. Ces systèmes se présentent sous la forme d'un ensemble de règles qu'on peut interpréter comme des lois d'évolution locale de S. Par exemple une règle de la forme
o + i -> o' + i'
peut s'interpréter en biologie comme l'action d'un signal i (molécule, stress, champ, ...) sur une entité biologique o (molécule, compartiment, cellule, tissu, organe, etc.) qui se transforme en une entité o' et émet un signal i'. Cette approche, de nature discrète et algébrique, bénéficie de tous les outils d'analyse et de preuve développés dans ce domaine mais ne permet pas encore la prise en compte d'organisations spatiales complexes. A ce jour, cette approche s'est ainsi révélé fructueuse pour les structures linéaires (filaments et organisations arborescentes) et été appliquée avec beaucoup de succès à la modélisation de la croissance des plantes. Nous présenterons plusieurs systèmes qui se distinguent par le type de structure S considérée : la réécriture de multi-ensemble avec GAMMA et la CHAM qui sont à la base de l'approche de la chimie artificielle, l'extension aux P-systèmes qui essaie de rendre compte de la compartimentation et des membranes, la réécriture de chaînes et d'arbres avec les systèmes de Lindenmayer. Nous présenterons en particulier la modéliation et de la croissance et de la différentiation des cellules hétérocystes chez Anabaena Catenula.

Vincent Vajnovszki (Université de Bourgogne) Génération sans boucle d'un code de Gray pour les permutations d'un multi-ensemble.

L'ensemble de permutations d'un multi-ensemble (permutations avec répétitions), noté par S(n_0,n_1,...,n_k), est l'ensemble des suites d'entiers avec exactement n_i occurrences de i, et S(n_0,n_1,...,n_k) généralise simultanément les permutations et les combinaisons. Un code de Gray pour S(n_0,n_1,...,n_k) est une liste pour cet ensemble où deux suites successives diffèrent par la transposition de deux éléments. Plusieurs algorithmes récursifs pour la génération des codes de Gray pour les permutations d'un multi-ensemble ont été proposés dans la littérature. Dans cet exposé je présente un algorithme sans boucle pour cette classe d'objets combinatoires. Mon approche est le suivante: j'exprime les permutations d'un multi-ensemble à l'aide du constructeur de mélange qui me permet de définir un code de Gray et finalement obtenir un algorithme sans boucle pour les permutations d'un multi-ensemble.

Sebastien Tixeuil (LRI - Université Paris XI, Orsay) Introduction à l'auto-stabilisation.

Quand un système réparti est sujet à des défaillances transitoires qui modifient arbitrairement son état, il est crucial de pouvoir retrouver un comportement correct au bout d'un temps fini. L'auto-stabilisation, introduite par Dijkstra en 1974, présente une telle garantie. Dans cet exposé, je présenterai la problématique et les hypothèses principales faites dans le cadre de l'étude des systèmes auto-stabilisants.

Eric Goubault (CEA Saclay) Sur quelques méthodes géométriques en parallélisme et distribution.

Ces dernières années, de nouvelles méthodes sont apparues, bien que basées sur de fort anciennes idées (Dijkstra 68), pour donner des sémantiques de systèmes parallèles et distribués, de manière "géométrique". J'expliquerai dans cet exposé de quoi il retourne, introduirai à quelques idées essentielles en topologie algébrique et montrerai que ceci donne de belles idées d'algorithmes de détermination de points morts, ordonnancements, inatteignables etc. Il y a également des connexions avec la réecriture de termes et les systèmes distribués tolérants aux pannes, dont j'effectuerais également un survol, si le temps le permet.

Chabane Djeraba (IRIN - Ecole Polytechnique de Nantes) Bases de données avancées.

Une base de données est un ensemble physique cohérent de données. Cette cohérence facilite les traitements postérieurs à la création de la base, principalement dans des traitements d'analyse et des requêtes multi-citères. Le stockage d'information dans une base de données présente de nombreux avantages. En effet, une base de données ne sert pas simplement à conserver des informations; elle permet aussi de les classer, les trier, les analyser de différentes façons et les présenter de façon très différente sans modifier leur contenu (intégrité de la base de données). Par rapport aux bases de données traditionnelles (hiérarchique, relationnelle, voire objet), les bases de données avancées font allusion à des fonctionnalités des systèmes de bases de données pour lesquelles les données sont de plus en plus complexes (c'est-à-dire semi ou non structurées) et de plus en plus volumineuses. Ainsi de nouveaux concepts ont vu le jour tels que les entrepôts de données, les bases de données multimédia, le data mining, les représentations normatives, etc. Dans le cadre de ce séminaire, nous nous intéresserons à deux points précis : les bases de données multimédia et l'extraction des connaissances à partir des bases de données.

Pascal Ferraro (LaBRI) Méthodes de comparaison d'arborescences. Applications à la comparaison des plantes.

L'organisation structurelle des entités d'une plante, i.e. son architecture, est souvent représentée par un graphe arborescent. Pour rendre compte des différents niveaux d'organisation dans la description de l'architecture des plantes, l'UMR AMAP a introduit un formalisme basé sur la notion de graphe quotienté : les structures arborescentes multi-échelles. Ainsi, comparer la structure de deux plantes se ramène formellement à comparer deux graphes arborescents multi-échelles. La famille d'algorithmes étudiée s'appuie sur une généralisation des méthodes de calcul de distance entre séquences, utilisées par exemple pour la comparaison du génome. Leur principe général consiste à reconstruire un graphe cible en appliquant à un graphe initial différentes opérations structurelles élémentaires, appelées opérations d'édition. La solution optimale est construite de façon incrémentale en utilisant des techniques de programmation dynamique.
Après avoir proposé un point de vue unifié de différentes distances entre arborescences, deux extensions algorithmiques permettant d'envisager le calcul d'une mesure de ressemblance entre arborescences quotientées seront présentées durant cet exposé. Ces différents algorithmes sont appliqués à la comparaison d'architecture de plantes afin d'évaluer les plantes obtenues par simulation et d'autres part, afin de permettre l'identification des propriétés d'autosimilarité des plantes. Nous envisageons d'utiliser par la suite ces méthodes pour la comparaison de structures secondaires d'ARN.

Xuding Zhu (Department of Applied Mathematics National Sun Yat-sen University, Taiwan, ROC.) Circular chromatic number of graphs.

The circular chromatic number of a graph G is a refinement of the chromatic number of G. This talk discusses the relation between circular chromatic number and chromatic number, and relation to other graph parameters. I will also talk about connection between circular coloring of graphs and problems in distributed computations.

Bill Rounds (Université d'Ann Arbor) pi-calculus and continuous systems.

In this talk we present a new laguage which allows concurrent programs to interact with continuous environments. It is an extension of the powerful pi-calculus of Milner, which already provides for concurrency and reconfigurability. Our contribution adds the notion of *active environments* which can specify flows over continuous time using ordinary differential equations. This allows us to extend ordinary hybrid automata to specify systems of physical agents which can reconfigure themselves.

Bruno Gaume (IRIT-Toulouse) Pour une ergonomie cognitive des dictionnaires électroniques : chaos, small world & information.

Première partie : Pour une ergonomie cognitive des dictionnaires électroniques
We compare a linguistic/psycholinguistic approach of the organisation of the mental lexicon with a computational approach of the implicit lexical organisation in dictionaries taken as graphs and whose structure is a small world. This double approach aims at showing that if the implicit structure of dictionaries, mathematically identified, is adequate with the way young children categorise, then those graphs might be considered as cognitive artefacts. This may lead to novel applications as well as to promising researches.
Deuxième partie : chaos, small world & information
A large class of networks observed in nature, as diverse as networks of genetic or semantic origin or even the web, often called "small worlds " = smw since Watts & Strogatz 1998 article, do not resemble either Erdös random networks nor regular networks. Indeed: 1) They are sparse in edges, that is they have relatively few edges in comparison to the number of their vertices. In a network with n vertices, the maximum number of edges possible is n(n-1)/2, (we will only consider non-oriented networks in this article) that is in the order of n2/2, when the number of edges of the smw is closer to n than to n2. 2) Like regular networks and unlike random networks, they possess a rich local structure. That is C their clustering coefficient is large, they are made of zones densely populated with edges (my friends tend to be friends). 3) Like random networks and unlike regular networks, their global connectivity is very "tight ". That is their average shortest path length L between pairs of vertices is small. 4) Moreover the degree distribution follows a power law. The probability P(k) that a vertex in a network would be linked to k vertices of the network decreases P(k)=k^-l, contrary to Erdös random networks where it is a Poisson line P(k) = e-l l^k/k!. Which signifies that these networks by their 4 characteristic properties posses a particular topology, in which the relation between the local and global structure has nothing to do with that of networks (regular or Erdös random ones) traditionnally studied in graph theory. This explains the considerable interest that these results have aroused in the scientific communities concerned. Indeed, it might be thought that these characteristics reflect the specific properties of the systems that these networks represent, and therefore that the study of these structures would enable better understanding of the phenomenon from which they come. In order to study the interaction between the local and global structures of the smw we tried to create such networks in an automatic way. Barabasi A.L. and Albert R. give a good model for the automatic generation of networks which is a dynamic model for construction by preferential attachment which produces networks with the 4 properties mentioned above. In this talk we suggest an alternative method, which is closer to information compression in multidimensional spaces: I keep in memory only my closest neighbours. This method enables the random construction of networks with the 4 fundamental properties of smws, by using the structural singularities of the vectors randomly distributed in the multidimensional spaces. This seems important for cognitive science knowlege representation and information theory in that it is a given that most big semantic networks are typical smws (sparse, short L, strong C, power law), and on the other hand, that the dynamic acquisition of the lexicon by young children (2 to 4 years old) seems linked to the smw structure. Indeed the studies carried out on children's metaphors, show that when a young child says "je déshabille l'orange " (I am undressing the orange) for "j'épluche l'orange] (I am peeling the orange) brings together the vertices within a zone densely populated with edges. The child learns first of all frequent words (corresponding to large incidence vertices) and uses them to designate a large area: a child who wants to communicate event A e.g. [to tear a book] for which he has no constituted verbal category (1) makes an analogy with an old event B [to break a glass] which he has already memorised with a lexical entry TO BREAK and (2) using this proximity, he says "the book is broken" in order to communicate event A. Then the child progressively acquires the less frequent words (corresponding to small incidence vertices) in this way refining his naming precision. The aquisition process of a smw class network consisting in local enrichment, reproduces in the same way the basic structure at finer and finer scales. The proximity link being the " pixel " from which the categorial image of the meanings of lexical entities present in the network is drawn.

Jaroslav NESETRIL (Université de Prague) Combinatorial Dualities

Duality in many of its forms is one of the leitmotives of modern (abstract) mathematics. In this talk we show how some general approaches to classical problems (such as 4-color theorem fame) and less classical (e.g. frequency assignement) coloring problems are related to a surprisingly rich spectrum of dualities and yield interesting results and problems.

Hubert de FRAYSSEIX (CNRS - CAMS Paris) Automorphismes et Isométries

Given a graph G on n vertices, we define a distance d among its vertices such that the graph can be isometrically embedded in R^n. This particular distance has the following reconstructibility property: up to an isomorphism, one can reconstruct the graph G from the distances among its vertices. It easily follows that the automorphisms of G are in a one to one correspondence with the isometries of its embedding. The computation of the embedding mainly consists in computing an orthonormal basis of eigenvectors of the inner product matrix omega defined by the distance d. Then isometries (i.e. the automorphisms of G) may be checked on each of the proper spaces. Hence the complexity of finding isometries is very much related to the multiplicity of the eigenvalues of omega. We get similar problems as in the graph spectral analysis approach to study automorphisms. But in this geometric framework many of the spectral properties of omega can be easily interpreted, which may help to improve our knowledge of graph automorphisms.

Mireille Bousquet-Mélou (LaBRI) Couplages parfaits et suites de Gale-Robinson

Considérons la suite définie par les conditions initiales a(0)=a(1)=a(2)=a(3) et par la récurrence suivante, valable pour n>3 :
a(n) a(n-4) = a(n-1) a(n-3) + a(n-2) a(n-2).
Bref, un produit de 2 termes est la somme de deux produits du même type. On remarque qu'il faut DIVISER par a(n-4) pour calculer a(n), et on se dit qu'on va trouver des nombres rationnels.
Eh bien non : la suite a(n) est entière. Qui plus est, ce résultat est vrai pour toutes les suites de Gale-Robinson :
a(n) a(n-m) = a(n-i) a(n-j) + a(n-k) a(n-l)
avec i+j=k+l=m. Ce résultat a été prouvé algébriquement, mais un combinatoriste ne connaîtra pas le repos avant d'avoir répondu à la question suivante :
Que comptent ces nombres ?
Réponse : des couplages parfaits de certains graphes bipartis qui ressemblent à des pommes de pin.
Travail en commun avec Jim Propp (Brandeis) et Julian West (Vancouver)

Volker DIEKERT (Université de Stuttgart) About Equations in graphs products

Makanin showed in 1977 that the existential theory of word equations with constants is decidable. This solved a question which was already raised by Markov in the late 1950's in connection with Hilbert's Tenth Problem. Later Makanin extended his result to the corresponding (but much more complicated) problem for free groups. For the complexity,both in the word and in the group case, the known lower bound is NP-hardness. A few years ago (1999) Plandowski introduced a new method for solving word equations in PSPACE and then, in 2000, Gutiérrez extended this method to free groups. In my lecture I will survey some progress over the past two years. Today, we know that not only the existential theory but also the positive theory of equations in the more general case of graph groups is decidable. Moreover, the techniques apply to the concept of graph products. (A graph product is given by a finite graph where each node is labeled with a finite monoid or with a free monoid or with a free group. Then one takes the free product and the edges of the underlying graph define a partial commutation.) The new results were obtained in collaboration with Muscholl and Lohrey We have obtained the following theorem:
Theorem: The existential theory of equations with recognizable constraints is decidable for graph products.
If the graph product is a group, then the positive theory is decidable, too. The complexity of these theories is not well-understood and deserves further research.