Relational Pattern

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

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

      [math]\displaystyle{ \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]\displaystyle{ (p,v_R) }[/math], denoted by [math]\displaystyle{ L(p,v_R) }[/math], is defined as [math]\displaystyle{ \{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]\displaystyle{ R }[/math] will be denoted by [math]\displaystyle{ \mathcal{L}_{\Sigma, R} }[/math].

      For instance, [math]\displaystyle{ 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]\displaystyle{ x_1 }[/math] and [math]\displaystyle{ x_2 }[/math] in a relational pattern [math]\displaystyle{ (p,v_R) }[/math], ensures that the substitutions of [math]\displaystyle{ x_1 }[/math] and [math]\displaystyle{ x_2 }[/math] generating words from [math]\displaystyle{ p }[/math] always have the same length. Formally, this is done by including [math]\displaystyle{ (r, x_1, x_2) }[/math] in [math]\displaystyle{ v_R }[/math]

2011b

2006