<p>I give here an answer for a very specific subcase.
We let <span class="math-container">$x \in A_1 \times \dots \times A_k$</span> be written <span class="math-container">$(x^1,\dots,x^k)$</span>.<br />
When the rule <span class="math-container">$\sigma$</span> acts on each <span class="math-container">$A_i$</span> independently, in the same way, that is <span class="math-container">$$\sigma(x_1,\dots,x_p) = (\sigma(x_1^1,\dots,x_p^1),\dots, \sigma(x_1^k,\dots,x_p^k))$$</span> there are better algorithms.
In particular, when the <span class="math-container">$A_i$</span> are of size <span class="math-container">$2$</span>, that is you compute the closure of sets by set operations, the complexity of computing the closure is well understood.
You get a complexity linear in the size of the closure you are computing
times a polynomial in <span class="math-container">$k$</span>. The only exception, is for the closure by union, for which the complexity is slightly worse: linear in the size of the closure times |R|.</p>
<p>To get the best possible complexity, there are different methods depending on the rules. But there is a general method with a decent complexity using backtrack search: You consider a partial solution
<span class="math-container">$(x_1,\dots,x_i)$</span> for <span class="math-container">$i \leq k$</span> and it is possible to decide
whether it can be extended into an element of the closure, which allows to efficiently produce all solutions by a search tree, pruning the branch without solution.
This method does not always work efficiently when <span class="math-container">$|A_i|&gt;2$</span> or when the rule does not act coordinate-wise.</p>
<p>You can check our paper, Efficient enumeration of solutions produced by closure operations, to look at the details <a href="https://arxiv.org/abs/1712.03714" rel="nofollow noreferrer">https://arxiv.org/abs/1712.03714</a></p>

CC BY-SA 4.0
2023-05-09T15:11:19.957Z
2023-05-09T15:11:19.957Z
Yann Strozecki
<p>(Recalling some) Definitions:</p>
<ol>
<li>Fix a finite collection of finite sets: <span class="math-container">$A_1,\ldots,A_k$</span>. Then relationship <span class="math-container">$R\subseteq A_1 \times A_2 \times \ldots\times A_k$</span>. (Remark: <span class="math-container">$A_i$</span>'s need not be distinct.)</li>
<li>A rule (or transition) <span class="math-container">$\sigma: R^m \to A_1 \times A_2 \times \ldots\times A_k$</span>.</li>
</ol>
<p>Examples:</p>
<ol>
<li><p>Consider the ancestor relationship <span class="math-container">$R = \{(x,y)\mid x \text{ is an ancestor of } y\}$</span>. Then the rule <span class="math-container">$\sigma: R^2 \to A \times A$</span> is given by <span class="math-container">$\sigma((x,y),(y,z)) = (x,z)$</span> represents the transitive rule that if <span class="math-container">$x \text{ is an ancestor of } y$</span> and <span class="math-container">$y \text{ is an ancestor of } z$</span> then <span class="math-container">$x \text{ is an ancestor of } z$</span>.</p>
</li>
<li><p>Consider the 3-cycles relationship <span class="math-container">$R = \{ (x, y, z) \mid x\rightarrow y \rightarrow z \rightarrow x \text{ is a directed cycle of a Graph}\}$</span>. Then the rule <span class="math-container">$\sigma: R \to R$</span> given by <span class="math-container">$\sigma((x,y,z)) = (y, z, x)$</span> represents the cyclic order symmetry relation.</p>
</li>
</ol>
<p>Question-1: Given <span class="math-container">$\sigma$</span> and <span class="math-container">$R$</span>, what is an <em>efficient algorithm</em> to compute the transitive closure of <span class="math-container">$\sigma$</span> with respect to <span class="math-container">$R$</span>?</p>
<p>(Remark: Some naive/ obvious approaches I thought of so far:</p>
<ol>
<li><p>(Brute force: ) Loop through all <span class="math-container">$e\in R^m$</span>,check if <span class="math-container">$e$</span> satisfies conditions of <span class="math-container">$\sigma$</span>, if yes then add <span class="math-container">$\sigma(e)$</span> to <span class="math-container">$R$</span>. Repeat until no more new elements can be added. <span class="math-container">$O(|R|^m)$</span>.</p>
</li>
<li><p>For example-1 with a binary relationship and transitive rule, I know about Floyd-Marshall Algorithm. <span class="math-container">$O(|A|^3)$</span>. There are 3 independent variables <span class="math-container">$x, y, z\in A$</span>. Looping through them would be <span class="math-container">$O(|A|^3)$</span>. But surely Floyd-Marshall is more superior than brute force looping over <span class="math-container">$x, y, z\in A$</span>.</p>
</li>
<li><p>Using the independent variable trick one gets <span class="math-container">$O(|A|^p)$</span>, where <span class="math-container">$p$</span> is number of independent variables. At this stage we need to check if all conditions satisfy or not. So in the most general case this is a <span class="math-container">$\mathrm{SAT}$</span> problem and hence probably no hopes of doing better. However I would love to know more about if anything more is known than what I am thinking about naively.)</p>
</li>
</ol>
<p>Question-2: Is there a software package that already implements this? (I prefer Python, but any language should be fine).</p>

CC BY-SA 4.0
2023-05-09T08:07:22.847Z
What is your definition of the transitive closure of $\sigma$ with respect to $R$?
D.W.
<graph-algorithms><sat><logical-relations><transitive-closure>
Efficient algorithm/ implementation to compute Transitive Closure of a Rule with respect to a Relationship
Inspired_Blue
# Efficient algorithm/ implementation to compute Transitive Closure of a Rule with respect to a Relationship

(Asked by: username_0 on 2023-05-08)

(Recalling some) Definitions:

1. Fix a finite collection of finite sets: $A\_1,\ldots,A\_k$. Then relationship $R\subseteq A\_1 \times A\_2 \times \ldots\times A\_k$. (Remark: $A\_i$'s need not be distinct.)
2. A rule (or transition) $\sigma: R^m \to A\_1 \times A\_2 \times \ldots\times A\_k$.

Examples:

1. Consider the ancestor relationship $R = \{(x,y)\mid x \text{ is an ancestor of } y\}$. Then the rule $\sigma: R^2 \to A \times A$ is given by $\sigma((x,y),(y,z)) = (x,z)$ represents the transitive rule that if $x \text{ is an ancestor of } y$ and $y \text{ is an ancestor of } z$ then $x \text{ is an ancestor of } z$.
2. Consider the 3-cycles relationship $R = \{ (x, y, z) \mid x\rightarrow y \rightarrow z \rightarrow x \text{ is a directed cycle of a Graph}\}$. Then the rule $\sigma: R \to R$ given by $\sigma((x,y,z)) = (y, z, x)$ represents the cyclic order symmetry relation.

Question-1: Given $\sigma$ and $R$, what is an *efficient algorithm* to compute the transitive closure of $\sigma$ with respect to $R$?

(Remark: Some naive/ obvious approaches I thought of so far:

1. (Brute force: ) Loop through all $e\in R^m$,check if $e$ satisfies conditions of $\sigma$, if yes then add $\sigma(e)$ to $R$. Repeat until no more new elements can be added. $O(|R|^m)$.
2. For example-1 with a binary relationship and transitive rule, I know about Floyd-Marshall Algorithm. $O(|A|^3)$. There are 3 independent variables $x, y, z\in A$. Looping through them would be $O(|A|^3)$. But surely Floyd-Marshall is more superior than brute force looping over $x, y, z\in A$.
3. Using the independent variable trick one gets $O(|A|^p)$, where $p$ is number of independent variables. At this stage we need to check if all conditions satisfy or not. So in the most general case this is a $\mathrm{SAT}$ problem and hence probably no hopes of doing better. However I would love to know more about if anything more is known than what I am thinking about naively.)

Question-2: Is there a software package that already implements this? (I prefer Python, but any language should be fine).

**Tags:** graph-algorithms, sat, logical-relations, transitive-closure

> **Comments:**
> **username_1**: What is your definition of the transitive closure of $\sigma$ with respect to $R$?  

---

## 1 answers

### Answer by username_2 on 2023-05-09. Score: 3

I give here an answer for a very specific subcase.
We let $x \in A\_1 \times \dots \times A\_k$ be written $(x^1,\dots,x^k)$.  
When the rule $\sigma$ acts on each $A\_i$ independently, in the same way, that is $$\sigma(x\_1,\dots,x\_p) = (\sigma(x\_1^1,\dots,x\_p^1),\dots, \sigma(x\_1^k,\dots,x\_p^k))$$ there are better algorithms.
In particular, when the $A\_i$ are of size $2$, that is you compute the closure of sets by set operations, the complexity of computing the closure is well understood.
You get a complexity linear in the size of the closure you are computing
times a polynomial in $k$. The only exception, is for the closure by union, for which the complexity is slightly worse: linear in the size of the closure times |R|.

To get the best possible complexity, there are different methods depending on the rules. But there is a general method with a decent complexity using backtrack search: You consider a partial solution
$(x\_1,\dots,x\_i)$ for $i \leq k$ and it is possible to decide
whether it can be extended into an element of the closure, which allows to efficiently produce all solutions by a search tree, pruning the branch without solution.
This method does not always work efficiently when $|A\_i|>2$ or when the rule does not act coordinate-wise.

You can check our paper, Efficient enumeration of solutions produced by closure operations, to look at the details <https://arxiv.org/abs/1712.03714>


---

