Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only terminals. In their original definition, patterns only allow for multiple distinct occurrences of some variables to be related by the equality relation, represented by using the same variable multiple times. In an extended notion, called relational patterns and relational pattern languages, variables may be related by arbitrary other relations. We extend the ongoing investigation of the main decision problems for patterns (namely, the membership problem, the inclusion problem, and the equivalence problem) to relational pattern languages under a wide range of individual relations. It is shown show that - even for many much simpler or less restrictive relations - the complexity and (un)decidability characteristics of these problems do not change compared to the classical case where variables are related only by equality.

翻译：模式是由终结符和变量构成的词。一个模式的语言是通过将所有变量统一替换为仅包含终结符的词所得到的词集合。在其原始定义中，模式仅允许通过相等关系（即同一变量的多次出现）来关联某些变量的多个不同实例。在一种称为关系模式与关系模式语言的扩展概念中，变量可通过任意其他关系进行关联。我们将当前对模式主要决策问题（即成员问题、包含问题与等价问题）的研究扩展至广泛个体关系下的关系模式语言。研究表明，即使对于许多更简单或限制更少的关系，这些问题的复杂度与（不）可判定性特征相较于仅通过相等关系关联变量的经典情形并未发生改变。