Concurrency is a fundamental concept in computer science. Theories of concurrency provide the basis for the difficult task of designing and specifying software and hardware for nonsequential computer systems: distributed, decentralized, loosely or tightly coupled, embedded, and reactive systems.

Existing mathematical theories of concurrency follow one of two main approaches. The first approach, Petri nets, was developed by C. A. Petri in the early 1960s. Petri nets feature nonsequential execution and asynchronous communication between distributed activities, which cause local state transformations. Later, relationships were demonstrated between Petri nets and formal languages, semilinear sets, and vector addition systems. The second approach to concurrency, developed in the late 1970s by R. Milner and  C. A. R.  Hoare, is derived from the lambda calculus of Alonso Church. In this approach, sequential processes communicate synchronously, and nonsequential systems are obtained from parallel compositions of sequential components. Here concurrency is modeled by nondeterminism. In contrast, Petri’s theory makes a clear distinction between nondeterminism and concurrency: concurrency is a nontransitive relation, and the resulting semantics is technically complicated and cumbersome. The Milner-Hoare theory allows the full use of the theory of automata and formal languages and the semantics of sequential programs, but it does not adequately model nonsequential systems.

In 1977, A. Mazurkiewicz proposed an idea for distinguishing concurrency from nondeterminism without departing greatly from the well-developed theory of sequential programs. Mazurkiewicz endows the sequential observer of a nonsequential system with a small amount of information about the structure of the system in the form of a concurrency relation. Consequently, a nonsequential system is associated with a free partially commutative monoid, called a trace monoid, which falls between the free noncommutative monoids used in the Milner-Hoare theory and the free totally commutative monoids obtained from Petri nets interpreted as vector addition systems. It became clear that this new trace theory is mathematically deep and semantically powerful.

In this book, Diekert presents the algebraic and combinatorial foundations of trace theory, develops a new theory of replacement systems for trace monoids, and enlarges the range of application of the theory to a much wider class of Petri nets than previously considered. Much of the development of trace theory is due to Diekert himself.

The first chapter starts with an example--updating interdependent records in a distributed database--in order to identify equivalence classes of sequential transactions, called traces, and to construct the corresponding Hasse diagrams. Following this example, the author gives basic definitions, the Levi lemma for traces, and the embedding theorem, which enables the factorization of a trace into subtraces.

Chapter 2 is dedicated to recognizable and rational sets (trace languages). Chapter 3 investigates the behavior of Petri nets and the synchronization of trace languages. The last two chapters cover replacement systems. Semi-Thue systems and Möbius functions are presented in chapter 4, and chapter 5 discusses completion procedures. A set of 82 references closes the monograph.

The text is understandable, but the presentation of the initial example is superficial and will confuse newcomers. The monograph is written on the level of a research survey. To serve as a textbook for a first-year graduate course, it would need many didactic improvements, such as examples and exercises in each section.