In mathematics and

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...

, trace theory aims to provide a concrete mathematical underpinning for the study of

concurrent computation Concurrent computing is a form of computing in which several computations are executed '' concurrently''—during overlapping time periods—instead of ''sequentially—''with one completing before the next starts. This is a property of a syst ...

and

process calculi In computer science, the process calculi (or process algebras) are a diverse family of related approaches for formally modelling concurrent systems. Process calculi provide a tool for the high-level description of interactions, communications, and ...

. The underpinning is provided by an algebraic definition of the free partially commutative monoid or

trace monoid In computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order, but allowing certa ...

, or equivalently, the

history monoid In mathematics and computer science, a history monoid is a way of representing the histories of concurrently running computer processes as a collection of strings, each string representing the individual history of a process. The history monoid p ...

, which provides a concrete algebraic foundation, analogous to the way that the

free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...

provides the underpinning for

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sy ...

s. The power of trace theory stems from the fact that the algebra of

dependency graph In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order t ...

s (such as

Petri net A Petri net, also known as a place/transition (PT) net, is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. A Petri net is a directed bipartite graph that ...

s) is isomorphic to that of trace monoids, and thus, one can apply both algebraic

tools, as well as tools from

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

. While the trace monoid had been studied by Pierre Cartier and

Dominique Foata Dominique Foata (born October 12, 1934) is a mathematician who works in enumerative combinatorics. With Pierre Cartier and Marcel-Paul Schützenberger he pioneered the modern approach to classical combinatorics, that lead, in part, to the current ...

for its combinatorics in the 1960s, trace theory was first formulated by Antoni Mazurkiewicz in the 1970s, in an attempt to evade some of the problems in the theory of concurrent computation, including the problems of interleaving and non-deterministic choice with regards to refinement in process calculi.

References

Volker Diekert Volker may refer to: * Volker (name), including a list of people with the given name or surname * Volker, Kansas City, a historic neighborhood in Kansas City * Volker Boulevard, Kansas City * '' Alien Nations'' (German: ''Die Völker''), a real-tim ...

Grzegorz Rozenberg Grzegorz Rozenberg (born 14 March 1942, Warsaw) is a Polish and Dutch computer scientist. His primary research areas are natural computing, formal language and automata theory, graph transformations, and concurrent systems. He is referre ...

, eds. ''The Book of Traces'', (1995) World Scientific, Singapore *

, Yves Metivier,
Partial Commutation and Traces
, In G. Rozenberg and A. Salomaa, editors, ''Handbook of Formal Languages'', Vol. 3, ''Beyond Words''. Springer-Verlag, Berlin, 1997. *

, ''Combinatorics on traces'',

LNCS ''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973. Overview The series contains proceedings, post-proceedings, monographs, and Festschrifts. In addition, tutorials, ...

454, Springer, 1990, Concurrent computing Formal languages Trace theory {{formalmethods-stub