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:
“To love someone is to isolate him from the world, wipe out every trace of him, dispossess him of his shadow, drag him into a murderous future. It is to circle around the other like a dead star and absorb him into a black light.”
—Jean Baudrillard (b. 1929)
“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)
“A horse, a buggy and several sets of harness, valued in all at about $250, were stolen last night from the stable of Howard Quinlan, near Kingsville. The county police are at work on the case, but so far no trace of either thieves or booty has been found.”
—H.L. (Henry Lewis)