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)
“Of moral purpose I see no trace in Nature. That is an article of exclusively human manufacture—and very much to our credit.”
—Thomas Henry Huxley (1825–95)
“Yet ere I can say where—the chariot hath
Passed over them—nor other trace I find
But as of foam after the ocean’s wrath”
—Percy Bysshe Shelley (1792–1822)