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:
“No trace of slavery ought to mix with the studies of the freeborn man.... No study, pursued under compulsion, remains rooted in the memory.”
—Plato (c. 427–347 B.C.)
“‘Tis chastity, my brother, chastity.
She that has that is clad in complete steel,
And like a quivered nymph with arrows keen
May trace huge forests and unharbored heaths,
Infamous hills and sandy perilous wilds,
Where, through the sacred rays of chastity,
No savage fierce, bandit, or mountaineer
Will dare to soil her virgin purity.”
—John Milton (1608–1674)
“What terrible questions we are learning to ask! The former men believed in magic, by which temples, cities, and men were swallowed up, and all trace of them gone. We are coming on the secret of a magic which sweeps out of men’s minds all vestige of theism and beliefs which they and their fathers held and were framed upon.”
—Ralph Waldo Emerson (1803–1882)