Les langages logico-fonctionnels sont des langages de programmation de très haut niveau permettant de définir dans un formalisme unifié des types de données, des fonctions et des prédicats (relations). Plusieurs propositions de langages logico-fonctionnels ont été faites mais toutes se restreignent à des calculs basés sur les termes du premier ordre. Cette restriction permet de programmer avec des types abstraits algébriques mais elle rend difficile la manipulation des structures de données du monde réel, modélisées sous la forme de graphes cycliques. L'objectif de cette thèse est donc d'introduire les graphes cycliques comme structure de données de base des langages logico-fonctionnels. Pour cela, nous voyons les programmes comme des systèmes de réécriture de graphes cycliques et nous étudions les relations de réécriture et de surréduction qu'ils induisent (sémantique opérationnelle). Une propriété importante de la réécriture concerne la confluence : elle exprime le déterminisme des calculs effectués. De nombreux résultats de confluence existent pour la réécriture de termes mais ils ne s'étendent généralement pas aux graphes cycliques. Nous mettons en évidence une classe de graphes cycliques particuliers, les graphes admissibles, pour laquelle nous donnons une preuve de confluence de la réécriture. Concernant la relation de surréduction, nous en proposons une définition puis nous montrons que ce calcul est cohérent et complet par rapport à celui de la réécriture dans le cadre des graphes admissibles. Nous étudions ensuite plusieurs stratégies de réécriture et de surréduction de graphes admissibles, c'est-à-dire des algorithmes permettant d'éliminer des calculs inutiles ou redondants. Nous montrons que nos stratégies sont optimales selon de nombreux critères dépendants des systèmes de réécriture considérés.

Les appareils modernes sont constitués de plusieurs sous-systèmes de différentes sortes qui communiquent et interagissent. L'hétérogénéité de ces sous-systèmes et leurs interactions complexes rendent très délicate leur développement. L'approche d'ingénierie dirigée par les modèles apporte une solution en permettant l'expression de nombreux modèles structurels et comportementaux de natures très diverses. Dans ce contexte, il est nécessaire de construire un modèle unique qui intègre ces différents modèles afin d'y appliquer des méthodes de validation et de vérification pour permettre aux ingénieurs système de comprendre et de valider un comportement global. Cependant, la coordination manuelle des différents modèles qui composent le système est une opération source d'erreurs et les approches automatiques proposent des patrons de coordination ad-hoc pour certaines paires de langages. Dans ces approches, le patron de coordination est souvent encapsulé dans un outil dont il est difficile d'extraire les liens avec le système global. Cette thèse propose le Behavioral Coordination Operator Language (BCOoL), un langage dédié à la spécification de patrons de coordination entre des langages à partir de la définition d'opérateurs de coordination. Ces opérateurs sont employés afin d'automatiser la coordination de modèles exprimés dans ces langages. BCOoL est implémenté comme une suite de plugins qui s'appuient sur l'Eclipse Modeling Framework et présente ainsi un environnement complet pour l'exécution et la vérification de différents modèles coordonnés. / Modern devices embed several subsystems with different characteristics that communicate and interact in many ways. This makes its development complex since a designer has to deal with the heterogeneity of each subsystem but also with the interaction between them. To tackle the development of complex systems, Model Driven Engineering promotes the use of various, possibly heterogeneous, structural and behavioral models. In this context, the coordination of behavioral models to produce a single integrated model is necessary to provide support for validation and verification. It allows system designers to understand and validate the global and emerging behavior of the system. However, the manual coordination of models is tedious and error-prone, and current approaches to automate the coordination are bound to a fixed set of coordination patterns. Moreover, they encode the pattern into a tool thus limiting reasoning on the global system behavior. In this thesis, we propose a Behavioral Coordination Operator Language (B-COoL) to reify coordination patterns between specific domains by using coordination operators between the Domain-Specific Modeling Languages used in these domains. Those operators are then used to automate the coordination of models conforming to these languages. B-COoL is implemented as plugins for the Eclipse Modeling Framework thus providing a complete environment to execute and verify coordinated models. We illustrate the use of B-COoL with the definition of coordination operators between timed finite state machines and activity diagrams. We then use these operators to coordinate and execute the heterogeneous models of a surveillance camera system.

Development and evolution of Domain-Specific Languages (DSLs) is becoming recurrent in the development of complex software-intensive systems. However, despite many advances in Software Language Engineering (SLE), DSLs and their tooling still suffer from substantial development costs which hamper their successful adoption in the industry. We identify two main challenges to be addressed. First, the proliferation of independently developed and constantly evolving DSLs raises the problem of interoperability between similar languages and environments. Second, since DSLs and their environments suffer from high development costs, tools and methods must be provided to assist language designers and mitigate development costs. To address these challenges, we first propose the notion of language interface. Using language interfaces, one can vary or evolve the implementation of a DSL while retaining the compatibility with the services and environments defined on its interface. Then, we present a mechanism, named model polymorphism, for manipulating models through different language interfaces. Finally, we propose a meta-language that enables language designers to reuse legacy DSLs, compose them, extend them, and customize them to meet new requirements. We implement all our contributions in a new language workbench named Melange that supports the modular definition of DSLs and the interoperability of their tooling. We evaluate the ability of Melange to solve challenging SLE scenarios. / Development and evolution of Domain-Specific Languages (DSLs) is becoming recurrent in the development of complex software-intensive systems. However, despite many advances in Software Language Engineering (SLE), DSLs and their tooling still suffer from substantial development costs which hamper their successful adoption in the industry. We identify two main challenges to be addressed. First, the proliferation of independently developed and constantly evolving DSLs raises the problem of interoperability between similar languages and environments. Second, since DSLs and their environments suffer from high development costs, tools and methods must be provided to assist language designers and mitigate development costs. To address these challenges, we first propose the notion of language interface. Using language interfaces, one can vary or evolve the implementation of a DSL while retaining the compatibility with the services and environments defined on its interface. Then, we present a mechanism, named model polymorphism, for manipulating models through different language interfaces. Finally, we propose a meta-language that enables language designers to reuse legacy DSLs, compose them, extend them, and customize them to meet new requirements. We implement all our contributions in a new language workbench named Melange that supports the modular definition of DSLs and the interoperability of their tooling. We evaluate the ability of Melange to solve challenging SLE scenarios.

La construction de programmes nécessite l'utilisation d'outils adaptés. Un outil particulier est le langage de programmation. Les langages logico-fonctionnels sont des langages de programmation dits déclaratifs qui se basent sur les notions mathématiques de fonction et de prédicat. Ce fondement théorique solide facilite à la fois la description d'un système à un niveau proche de la spécification ainsi que la validation de programmes. Néanmoins, les concepts sous-jacents aux langages logico-fonctionnels sont insuffisants pour la description aisée de systèmes complexes qui nécessitent l'interactivité, la concurrence et la distribution. Pour la modélisation de ces systèmes, la notion de processus a été introduite. Dans le contexte des algèbres de processus, un processus est caractérisé par les actions qu'il est capable d'exécuter. Cependant, les langages fondés uniquement sur les algèbres de processus doivent être étendus afin d'éviter le codage de fonctions et de prédicats en termes de processus. Dans cette thèse nous proposons un modèle de calcul qui intègre la programmation concurrente et déclarative. Nous suggérons de modéliser un système par un ensemble de composants. Chacun de ces composants comporte un programme déclaratif, appelé store, et un ensemble de processus interagissant par l'exécution d'actions. De plus, un composant peut contenir de nouvelles actions définissables par le programmeur. L'interaction entre composants est fondée sur le même principe, c.-à.-d. un processus peut exécuter des actions sur les stores des autres composants. Les différents composants d'un système peuvent utiliser des langages déclaratifs différents pour la description de leurs stores respectifs, ce qui nécessite la traduction des valeurs communiquées. Nous donnons une sémantique compositionnelle ainsi qu'une analyse de la confidentialité pour les processus d'un composant, et présentons les principes d'un prototype implanté

.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Développer des analyseurs statiques nécessite une manipulation intensive de structures d'arbres et de graphes représentant le programme. La finalité de cette thèse est de proposer des constructions de langage dédiées au prototypage d'outils d'analyse et de transformation de programmes et inspirées de la réécriture de termes et de termes-graphes. L'originalité de notre approche est d'embarquer ces nouvelles constructions dans les langages généralistes sous la forme d'un langage dédié embarqué. Les travaux de cette thèse se fondent sur le langage Tom qui propose d'embarquer des constructions de réécriture dans des langages généralistes comme Java. La première contribution de cette thèse a été de formaliser les langages embarqués sous le concept de langage îlot. Ce formalisme a ainsi permis de certifier la compilation du langage Tom. Nos travaux sur l'analyse de Bytecode nous ont ensuite conduit à réfléchir à la représentation et la manipulation de graphes de flot de programmes et nous avons alors proposé des constructions de langage inspirées de la réécriture de termes-graphes. Une autre contribution de cette thèse est la conception d'un langage de stratégies adapté à l'expression de propriétés sur un programme. Associé au filtrage, ce langage permet d'exprimer de manière déclarative des analyses et des transformations sur des arbres ou des graphes. Enfin, l'ensemble des propositions de cette thèse a été intégré au langage Tom sous la forme de nouvelles constructions syntaxiques ou d'améliorations de constructions existantes et a ainsi pu être appliqué à l'analyse du langage Java. / Developing static analyzers requires an intensive handling of tree and graph structures representing the program. Even if generalist languages such as Java or C++ have libraries dedicated to the manipulation of such structures, the absence of specialized statements makes the code complex and difficult to maintain. The purpose of this thesis is to provide dedicated language constructs to prototype tools for analysis and program transformation inspired by the term and term-graph rewriting. The originality of our approach is to embed these new statements in generalist languages. This is motivated by the development of the Tom language that offers rewriting constructs for generalist languages like Java. The first contribution of this thesis is to formalize embedded languages in the concept of island languages. This formalism enables the certification of the Tom compiler. Our work on Bytecode analysis leads us to propose a dedicated language for the representation and manipulation of program flow graphs. Thus we propose language constructs based on the term-graph rewriting. A further contribution of this thesis is to design a strategy language adapted to the expression of properties on a program. Associated with matching capabilities, this language allows to express in a declarative way analysis and transformations on trees or graphs. Finally, all the proposals of this thesis have been integrated into the Tom language in the form of new statements or improvements of existing ones. This language proposal has been applied to the analysis of Java programs.

L’objectif de cette thèse est d’obtenir des algorithmes sous linéaire permettant de répondre à des problèmes de décision dans les bases de données XML. Plus précisément, on s’inspire du property testing, pour décider approximativement si un arbre d’arité non bornée est valide par rapport à une DTD ; ou plus généralement si un tel arbre est reconnu par un automate d’arbre.Nous avons d’abord étudié le cas simple des mots, c’est-à-dire l’appartenance approchée d’un mot à un langage régulier défini par un automate non-déterministe. Sous la distance d’édition entres les mots, nous proposons un algorithme (ou tester) résolvant l’appartenance approchée en un temps polynomial : en la taille de l’automate aussi bien qu’en la précision (où le paramètre d’erreur). Nous avons aussi amélioré le précédent algorithme d’Alon, Krivelevich, Newman, et Szegedy, (2000) pour l’approximation de l’appartenance à un langage régulier modulo la distance de Hamming. Notre amélioration consiste à rendre cet algorithme polynomial en la taille de l’automate non-déterministe. Ensuite nous avons considéré l’appartenance approchée d’un arbre à un automate d’arbre sous la distance d’édition standard. Notre algorithme résout ce problème avec une complexité en temps exponentielle en la hauteur de l’arbre. Enfin nous avons considéré la validation approchée de DTD par rapport à la « strong edit distance » ; et nous obtenons dans ce cas un algorithme polynomial en la hauteur de l’arbre. Nous complétons nos résultats en prouvant une borne inférieure linéaire en la taille de l’arbre, pour la complexité de tout algorithme décidant l’appartenance approchée d’un arbre à une DTD, sous la strong edit distance. / Inspired by property testing, our objective is to obtain sublinear algorithms for deciding properties of XML databases approximatively. More precisely, we investigate the properties of whether an unranked tree is valid for a DTD, or more generally, whether it is recognized by a tree automaton. We start our studies by the simpler case of words and we considered the approximate membership problem for word non-deterministic automata. For this problem, we provide an efficient tester that runs in polynomial time in the size of the input automata and the error precision. We also improve the previous [Alon, Krivelevich, Newman, and Szegedy, 2000b] approximate membership tester for regular languages modulo the Hamming distance, so that it runs in polynomial time in the size of the input automata. Secondly, we study approximate membership testing for tree automata modulo the standard edit distance, and obtain a tester with run time exponential in the input tree depth. Next we consider approximate DTD validity modulo the strong edit distance. We then provide a tester that depends polynomially on the height of the tree. Finally, modulo the strong edit distance, we prove a linear lower bound on the depth of the input tree.

Les automates cellulaires sont un modèle de calcul massivement parallèle introduit dans les années 50. De nombreuses variantes peuvent être considérées par exemple en faisant varier la dimension de l’espace de calcul, ou les possibilités de communication entre les différentes cellules. En effet, chaque cellule ne peut communiquer qu’avec un nombre fini d’autres cellules que l’on appelle son voisinage. Mes travaux s’intéressent principalement à l’impact du choix du voisinage sur les capacités algorithmiques de ce modèle. Cet impact étant bien compris en une dimension, mes travaux portent majoritairement sur les automates cellulaires bidimensionnels. J’ai tout d’abord essayé de généraliser des propriétés classiques de certaines classes de complexité au plus de voisinages possibles. On arrive notamment à un théorème d’accélération linéaire valable pour tous les voisinages. J’ai ensuite étudié les différences entre les classes de faibles complexités en fonction du voisinage choisi. Ces travaux ont permis d’exhiber des voisinages définissant des classes incomparables, ainsi que des ensembles de voisinages définissant exactement les mêmes classes de complexité. Enfin, je présente aussi des travaux sur les différences de puissance de calcul entre les automates de dimensions différentes. / Cellular automata were introduced in the 50s by J. von Neumann and S. Ulamas an efficient way of modeling massively parallel computation. Many variations of the model can be considered such as varying the dimension of the computation space or the communication capabilities of the computing cells. In a cellular automaton each cell can communicate only with a finite number of other cells called its neighbors. My work focuses on the impact of the choice of the neighbors on the algorithmic properties of the model. My first goal was to generalize some classical properties of computation models to the widest possible class of neighborhoods, in particular I prove a linear speedup theorem for any two dimensional neighborhood. I then study the difference between the complexity classes defined by different neighborhoods, show the existence of neighborhoods defining incomparable classes, and some sets of neighborhoods defining identical classes. Finally, I also discuss the impact of the dimension of the automata on their computational power.

La validation temporelle des systèmes temps réel est nécessaire dans le cadre d’applications critiques tels l’aéronautique, le spatial ou l’automobile. Il s’agit, dans ces systèmes, de garantir les temps de réponse des tâches ainsi que le déterminisme de leurs communications. En raison de la complexité des systèmes actuels ainsi que de leur criticité, il est nécessaire de mettre en place une démarche de conception réduisant le temps de développement et ainsi le temps de mise en marché (time-to-market), tout en réduisant les risques d’erreurs de conception.Ce contexte rend l’ingénierie dirigée par les modèles particulièrement adaptée au développement de ce type de système. Les contributions de cette thèse partent des constats suivants. Premièrement, malgré la multitude des modèles d’analyses existants les modèles actuels ne peuvent retranscrire de nombreux cas rencontrés en industrie. Pour pouvoir analyser ces cas, il est nécessaire de les adapter `a l’analyse. Le deuxième constat porte sur l’adaptation qui n’est toujours pas simple surtout quand il existe une disparité sémantique entre les langages de description d’architecture et les modèles d’analyse ce qui nécessite de les rapprocher. Le dernier constat porte sur les difficultés dans la modélisation des systèmes distribués complexes car à moins de connaître le système complet, la représentation globale et sa validation temporelle reste coûteuse.Cette thèse propose des outils et méthodes pour améliorer le processus de modélisation et d’analyses temps réel. La première contribution consiste en la mise en place d’un référentiel de transformation de modèles endogène pour effectuer une adaptation conservative des modèles industriels aux modèles d’analyses. Dans l’optique de réduire l’écart sémantique entre les langages de description et les modèles d’analyse, cette thèse propose également une modélisation incrémentale des réseaux temps réel en vue de leur validation temporelle car les langages existants les considèrent de fa¸con limitée. La troisième contribution de la thèse porte sur la réduction des artéfacts de modélisation par extraction et élagage de méta-modèles afin d’obtenir les éléments nécessaires par rapport au points de vue d’analyse souhait´es.Toutes ces contributions sont implémentées dans des frameworks intégrant les processus d’analyses temps réel tels Time4Sys et MoSaRT et utilisées, dans le cadre d’un projet collaboratif, par des partenaires industriels. / The timing validation of real-time systems is mandatory for critical applications such as aeronautics,aerospace or automotive systems. The aim is to guarantee tasks response time and messages transmission time on networks. As for the criticality of these complex systems, it is necessary to implement a design process that reduces the development time therefore the time-to-market while reducing design errors risks.This context makes model-driven engineering well adapted for the development of critical real-time systems.The contributions of this thesis rely on the following observations. First of all, despite the existence of various analysis models, they often cannot represent perfectly some industrial cases. To analyze these cases,an adaptation is required to make them analyzable with existing tests. However, the adaptation is not quite easy especially in case of a semantic gap between systems description languages and analysis models. Also,several difficulties have been noticed to design and analyze an entire distributed complex system in one-shot unless knowing well the full system.In this PhD thesis, tools and methods are proposed to ease and improve the modeling and analysis processes of real-time systems. The first thesis contribution consists of implementing a rule-based endogenous transformation repository dedicated to adapt conservatively industrial models to the analysis models. The second contribution is focused on real-time networks and is dedicated to reduce the semantic gap between description languages and analysis models by proposing artefacts allowing to design networks on an incremental way. Moreover, this thesis proposes to reduce modeling artifacts using extraction and meta-models pruning inorder to retrieve useful elements referring to chosen analysis viewpoints.All these contributions are implemented in modeling frameworks integrating real-time analyses processes such as Time4Sys and MoSaRT, and used in a collaborative project by industrial partners.