Relational Pattern

From GM-RKB
Jump to: navigation, search

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



References

2016a

2016b

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 [math]R[/math] be a set of relations over [math]\Sigma^*[/math]. Then, for any [math]n \in N_+[/math], [math]R_n[/math] denotes the set of [math]n[/math]-ary relations in [math]R[/math]. A relational pattern with respect to [math]\Sigma[/math] and [math]R[/math] is a pair [math](p,v_R)[/math] where [math]p[/math] is a pattern over [math]\Sigma[/math] and [math]v_R \subseteq \{(r,y_1,\cdots,y_n) | n \in N_+, r \in R_n,[/math] and [math]y_1,\cdots,y_n[/math] are variables in [math]p\}[/math]. The set of relational patterns with respect to [math]R[/math] will be denoted by [math]Pat_{\Sigma, R}[/math].

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

      [math]\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] [/math]

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

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

2011b

2006