Formal methods provide means for rigorously specifying the desired behaviour of a hardware or software system, making a precise model of its actual behaviour, and then verifying whether that actual behaviour corresponds to the specification.<br><br> My habiliation thesis reports on various contributions to this realm, where my main interest has been on algorithmic aspects. This is motivated by the observation that asymptotic worst-case complexity, often used to characterize the difficulty of algorithmic problems, is only loosely related to the difficulty encountered in solving those problems in practice.<br><br> The two main types of system I have been working on are pushdown systems and Petri nets. Both are fundamental notions of computation, and both offer, in my opinion, particularly nice opportunities for combining theory and algorithmics.<br><br> Pushdown systems are finite automata equipped with a stack; since the height of the stack is not bounded, they represent a class of infinite-state systems that model programs with (recursive) procedure calls. Moreover, we shall see that specifying authorizations is another, particularly interesting application of pushdown systems.<br><br> While pushdown systems are primarily suited to express sequential systems, Petri nets model concurrent systems. My contributions in this area all concern unfoldings. In a nutshell, the unfolding of a net N is an acyclic version of N in which loops have been unrolled. Certain verification problems, such as reachability, have a lower complexity on unfoldings than on general Petri nets.

Les automates d'ordres, plus connus sous le nom de Message sequence Charts (MSC), ont connu une énorme popularité depuis les années 1990. Ce succès est à la fois académique et industriel. Les raisons de ce succès sont multiples : le modèle est simple et s'apprend très vite. De plus il possède une puissance d'expression supérieure à celle des automates finis, et pose des problèmes difficiles. L'apparente simplicité des MSCs est en fait trompeuse, et de nombreuses manipulations algorithmiques se révèlent rapidement être des problèmes indécidables. Dans ce document, nous revenons sur 10 années de recherches sur les Message Sequence Charts, et plus généralement sur les langages de scénarios, et tirons quelques conclusions à partir des travaux effectués. Nous revenons sur les propriétés formelles des Message Sequence charts, leur décidabilité, et les sous-classes du langage permettant la décision de tel ou tel problème. L'approche classique pour traiter un problème sur les MSCs est de trouver la plus grande classe possible sur laquelle ce problème est décidable. Un autre challenge est d'augmenter la puissance d'expression des MSCs sans perdre en décidabilité. Nous proposons plusieurs extensions de ce type, permettant la crétion dynamique de processus, ou la définition de protocoles de type "fenêtre glissante". Comme tout modèle formel, les MSCs peuvent difficilement dépasser une taille critique au delà de laquelle un utilisateur ne peut plus vraiment comprendre le diagramme qu'il a sous les yeux. Pour pallier à cette limite, une solution est de travailler sur de plus petits modules comportementaux, puis de les assembler pour obtenir des ensembles de comportements plus grands. Nous étudions plusieurs mécanismes permettant de composer des MSCs, et sur la robustesses des sous-classes de scénarios connues à la composition. La conclusion ce cette partie est assez négative: les scénarios se composent difficilement, et lorsqu'une composition est faisable, peu de propriétés des modèles composés sont préservées. Nous apportons ensuite une contributions à la synthèse automatique de programmes distribués à partir de spécification données sous forme d'automates d'ordres. Cette question répond à un besoin pratique, et permet de situer un role possible des scénarios dans des processus de conception de logiciels distribués. Nous montrons que la synthèse automatique est possible sur un sous ensemble raisonnable des automates d'ordres. Dans une seconde partie de ce document, nous étudions des applications possibles pour les MSCs. Nous regardons entre autres des algorithmes de model-checking, permettant de découvrir des erreurs au moment de la spécification d'un système distribué par des MSCs. La seconde application considérée est le diagnostic, qui permet d'expliciter à l'aide d'un modèle les comportement d'un système réel instrumenté. Enfin, nous regardons l'utilisation des MSCs pour la recherche de failles de sécurité dans un système. Ces deux applications montrent des domaines réalistes d'utilisation des scénarios. Pour finir, nous tirons quelques conclusions sur les scénarios au regard du contenu du document et du travail de ces 10 dernières années. Nous proposons ensuite quelques perspectives de recherche.

Formal methods offer a way to deal with the complexity of information systems. They are adapted to a variety of domains like design, verification, model-checking, test and supervision. But information systems are also more and more often distributed, first because of the generalization of information networks, but also because inside a single device, like a computer, the numerous components run concurrently. The problem is that concurrency is known to be a major difficulty for the use of formal methods because it causes a combinatorial explosion of the state space of the systems. This difficulty comes sometimes with another one due to time when it plays an important role in the behaviour of the systems, for instance when the execution time is a critical parameter. These two difficulties, concurrency and real-time, have guided my research works. Sometimes I have tackled one of these two aspects separately, but in many of my works, I have dealt with the problems that arise when one studies systems that are both concurrent and real-time. In my habilitation thesis, I give an overview of my recent research works on dependencies between events in real-time distributed systems and on implementability issues for these systems.

Qu'y a-t-il de commun entre F. Cheng, écrivain français d'origine chinoise, H. Bianciotti, enfant d'immigrés italiens en Argentine, G. Macé, dilettante du voyage, attiré par l'anthropologie, Rome ou encore l'Asie, et C. Magris, un Italien de Trieste qui a consacré sa vie à la littérature et à la géographie des frontières ? Au-delà de leurs divergences, on rencontre chez ces quatre auteurs une telle sensibilité à l'espace et aux déplacements qu'ils peuvent tous être définis comme des " écrivains non sédentaires ". La non-sédentarité n'est pas un nomadisme : très concernée par les frontières, avec tout ce qui en découle d'interférences et d'inquiétudes quant au sentiment et à la pratique de la langue, fascinée par les seuils et attirée par les refuges, cette posture non assise est issue d'un rapport aux lieux marqué par la volonté de se tenir debout tout en refusant l'errance. Il en résulte une écriture façonnée par tout ce qu'elle relie. Ainsi, notre corpus, constitué d'essais, de récits et de poèmes, entraîne une réflexion sur le langage à partir de l'appétit, à la fois avide et soucieux, de nos auteurs pour l'espace-monde. Il aborde les thématiques de la voix et du corps en tant que seuils pour l'existence, et situe l'homme en ses évolutions intérieures et historiques à partir de la représentation de jardins et de villes, dans lesquels se logent moins des histoires que des aspirations. La notion d' " écriture non sédentaire " nous a menée à définir son lieu par un néologisme, l' " antrait ", par lequel nous désignons des espaces qui sont à la fois " antre " et " entre ", qui contiennent le repli et l'ouverture, qui engagent l'hospitalité comme accueil et comme partir.

Les travaux présentés ici s'intéressent aux coloriages du plan discret. Ce modèle d'inspiration géométrique est intrinsèquement lié aux modèles de calcul, et son étude se décline ici suivant deux axes complémentaires: calculabilité et combinatoire. Nous montrons en particulier ici comment de nombreux résultats récents s'expriment naturellement à travers le concept de bases, propriétés vérifiées par au moins un point de tout ensemble de coloriages, et d'antibases, contre-exemples à ce concept. Nous examinons ensuite les différents codages du calcul par des jeux de tuiles et exhibons en particulier un nouveau codage épars, permettant de caractériser les degrés Turing des ensembles de coloriages. Enfin nous revenons aux origines en étudiant les pavages du point de vue de la logique. Nous caractérisons ainsi les grandes familles d'ensembles de coloriages par des fragments de la logique monadique du second ordre.

Humans make mistakes, especially when faced to complex tasks, such as the construction of modern hardware or software. This thesis focuses on machine-assisted techniques to guarantee that computers behave correctly. Modern computer systems are large and complex. Automated formal verification stands as an alternative to testing or simulation to ensuring their reliability. It essentially proposes to employ computers to exhaustively check the system behavior. Unfortunately, automated verification suffers from the state-space explosion problem: even relatively small systems can reach a huge number of states. Using the right representation for the system behavior seems to be a key step to tackle the inherent complexity of the problems that automated verification solves. The verification of concurrent systems poses additional issues, as their analysis requires to evaluate, conceptually, all possible execution orders of their concurrent actions. Petri net unfoldings are a well-established verification technique for concurrent systems. They represent behavior by partial orders, which not only is natural but also efficient for automatic verification. This dissertation focuses on the verification of concurrent systems, employing Petri nets to formalize them, and studies two prominent verification techniques: model checking and fault diagnosis. We investigate the unfoldings of Petri nets extended with read arcs. The unfoldings of these so-called contextual nets seem to be a better representation for systems exhibiting concurrent read access to shared resources: they can be exponentially smaller than conventional unfoldings on these cases. Theoretical and practical contributions are made. We first study the construction of contextual unfoldings, introducing algorithms and data structures that enable their efficient computation. We integrate contextual unfoldings with merged processes, another representation of concurrent behavior that alleviates the explosion caused by non-determinism. The resulting structure, called contextual merged processes, is often orders of magnitude smaller than unfoldings, as we experimentally demonstrate. Next, we develop verification techniques based on unfoldings. We define SAT encodings for the reachability problem in contextual unfoldings, thus solving the problem of detecting cycles of asymmetric conflict. Also, an unfolding-based decision procedure for fault diagnosis under fairness constraints is presented, in this case only for conventional unfoldings. Finally, we implement our verification algorithms, aiming at producing a competitive model checker intended to handle realistic benchmarks. We subsequently evaluate our methods over a standard set of benchmarks and compare them with existing unfolding-based techniques. The experiments demonstrate that reachability checking based on contextual unfoldings outperforms existing techniques on a wide number of cases. This suggests that contextual unfoldings, and asymmetric event structures in general, have a rightful place in research on concurrency, also from an efficiency point of view.

Qu'y a-t-il de commun entre F. Cheng, écrivain français d'origine chinoise, H. Bianciotti, enfant d'immigrés italiens en Argentine, G. Macé, dilettante du voyage, attiré par l'anthropologie, Rome ou encore l'Asie, et C. Magris, un Italien de Trieste qui a consacré sa vie à la littérature et à la géographie des frontières ? Au-delà de leurs divergences, on rencontre chez ces quatre auteurs une telle sensibilité à l'espace et aux déplacements qu'ils peuvent tous être définis comme des « écrivains non sédentaires ». La non-sédentarité n'est pas un nomadisme : très concernée par les frontières, avec tout ce qui en découle d'interférences et d'inquiétudes quant au sentiment et à la pratique de la langue, fascinée par les seuils et attirée par les refuges, cette posture non assise est issue d'un rapport aux lieux marqué par la volonté de se tenir debout tout en refusant l'errance. Il en résulte une écriture façonnée par tout ce qu'elle relie. Ainsi, notre corpus, constitué d'essais, de récits et de poèmes, entraîne une réflexion sur le langage à partir de l'appétit, à la fois avide et soucieux, de nos auteurs pour l'espace-monde. Il aborde les thématiques de la voix et du corps en tant que seuils pour l'existence, et situe l'homme en ses évolutions intérieures et historiques à partir de la représentation de jardins et de villes, dans lesquels se logent moins des histoires que des aspirations. La notion d' « écriture non sédentaire » nous a menée à définir son lieu par un néologisme, l' « antrait », par lequel nous désignons des espaces qui sont à la fois « antre » et « entre », qui contiennent le repli et l'ouverture, qui engagent l'hospitalité comme accueil et comme partir. / What do François Cheng, a French writer of Chinese origin, Hector Bianciotti, the son of Italian immigrants to Argentina, Gérard Macé, a dilettante traveller, with a penchant for anthropology, Rome or Asia, to name but a few of his interests, and Claudio Magris, an Italian from Trieste who has devoted his life to the literature and geography of frontiers have in common ? Above and beyond their differences, these four authors share such a sensibility to spaces and movements that they can be defined as "non-sedentary writers". Non-sedentarity is not nomadism : very much concerned by frontiers, with all the interferences and worries that these entail regarding the feeling and the practice of language, fascinated by thresholds and attracted by refuges, this restless posture is the result of a relationship with places characterised by the wish to remain standing while refusing to wander. Thus ensues a writing that is shaped by all that it binds together. So our corpus, made up of essays, narratives and poems, initiates a reflection on language from the appetite - avid and anxious at the same time - of our authors for the world-space. It tackles the themes of voice and body as thresholds for existing, and positions mankind within its inner and historic evolutions, according to the representations of gardens and cities, where aspirations matter more than stories. The notion of "non-sedentary writing" has led us to define its locus through a neologism, the "antrait" (prounounced like "entrée", entrance) by which we designate spaces that are both "antre" (den) and "entre" (between), that contain retreat and openness, that make hospitality both a welcome and a leavetaking.

L'analyse prévisionnelle des risques d'un système complexe repose aujourd'hui sur une modélisation de la dynamique du système vis-à-vis des défaillances et réparations de ses composants. L'analyse qualitative d'un tel système consiste à rechercher et à analyser les scénarios conduisant à la panne. En raison de leur nombre, il est courant de ne s'intéresser qu'aux scénarios les plus caractéristiques, les Séquences de Coupe Minimales (SCM). L'absence de formalisation de ces SCM a généré soit des définitions spécifiques à certains outils de modélisation soit des définitions informelles. Les travaux présentés dans cette thèse proposent: i) un cadre et une définition formelle des séquences de coupe minimales, tout deux indépendants de l'outil de modélisation de fiabilité utilisé, ii) une méthode permettant leur calcul, méthode basée sur des propriétés déduites de leur définition, iii) l'extension des premières définitions aux composants multimodes. Ce cadre permet le calcul des SCM pour des installations décrites avec les Boolean logic Driven Markov Processes (BDMP). Sous l'hypothèse que l'ensemble des scénarios représentés implicitement via le modèle de sûreté établi peut être modélisé à l'aide d'un automate fini, ces travaux définissent la notion de cohérence des systèmes dynamiques et réparables, et le moyen d'obtenir une représentation minimale de l'ensemble des scénarios menant à la défaillance du système. / Preventive risk assessment of a complex system rely on a dynamic models which describe the link between the system failure and the scenarios of failure and repair events from its components. The qualitative analyses of a binary dynamic and repairable system is aiming at computing and analyse the scenarios that lead to the system failure. Since such systems describe a large set of those, only the most representative ones, called Minimal Cut Sequences (MCS), are of interest for the safety engineer. The lack of a formal definition for the MCS has generated multiple definitions either specific to a given model (and thus not generic) or informal. This work proposes i) a formal framework and definition for the MCS while staying independent of the reliability model used, ii) the methodology to compute them using property extracted from their formal definition, iii) an extension of the formal framework for multi-states components in order to perform the qualitative analyses of Boolean logic Driven Markov Processes (BDMP) models. Under the hypothesis that the scenarios implicitly described by any reliability model can always be represented by a finite automaton, this work is defining the coherency for dynamic and repairable systems as the way to give a minimal representation of all scenarios that are leading to the system failure.

La vérification automatique est aujourd'hui devenue un domaine central de recherche en informatique. Depuis plus de 25 ans, une riche théorie a été développée menant à de nombreux outils, à la fois académiques et industriels, permettant la vérification de propriétés booléennes -- celles qui peuvent être soit vraies soit fausses. Les besoins actuels évoluent vers une analyse plus fine, c'est-à-dire plus quantitative. L'extension des techniques de vérification aux domaines quantitatifs a débuté depuis 15 ans avec les systèmes probabilistes. Cependant, de nombreuses autres propriétés quantitatives existent, telles que la durée de vie d'un équipement, la consommation énergétique d'une application, la fiabilité d'un programme, ou le nombre de résultats d'une requête dans une base de données. Exprimer ces propriétés requiert de nouveaux langages de spécification, ainsi que des algorithmes vérifiant ces propriétés sur une structure donnée. Cette thèse a pour objectif l'étude de plusieurs formalismes permettant de spécifier de telles propriétés, qu'ils soient dénotationnels -- expressions régulières, logiques monadiques ou logiques temporelles -- ou davantage opérationnels, comme des automates pondérés, éventuellement étendus avec des jetons. Un premier objectif de ce manuscript est l'étude de résultats d'expressivité comparant ces formalismes. En particulier, on donne des traductions efficaces des formalismes dénotationnels vers celui opérationnel. Ces objets, ainsi que les résultats associés, sont présentés dans un cadre unifié de structures de graphes. Ils peuvent, entre autres, s'appliquer aux mots et arbres finis, aux mots emboîtés (nested words), aux images ou aux traces de Mazurkiewicz. Par conséquent, la vérification de propriétés quantitatives de traces de programmes (potentiellement récursifs, ou concurrents), les requêtes sur des documents XML (modélisant par exemple des bases de données), ou le traitement des langues naturelles sont des applications possibles. On s'intéresse ensuite aux questions algorithmiques que soulèvent naturellement ces résultats, tels que l'évaluation, la satisfaction et le model checking. En particulier, on étudie la décidabilité et la complexité de certains de ces problèmes, en fonction du semi-anneau sous-jacent et des structures considérées (mots, arbres...). Finalement, on considère des restrictions intéressantes des formalismes précédents. Certaines permettent d'étendre l'ensemble des semi-anneau sur lesquels on peut spécifier des propriétés quantitatives. Une autre est dédiée à l'étude du cas spécial de spécifications probabilistes : on étudie en particulier des fragments syntaxiques de nos formalismes génériques de spécification générant uniquement des comportements probabilistes.

L'analyse prévisionnelle des risques d'un système complexe repose aujourd'hui sur une modélisation de la dynamique du système vis-à-vis des défaillances et réparations de ses composants. L'analyse qualitative d'un tel système consiste à rechercher et à analyser les scénarios conduisant à la panne. En raison de leur nombre, il est courant de ne s'intéresser qu'aux scénarios les plus caractéristiques, les Séquences de Coupe Minimales (SCM). L'absence de formalisation de ces SCM a généré soit des définitions spécifiques à certains outils de modélisation soit des définitions informelles. Les travaux présentés dans cette thèse proposent: i) un cadre et une définition formelle des séquences de coupe minimales, tout deux indépendants de l'outil de modélisation de fiabilité utilisé, ii) une méthode permettant leur calcul, méthode basée sur des propriétés déduites de leur définition, iii) l'extension des premières définitions aux composants multimodes. Ce cadre permet le calcul des SCM pour des installations décrites avec les Boolean logic Driven Markov Processes (BDMP). Sous l'hypothèse que l'ensemble des scénarios représentés implicitement via le modèle de sûreté établi peut être modélisé à l'aide d'un automate fini, ces travaux définissent la notion de cohérence des systèmes dynamiques et réparables, et le moyen d'obtenir une représentation minimale de l'ensemble des scénarios menant à la défaillance du système.