When reading about descriptive complexity theory, I have read about a "commutative transitive closure operator". I understand transitive closure operators, but what is a commutative transitive closure operator?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Where in "From descriptive complexity" did you see the term used? The source probably provides more context. $\endgroup$– Vijay DFeb 25 '13 at 10:42
Add a comment
|
$\begingroup$
$\endgroup$
Take a relation $R \subseteq X \times X$. Now, let $R^\dagger$ be the converse relation to $R$, and let $\Delta_X$ be the identity relation on $X$.
The commutative transitive closure $R^*$ is the smallest relation $S $ such that $\Delta_X \cup R \cup R^\dagger \cup S \circ S \subseteq S$.
Intuitively, think of the relation $R$ as being the edge relation on a directed graph. The commutative transitive closure tells you whether or not there is a path between two nodes, if you let yourself ignore the directedness.
answered Feb 25 '13 at 11:52