Les systèmes ouverts reconfigurables sont aujourd'hui omniprésents dans le paysage informatique : réseaux mobiles, calculs et données dans “le nuage”, etc. Une particularité de ces systèmes est que leur topologie de communication évolue dynamiquement - nous parlerons de reconfiguration - en conséquence d'activités concurrentes internes ou externes. Les systèmes de transitions étiquetées pour les systèmes ouverts permettent de prendre en considération l'environnement extérieur de façon implicite.Les systèmes ouverts reconfigurables sont souvent modélisés par des formalismes inspirés ou dérivés du π-calcul. Le passage de nom permet de modéliser la dynamique des topologies de communication. Dans cette thèse, nous introduisons les π-graphs, une variante du π-calcul qui possède, entre autre, une interprétation graphique naturelle. De plus, le formalisme a été conçu pour servir de langage intermédiaire entre le π-calcul abstrait et des formalismes plus concrets, en particulier dans la famille des réseaux de Petri de haut-niveau.Nous proposons tout d'abord une traduction formelle et prouvée des π-graphes vers des réseaux de Petri de haut niveau supportés par des outils de modélisation et de vérification courants. Nous montrons que cette traduction peut-être élevée au rang d'isomorphisme entre les deux formalismes. Ainsi, les outils prototypes que nous avons développés dans le cadre des π-graphes peuvent travailler de concert avec des outils plus stables et plus généraux basés sur les réseaux de Petri.En se basant sur cette traduction bi-directionnelle, nous développons une extension de la logique temporelle linéaire (LTL) - la logique des systèmes ouverts reconfigurables - permettant de spécifier des propriétés portant sur la dynamique d'évolution de la topologie de communication dans le cadre d'environnements ouverts. Les propositions atomiques de cette logique caractérisent précisément les propriétés d'état des π-graphs.Un prototype d'outil a été développé dans le cadre de cette thèse pour valider expérimentalement l'approche proposée. Cet outil fournit un simulateur pour les modèles exprimés dans le formalisme des π-graphes. Ces modèles peuvent être compilés en réseaux de Petri de haut niveau et manipulés dans le cadre de l'outil SNAKES. Enfin, nous proposons une traduction de la logique des systèmes ouverts reconfigurables vers la logique de plus bas niveau supportée par le vérificateur de modèle NECO. Grâce à notre prévue constructive d'isomorphisme entre les π-graphes et leur traduction en réseaux de Petri, les contre-exemples générés pour les réseaux de Petri en cas d'invalidation de proposition par NECO peuvent être réinterprétées et expliquées dans les termes des π-graphes. / Today we witness the rapid spread of highly dynamic reconfigurable and distributed infrastructures that we group under the common name of open reconfigurable systems. The communication topology of those systems can dynamically change - or reconfigure - as a consequence of an internal or external concurrent activity. Labelled transition semantics for open systems allow to take into account the external activities in an implicit way.Open reconfigurable systems are commonly modeled using formalisms inspired by the π-calculus. Name passing makes it possible to model dynamic communication topologies. In this thesis, we introduce the π-graphs, a variant of the π-calculus that among other things enjoys a natural graphical interpretation. Moreover, the formalism has been designed to serve as an intermediate language between the abstract π-calculus and more concrete realizations, especially in the realm of high-level Petri nets.We first propose a faithful encoding of π-graphs into high-level Petri nets that are supported by common modelling and verification tools. We show that the translation can be lifted to an isomorphism between the two formalisms. Hence, the prototype tools that are developed specifically for π-graphs can be used in conjunction with more mature and general tools for Petri nets.Based on this bidirectional encoding, we develop a high-level variant of the linear temporal logic - namely the open system logic - to specify properties about the dynamic evolution of systems taking into account interactions within open environments. The atomic propositions of the logic precisely capture the state properties of π-graphs processes.The whole framework has been implemented during the course of this thesis. Our prototype tool provides a simulator for π-graphs models. These models can also be compiled into high-level Petri nets and then manipulated using the SNAKES framework. Finally, we provide an encoding of open system logic into linear temporal logic with state properties to be used with the NECO model checker for the automated verification of properties. Thanks to the bidirectional encoding from-and-to high-level Petri nets, counterexamples provided by the model checker for Petri nets can be easily reconstructed in terms of the original π-graphs.

Reproduction de : Thèse de doctorat : mathématiques appliquées : Grenoble 1 : 1990. / Titre provenant de l'écran-titre. Bibliogr. p. [163]-172.

Th.--Sc. math.--Paris VI, 1980. / 1984 d'après la déclaration de dépôt légal. Bibliogr., 6 p.

Th. 3e cycle--Sc. math.--Paris VI, 1981. / 1984 d'après la déclaration de dépôt légal. Bibliogr., 8 p.

Thèse--Sc. math.--Paris XIII, 1982. / 1984 d'après la déclaration de dépôt légal. Notes bibliogr.

Les services Web sont des composant accessibles via internet. Dans cette thèse nous présentons une plateforme d'aide à la conception de services Web basée sur le langage PEWS (Path Expressions for Web Services ). PEWS peut être vu comme une extension du langage WSDL permettant la description de l'interface comportementale d'un service. Notre plateforme propose des mécanismes pour analyser la correction (faculté qu'ont des services à communiquer) et la possibilité de remplacer un service par un autre dans une composition. Pour cela, nous avons utilisé la théorie des traces introduite par Mazurkiewicz. Les traces représentent le comportement non séquentiel de systèmes concurrents via une observation séquentielle. Nous travaillons sur les graphes de dépendance, qui sont la représentation des traces la plus intéressante pour l'implémentation de nos propositions. / Web services are software components accessible via Internet. The present work introduce a PEWS- based platform conceived to help web service designers. PEWS (Path Expressions for Web Services ) is a new language that can be seen as an extension of the language WSDL enabling the description of Web services behavioural interfaces. Our platform provide mechanisms to analyse the correctness (the assurance that two or more services can communicate) and the substitutability (the assurance that a given service can be replaced by another one in a given composition). For this purpose, we use traces theory (introduced by Mazurkiewicz). Traces represent the non-sequential behaviour of concurrent systems via a sequential observation. We work with the dependance graphs representation of traces, wich is more efficient for the implementation of our proposal.

Nous nous intéressons dans cette thèse à la résolution d'un problème de classification non supervisée d'un grand volume de données (i.e. 1 million). Nous proposons une méthode de construction incrémentale de grands graphes de voisinage par des fourmis artificielles qui s'inspire du comportement d'auto-assemblage de fourmis réelles se fixant progressivement à un support puis successivement aux fourmis déjà fixées afin de créer une structure vivante. La connexion entre fourmis (données) se fait à partir d'une mesure de similarité entre les données. Nous permettons également l'exploration visuelle et interactive de nos graphes en réponse aux besoins d'extraction de connaissances de l'expert du domaine. Ce dernier peut visualiser la forme globale d'un graphe et explorer localement les relations de voisinage avec une navigation guidée par le contenu. Nos travaux s'inscrivent pleinement en classification interactive ainsi qu'en fouille de textes avec une immersion en réalité virtuelle. / We present in this work a new incremental algorithm for building proximity graphs for large data sets in order to solve a clustering problem. It is inspired from the self-assembly behavior observed in real ants where ants progressively become attached to an existing support and then successively to other attached ants. Each artificial ant represents one data. The way ants move and build a graph depends on the similarity between the data. A graph, built with our method, is well suitable for visualization and interactively exploration depending on the needs of the domain expert. He can visualize the global shape of the graph and locally explore the neighborhood relations with a content-based navigation. Finally, we present different applications of our work as the interactive clustering, the automatic graph construction of documents and an immersion in a virtual reality environment for discovering knowledge in data.

Les travaux exposés dans cette thèse portent sur une contribution aux techniques de projection de graphes, appliquées à la reconnaissance de formes, visant à tirer parti de la richesse des méthodes structurelles et de l’efficacité des outils statistiques. Nous présentons une nouvelle projection s’inscrivant dans la catégorie des sondages de graphes. La première contribution de cette thèse porte sur l’encapsulation de la topologie du graphe dans une représentation vectorielle, en s’appuyant sur le dénombrement de motifs (sous-graphes) issus d’un lexique généré indépendamment du contexte. Ces motifs permettent de minimiser les pertes de l’information topologique lors de la projection. La deuxième contribution porte sur l’intégration de l’information relative aux étiquettes au sein de notre projection par l’adjonction de leurs dénombrements. Aux problèmes liés à la nature et la variabilité des attributs, nous proposons deux solutions dans le but de constituer des classes d’étiquettes moins nombreuses. La première consiste à discrétiser les attributs numériques puis à les combiner. La deuxième vise à former ces classes par un partitionnement global de l’ensemble des étiquettes. Ces propositions sont ensuite évaluées sur différentes bases de graphes et dans différents contextes. / The work exposed in this thesis focuses on a contribution to techniques of graph embedding, applied to pattern recognition, aiming to take advantages of the richness of structural methods and the efficiency of statistical tools. We present a new embedding, joining the category of graph probing. The first contribution of this thesis deals with the embedding of the graph topology in a vectorial representation, based on the counting of patterns (subgraphs) stemming of a lexicon generated independently of the context. These patterns permit the minimization of losses of the topological information during the embedding. The second contribution focuses on the integration of the information related to labels inside our embedding by adding their counting. To deal with problems linked to the nature and the variability of the attributes, we suggest two solutions to reduce the number of label classes. The first one consists of discretizing numeral attributes and combining them The second one aims to build these classes by a global clustering on the set of labels. Then, these proposals are evaluated on different datasets of graphs and in different contexts.

Avec le développement récent des technologies 3D, les formes 3D sont devenues un type de données multimedia interactives de première importance. Leur représentation la plus courante, le maillage de polygones, souffre cependant de grande variabilité face à des transformations canoniques préservant la forme. Il est donc nécessaire de concevoir des techniques de modélisation intrinsèque de forme. Dans cette thèse, nous explorons la modélisation topologique par l’étude de structures basées sur les graphes de Reeb. En particulier, nous introduisons une nouvelle abstraction de forme, appelée squelette topologique avancé, qui permet non seulement l’étude de l’évolution topologique des lignes de niveau de fonctions de Morse mais aussi l’étude de leur évolution géométrique. Nous démontrons l’utilité de cette représentation intrinsèque de forme dans trois problèmes de recherche liés à l’Informatique Graphique et à la Vision par Ordinateur.Tout d’abord, nous introduisons la notion de calcul géométrique sur les graphes de Reeb pour le calcul automatique et stable de squelettes de contrôle pour la manipulation interactive de forme. Ensuite, en introduisant les notions de cartes de Reeb et de motifs de Reeb, nous proposons une nouvelle méthode pour l’estimation de similarité partielle entre formes 3D. Nous montrons que cette approche dépasse les méthodes participant au concours international de reconnaissance de forme 2007 (SHREC 2007) par un gain de 14%. Enfin, nous présentons deux techniques permettant de fournir une décomposition fonctionnelle d’une forme 3D, à la fois en considérant des heuristiques issues de la théorie de la perception humaine et des données 3D variant dans le temps. / With the ongoing development of 3D technologies, 3D shapes are becoming an interactive media of major importance. Their commonest representation, the surface mesh, suffers however from high variability towards standard shape-preserving surface transformations.It is necessary thus to design intrinsic shape modeling techniques. In this thesis, we explore topological modeling by studying Reeb graph based structures. In particular, we introduce a novel shape abstraction, called the enhanced topological skeleton, which enables not only the study of the topological evolution of Morse functions’ level sets but also that of their geometrical evolution. We show the utility of this intrinsic shape representation in three research problems related to Computer Graphics and Computer Vision. First, we introduce the notion of geometrical calculus on Reeb graphs for the stable and automatic computation of control skeletons for interactive shape handling. Then, by introducing the notions of Reeb chart and Reeb pattern, we propose a new method for partial 3D shape similarity estimation. We show this approach outperforms the competing methods of the international SHape REtrieval Contest 2007 by a gain of 14%. Finally, we present two techniques for the functional decomposition computation of a 3D shape, both from human perception based heuristics and from the analysis of time-varying 3D data.

Dans ce mémoire, nous utiliserons l’approche de Pólya pour dénombrer et énumérer des graphes répondant à certaines conditions. Nous étendons ensuite ce résultat pour des graphes plus spécifiques comme des réseaux, et des réseaux de type "feed-forward". Finalement, nous supposons ensuite que deux sommets d’un graphe puissent être connectés ou non, et étant donné une probabilité de connexion donnée, nous étudions, en tant que variables aléatoires, certaines propriétés que l’on aimerait retrouver parmi ces graphes. Le but de ce mémoire est donc d’étendre la portée du théorème de Pólya afin de dénombrer efficacement plusieurs familles de graphes. Le chapitre 1 servira à l’étude de ce théorème, des rappels nécessaires et suffisants de la théorie des groupes jusqu’à la démonstration du théorème de Pólya. Le chapitre 2 nous permettra de voir la flexibilité du résultat primordial développé au chapitre précédent. Finalement, au chapitre 3, nous abordons une approche plus probabiliste du problème d’énumération de graphes. / In this memoir, we use Pólya approach to count and enumerate graphs under a set of conditions. We then extend the reach of this result for some particular types of graphs, namely networks and feed forward networks. Finally, given probabilistic constraints, e.g. two nodes are connected with probability p, we find the probability that a random graph meets those constraints. The objective of this memoir is thus to remind necessary and sufficient notions of group theory in order to state and prove Pólya Enumeration Theorem, an extremely efficient theorem as for counting objects. We then use this result throughout chapter 2 to enumerate many types of graphs. Chapter 3 is where we get more probabilistic.