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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.