<p>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$.</p>

<p>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$. </p>

<p>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. </p>

CC BY-SA 3.0
2013-02-25T11:52:23.983Z
2013-02-26T15:32:15.097Z
2013-02-26T15:32:15.097Z
Neel Krishnaswami
<p>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?</p>

CC BY-SA 3.0
2013-02-25T10:42:10.747Z
Where in "From descriptive complexity" did you see the term used? The source probably provides more context.
Vijay D
<cc.complexity-theory><lo.logic><descriptive-complexity>
What is a commutative transitive closure operator?
Mells
# What is a commutative transitive closure operator?

(Asked by: username_0 on 2013-02-25)

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?

**Tags:** cc.complexity-theory, lo.logic, descriptive-complexity
> **Comments:**
> **username_1**: Where in "From descriptive complexity" did you see the term used? The source probably provides more context.  

---

## 1 answers

### Answer by username_2 on 2013-02-25. Score: 12 | Accepted answer

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.


---

