Le stockage et la gestion de données sont des questions centrales en infor- matique. La structuration sous forme d'arbres est devenue la norme (XML, JSON). Pour en assurer la pérennité et l'échange efficace des données, il est nécessaire d'identifier de nouveaux mécanismes de transformations automati- sables. Nous nous concentrons sur l'étude de transformations d'arbres en mots représentées par des machines à états finies. Nous définissons les transducteurs séquentiels d'arbres en mots ne pouvant utiliser qu'une et unique fois chaque nœud de l'arbre d'entrée pour décider de la production. En réduisant le problème d'équivalence des transducteurs séquentiels à celui des morphismes appliqués à des grammaires algébriques (Plandowski, 95), nous prouvons qu'il est décidable en temps polynomial. Cette thèse introduit la notion de transducteur travailleur, forme norma- lisée de transducteurs séquentiels, cherchant à produire la sortie le "plus tôt possible" dans la transduction. A l'aide d'un algorithme de normalisation et de minimisation, nous prouvons qu'il existe un représentant canonique, unique transducteur travailleur minimal, pour chaque transduction de notre classe. La décision de l'existence d'un transducteur séquentiel représentant un échantillon, i.e. paires d'entrées et sorties d'une transformation, est prouvée NP-difficile. Nous proposons un algorithme d'apprentissage produisant à par- tir d'un échantillon le transducteur canonique le représentant, ou échouant, le tout en restant polynomial. Cet algorithme se base sur des techniques d'infé- rence grammaticales et sur l'adaptation du théorème de Myhill-Nerode.

Ce travail présente l'approche UML/PNO (Unified Modelling Language with Petri Net Objects) pour la spécification de systèmes temps réel. La méthode propose d'enrichir la description semi-formelle UML du système par une modélisation formelle basée sur les réseaux de Petri. Les concepts UML de sous-système et d'interface ont été étendus afin d'améliorer la description de la vue système en termes de tructuration, gestion de projet et organisation de la modélisation. L'objectif est également d'adapter la méthode de modélisation système à une approche " orientée composant " pour le temps réel. Le concept " d'objet composé " permet d'intégrer des spécificités temps réel au sein du composant (protocole de communication, contrainte temporelle, effet observable). Le comportement des objets est spécifié à l'aide des réseaux de Petri à places et transitions stochastiques temporelles afin de permettre la validation et la vérification du système en cours de spécification. L'approche de validation propose des traductions semi-automatiques des diagrammes UML en réseaux de Petri. Les techniques classiques de simulation et d'évaluation de performances peuvent alors être appliquées. Ces traductions présentent l'avantage de rassembler, sur un même modèle à réseau de Petri, tous les aspects dynamiques du composant apparaissant dans différents diagrammes UML et de vérifier ainsi la cohérence de son comportement et de son utilisation. La vérification utilise les techniques d'analyse formelle, basées sur l'utilisation conjointe du graphe de classes et de la logique linéaire. Une approche de vérification quantitative des contraintes temporelles est proposée au niveau de l'analyse des besoins et des exigences du système. Une partie de ce travail a été concrétisée par l'intégration d'un module (ArgoPNO) dans l'atelier de génie logiciel ArgoUML. A ce jour, une première automatisation de la démarche de vérification des contraintes temporelles est opérationnelle sur cet outil.

Nous nous positionnons dans un contexte d'informatique ambiante dans lequel il arrive que les besoins de l'utilisateur n'aient pas été prévus, notamment en situation exceptionnelle. Dans ce cas, il peut ne pas exister de système préconçu qui réponde exactement à ces besoins. Pour les satisfaire, il faut alors pouvoir composer les systèmes disponibles dans l'environnement, et le système composé doit permettre à l'utilisateur de faire des choix à l'exécution. Ainsi, l'utilisateur a la possibilité d'adapter l'exécution de la composition à son contexte. Cela signifie que la composition intègre des structures de contrôle de l'exécution, destinées à l'utilisateur : la composition est dite flexible. Dans cette thèse, nous proposons de répondre au problème de la composition flexible en contexte d'intelligence ambiante avec un planificateur produisant des plans flexibles. Dans un premier temps, nous proposons une modélisation de la planification flexible. Pour cela, nous définissons les opérateurs de séquence et d'alternative, utilisés pour caractériser les plans flexibles. Nous définissons deux autres opérateurs au moyen de la séquence et de l'alternative : l'entrelacement et l'itération. Nous nous référons à ce cadre théorique pour délimiter la flexibilité traitée par notre planificateur Lambda-Graphplan. L'originalité de Lambda-Graphplan est de produire des itérations en s'appuyant sur une approche par graphe de planification. Nous montrons notamment que Lambda-Graphplan est très performant avec les domaines se prêtant à la construction de structures itératives. / In a context of Ambient Intelligence, some of the user's needs might not be anticipated, e.g. when the user is in an unforeseen situation. In this case, there could exist no system that exactly meets their needs. By composing the available systems, the user could obtain a new system that satisfies their needs. In order to adapt the composition to the context, the composition must allow the user to make choices at runtime. So the composition includes control structures for the user: the composition is flexible. In this thesis, I deal with the problem of the flexible composition by automated planning. I propose a model of flexible planning. The sequence and the choice operators are defined and used to characterize flexible plans. Then, two other operators are derived from the sequence and the choice operators: the interleaving and the iteration operators. I refer to this framework to define the flexibility produced by my planner, Lambda-Graphplan, which is based on the planning graph. The originality of Lambda-Graphplan is to produce iterations. I show that Lambda-Graphplan is very efficient on domains that allow the construction of iterative structures.

Les grammaires catégorielles abstraites (ou λ-grammaires) sont un formalisme basé sur le λ-calcul simplement typé. Elles peuvent être vues comme des grammaires générant de tels termes, et ont été introduites afin de modéliser l'interface entre la syntaxe et la sémantique du langage naturel, réunissant deux idées fondamentales : la distinction entre tectogrammaire (c.a.d. structure profonde d'un énoncé) et phénogrammaire (c.a.d représentation de la surface d'un énoncé) de la langue, exprimé par Curry ; et une modélisation algébrique du principe de compositionnalité afin de rendre compte de la sémantique des phrases, due à Montague. Un des avantages principaux de ce formalisme est que l'analyse d'une grammaires catégorielle abstraite permet de résoudre aussi bien le problème de l'analyse de texte, que celui de la génération de texte. Des algorithmes d'analyse efficaces ont été découverts pour les grammaires catégorielles abstraites de termes linéaires et quasi-linéaires, alors que le problème de l'analyse est non-élémentaire dans sa forme la plus générale. Nous proposons d'étudier des classes de termes pour lesquels l'analyse grammaticale reste solvable en temps polynomial. Ces résultats s'appuient principalement sur deux théorèmes de typage : le théorème de cohérence, spécifiant qu'un λ-terme donné est l'unique habitant d'un certain typage ; et le théorème d'expansion du sujet, spécifiant que deux termes β-équivalents habitent les même typages. Afin de mener cette étude à bien, nous utiliserons une représentation abstraite des notions de λ-termes et de typages, sous forme de jeux. En particulier, nous nous appuierons grandement sur cette notion afin de démontrer le théorème de cohérence pour de nouvelles familles de λ-termes et de typages. Grâce à ces résultats, nous montrerons qu'il est possible de construire de manière directe, un reconnaisseur dans le langage Datalog, pour des grammaires catégorielles abstraites de λ-termes quasi-affines.

Les systèmes embarqués modernes ont atteint un niveau de complexité qui fait qu'il n'est plus possible d'attendre les premiers prototypes physiques pour valider les décisions sur l'intégration des composants matériels et logiciels. Il est donc nécessaire d'utiliser des modèles, tôt dans le flot de conception. Les travaux présentés dans ce document contribuent à l'état de l'art dans plusieurs domaines. Nous présentons dans un premier temps de nouvelles techniques de vérification de programmes écrits dans des langages généralistes comme C, C++ ou Java. Dans un second temps, nous utilisons des outils de vérification formelle sur des modèles écrits en SystemC au niveau transaction (TLM). Plusieurs approches sont présentées, la plupart d'entre elles utilisent des techniques de compilations spécifiques à SystemC pour transformer le programme SystemC en un format utilisable par les outils. La seconde partie du document s'intéresse aux propriétés non-fonctionnelles des modèles~: performances temporelles, consommation électrique et température. Dans le contexte de la modélisation TLM, nous proposons plusieurs techniques pour enrichir des modèles fonctionnels avec des informations non-fonctionnelles. Enfin, nous présentons les contributions faites à l'analyse de performance modulaire (MPA) avec le calcul temps-réel (RTC). Nous proposons plusieurs connections entre ces modèles analytiques et des formalismes plus expressifs comme les automates temporisés et le langage de programmation Lustre. Ces connexion posent le problème théorique de la causalité, qui est formellement défini et résolu avec un algorithme nouveau dit de " fermeture causale ".