The theory of traces employs techniques and tackles problems from quite diverse areas which include formal language theory, combinatorics, graph theory, algebra, logic, and the theory of concurrent systems. In all these areas the theory of traces has led to interesting problems and significant results. It has made an especially big impact in formal language theory and the theory of concurrent systems. In both these disciplines it is a well-recognized and dynamic research area. Within formal language theory it yields the theory of partially commutative monoids, and provides an important connection between languages and graphs. Within the theory of concurrent systems it provides an important formal framework for the analysis and synthesis of concurrent systems.
This monograph covers all important research lines of the theory of traces; each chapter is devoted to one research line and is written by leading experts. The book is organized in such a way that each chapter can be read independently — and hence it is very suitable for advanced courses or seminars on formal language theory, the theory of concurrent systems, the theory of semigroups, and combinatorics. An extensive bibliography is included. At present, there is no other book of this type on trace theory.
Sample Chapter(s)
Chapter 1: Introduction to Trace Theory (1,575 KB)
Contents:
- Basic Notions:
- Introduction to Trace Theory (A Mazurkiewicz)
- Dependence Graphs (H J Hoogeboom & G Rozenberg)
- Algebra and Combinatorics:
- Combinatorics in Trace Monoids I (C Choffrut)
- Combinatorics in Trace Monoids II (G Duchamp & D Krob)
- Counting Techniques for Inclusion, Equivalence and Membership Problems (A Bertoni et al.)
- Languages and Automata:
- Recognizable Trace Languages (E Ochma(ski)
- Asynchronous Automata (W Zielonka)
- Construction of Asynchronous Automata (V Diekert & A Mischoll)
- Concurrency and Logic:
- Trace Structures and Other Models for Concurrency (M Nielsen & G Winskel)
- Traces and Logic (W Penczek & R Kuiper)
- Generalizations:
- Infinite Traces (P Gastin & A Petit)
- Semi-Commutations (M Clerbout et al.)
Readership: Computer scientists and mathematicians.
