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?
Notion of associativity for ternary relations?
cc.complexity theory