pipette
ESEspañol

An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints

Klaus Jansen, Dirk Nowotka, Lis Pirotton, Corinna Wambsganz, Max Wiedenh\"oft

Preprint with a published version

In the authors' words

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, achieved by using regular patterns and relating individual variables independently from the patterns structure separately. We extend the ongoing investigation of the main decision problems for patterns (namely, the equivalence problem, the inclusion problem, and the membership problem) to relational pattern languages under a wide range of relevant individual relations, providing a comprehensive foundation in all three research directions.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 7. arXiv. Preprint with a published version.

DOI: 10.4204/EPTCS.451.13

Published version: EPTCS 451, 2026, pp. 186-200

Authors' comment: In Proceedings AFL 2026, arXiv:2608.23071. A full version of this paper, containing all proofs, can be found at arXiv:2512.07476