Trace
Let denote the free monoid, that is, the set of all strings written in the alphabet . Here, the asterisk denotes, as usual, the Kleene star. An independency relation then induces a binary relation on, where if and only if there exist, and a pair such that and . Here, and are understood to be strings (elements of ), while and are letters (elements of ).
The trace is defined as the symmetric, reflexive and transitive closure of . The trace is thus an equivalence relation on, and is denoted by . The subscript D on the equivalence simply denotes that the equivalence is obtained from the independency I induced by the dependency D. Clearly, different dependencies will give different equivalence relations.
The transitive closure simply implies that if and only if there exists a sequence of strings such that and and for all .
Read more about this topic: Trace Monoid
Famous quotes containing the word trace:
“Emancipation should make it possible for woman to be human in the truest sense. Everything within her that craves assertion and activity should reach its fullest expression; all artificial barriers should be broken, and the road towards greater freedom cleared of every trace of centuries of submission and slavery.”
—Emma Goldman (1869–1940)
“Beauty is a precious trace that eternity causes to appear to us and that it takes away from us. A manifestation of eternity, and a sign of death as well.”
—Eugène Ionesco (b. 1912)
“We can trace almost all the disasters of English history to the influence of Wales.”
—Evelyn Waugh (1903–1966)