Combinatorics on traces (Q1188891): Difference between revisions

The theory of free partially commutative monoids has been originally introduced in combinatorics by \textit{P. Cartier} and \textit{D. Foata} in order to solve some problems of rearrangements and it has later reappeared in the field of Computer Science as a tool for describing the behaviour of nonsequential systems, following a proposal of \textit{A. Mazurkiewicz}. Elements of free partially commutative monoids, called traces by Mazurkiewicz, have been recognized as an algebraic model of concurrent processes and this observation has led to the use of traces for a mathematical theory of concurrency which owes its importance to the fact that it combines fundamental work and knowledge from automata and formal language theory with a notion of concurrency distinct from nondeterminism. The present volume gives a deep and clear overview of the theory for the reader who is not familiar with it, and also collects original research contributions by the author on connections between trace theory and rewriting systems. A well developed thread in this area is, for example, the link to the theory of semi-Thue systems (E. Ochmanski). In this framework, the original contribution of Diekert consists in the development of a new theory of replacement systems which uses trace rewriting directly, these systems providing algebraic means to describe transformations on concurrent processes. The contents of the volume are organized as follows. The first chapter illustrates the combinatorial background and general concepts of trace theory. An embedding theorem for partially commutative monoids is thoroughly described and proved in a categorical framework. The study of trace monoids in the context of formal languages is introduced in chapter 2, which is devoted to the relation between the notions of rational and recognizable trace languages. Two main results in the theory of trace languages are Zielonka's theorem on recognizability by asynchronous automata and Ochmanski's characterization of recognizable languages in terms of so called recognizable expressions: these are suitably explained. The application of trace theory to the investigation of Petri nets is considered in chapter 3, where some extensions of previous work in this area are presented. Finally, the last two chapters are devoted to the investigation of replacement systems. Semi-Thue systems are described in relation to properties of free partially commutative monoids, for example, the presentation of a monoid by a complete (i.e. noetherian and confluent) semi-Thue system is related to the word problem for the monoid. There is also an original proof of the confluence of Thue-systems: confluence of noetherian semi-Thue systems can be decided on so called critical ``minimal'' pairs, and some evaluations of the complexity of the decision procedure are given. An interesting combinatorial result of Diekert shows that there exists an intimate connection between a Möbius function defined for free partially commutative monoid and finite complete semi-Thue systems. This result gives interesting connections between formal power series and semi-Thue systems. The good choice and organization of the material in the first chapters, gives the reader a taste of the deepness and beauty of the mathematical content of trace theory. In fact its foundations are clearly presented, emphasizing the algebraic and combinatorial aspects, and meaningful applications of the theory are illustrated by algorithms. For this reasons, and above all for the fact that the main results are proved in detail, this volume may serve as a good reference on trace theory. The text is self-contained and easily readable.