Bien que les techniques d'autotest intégré soient en perpétuel développement sous forme de théories et de schémas de conception, leur réalisation concrète et leur implémentation posent des problèmes cruciaux. Une stratégie d'autotest intégré est proposée dans cette thèse pour des circuits générés par compilation de silicium. Le schéma UBIST d'unification du test en-ligne et hors-ligne assure la plupart des tests nécessaires durant la vie d'un circuit intégré (test de fin de fabrication, test de maintenance, test en-ligne,...). A la base du schéma ubist se trouve le schéma self-checking (test en-ligne, pour lequel le circuit est compose de blocs fonctionnels strongly fault secure (sfs) et de contrôleurs strongly code disjoint (scd). Le but a atteindre par de tels circuits est couramment appelé le totally self-checking goal, qui consiste a détecter la première erreur survenant aux sorties du bloc fonctionnel, sous forme d'indication d'erreur sur les sorties du contrôleur. Autour de ce schéma self-checking est implémentée une structure de test, du type bilbo, assurant des phases de test hors-ligne, qui a pour objectif d'augmenter le taux de couverture des pannes multiples et de renforcer les propriétés SFS et SCD pour certains blocs fonctionnels et contrôleurs. L'unification des tests en-ligne et hors-ligne permet de tirer les avantages de chacun de ces tests, permettant une implémentation efficace d'autotest intégré. Une méthodologie de conception pour implémenter ce schéma UBIST est proposée pour des parties contrôle hiérarchiques a base de plas et des parties operatives parallèles en structure bit-slice (du type de celle du mc 68000). Ce sont les architectures cibles utilisées par le compilateur de silicium SYCO (développé au sein de l'équipe d'architecture des ordinateurs du laboratoire TIM3/IMAG). Une solution topologique efficace est proposée pour ces schémas UBIST

La synthèse logique joue un rôle fondamental dans les compilateurs de silicium. Alors que l'état de l'art de la synthèse deux couches est très avance, celui de la synthèse multi-couches reste encore un sujet très ouvert. L'objet de cette thèse est de présenter des méthodes originales de synthèse de contrôleurs et de systèmes combinatoires pour une implémentation multi-couches a base de cellules de bibliothèque. Le premier chapitre définit le concept de compilation de silicium et introduit l'une de ses composantes, la synthèse logique. L'importance du marche de la synthèse logique y est clairement définie ainsi que ses implications dans la conception actuelle de circuits intégrés. Le deuxième chapitre concerne la synthèse de contrôleurs. Le probleme du codage des machines d'états fini est traite en détail et une methode basée sur la théorie d'immersion de cubes intersectant dans un hypercube booléen est proposée. Le troisième chapitre est consacre a la synthèse de circuits combinatoires et une methode d'optimisation temporelle de tels dispositifs est développée. Ces travaux ont été implémentés dans un environnement industriel

Le but de ce travail est d'exposer de nouveaux résultats concernant l'utilisation d'une classe particulière de réseaux de neurones formels (les Perceptrons Affines Par morceaux: PAP) dans le cadre du contrôle optimal en boucle fermée. Les résultats principaux obtenus sont: plusieurs propriétés des PAP, concernant la nature des fonctions qu'ils peuvent émuler, un théorème constructif de représentation des fonctions continues affines par morceaux, qui permet de construire explicitement un PAP à partir d'une collection de fonctions affines, une série d'heuristiques pour l'apprentissage des paramètres d'un perceptron dans une boucle fermée et dans un cadre de contrôle optimal, des résultats théoriques concernant la stabilité de PAP utilisés comme contrôleurs. La dernière partie est consacrée des applications de ces résultats à la construction automatique de contrôleurs de la combustion de moteurs de voiture, qui ont donné lieu au dépot de deux brevets par Renault.

L'Internet des Objets (IdO) et les Environnements Intelligents (EI) ont attiré beaucoup d'activités de recherche et développement au cours de la dernière décennie. Pourtant, de nombreuses applications IdO/EI d'aujourd'hui sont encore limitées à l'acquisition et au traitement des données de capteurs et de leur contexte, avec un contrôle, le cas échéant, utilisant soit des solutions de base ou demandant l'intervention humaine, loin du contrôle automatique qui est un facteur essentiel de promouvoir ces technologies. Cette thèse vise à apporter le savoir-faire de la théorie du contrôle et des systèmes réactifs dans le domaine IdO/EI pour arriver à une solution avec une méthode formelle pour l'aspect de contrôle qui fait défaut. Nous proposons l'extension d'un canevas logiciel pour une infrastructure générique et partagée IdO/EI qui offre des interfaces de haut niveau pour réduire l'effort de conception, et qui permet l'auto-configuration et l'adaptation des applications de contrôle sur des propriétés génériques de l'environnement sans intervention humaine en utilisant les connaissances générales sur le domaine qui s'appliquent à chaque instance cible de système IdO/EI. Dans cette infrastructure étendue, les entités physiques individuelles (y compris toutes les "choses", appareils électriques et sous-ensembles de l'espace) peuvent être regroupées comme des entités virtuelles par des propriétés communes afin de fournir un niveau d'abstraction plus élevé pour le contrôle et d'autres applications, ainsi qu'une meilleure adaptation aux changements des configurations au niveau inférieur. Sur le requis d'une solution générique et commun dénominateur partagée par toutes les applications de l'IdO/EI dans un environnement donné, nous proposons pour cette infrastructure, de modéliser les entités cibles supervisées et contrôlées, y compris les entités individuelles et de leurs regroupements, ainsi que les choses et les entités spatiales, par des automates à états finis, pour être en mesure d'appliquer la technique de la synthèse des contrôleur discrets (SCD) aux différents niveaux d'abstraction et de granularité. SCD est une méthode formelle qui construit automatiquement un contrôleur, s'il existe, en assurant les objectifs de contrôle exigés concernant le modèle de comportement du système donné en termes d'automates parallèles synchrones. Les langages de programmation BZR et les outils Sigali existants sont utilisés pour effectuer la SCD et de générer un contrôleur de manière automatique. Les modules logiciels nécessaires sont proposés dans l'implémentation tels que le module de maintenance de relation qui garde une association correcte entre les instances d'entités individuelles et les groupes, et répercute des commandes d'action du contrôle de haut niveau aux actionneurs correspondants. Ce module est destiné à évoluer plus tard vers une solution plus générique comme une base de données graphes comprenant à la fois la base de connaissances générales et relations spécifiques d'instance environnement. La résolution des conflits entre les objectifs de contrôle venant de contrôleurs concurrent est également indispensable en raison des objectifs de l'ouverture de la plateforme. Un simulateur de contexte basé sur Java a été développé pour simuler l'environnement de la maison au sein de plusieurs scénarios proposés pour la validation, tels que le contrôle de la charge électrique et l'adaptation au contexte de l'activité. / The Internet of Things (IoT) and Smart Environments (SE) have attracted a lot of research and development activities during the last decade. Yet many present-day IoT/SE applications are still limited to the acquisition and processing of sensor data and its context, with control, if any, using either basic solutions or requiring human intervention, far away from the automatic control which is an essential factor to promote the technologies. This thesis targets to bring knowhow from control theory and reactive systems to the IoT/SE domain to achieve a solution with a formal method for the missing control aspect. We propose the extension of a framework in order to build a shared generic IoT/SE infrastructure offering high-level interfaces to reduce design effort, and enabling the self-configuration and adaptation of control applications over generic properties of the environment without human interaction by using general knowledge over the domain that applies to each target instance of IoT/SE system. In this extended framework, individual physical entities (including all relevant "things", appliances and subsets of space) may be grouped as virtual entities by shared properties to provide a higher level abstraction for control and other applications and better adaptation to lower level configuration changes. Requiring a generic common denominator solution shared by all IoT/SE applications in a given environment, we propose for this infrastructure, to model by finite state automata the target entities to be monitored and controlled, including both individual entities and their groupings, as well as things and space entities, to be able to apply discrete controller synthesis (DCS) technique over any of these at different levels of abstraction and granularity. DCS is a formal method which constructs automatically a controller, if it exists, guaranteeing the required control objectives regarding to the given system behavior model in terms of synchronous parallel automata. The existing BZR programming language and Sigali tools are employed to perform DCS and generate a controller in an automatic way. Necessary supporting software modules are proposed in the implementation such as the relation maintenance module keeping the correct association between individual entity instances and groups, and dispatching the action orders from the high level control to corresponding actuators. This module would evolve later to a more generic solution such as a graph data base including both the general knowledge base and specific environment instance relations. Conflict resolution between objectives of control coming from concurrent controllers is also indispensable due to the intended openness of the platform. A java based context simulator has been developed to simulate the home environment within several scenarios proposed for the validation, such as electrical load control and activity context adaptation.

Ce travail de thèse, effectué dans la cadre du projet FUI Minalogic Bluesky, porte sur le test fonctionnel automatisé d'une classe particulière de contrôleurs logiques programmables (em4) produite par InnoVista Sensors. Ce sont des systèmes synchrones qui sont programmés au moyen d'un environnement de développement intégré (IDE). Les personnes qui utilisent et programment ces contrôleurs ne sont pas nécessairement des programmeurs experts. Le développement des applications logicielles doit être par conséquent simple et intuitif. Cela devrait également être le cas pour les tests. Même si les applications définies par ces utilisateurs ne sont pas nécessairement très critiques, il est important de les tester d'une manière adéquate et efficace. Un simulateur inclu dans l'IDE permet aux programmeurs de tester leurs programmes d'une façon qui reste à ce jour informelle et interactive en entrant manuellement des données de test. En se basant sur des recherches précédentes dans le domaine du test des programmes synchrones, nous proposons un nouveau langage de spécification de test, appelé SPTL (Synchronous Programs Testing Language) qui rend possible d'exprimer simplement des scénarios de test qui peuvent être exécutées à la volée pour générer automatiquement des séquences d'entrée de test. Il permet aussi de décrire l'environnement où évolue le système pour mettre des conditions sur les entrées afin d'arriver à des données de test réalistes et de limiter celles qui sont inutiles. SPTL facilite cette tâche de test en introduisant des notions comme les profils d'utilisation, les groupes et les catégories. Nous avons conçu et développé un prototype, nommé "Testium", qui traduit un programme SPTL en un ensemble de contraintes exploitées par un solveur Prolog qui choisit aléatoirement les entrées de test. La génération de données de test s'appuie ainsi sur des techniques de programmation logique par contraintes. Pour l'évaluer, nous avons expérimenté cette méthode sur des exemples d'applications EM4 typiques et réels. Bien que SPTL ait été évalué sur em4, son utilisation peut être envisagée pour la validation d'autres types de contrôleurs ou systèmes synchrones. / This thesis work done in the context of the FUI project Minalogic Bluesky, concerns the automated functional testing of a particular class of programmable logic controllers (em4) produced by InnoVista Sensors. These are synchronous systems that are programmed by means of an integrated development environment (IDE). People who use and program these controllers are not necessarily expert programmers. The development of software applications should be as result simple and intuitive. This should also be the case for testing. Although applications defined by these users need not be very critical, it is important to test them adequately and effectively. A simulator included in the IDE allows programmers to test their programs in a way that remains informal and interactive by manually entering test data.Based on previous research in the area of synchronous test programs, we propose a new test specification language, called SPTL (Synchronous Testing Programs Language) which makes possible to simply express test scenarios that can be executed on the fly to automatically generate test input sequences. It also allows describing the environment in which the system evolves to put conditions on inputs to arrive to realistic test data and limit unnecessary ones. SPTL facilitates this testing task by introducing concepts such as user profiles, groups and categories. We have designed and developed a prototype named "Testium", which translates a SPTL program to a set of constraints used by a Prolog solver that randomly selects the test inputs. So, generating test data is based on constraint logic programming techniques.To assess this, we experimented this method on realistic and typical examples of em4 applications. Although SPTL was evaluated on EM4, its use can be envisaged for the validation of other types of synchronous controllers or systems.

L'Internet des Objets (IdO) et les Environnements Intelligents (EI) ont attiré beaucoup d'activités de recherche et développement au cours de la dernière décennie. Pourtant, de nombreuses applications IdO/EI d'aujourd'hui sont encore limitées à l'acquisition et au traitement des données de capteurs et de leur contexte, avec un contrôle, le cas échéant, utilisant soit des solutions de base ou demandant l'intervention humaine, loin du contrôle automatique qui est un facteur essentiel de promouvoir ces technologies. Cette thèse vise à apporter le savoir-faire de la théorie du contrôle et des systèmes réactifs dans le domaine IdO/EI pour arriver à une solution avec une méthode formelle pour l'aspect de contrôle qui fait défaut. Nous proposons l'extension d'un canevas logiciel pour une infrastructure générique et partagée IdO/EI qui offre des interfaces de haut niveau pour réduire l'effort de conception, et qui permet l'auto-configuration et l'adaptation des applications de contrôle sur des propriétés génériques de l'environnement sans intervention humaine en utilisant les connaissances générales sur le domaine qui s'appliquent à chaque instance cible de système IdO/EI. Dans cette infrastructure étendue, les entités physiques individuelles (y compris toutes les "choses", appareils électriques et sous-ensembles de l'espace) peuvent être regroupées comme des entités virtuelles par des propriétés communes afin de fournir un niveau d'abstraction plus élevé pour le contrôle et d'autres applications, ainsi qu'une meilleure adaptation aux changements des configurations au niveau inférieur. Sur le requis d'une solution générique et commun dénominateur partagée par toutes les applications de l'IdO/EI dans un environnement donné, nous proposons pour cette infrastructure, de modéliser les entités cibles supervisées et contrôlées, y compris les entités individuelles et de leurs regroupements, ainsi que les choses et les entités spatiales, par des automates à états finis, pour être en mesure d'appliquer la technique de la synthèse des contrôleur discrets (SCD) aux différents niveaux d'abstraction et de granularité. SCD est une méthode formelle qui construit automatiquement un contrôleur, s'il existe, en assurant les objectifs de contrôle exigés concernant le modèle de comportement du système donné en termes d'automates parallèles synchrones. Les langages de programmation BZR et les outils Sigali existants sont utilisés pour effectuer la SCD et de générer un contrôleur de manière automatique. Les modules logiciels nécessaires sont proposés dans l'implémentation tels que le module de maintenance de relation qui garde une association correcte entre les instances d'entités individuelles et les groupes, et répercute des commandes d'action du contrôle de haut niveau aux actionneurs correspondants. Ce module est destiné à évoluer plus tard vers une solution plus générique comme une base de données graphes comprenant à la fois la base de connaissances générales et relations spécifiques d'instance environnement. La résolution des conflits entre les objectifs de contrôle venant de contrôleurs concurrent est également indispensable en raison des objectifs de l'ouverture de la plateforme. Un simulateur de contexte basé sur Java a été développé pour simuler l'environnement de la maison au sein de plusieurs scénarios proposés pour la validation, tels que le contrôle de la charge électrique et l'adaptation au contexte de l'activité. / The Internet of Things (IoT) and Smart Environments (SE) have attracted a lot of research and development activities during the last decade. Yet many present-day IoT/SE applications are still limited to the acquisition and processing of sensor data and its context, with control, if any, using either basic solutions or requiring human intervention, far away from the automatic control which is an essential factor to promote the technologies. This thesis targets to bring knowhow from control theory and reactive systems to the IoT/SE domain to achieve a solution with a formal method for the missing control aspect. We propose the extension of a framework in order to build a shared generic IoT/SE infrastructure offering high-level interfaces to reduce design effort, and enabling the self-configuration and adaptation of control applications over generic properties of the environment without human interaction by using general knowledge over the domain that applies to each target instance of IoT/SE system. In this extended framework, individual physical entities (including all relevant "things", appliances and subsets of space) may be grouped as virtual entities by shared properties to provide a higher level abstraction for control and other applications and better adaptation to lower level configuration changes. Requiring a generic common denominator solution shared by all IoT/SE applications in a given environment, we propose for this infrastructure, to model by finite state automata the target entities to be monitored and controlled, including both individual entities and their groupings, as well as things and space entities, to be able to apply discrete controller synthesis (DCS) technique over any of these at different levels of abstraction and granularity. DCS is a formal method which constructs automatically a controller, if it exists, guaranteeing the required control objectives regarding to the given system behavior model in terms of synchronous parallel automata. The existing BZR programming language and Sigali tools are employed to perform DCS and generate a controller in an automatic way. Necessary supporting software modules are proposed in the implementation such as the relation maintenance module keeping the correct association between individual entity instances and groups, and dispatching the action orders from the high level control to corresponding actuators. This module would evolve later to a more generic solution such as a graph data base including both the general knowledge base and specific environment instance relations. Conflict resolution between objectives of control coming from concurrent controllers is also indispensable due to the intended openness of the platform. A java based context simulator has been developed to simulate the home environment within several scenarios proposed for the validation, such as electrical load control and activity context adaptation.

La méthode des invariants est une des plus utilisées méthodes de synthèse pour les SED modélisés par des réseaux de Petri (RdP). Cependant, elle ne garantit pas en général une solution optimale dans la présence de l'incontrôlabilité. Dans ce travail nous proposons une solution à ce problème pour les RdP généralisés. Premièrement, nous proposons une solution d'identification des contraintes admissibles pour les RdP saufs non-conservatifs. La méthode repose sur une définition des contraintes contenant des marquages complémentés. Ceux-ci sont après éliminés en exploitant les composants conservatifs des RdP. Deuxièmement, nous avançons une technique de détermination des contraintes admissibles pour les RdP généralisés. La méthode est basée sur une vision spatiale de l'espace d'états du modèle. Les contraintes sont dérivées de l'équation d'hyperplan affin qui sépare les régions interdite- et autorisée- de cet espace. Nous proposons un algorithme pour le calcul du contrôleur optimal minimal. / The place-invariants method is one of the most popular controller synthesis approaches for Petri net (PN) modeled DES. Unfortunately, the observance of the constraints is not certain in the presence of uncontrollable transitions. This thesis offers a solution to this problem for ordinary and generalized PNs. We begin by studying safe non-conservative PNs, and devising a constraint-determination technique that will always provide a set of admissible constraints for this type of model. The approach stems from the general definition of forbidden states --- that of marking vectors. In the second part of our work, we present an admissible constraint-determination technique for generalized PNs. The method is based on a special view of the system's state space. The constraints are derived from the equation of the affine hyper-plane separating the authorized- and forbidden- regions of this space. We propose an algorithm that allows the identification of the minimal maximally permissive controller.

Garantir le confort thermique des bâtiments est directement lié à la consommation d'énergie. Dans les zones tropicales, les systèmes de refroidissement représentent l'un des postes les plus gourmands en énergie. Afin de réduire la consommation d'énergie mondiale, il est primordial d'améliorer l'efficacité de ces systèmes ou bien de développer de nouvelles méthodes de production de froid. Une installation de refroidissement solaire basé sur le cycle à absorption est une alternative pour réduire les émissions de gaz à effet de serre et la consommation d'électricité. Contrairement aux systèmes classiques de refroidissement à compression mécanique, la production de froid par absorption est un système complexe composé de plusieurs composants comme des panneaux solaires, un ballon de stockage, une tour de refroidissement et une machine à absorption. Outre le dimensionnement des composants, ce système complexe nécessite des actions de contrôle pour être efficace parce que la coordination entre le stockage d'eau chaude, la production et la consommation du froid est nécessaire. Le but de cette thèse est de proposer une structure producteur-consommateur d'énergie basée sur la commande prédictive (MPC). Le système de refroidissement par absorption solaire est considéré comme faisant partie de ce système de production-consommation d'énergie, le système de stockage d'eau chaude est le producteur et la machine à absorption qui distribue de l'eau froide au bâtiment est l'un des consommateurs. Pour que la structure de commande soit modulaire, la coordination entre les sous-systèmes est réalisée en utilisant une approche de partitionnement où des contrôleurs prédictifs locaux sont conçus pour chacun des sous-systèmes. Les contrôleurs des consommateurs calculent un ensemble de profils de demande d'énergie. Ces profils sont ensuite envoyés au contrôleur du producteur qui sélectionne le profil qui minimise le coût global. Dans une première partie, l'approche proposée est testée sur un modèle linéaire simplifié composé d'un producteur et plusieurs consommateurs. Dans une deuxième partie, un cas plus complexe est étudié. Un modèle simplifié d'un système de refroidissement à absorption est évaluée en utilisant l'outil de simulation TRNSYS. Le modèle de production n'est plus linéaire, il est décrit par un modèle non linéaire hybride qui augmente la complexité du problème d'optimisation. Les résultats des simulations montrent que la sous-optimalité induite par la méthode est faible. De plus, la performance de l'approche atteint les objectifs de commande tout en respectant les contraintes. / To guarantee thermal comfort in buildings is directly related to energy consumption. In tropical climates, cooling systems for buildings represent one of the largest energy consumers. Therefore, as energy consumption is a major concern around the world, it is important to improve the systems efficiency or seeking new methods of cooling production. A solar cooling installation based on the absorption cycle is an alternative to mitigate greenhouse gas emissions and electricity consumption. In contrast to conventional vapor-compression based cooling systems, the absorption cooling production involves a complex system composed of several components as collector panel, storage tank, cooling tower and absorption chiller. Besides the sizing of the components, this complex system requires control actions to be efficient as a coordination between hot water storage, cooling water production and consumption is necessary. The aim of this research is to propose a management approach for a production-consumption energy system based on Model Predictive Control (MPC). The solar absorption cooling system is seen as part of this production-consumption energy system where the hot water storage system is the producer and the chiller-building system is one of the consumers. In order to provide modularity to the control structure, the coordination between the subsystems is achieved by using a partitioning approach where local predictive controllers are developed for each of the subsystems. The consumer controllers compute a set of energy demand profiles sent to the producer controller which selects the profile that better minimize the global optimization cost. In a first part, the proposed approach is tested on a simplified linear model composed of one producer and several consumers. In a second part, a more complex case is studied. A simplified model of an absorption cooling system is evaluated using the simulation tool TRNSYS. The producer model is no longer linear, instead it is described by a nonlinear hybrid model which increases the complexity of the optimization problem. The simulations results show that the suboptimality induced by the method is low and the control strategy fulfills the objectives and constraints while giving good performances.

Cette thèse développe des techniques à base d'automates pour la vérification formelle de systèmes physiquement distribués communiquant via des canaux fiables de tailles non bornées. Chaque machine peut exécuter localement plusieurs programmes récursifs (multi-threading). Un programme récursif peut également utiliser pour ses calculs locaux des structures de données non bornées, comme des files ou des piles. Ces systèmes, utilisés en pratique, sont si puissants que tous leurs problèmes de vérification deviennent indécidables. Nous introduisons et étudions un nouveau paramètre, appelé largeur de coupe (split-width), pour l'analyse de ces systèmes. Cette largeur de coupe est définie comme le nombre minimum de scissions nécessaires pour partitioner le graphe d'une exécution en parties sur lesquelles on pourra raisonner de manière indépendante. L'analyse est ainsi réalisée avec une approche diviser pour régner. Lorsqu'on se restreint à la classe des comportements ayant une largeur de coupe bornée par une constante, on obtient des procédures de décision optimales pour divers problèmes de vérification sur ces systèmes tels que l'accessibilité, l'inclusion, etc. ainsi que pour la satisfaisabilité et le model checking par rapport à divers formalismes comme la logique monadique du second ordre, la logique dynamique propositionnelle et des logiques temporelles. On montre aussi que les comportements d'un système ont une largeur de coupe bornée si et seulement si ils ont une largeur de clique bornée. Ainsi, grâce aux résultats de Courcelle sur les graphes de degré uniformément borné, la largeur de coupe est non seulement suffisante, mais aussi nécessaire pour obtenir la décidabilité du problème de satisfaisabilité d'une formule de la logique monadique du second ordre. Nous étudions ensuite l'existence de contrôleurs distribués génériques pour nos systèmes distribués. Nous proposons plusieurs contrôleurs, certains ayant un nombre fini d'états et d'autres étant déterministes, qui assurent que les comportements du système sont des graphes ayant une largeur de coupe bornée. Un système ainsi contrôlé de manière distribuée hérite des procédures de décision optimales pour les différents problèmes de vérification lorsque la largeur de coupe est bornée. Cette classe décidable de système généralise plusieurs sous-classes décidables étudiées précédemment. / This thesis investigates automata-theoretic techniques for the verification of physically distributed machines communicating via unbounded reliable channels. Each of these machines may run several recursive programs (multi-threading). A recursive program may also use several unbounded stack and queue data-structures for its local-computation needs. Such real-world systems are so powerful that all verification problems become undecidable. We introduce and study a new parameter called split-width for the under-approximate analysis of such systems. Split-width is the minimum number of splits required in the behaviour graphs to obtain disjoint parts which can be reasoned about independently. Thus it provides a divide-and-conquer approach for their analysis. With the parameter split-width, we obtain optimal decision procedures for various verification problems on these systems like reachability, inclusion, etc. and also for satisfiability and model checking against various logical formalisms such as monadic second-order logic, propositional dynamic logic and temporal logics. It is shown that behaviours of a system have bounded split-width if and only if they have bounded clique-width. Thus, by Courcelle's results on uniformly bounded-degree graphs, split-width is not only sufficient but also necessary to get decidability for MSO satisfiability checking. We then study the feasibility of distributed controllers for our generic distributed systems. We propose several controllers, some finite state and some deterministic, which ensure that the behaviours of the system have bounded split-width. Such a distributedly controlled system yields decidability for the various verification problems by inheriting the optimal decision procedures for split-width. These also extend or complement many known decidable subclasses of systems studied previously.

Les travaux présentés dans ce mémoire de thèse s'intéressent à la génération et à la mise en œuvre de séquences de test pour le test de conformité de contrôleurs logiques. Dans le cadre de ces travaux, le Grafcet (IEC 60848 (2002)), langage de spécification graphique utilisé dans un contexte industriel, a été retenu comme modèle de spécification. Les contrôleurs logiques principalement considérés dans ces travaux sont les automates programmables industriels (API). Afin de valider la mise en œuvre du test de conformité pour des systèmes de contrôle/commande critiques, les travaux présentés proposent: - Une formalisation du langage de spécification Grafcet. En effet, l'application des méthodes usuelles de vérification et de validation nécessitent la connaissance du comportement à partir de modèles formels. Cependant, dans un contexte industriel, les modèles utilisés pour la description des spécifications fonctionnelles sont choisis en fonction de leur pouvoir d'expression et de leur facilité d'utilisation, mais ne disposent que rarement d'une sémantique formelle. - Une étude de la mise en œuvre de séquences de test et l'analyse des verdicts obtenus lors du changement simultané de plusieurs entrées logiques. Une campagne d'expérimentation a permis de quantifier, pour différentes configurations de l'implantation, le taux de verdicts erronés dus à ces changements simultanés. - Une définition du critère de SIC-testabilité d'une implantation. Ce critère, déterminé à partir de la spécification Grafcet, définit l'aptitude d'une implantation à être testée sans erreur de verdict. La génération automatique de séquences de test minimisant le risque de verdict erroné est ensuite étudiée. / The works presented in this PhD thesis deal with the generation and implementation of test sequences for conformance test of logic controllers. Within these works, Grafcet (IEC 60848 (2002)), graphical specification language used in industry, has been selected as the specification model. Logic controllers mainly considered in these works are Programmable Logic Controllers (PLC). In order to validate the carrying out of conformance test of critical control systems, this thesis presents: - A formalization of the Grafcet specification language. Indeed, to apply usual verification and validation methods, the behavior is required to be expressed through formal models. However, in industry, the models used to describe functional specifications are chosen for their expression power and usability, but these models rarely have a formal semantics. - A study of test sequences execution and analysis of obtained verdicts when several logical inputs are changed simultaneously. Series of experimentation have permitted to quantify, for different configurations of the implantation under test, the rate of erroneous verdicts due to these simultaneous changes. - A definition of the SIC-testability criterion for an implantation. This criterion, determined on the Grafect specification defines the ability of an implementation to be tested without any erroneous verdict. Automatic generation of test sequences that minimize the risk of erroneous verdict is then studied.