Trace theory

Trace theory

In mathematics and computer science, trace theory aims to provide a concrete mathematical underpinning for the study of concurrent computation and process calculi. The underpining 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 underpining 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.

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

* V. Diekert, G. Rozenberg, eds. "The Book of Traces", (1995) World Scientific, Singapore ISBN 9810220588
* Volker Diekert, Yves Metivier, " [http://citeseer.ist.psu.edu/diekert97partial.html Partial Commutation and Traces] ", In G. Rozenberg and A. Salomaa, editors, "Handbook of Formal Languages", Vol. 3, Beyond Words, pages 457--534. Springer-Verlag, Berlin, 1997.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Multiple trace theory — (MTT) is a memory consolidation model advanced as an alternative model to strength theory. It posits that each time some information is presented to a person, it is neurally encoded in a unique memory trace composed of a combination of its… …   Wikipedia

  • Trace monoid — In mathematics and 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,… …   Wikipedia

  • Trace (psycholinguistics) — TRACE is a connectionist model of speech perception, proposed by James McClelland and Jeffrey Elman in 1986McClelland, J.L., Elman, J.L. (1986). The TRACE model of speech perception. Cognitive Psychology, 18, 1 86.] . TRACE was made into a… …   Wikipedia

  • Trace (deconstruction) — Trace is one of the most important concepts in Derridian Deconstruction. In the 1960s, Derrida used this word in two of his early books, namely “Writing and Difference” and “Of Grammatology”. The English word “trace” was first used by Gayatri… …   Wikipedia

  • Trace — may refer to:;Mathematics, computing and electronics: * Trace (linear algebra) of a square matrix or a linear transformation * Trace class, a certain set of operators in a Hilbert space * Trace operator, a restriction to boundary operator in a… …   Wikipedia

  • Trace de graphes — Tracé de graphes En théorie des graphes, le tracé de graphes s applique à une topologie et géométrie pour produire une représentation à deux ou trois dimensions des graphes. Le tracé de graphes est utile à des applications telles que la… …   Wikipédia en Français

  • Trace (linear algebra) — In linear algebra, the trace of an n by n square matrix A is defined to be the sum of the elements on the main diagonal (the diagonal from the upper left to the lower right) of A, i.e., where aii represents the entry on the ith row and ith column …   Wikipedia

  • Trace diagram — In mathematics, trace diagrams are a graphical means of performing computations in linear and multilinear algebra. They can be represented as graphs with edges labeled by matrices. Without the matrix labels, they are equivalent to Penrose s… …   Wikipedia

  • Trace (linguistics) — In transformational grammar, a trace is an empty (phonologically null) category that occupies a position in the syntactic structure. In some theories of syntax, traces are used in the account of constructions such as wh movement and passive.… …   Wikipedia

  • Trace (algèbre) — Pour les articles homonymes, voir Trace. En algèbre linéaire, la trace d une matrice carrée A est définie comme la somme de ses coefficients diagonaux et notée Tr(A). La trace peut être vue comme une forme linéaire sur l espace vectoriel des… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”