# Relational Pattern

A Relational Pattern is a Pattern that is composed of variables that are connected by a set of relations.

## References

### 2011a

• (Zilles, 2011) ⇒ Michael Geilke, and Sandra Zilles. (2011). “Learning Relational Patterns.” In: Proceedings of International Conference on Algorithmic Learning Theory (ALT 2011). Lecture Notes in Computer Science. ISBN:978-3-642-24411-7, 978-3-642-24412-4, doi:10.1007/978-3-642-24412-4_10
• QUOTE: Let $R$ be a set of relations over $\Sigma^*$. Then, for any $n \in N_+$, $R_n$ denotes the set of $n$-ary relations in $R$. A relational pattern with respect to $\Sigma$ and $R$ is a pair $(p,v_R)$ where $p$ is a pattern over $\Sigma$ and $v_R \subseteq \{(r,y_1,\cdots,y_n) | n \in N_+, r \in R_n,$ and $y_1,\cdots,y_n$ are variables in $p\}$. The set of relational patterns with respect to $R$ will be denoted by $Pat_{\Sigma, R}$.

The set of all possible substitutions for $(p,v_R)$ is denoted $\Theta_{(p,v_R),\Sigma}$ It contains all substitutions $\theta \in \Theta_{\Sigma}$ that fulfill, for all $n \in N_+$:

$\forall\, r\in R_n \; \forall \,y_1,\dots,y_n \in X \Big[r, y_1,\cdots, y_n \in v_R \Rightarrow \left(\theta(y_1), \cdots, \theta(y_n)\right) \in r\Big]$

The language of $(p,v_R)$, denoted by $L(p,v_R)$, is defined as $\{w \in \Sigma^* | \exists \theta \in \Theta_{(p,v_R),\Sigma}: \theta(p) = w\}$. The set of all languages of relational patterns with respect to $R$ will be denoted by $\mathcal{L}_{\Sigma, R}$.

For instance, $r=\{(w_1,w_2)|w_1,w_2 \in \Sigma^* \wedge |w_1|=|w_2| \}$ is a binary relation, which, applied to two variables $x_1$ and $x_2$ in a relational pattern $(p,v_R)$, ensures that the substitutions of $x_1$ and $x_2$ generating words from $p$ always have the same length. Formally, this is done by including $(r, x_1, x_2)$ in $v_R$