Les utilisateurs s'attendent à ce que les logiciels soient à la fois continuellement disponibles et mis-à-jour à la volée. L'introduction de nouvelles fonctionnalités et l'intégration de correctifs ne doit pas perturber la bonne marche d'une application. Les développeurs bénéficient aussi de la modification dynamique des logiciels en adaptant le code à de nouvelle situations ou bien an exécutant des analyses dynamiques à des fins de monitorage, de déboguage et d’optimisation. Les langages de programmation doivent donc fournir aux développeurs des mécanismes qui améliorent l'adaptabilité logicielle. Dans le même temps, l'augmentation de la taille et de la complexité des logiciels requièrent des applications faites de nombreux composants développés par différents groupes. Dans ce contexte chaque composant doit être convenablement protégé des autres. Les langages de programmation doivent donc aussi fournir des mécanismes qui améliorent l'encapsulation. Le besoin de supporter des adaptations dynamiques d'un côté, et le besoin d'avoir des composants convenablement confinés d'un autre, poussent la conception des langages de programmation dans deux directions opposées: soit plus de flexibilité, soit plus de contrôle. Cette dissertation étudie cette tension dans le contexte des langages orientée-objet dynamiquement typés via deux mécanismes qui promeuvent l'adaptabilité logicielle: la réflexion et les méthodes d’extension. Pour chacun de ces mécanismes, nous démontrons leur utilité, leurs effets néfastes sur l'encapsulation et proposons des solutions qui conservent leurs forces tout en maintenant l'encapsulation. / Users expect modern software to be both continually available and updated on the fly. Introduction of new features and integration of bug fixes should not trouble the smooth running of an application. Developers also benefit from dynamic modifications of software by adapting code to new unanticipated situations or by running dynamic analyses to get feedback about the behavior of running applications for monitoring, debugging and optimization purposes. Programming languages should thus provides developers with mechanisms that improve software adaptability. At the same time, the increasing size and complexity of software call for applications made up of many interacting components developed by different parties. In this context, each component needs to be properly protected from other ones. Programming languages should thus provide developers with mechanisms that improve encapsulation. The need for dynamic adaptations on the one hand and the need for properly confined components on the other hand pulls programming language design in two opposite directions: either more flexi-bility or more control.This dissertation studies this tension in the context of dynamically-typed object-oriented languages with two language mechanisms that promote software adaptability: reflection and extension meth-ods. For both mechanisms, we demonstrate their usefulness, their harmful effect on encapsulation and propose solutions to retain their power while maintaining encapsulation.

La performance des unités de calcul séquentiel a atteint des limites technologiques qui ont conduit à une transition de la tendance à l'accélération des calculs séquentiels vers une augmentation exponentielle du nombre d'unités de calcul par microprocesseur. Ces nouvelles architectures ne permettent d'augmenter la vitesse de calcul que proportionnellement au parallélisme qui peut être exploité, soit via le modèle de programmation soit par un compilateur optimiseur. Cependant, la disponibilité du parallélisme en soi ne suffit pas à améliorer les performances si un grand nombre de processeurs sont en compétition pour l'accès à la mémoire. Le modèle de streaming répond à ce problème et représente une solution viable pour l'exploitation des architectures à venir. Cette thèse aborde le streaming comme un modèle général de programmation parallèle, plutôt qu'un modèle dédié à une classe d'applications, en fournissant une extension pour le streaming à un langage standard pour la programmation parallèle avec mémoire partagée, OpenMP. Un nouveau modèle formel est développé, dans une première partie, pour étudier les propriétés des programmes qui font appel au streaming, sans les restrictions qui sont généralement associées aux modèles de flot de données. Ce modèle permet de prouver que ces programmes sont déterministes à la fois fonctionnellement et par rapport aux deadlocks, ce qui est essentiel pour la productivité des programmeurs. La deuxième partie de ce travail est consacrée à l'exploitation efficace de ce modèle, avec support logiciel à l'exécution et optimisations de compilation, à travers l'implantation d'un prototype dans le compilateur GCC.

Cette thèse s'inscrit dans l'étude de familles de graphes infinis de présentation finie, de leurs propriétés structurelles, ainsi que des comparaisons entre ces familles. Étant donné un alphabet fini Σ, un graphe infini étiqueté par Σ peut être caractérisé par un ensemble fini de relations binaires (Ra )a∈Σ sur un domaine dénombrable V quelconque. De multiples caractérisations finies de tels ensembles de relations existent, soit de façon explicite grâce à des systèmes de réécriture ou à divers formalismes de la théorie des automates, soit de façon implicite. Après un survol des principaux résultats existants, nous nous intéressons plus particulièrement à trois problèmes. Dans un premier temps, nous définissons trois familles de systèmes de réécriture de termes dont nous démontrons que la rela- tion de dérivation peut être représentée de façon finie. De ces résultats découlent plusieurs questions sur les familles de graphes infinis correspondantes. Dans un se- cond temps, nous étudions deux familles de graphes dont les ensembles de traces forment la famille des langages contextuels, à savoir les graphes rationnels et les graphes linéairement bornés. Nous nous intéressons en particulier au cas des langages contextuels déterministes, ainsi qu'à la comparaison structurelle de ces deux familles. Enfin, d'un point de vue plus proche du domaine de la vérifica- tion, nous proposons un algorithme de calcul des prédécesseurs pour une famille d'automates à pile d'ordre supérieur.

Soit un langage composé par tous les mots d'une longueur donnée $n$. Un cycle de de Bruijn d'ordre $n$ est un mot cyclique tel que tous les mots du langage apparaissent exactement une fois comme facteurs de ce cycle. Un algorithme pour construire le cycle de de Bruijn lexicographiquement minimal est dû à Fredricksen et Maiorana, il utilise les mots de Lyndon du langage. Cette thèse étudie comment généraliser le concept de cycles de de Bruijn pour un langage composé par un sous-ensemble de mots de longueur $n$, en particulier les langages de tous les mots de longueur $n$ sans facteurs dans une liste de facteurs interdits. Premièrement, nous étudions le cas des mots sans le facteur 11. Nous fournissons de nouvelles preuves de l'algorithme de Fredricksen et Maiorana qui nous permettent de prolonger ce resultat au cas des mots sans le facteur $1^i$ pour n'importe quel $i$. Nous caractérisons pour quels langages de mots de longueur $n$ existe un cycle de de Bruijn, et nous étudions également quelques propriétés de la dynamique symbolique de ces langages, en particulier des langages définis par des facteurs interdits. Pour ces genres de langages, nous présentons un algorithme pour produire un cycle de de Bruijn, en utilisant les mots de Lyndon du langage. Ces résultats utilisent la notion du graphe de de Bruijn et réduit le problème à construire un cycle eulérien dans ce graphe. Nous étudions le problème de la construction du cycle minimal dans un langage avec des facteurs interdits en employant le graphe de de Bruijn. Nous étudions deux algorithmes, un algorithme glouton simple et efficace qui fonctionne avec quelques familles de langages, et un algorithme plus complexe qui résout ce problème pour n'importe quel graphe eulérien.

Cette thèse traite des langages reconnaissables de mots indexés par des ordinaux. Plusieurs classes d'automates qui reconnaissent de tels mots ont été introduites par Büchi. Elles diffèrent par la longueur des mots reconnus par les automates. Nous en utilisons quatre: la classe pour les mots de longueur , celle pour les mots de longueur inférieure à , où n est un entier naturel, celle pour les mots de longueur dénombrable, et celle pour les mots de longueur quelconque. Nous y ajoutons la classe des automates de Kleene traditionnelle, sur les mots finis. Nous remontrons que ces différentes définitions d'automates sont équivalentes, c'est-à-dire que données deux de ces classes et un automate d'une des deux, la restriction du langage reconnu par l'automate aux mots du domaine le plus petit des deux classes est la restriction du langage reconnu par un automate de l'autre classe au même domaine. Nous donnons également une présentation unifiée de la déterminisation pour chacune des classes qui reconnaît au plus des mots de longueur dénombrable. Les semigroupes finis sont un formalisme équivalent aux automates pour définir des ensembles de mots finis. Perrin, Pin et Wilke ont introduits des structures algébriques adaptées à l'étude des langages de mots de longueur , qui, quand elles sont finies, sont équivalentes aux automates. Nous généralisons l'approche algébrique de la théorie des langages reconnaissables de mots de longueur aux mots de longueur inférieure à , puis aux mots de longueur dénombrable. Pour cela, nous définissons deux structures algébriques, les -semigroupes et les -semigroupes, qui, quand elles sont finies, sont équivalentes respectivement aux automates pour les mots de longueur inférieure à et aux automates pour les mots de longueur dénombrable. Comme pour le cas des mots de longueur , une algèbre syntaxique peut être canoniquement associée à chaque langage reconnaissable. Nous définissons le produit de Schützenberger et le produit en couronne sur les -semigroupes. Nous étendons également le théorème des variétés d'Eilenberg aux mots de longueur dénombrable. Finalement, nous remontrons l'équivalence entre langages reconnus par automates et langages définis par énoncés de logique monadique du second ordre quand on s'intéresse aux mots de longueur dénombrable. Le théorème d'équivalence de Schützenberger entre langages sans étoile et semigroupes finis apériodiques est étendu aux mots de longueur inférieure à , et le théorème d'équivalence entre langages sans étoile et langages définis par énoncés de logique du premier ordre de l'ordre linéaire de McNaughton et Papert est étendu aux mots de longueur quelconque.

Les services informatiques, et particulièrement les services sur le Web, permettent le traitement ou l'échange d'informations. Leur composition ainsi que la construction de workflows à partir de services permettent la réalisation de tâches complexes. Toutefois, seules des informations utiles à leur gestion informatique (stockage, exécution, etc.) sont spécifiées dans les langages de description de services ou de compositions de services tels que WSDL, BPEL ou XPDL. Ces descriptions, essentiellement syntaxiques, ne sont pas suffisamment riches pour permettre une gestion complexe supportant la découverte, l'interopérabilité ou l'adaptativité de services au niveau sémantique. En effet, ces descriptions ne permettent pas de lier explicitement les services informatiques et les compositions qu'elles définissent aux fonctions et aux processus implémentés ainsi qu'aux concepts manipulés. Dans les domaines de l'ingénierie par exemple, l'activité de composition de services informatiques reste traditionnellement à la charge des ingénieurs. L'absence de sémantique explicite rend les services et workflows informatiques difficilement compréhensibles, réutilisables et composables pour les ingénieurs du domaine d'intérêt qui n'ont pas contribué à leur conception et ayant des connaissances techniques et informatiques en général limitées. Ces ingénieurs restent ainsi dépendants des développeurs de logiciels pour l'utilisation ou la composition de services informatiques. Pour apporter une solution aux problèmes évoqués, de récentes approches ont été proposées. Cependant, leurs mécanismes d'enrichissement sémantique ne séparent pas la partie syntaxique, utile au stockage ou à l'exécution, de la partie sémantique, utile à la découverte ou à la composition. En outre, ces mécanismes ne fournissent aucune classification hiérarchique ou relationnelle selon la sémantique des services informatiques. Pour remédier à ces limitations, nous proposons une approche basée sur la définition d'ontologies de services (conceptualisations partagées) et d'indexations sémantiques. Notre proposition s'appuie sur une architecture de persistance centrée autour des bases de données à base ontologique pour stocker et indexer les différents services ainsi que leurs compositions. La mise en oeuvre de notre approche consiste en un prototype logiciel implantant les concepts de service et de workflow sémantiques permettant de stocker, de rechercher, de remplacer, de réutiliser les services et les workflows informatiques existants et d'en construire de nouveaux de manière incrémentale. Ces travaux sont validés en étant appliqués au domaine de la modélisation géologique et de l'ingénierie pétrolière et plus particulièrement à l'interprétation sismique.

Ce document présente différents outils pour représenter et manipuler des ensembles infinis de n-uplets d'arbres appelés langages de n-uplets d'arbres. Nous avons choisi la programmation logique comme formalisme pour décrire les langages de n-uplets d'arbre (c.à.d. les relations) et les techniques de transformations de programmes pour calculer les opérations sur ceux-ci. Dans un premier temps on étudie une classe de relations closes par la plupart des opérations ensemblistes, la classe des relations pseudo-régulières. Grâce à un lien entre programmes logiques et systèmes de réécriture, nous définissons des classes de systèmes de réécriture conditionnelle dont la clôture transitive est une relation pseudo-régulière. On applique ce résultat pour donner une classe décidable de formules du premier ordre basées sur le prédicat de joignabilité où R est un système de réécriture conditionnel pseudo-régulier. Ensuite on étend ce résultat au second ordre, les variables du second ordre étant interprétées comme des relations. A partir d'un algorithme général original décidant de la satisfiabilité de formules du second ordre sous certaines conditions, nous représentons une instance des variables du second ordre en système de réécriture conditionnel. On montre que ce travail peut permettre la synthèse automatique de programme. Dans un dernier temps, nous utilisons des sur-approximations pour des tests d'inconsistances. A cet effet, nous utilisons une classe de programmes logiques non réguliers dont le test du vide est décidable pour effectuer la sur-approximation. Nous appliquons finalement cette méthode à la vérification de protocoles cryptographiques.

L'interopérabilité des systèmes informatiques est un besoin important dans une société mondialisée où les entreprises tendent plus à communiquer et à intégrer leurs systèmes qu'à rester isolées. Cette notion implique de faire communiquer et de coordonner efficacement des systèmes qui souvent n'ont pas été conçus pour fonctionner ensemble. Afin d'obtenir l'interopérabilité, il s'avère donc toujours nécessaire de modifier les systèmes existants pour les intégrer dans un nouveau système, mais en réutilisant autant que possible les notions liées aux systèmes préexistants. Les langages de programmation, en tant qu'outils de construction de systèmes informatiques, jouent un rôle non négligeable dans les solutions aux problèmes d'interopérabilité, en particulier lorsque les systèmes ont été construits avec des langages différents. Les langages de programmation peuvent être considérés également comme des systèmes qui interopèrent grâce à des mécanismes spécifiques permettant aux programmes écrits dans les différents langages d'échanger des données et d'invoquer des algorithmes. Ces mécanismes sont appelés emph{interfaces à un langage étranger} (ILE). L'objectif de cette thèse est de définir théoriquement le concept de l'interopérabilité des langages de programmation et de proposer un cadre conceptuel pour étudier et spécifier des mécanismes d'interopérabilité, à partir de la combinaison systématique des sémantiques opérationnelles des langages. Notre cadre peut s'appliquer à la formalisation d'interfaces (ILE) existantes entre deux langages de programmation où l'un est implémenté dans l'autre, et à la conception de nouvelles interfaces entre langages de programmation qui ont des implémentations indépendantes. / Interoperability of computing systems is a real need in a ``global society' where most enterprises want to communicate and integrate their information systems. This concept implies to coordinate systems that were not designed at the start to work together. Hence, to obtain the interoperability, it is always necessary to modify the existing systems and integrate them into a new system, for which the concepts related to those legacy systems have been reused as most as possible. Programming languages are an essential tool for building computing systems, so they play a non negligible role in the solutions for interoperability, specially when systems have been built with different languages. We can also consider programming languages as interoperable systems that can work together by defining mechanisms that allow programs written in the different languages to exchange data and algorithm calls. Those mecanisms are incorportated into a {it foreign-language interface} (FLI). The main goal of this thesis is the definition of a conceptual framework for programming language interoperability. That framework is based on the systematic composition of the execution models of programming languages according to a mechanism for program interoperability. We use the formalism of structural operational semantics as the way to have precise descriptions of execution models of programming languages. Our framework can be used to describe existing interfaces (FLI) between two programming languages where one of the languages is implemented in the other language, and to design new interfaces for programming languages that have independent implementations.

Thèse doctorat : Informatique : Rennes 1 : 2005. / Bibliogr. p. 193-202.

Thèse de doctorat : Informatique : Paris 12 : 2005. / Titre provenant de l'écran-titre. Bibliogr. p. 267-281.