Ces dernières années ont vu l’émergence d’architectures orientées services (SOA) conçues pour faciliter la création, l’exposition, l’interconnexion et la réutilisation d’applications à base de services. Les services Web sont la réalisation la plus importante de cette architecture SOA. Ce sont des applications auto descriptives et modulaires fournissant un modèle simple de programmation et de déploiement d’applications. La composition de services Web, en particulier l’orchestration, est au coeur de l’ingénierie à base de services (SOC pour Service Oriented Computing) puisque elle supporte la construction de nouveaux services composés à partir de services de base. De son côté, WS-BPEL (ou BPEL) s’est imposé depuis 2005 comme le langage standard d’orchestration de services Web. Cette thèse de Doctorat s’articule autour du test fonctionnel de l’orchestration de services décrite en langage BPEL, qui consiste à établir la conformité de l’implantation d’un service composé par rapport à sa spécification. Nos activités de recherche ont été motivées par les caractéristiques spécifiques de la composition de services surtout celle décrite en BPEL, et par la nécessité d’automatisation des tests. L’objectif de cette thèse est double : d’une part, proposer une modélisation formelle de l’orchestration de services, et d’autre part, proposer une méthode de test complète de l’orchestration de services, allant de la modélisation formelle de l’orchestration à l’exécution des tests, incluant la génération automatique de cas de test. Notre modèle formel (appelé WS-TEFSM) permet de décrire une grande partie de BPEL et prend en considération les propriétés temporelles de la composition de service. La modélisation formelle est la première phase de notre approche de test. Par conséquent, nous utilisons le modèle formel résultant pour la génération de cas de test satisfaisant un ensemble d’objectifs de test. L’automatisation de la génération de cas de test a été mise en oeuvre par l’implémentation d’une stratégie efficace d’exploration partielle de l’espace d’états (i.e. Hit-Or-Jump) dans le simulateur IF. Pour se focaliser seulement sur les erreurs potentielles du service orchestrateur (service composé), nous proposons une approche de test boîte grise consistant à simuler les services partenaires de cet orchestrateur. Nous avons abordé ces problématiques à la fois d’un point de vue théorique et pratique. En plus de la proposition d’une modélisation formelle de l’orchestration de services et d’un algorithme de génération de cas de test temporisés, nous avons implémenté ces deux concepts en développant deux prototypes. BPEL2IF permet de transformer une orchestration de services décrite en BPEL en une spécification formelle à base d’automates temporisés (spécification IF). TestGen-IF permet de dériver automatiquement des cas de test temporisés. Enfin, pour valider notre démarche, nous avons appliqué notre approche de test à des cas d’études de taille réelle. / Last years have seen the emergence of the service oriented architecture (SOA) designed to facilitate the creation, the publication, the networking and the reuse of applications based on services. Web services are the most important realization of the SOA architecture. They are self descriptive and modular entities which provide a simple model of programming and application deployment. Web services composition, especially orchestration, is at the heart of service oriented computing (SOC), since it supports the construction of new composite services out of basic services. WS-BPEL (BPEL for short) has emerged since 2005 as the standard language for Web service orchestration. This PhD thesis focuses on functional testing of service orchestrations described in BPEL, which aims to establish the conformance of a composite service implementation to its specification. Our research activities have been motivated by specific features of the BPEL composition, and the need for test automation. The objective of this thesis is twofold : on the one hand, to propose a formal modeling of service orchestration, and on the other hand, to propose a comprehensive testing approach for orchestrations, ranging from orchestration modeling to tests execution, including automatic test case generation. Compared to existing work, our formal model covers a large subset of BPEL constructs and focuses on the temporal properties of the composition. The formal model is a first step of our testing approach. Afterwards, we use the model to generate the test cases according to test purposes. We automate the test generation by implementing an efficient state space search strategy inside an open-source simulator, i.e. the IF simulator. In our case, to focus on the potential errors of the orchestrator, we propose a gray box approach which consists on the simulation of the partners of this orchestrator. We have addressed these issues both from a theoretical and practical perspective. Therefore, besides proposing expressive orchestration models and test case generation algorithm, we have developed prototypes (BPEL2IF and TestGen-IF) as a proof of concepts. BPEL2IF transforms a BPEL orchestration into a formal specification based on timed automata (IF specification). TestGen- IF generates automatically timed test cases. Moreover, to validate our proposal, we have applied our testing approach on real size case studies.

Le problème de l'extraction d'information dans des documents semi-structurés, du type XML, constitue un des plus importants domaines de la recherche actuelle en informatique. Il a généré un grand nombre de travaux tant d'un point de vue pratique, que d'un point de vue théorique. Dans ce travail de thèse, notre étude porte sur deux objectifs : 1. évaluation des requêtes sur un document assujetti à une politique de contrôle d'accès, 2. évaluation des requêtes sur un document pouvant être partiellement ou totalement compressé. Notre étude porte essentiellement sur l'évaluation des requêtes unaires, càd. sélectionnant un ensemble des noeuds du document qui satisfont les propriétés spéciées par la requête. Pour exprimer les requêtes, nous utilisons le XPath le principal langage de sélection dans les documents XML. Grâce à ses axes navigationels, et ses ltres qualicatifs, XPath permet la navigation dans des documents XML, et la sélection des noeuds répondant à la requête. Les expressions XPath sont à la base de plusieurs formalismes de requêtes comme XQuery, XSLT, ils permettent également de dénir les clés d'accès dans XML Schema et XLink, et de référencer les éléments d'un document externe dans XPointer.

Ce mémoire fait partie du domaine de la combinatoire des mots et plus particulièrement de l'étude de la complexité palindromique (le nombre de facteurs palindromes) des mots infinis. La conjecture de Hof, Knill et Simon, énoncée pour la première fois en 1995, donne une caractérisation des points fixes dont la complexité palindromique est infinie. Récemment, elle a été résolue pour les points fixes sur un alphabet binaire (Tan, 2007). Dans ce mémoire, nous la démontrons pour les points fixes de morphismes uniformes sur un alphabet binaire (ce n'est pas plus général que le résultat de Tan). De plus, notre approche permet d'obtenir une démonstration d'un résultat similaire pour les points fixes contenant une infinité d'antipalindromes. Afin d'atteindre notre objectif, nous établissons un ensemble de résultats combinatoires sur les mots. En effet, nous faisons une étude des ƒ-palindromes et de certaines équations qui en contiennent. Ensuite, nous introduisons les morphismes de classe P, P¹ et ƒ-P et nous démontrons notamment que l'ensemble des morphismes de classe P¹ est un monoïde. Nous rassemblons également les résultats d'un travail précédent sur les morphismes conjugués. Finalement, nous étudions les chevauchements de mots et nous construisons un graphe de chevauchements, assise de notre démonstration de la conjecture. Toutes ces recherches ont contribué au développement d'un outil informatique voué à l'étude de questions soulevées en combinatoire des mots. Ce dernier est constitué d'un ensemble de classes et de fonctions écrites en langage Python annexées à ce mémoire. Elles seront bientôt incluses dans un paquetage sur la combinatoire des mots associé au logiciel libre Sage. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire des mots, ƒ-palindrome, Complexité palindromique, Conjecture de Hof, Knill et Simon, Point fixe de morphisme, Chevauchement, Automates.

L'objectif du projet « Apparatus » est de créer un système interactif dont le modèle ultime est la conversation, c'est-à-dire un système où le participant et l'automate s'engagent dans une dynamique dialogique. Il s'agit d'un mémoire-création contenant deux facettes. L'une est la création d'un processus automate basé sur des algorithmes déterministes et modélisés à l'aide du logiciel de programmation Max/MSP/Jitter permettant d'effectuer des performances en temps réel, et l'autre consiste à présenter, à l'aide du document d'accompagnement, les notions sous-jacentes à notre démarche de création. Les sujets traités dans ce mémoire touchent les relations ontologiques, l'intentionnalité, la représentation et la modélisation du vivant d'un système interactif. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : interaction, conversation, automate, participant, représentation, autopoièse

The development of large products, whether it is software or hardware, faces many challenges. Two of these challenges are to keep everyone involved up-to-date on the latest developments, and to get a clear overview of the components of the product. A proposed solution is to have a graph presenting all the necessary information about the product. The issue with having a graph of a constantly changing product is that it requires a lot of maintenance to keep it up-to-date. This thesis presents the implementation of a software for Ericsson, that can gather automatically the required information about a given product and creates a graph to present it. The software traverses a file structure, containing information about a product, and stores it. This information is then used to create two different graphs: a tree graph and a box graph.The graphs were evaluated, both by the author and by the team at Ericsson, based on visualisation principles.  The results show that the automatically gathered information is effective and can communicate the information needed. The tree graph receives slightly favourable reviews in comparison to the currently available and manually created graph. However, limitations for graph layout on the visualisation tool made the graphs larger than necessary and, therefore, harder to understand. In order to achieve a better result, other visualisation tools could be considered. The software created tree graphs that are useable at Ericsson, and could prove helpful for development.

Cette thèse contribue à une approche formelle de conception d'un programme de contrôle/commande pour les systèmes automatisés de production (SAP) contrôlés par des automates programmables industriels (API). Dans ce contexte, deux constats principaux ont été soulevés : il existe manque de méthodologie efficace pour la conception d'un programme API dans le monde industriel et les méthodes formelles issues du monde académique ne sont ni connues ni utilisées par l'industrie car trop complexes. Par ailleurs, l'industrie du futur nécessitera des contrôleurs toujours plus flexibles et fiables. La flexibilité implique que les programmes seront encore plus difficiles à réaliser, et par conséquent, la difficulté pour garantir la fiabilité de ceux-ci sera accrue.Pour répondre à ces problématiques, une méthode de conception formelle s'intégrant dans un cycle de développement industriel classique (cycle en V) a été proposée. De plus, afin de faciliter le transfert vers l'industrie tant d'un point de vue technique (API) qu’humain (pratique des automaticiens), le formalisme utilisé est entièrement basé sur des variables et des équations logiques appelées contraintes logiques. Ces contraintes logiques permettent la spécification des exigences informelles recensées dans le cahier des charges. A partir de ces contraintes logiques, un algorithme de résolution des contraintes, implémentable dans un API, est synthétisé et implémenté automatiquement dans un langage de programmation normalisé pour API. Ce filtre logique peut être utilisé pour : commander un SAP contrôlé par un API, vérifier formellement un programme API, mettre en sécurité un programme API déjà existant présentant des erreurs.Les travaux de cette thèse ont eu pour objectif de lever certains verrous et de globalement améliorer et renforcer l'approche par filtre logique. Dans le but de généraliser l'approche par filtre, un effort important a été réalisé autour de la formalisation des contraintes logiques et des différentes fonctions et propriétés associées au filtre logique. Cet apport de formalisation a permis, en particulier, de proposer une approche de vérification formelle de la notion de cohérence d'un filtre logique ainsi qu'une condition nécessaire et suffisante à cette propriété. Enfin, après avoir mis à jour l'algorithme d'implémentation classique, deux algorithmes de recherche locale d'une solution basés sur des techniques de solveur SAT ont été proposés. / This thesis contributes to a formal approach to design control/command program for automated production systems controlled by Programmable Logical Controller (PLC). In this context, two main observations have been highlighted: there is a lack of efficient methodology for the design of PLC program in the industrial field and the academicals formal approaches are neither known nor used in manufacturing industry due to high complexity. Furthermore, the industry of future will require flexible and reliable PLC program. The flexibility implies that programs will be even more difficult to design and, consequently, the complexity to guarantee the reliability will be increased.To address these issues, a formal design approach, presented as a classical V-cycle, have been proposed. Moreover, to facilitate the industrial transfer from both technical (PLC) and human (engineer practice) point of view, the formalism is exclusively based on logical variables and equations called logical constraints. These constraints are used to specify the informal requirements described in the specification book. From these constraints, a logical filter is synthesized automatically and a solving algorithm, IEC 61131-3 compliant, is implemented in the PLC program. This logical filter may be used to: command an automated production system controlled by a PLC, verify formally a PLC program, and make safe an existing PLC program containing errors.The contributions of this thesis covered the whole development cycle: formal specification, formal analysis and synthesis, automatic implementation in a PLC program. To support these contributions, a significant effort was made on the formalism based on logical constraints. This new formalism has allowed, in particular, to propose a necessary and sufficient condition to the coherence property of a logical filter and to guarantee the convergence of the online solving algorithm. At least, the classical solving algorithm has been updated according to the new formalism, and two algorithms based on SAT solver techniques and local research have been proposed and tested on real PLC.

Les systèmes hybrides sont des systèmes qui combinent des composantes discrètes et des composantes continues. Les composantes continues peuvent représenter un environnement physique obéissant à des règles de changement continu, par contre les composantes discrètes peuvent représenter des contrôleurs discrets qui sondent et manipulent les composantes continues en temps réel. Deux approches peuvent être adoptées pour spécifier ces systèmes, la première étant basée sur des automates (hybrides) et utilise des méthodes d'analyse algorithmiques. La seconde est basée sur les logiques et utilise des preuves formelles comme méthodes d'analyse. Dans une première partie de cette thèse nous considérons l'approche basée sur les automates. Nous étudions la décidabilité du problème de la vérification pour certaines classes de systèmes hybrides linéaires. Nous prenons comme modèles des automates hybrides linéaires avec des structures de données discrètes non bornées. Nous exhibons différents cas de tels systèmes dont le problème de la vérification est décidable. Dans une seconde partie nous considérons l'approche basée sur les logiques et plus particulièrement celle basée sur le «Calcul de Durées». Nous étudions les relations existantes entre cette approche et la précédente ; nous montrons comment cette liaison permet de mettre en évidence un fragment important du «Calcul de Durées» pour lequel le problème de la vérification est décidable

Ce travail concerne l'expérimentation numérique de trois modèles de mathématiques appliquées : le premier chapitre est consacré à la localisation des minima de Pareto relatifs à plusieurs formes quadratiques ; le second chapitre concerne l'expérimentation numérique d'un modèle itératif de la respiration; le troisième chapitre, le plus développé, est consacré à la reconnaissance de caractères par un réseau d'automates à seuil. De nouveaux algorithmes sont proposés, dont on montre l'efficacité accrue. L'expérimentation est conduite sur la reconnaissance de caractères chinois

Cette thèse rassemble plusieurs articles ayant pour sujet l'étude de la dynamique d'une large classe de réseaux d'automates. Deux outils sont introduits: les invariants algébriques associés à l'évolution temporelle; la fonction d'énergie permettant de déterminer l'évolution du réseau, tant en régime transitoire qu'en régime stationnaire. Finalement, nous étudions des réseaux unidimensionnels, la dynamique d'un automate à mémoire et les réseaux des fonctions booléennes à deux variables

No description available.