<p>Consider the problem $\def\GEN{\mathrm{GEN}}\GEN$: given a ternary relation $R \subseteq X^3$ and a subset $S \subseteq X$, is the closure of $S$ with respect to $R$ equal to the whole set $X$? By this we mean the smallest set $S \subseteq C \subseteq X$ such that $u,v \in C$ and $R(u,v,w)$ implies $w \in C$.</p>

<p>It is known that $\GEN$ is $\mathsf{P}$-complete for arbitrary relations, and $\mathsf{NL}$-complete when the relation $R$ expresses an associative composition law $*$ (i.e. $R(u,v,w)$ holds iff $w = u*v$).</p>

<p>We can define a notion of "associative relation" extending the above situation, as follows: say that $R$ is associative if for each $a,b,d,e \in X$, we have</p>

<p>$\exists c. (R(a,b,c) \wedge R(c,d,e)) \Rightarrow \exists c. (R(a,c,e) \wedge R(b,d,c)).$</p>

<p>So I would like to know: what is the complexity of the $\GEN$ problem for such relations?
Also, is it possible to define a notion of "$k$-associative relations" that would induce a hierarchy in the space complexity of the $\GEN$ problem?</p>

CC BY-SA 3.0
2014-03-20T09:20:41.670Z
Your relations are in effect directed 3-edges (hypergraph edges, with 3 nodes, some of which are sources and some of which are targets). In this setting, to define associativity, only edges with 2 sources and 1 target make sense. For k-ary relationships, you could have $k-1$ sources and $1$ target (generalising functions $f:S^{k-1} \to S$), but you could also have $s>\lfloor k/2 \rfloor$ sources and $t=k-s$ targets (generalising functions $f:S^s \to S^t$). I think whether you should consider only $t=1$ or allow $t>1$ depends on whether you have any particular relations/functions in mind.
Niel de Beaudrap
CC BY-SA 3.0
2014-03-20T11:56:10.103Z
In any case, I think the answer is "yes": you can define such a notion. Your notion of "associative ternary relation" suggests thinking of relations (with designated sources/targets) as a nondeterministic transition which transforms tuples. We're interested here in transitions which shorten them. For instance, if $R(a,b,c)$, then we can (maybe non-uniquely) map $ab \to c$. $R$ being associative means that if there is a transition $abc \to ec \to d$, then there is also a transition $abc \to af \to d$. Generalising this to arbitrary transitions which decrease tuple length is then an exercise.
Niel de Beaudrap
CC BY-SA 3.0
2014-03-20T14:21:45.537Z
An example of a 5-ary associative relationship with three sources and two targets: $R \subseteq \def\R{\mathbb R}\def\vec{\mathbf}\R^2 \times \R^2 \times\R^2 \times\R^2 \times\R^2$, where $R(\vec u,\vec  v, \vec w, \vec b_1, \vec b_2) \iff [\mathrm{span}\{ \vec b_1, \vec b_2 \} = \mathrm{span}\{\vec u,\vec v,\vec w\}]$. One "applies $R\,$" by replacing triples $(\vec u,\vec v,\vec w)$ of vectors with a pair $(\vec b_1, \vec b_2)$ of vectors which span the same subspace of $\R^2$. Similarly, there's a 7-ary associative relation on $\R^2$ to simplify specifications of affine subspaces of $\R^2$.
Niel de Beaudrap
CC BY-SA 3.0
2014-03-21T18:19:34.070Z
I understand that you interpret $R$ being $k$-ary associative as the existence of two integers $r,s$ that yield a perfect matching in the graph induced by $R$ on $X^r \times X^s$ (up to renumbering of variables). This does not seem to capture what I want, for instance with $r = 2, s = 1$ this only expresses that the third argument is obtained from the first two by some arbitrary operation. Do you see a way to modify the definition to enforce the associativity?
NisaiVloot
CC BY-SA 3.0
2014-03-22T09:59:44.257Z
Er, no; I don't mean anything to do with a matching. See my second comment above. That's a transformation, and despite my earlier comments about directed hypergraphs, you don't have to read it as in any way having to do with a directed edge.
Niel de Beaudrap
<cc.complexity-theory>
Notion of associativity for ternary relations?
NisaiVloot
# Notion of associativity for ternary relations?

(Asked by: username_0 on 2014-03-19)

Consider the problem $\def\GEN{\mathrm{GEN}}\GEN$: given a ternary relation $R \subseteq X^3$ and a subset $S \subseteq X$, is the closure of $S$ with respect to $R$ equal to the whole set $X$? By this we mean the smallest set $S \subseteq C \subseteq X$ such that $u,v \in C$ and $R(u,v,w)$ implies $w \in C$.

It is known that $\GEN$ is $\mathsf{P}$-complete for arbitrary relations, and $\mathsf{NL}$-complete when the relation $R$ expresses an associative composition law $\*$ (i.e. $R(u,v,w)$ holds iff $w = u\*v$).

We can define a notion of "associative relation" extending the above situation, as follows: say that $R$ is associative if for each $a,b,d,e \in X$, we have

$\exists c. (R(a,b,c) \wedge R(c,d,e)) \Rightarrow \exists c. (R(a,c,e) \wedge R(b,d,c)).$

So I would like to know: what is the complexity of the $\GEN$ problem for such relations?
Also, is it possible to define a notion of "$k$-associative relations" that would induce a hierarchy in the space complexity of the $\GEN$ problem?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Your relations are in effect directed 3-edges (hypergraph edges, with 3 nodes, some of which are sources and some of which are targets). In this setting, to define associativity, only edges with 2 sources and 1 target make sense. For k-ary relationships, you could have $k-1$ sources and $1$ target (generalising functions $f:S^{k-1} \to S$), but you could also have $s>\lfloor k/2 \rfloor$ sources and $t=k-s$ targets (generalising functions $f:S^s \to S^t$). I think whether you should consider only $t=1$ or allow $t>1$ depends on whether you have any particular relations/functions in mind.  
> **username_1**: In any case, I think the answer is "yes": you can define such a notion. Your notion of "associative ternary relation" suggests thinking of relations (with designated sources/targets) as a nondeterministic transition which transforms tuples. We're interested here in transitions which shorten them. For instance, if $R(a,b,c)$, then we can (maybe non-uniquely) map $ab \to c$. $R$ being associative means that if there is a transition $abc \to ec \to d$, then there is also a transition $abc \to af \to d$. Generalising this to arbitrary transitions which decrease tuple length is then an exercise.  
> **username_1**: An example of a 5-ary associative relationship with three sources and two targets: $R \subseteq \def\R{\mathbb R}\def\vec{\mathbf}\R^2 \times \R^2 \times\R^2 \times\R^2 \times\R^2$, where $R(\vec u,\vec  v, \vec w, \vec b_1, \vec b_2) \iff [\mathrm{span}\{ \vec b_1, \vec b_2 \} = \mathrm{span}\{\vec u,\vec v,\vec w\}]$. One "applies $R\,$" by replacing triples $(\vec u,\vec v,\vec w)$ of vectors with a pair $(\vec b_1, \vec b_2)$ of vectors which span the same subspace of $\R^2$. Similarly, there's a 7-ary associative relation on $\R^2$ to simplify specifications of affine subspaces of $\R^2$.  
> **username_0**: I understand that you interpret $R$ being $k$-ary associative as the existence of two integers $r,s$ that yield a perfect matching in the graph induced by $R$ on $X^r \times X^s$ (up to renumbering of variables). This does not seem to capture what I want, for instance with $r = 2, s = 1$ this only expresses that the third argument is obtained from the first two by some arbitrary operation. Do you see a way to modify the definition to enforce the associativity?  
> **username_1**: Er, no; I don't mean anything to do with a matching. See my second comment above. That's a transformation, and despite my earlier comments about directed hypergraphs, you don't have to read it as in any way having to do with a directed edge.  

---

## 0 answers

