Mazurkiewicz traces were introduced by A. Mazurkiewicz in 1977 as a language representation of partial orders to model "true concurrency". The theory of Mazurkiewicz traces has been utilised to tackle not only various aspects of concurrency theory but also problems from other areas, including combinatorics, graph theory, algebra, and logic. However, neither Mazurkiewicz traces nor partial orders can model the "not later than" relationship. In 1995, comtraces (combined traces) were introduced by Janicki and Koutny as a formal language counterpart to finite stratified order structures. They show that each comtrace uniquely determines a finite stratified order structure, yet their work contains very little theory of comtraces. This thesis aims at enriching the tools and techniques for studying the theory of comtraces. Our first contribution is to introduce the notions of absorbing monoids, generalised comtrace monoids, partially commutative absorbing monoids, and absorbing monoids with compound generators, all of which are the generalisations of Mazurkiewicz trace and comtrace monoids. We also define and study the canonical representations of these monoids. Our second contribution is to define the notions of non-serialisable steps and utilise them to study the construction which Janicki and Koutny use to build stratified order structures from comtraces. Moreover, we show that any finite stratified order structure can be represented by a comtrace. Our third contribution is to study the relationship between generalised comtraces and generalised stratified order structures. We prove that each generalised comtrace uniquely determines a finite generalised stratified order structure. / Thesis / Master of Computer Science (MCS)

In concurrency theory—the branch of (theoretical) computer science that studies the logical and mathematical foundations of parallel computation—there are two main formal ways of modelling the behaviour of systems where multiple actions or events can happen independently and at the same time: either with interleaving or with partial order semantics. On the one hand, the interleaving semantics approach proposes to reduce concurrency to the nondeterministic, sequential computation of the events the system can perform independently. On the other hand, partial order semantics represent concurrency explicitly by means of an independence relation on the set of events that the system can execute in parallel; following this approach, the so-called ‘true concurrency’ approach, independence or concurrency is a primitive notion rather than a derived concept as in the interleaving framework. Using interleaving or partial order semantics is, however, more than a matter of taste. In fact, choosing one kind of semantics over the other can have important implications—both from theoretical and practical viewpoints—as making such a choice can raise different issues, some of which we investigate here. More specifically, this thesis studies concurrent systems with partial order semantics and focuses on their bisimulation and model-checking problems; the theories and techniques herein apply, in a uniform way, to different classes of Petri nets, event structures, and transition system with independence (TSI) models. Some results of this work are: a number of mu-calculi (in this case, fixpoint extensions of modal logic) that, in certain classes of systems, induce exactly the same identifications as some of the standard bisimulation equivalences used in concurrency. Secondly, the introduction of (infinite) higher-order logic games for bisimulation and for model-checking, where the players of the games are given (local) monadic second-order power on the sets of elements they are allowed to play. And, finally, the formalization of a new order-theoretic concurrent game model that provides a uniform approach to bisimulation and model-checking and bridges some mathematical concepts in order theory with the more operational world of games. In particular, we show that in all cases the logic games for bisimulation and model-checking developed in this thesis are sound and complete, and therefore, also determined—even when considering models of infinite state systems; moreover, these logic games are decidable in the finite case and underpin novel decision procedures for systems verification. Since the mu-calculi and (infinite) logic games studied here generalise well-known fixpoint modal logics as well as game-theoretic decision procedures for analysing concurrent systems with interleaving semantics, this thesis provides some of the groundwork for the design of a logic-based, game-theoretic framework for studying, in a uniform manner, several concurrent systems regardless of whether they have an interleaving or a partial order semantics.

Models of true concurrency have gained a lot of interest over the last decades as models of concurrent or distributed systems which avoid the well-known problem of state space explosion of the interleaving models. In this thesis, we study such models from two perspectives. Firstly, we study the relation between Petri nets and stable event structures. Petri nets can be considered as one of the most general and perhaps wide-spread models of true concurrency. Event structures on the other hand, are simpler models of true concurrency with explicit causality and conflict relations. Stable event structures expand the class of event structures by allowing events to be enabled in more than one way. While the relation between Petri nets and event structures is well understood, the relation between Petri nets and stable event structures has not been studied explicitly. We define a new and more compact unfoldings of safe Petri nets which is directly translatable to stable event structures. In addition, the notion of complete finite prefix is defined for compact unfoldings, making the existing model checking algorithms applicable to them. We present algorithms for constructing the compact unfoldings and their complete finite prefix. Secondly, we study probabilistic models of true concurrency. We extend the definition of probabilistic event structures as defined by Abbes and Benveniste to a newly defined class of stable event structures, namely, jump-free stable event structures arising from Petri nets (characterised and referred to as net-driven). This requires defining the fundamental concept of branching cells in probabilistic event structures, for jump-free net-driven stable event structures, and by proving the existence of an isomorphism among the branching cells of these systems, we show that the latter benefit from the related results of the former models. We then move on to defining a probabilistic logic over probabilistic event structures (PESL). To our best knowledge, this is the first probabilistic logic of true concurrency. We show examples of expressivity achieved by PESL, which in particular include properties related to synchronisation in the system. This is followed by the model checking algorithm for PESL for finite event structures. Finally, we present a logic over stable event structures (SEL) along with an account of its expressivity and its model checking algorithm for finite stable event structures.

Le but principal de la topologie algébrique dirigée est d’étudier des systèmes qui évoluent avec le temps à travers leur géométrie. Ce sujet émergea en informatique, plus particulièrement en vraie concurrence, où Pratt introduisit les automates de dimension supérieure (HDA) en 1991 (en réalité, l’idée de la géométrie de la concurrence peut être retracée jusque Dijkstra en 1965). Ces automates sont géométriques par nature: chaque ensemble de n processus exécutant des actions indépendantes en parallèle peuvent être modélisées par un cube de dimension n, et un tel automate donne naissance à un espace topologique, obtenu en recollant ces cubes. Cet espace a naturellement une direction du temps provenant du flot d’exécution. Il semble alors totalement naturel d’utiliser des outils provenant de la topologie algébrique pour étudier ces espaces: les chemins modélisent les exécutions et les homotopies de chemins, c’est-à-dire les déformations continues de chemins, modélisent l’équivalence entre exécutions modulo ordonnancement d’actions indépendantes, mais ces notions géométriques doivent préserver la direction du temps, d’une façon ou d’une autre. Ce caractère dirigé apporte des complications et la théorie doit être refaite, essentiellement depuis le début. Dans cette thèse, j’ai développé des théories de l’homotopie et de l’homologie pour ces espaces dirigés. Premièrement, ma théorie de l’homotopie dirigée est basée sur la notion de rétracts par déformations, c’est-à-dire de déformations continues d’un gros espaces sur un espace plus petit, suivant des chemins inessentiels, c’est-à-dire qui ne changent pas le type d’homotopie des « espaces d’exécutions ». Cette théorie est reliée aux catégories de composantes et catégories de dimension supérieures. Deuxièmement, ma théorie de l’homologie dirigée suit l’idée que l’on doit regarder les « espaces d’exécutions » et comment ceux-ci évoluent avec le temps. Cette évolution temporelle est traitée en définissant cette homologie comme un diagramme des « espaces d’exécutions » et en comparant de tels diagrammes en utilisant une notion de bisimulation. Cette théorie homologique a de très bonnes propriétés: elle est calculable sur des espaces simples, elle est un invariant de notre théorie homotopique, elle est invariante par des raffinements d’actions simples et elle une théorie des suites exactes. / Studying a system that evolves with time through its geometry is the main purpose of directed algebraic topology. This topic emerged in computer science, more particularly in true concurrency, where Pratt introduced the higher dimensional automata (HDA) in 1991 (actually, the idea of geometry of concurrency can be tracked down Dijkstra in 1965). Those automata are geometric by nature: every set of n processes executing independent actions can be modeled by a n-cube, and such an automaton then gives rise to a topological space, obtained by glueing such cubes together. This space naturally has a specific direction of time coming from the execution flow. It then seems natural to use tools from algebraic topology to study those spaces: paths model executions, homotopies of paths, that is continuous deformations of paths, model equivalence of executions modulo scheduling of independent actions, and so on, but all those notions must preserve the direction. This brings many complications and the theory must be done again.In this thesis, we develop homotopy and homology theories for those spaces with a direction. First, my directed homotopy theory is based on deformation retracts, that is continuous deformation of a big space on a smaller space, following directed paths that are inessential, meaning that they do not change the homotopy type of spaces of executions. This theory is related to categories of components and higher categories. Secondly, my directed homology theory follows the idea that we must look at the spaces of executions and those evolves with time. This evolution of time is handled by defining such homology as a diagram of spaces of executions and comparing such diagrams using a notion of bisimulation. This homology theory has many nice properties: it is computable on simple spaces, it is an invariant of our homotopy theory, it is invariant under simple action refinements and it has a theory of exactness.