In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, in particular in
concurrency theory
In computer science, concurrency is the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the outcome. This allows for parallel execution of the concur ...
, a dependency relation is a
binary relation on a finite domain
,
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
, and
reflexive;
i.e. a finite
tolerance relation
In universal algebra and lattice theory, a tolerance relation on an algebraic structure is a reflexive symmetric relation that is compatible with all operations of the structure. Thus a tolerance is like a congruence, except that the assumption ...
. That is, it is a finite set of
ordered pairs
, such that
* If
then
(symmetric)
* If
, then
(reflexive)
In general, dependency relations are not
transitive; thus, they generalize the notion of an
equivalence relation by discarding transitivity.
is also called the
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syllab ...
on which
is defined. The independency induced by
is the binary relation
:
That is, the independency is the set of all ordered pairs that are not in
. The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation
on a finite alphabet, the relation
:
is a dependency relation.
The pair
is called the concurrent alphabet. The pair
is called the independency alphabet or reliance alphabet, but this term may also refer to the triple
(with
induced by
).
Elements
are called dependent if
holds, and independent, else (i.e. if
holds).
Given a reliance alphabet
, a symmetric and irreflexive relation
can be defined on the
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
of all possible strings of finite length by:
for all strings
and all independent symbols
. The
equivalence closure
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but ...
of
is denoted
or
and called
-equivalence. Informally,
holds if the string
can be transformed into
by a finite sequence of swaps of adjacent independent symbols. The
equivalence classes of
are called
traces
Traces may refer to:
Literature
* ''Traces'' (book), a 1998 short-story collection by Stephen Baxter
* ''Traces'' series, a series of novels by Malcolm Rose
Music Albums
* ''Traces'' (Classics IV album) or the title song (see below), 1969
* ''Tra ...
,
and are studied in
trace theory.
Examples
200px, right
Given the alphabet
, a possible dependency relation is
, see picture.
The corresponding independency is
. Then e.g. the symbols
are independent of one another, and e.g.
are dependent. The string
is equivalent to
and to
, but to no other string.
References
{{reflist
Binary relations