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:
“The land of shadows wilt thou trace
And look nor know each other’s face
The present mixed with reasons gone
And past and present all as one
Say maiden can thy life be led
To join the living with the dead
Then trace thy footsteps on with me
We’re wed to one eternity”
—John Clare (1793–1864)
““In your company a man could die,” I said, “a man could die and you wouldn’t even notice, there’s no trace of friendship, a man could die in your company.””
—Max Frisch (1911–1991)
“Muhammad is the Messenger of God,
and those who are with him are hard
against the unbelievers, merciful
one to another. Thou seest them
bowing, prostrating, seeking bounty
from God and good pleasure. Their
mark is on their faces, the trace of
prostration....
God has promised
those of them who believe and do deeds
of righteousness forgiveness and
a mighty wage.”
—Qur’An. Victory 48:35, ed. Arthur J. Arberry (1955)