Trace theory

Short description: Theory of trace monoids

For trace theory in natural language syntax, see Trace (linguistics).

In mathematics and computer science, trace theory aims to provide a concrete mathematical underpinning for the study of concurrent computation and process calculi. The underpinning is provided by an algebraic definition of the free partially commutative monoid or trace monoid, or equivalently, the history monoid, which provides a concrete algebraic foundation, analogous to the way that the free monoid provides the underpinning for formal languages.

The power of trace theory stems from the fact that the algebra of dependency graphs (such as Petri nets) is isomorphic to that of trace monoids, and thus, one can apply both algebraic formal language tools, as well as tools from graph theory.

While the trace monoid had been studied by Pierre Cartier and Dominique Foata 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 regard to refinement in process calculi.

## References

* Volker Diekert, Grzegorz Rozenberg, eds. The Book of Traces, (1995) World Scientific, Singapore ISBN 981-02-2058-8
* Volker Diekert; Yves Metivier (1997). "Partial Commutation and Traces". Beyond Words. Handbook of Formal Languages. 3. Berlin: Springer. pp. 457-534. doi:10.1007/978-3-642-59126-6. ISBN 978-3-540-60649-9. https://web.archive.org/web/20170908153838/https://pdfs.semanticscholar.org/d67a/c4c1e5967f7e114f390245f28909f259c034.pdf.
* Volker Diekert, Combinatorics on traces, LNCS 454, Springer, 1990, ISBN 3-540-53031-2

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Trace theory. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Trace_theory&oldid=4229062"