Can symmetry be utilized as a design principle to constrain evolutionary search, making it more effective? This dissertation aims to show that this is indeed the case, in two ways. First, an approach called ENSO is developed to evolve modular neural network controllers for simulated multilegged robots. Inspired by how symmetric organisms have evolved in nature, ENSO utilizes group theory to break symmetry systematically, constraining evolution to explore promising regions of the search space. As a result, it evolves effective controllers even when the appropriate symmetry constraints are difficult to design by hand. The controllers perform equally well when transferred from simulation to a physical robot. Second, the same principle is used to evolve minimal-size sorting networks. In this different domain, a different instantiation of the same principle is effective: building the desired symmetry step-by-step. This approach is more scalable than previous methods and finds smaller networks, thereby demonstrating that the principle is general. Thus, evolutionary search that utilizes symmetry constraints is shown to be effective in a range of challenging applications. / text

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.

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 systèmes intégrés sont aujourd’hui de plus en plus fréquemment confrontés à des contraintes de faible consommation ou d’efficacité énergétique. Ces problématiques se doivent d’être intégrées le plus en amont possible dans le flot de conception afin de réduire les temps de design et d’éviter de nombreuses itérations dans le flot. Dans ce contexte, le projet collaboratif HiCool, partenariat entre les laboratoires LIRMM et TIMA, les sociétés Defacto, Docea et ST Microelectronics, a mis en place une stratégie et un flot de conception pour concevoir des systèmes intégrés faible consommation tout en facilitant la réutilisation de blocks matériels (IPs) existants. L’approche proposée dans cette thèse s’intègre dans cette stratégie en apportant une petite dose d’asynchronisme dans des systèmes complètement synchrones. En effet, la réduction de la consommation est basée sur le constat que l’activation permanente de la totalité du circuit est inutile dans bien des cas. Néanmoins, contrôler l’activité avec des techniques de « clock gating » ou de « power gating » nécessitent usuellement d’effectuer un re-design du système et d’ajouter un organe de commande pour contrôler l’activation des zones effectuant un traitement. Le travail présenté dans ce manuscrit définit une stratégie basée sur des contrôleurs d’horloge et de domaine d’alimentation, asynchrones, distribués et facilement insérables dans un circuit avec un coût de re-design des plus réduit. / Today integrated systems are increasingly faced with the constraints of low consumption or energy efficiency. These issues need to be integrated as far upstream as possible in the design flow to reduce design time and avoid much iteration in the flow. In this context, the collaborative project HiCool, between LIRMM and TIMA laboratories, Defacto, Docea and ST Microelectronics companies, has set up a strategy and design flow to design integrated low power systems while facilitating the reuse of existing hardware blocks (IPs). The approach proposed in this thesis fits into this strategy by bringing a small dose of asynchrony in completely synchronous systems. Indeed, the reduction in consumption is based on the observation that permanent activation of the entire circuit is unnecessary in many cases. However, controlling the activity with techniques of "clock gating" or "power gating" usually need to perform a re-design of the system and to add a control device for controlling activation of areas effecting treatment. The work presented in this manuscript provides a strategy based clock controllers and power domain, asynchronous, distributed and easily insertable into a circuit with a low cost design.