Studies in Comtrace Monoids

Abstract

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.