Source-linked AI summary
An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints
Klaus Jansen, Dirk Nowotka, Lis Pirotton, Corinna Wambsganz, Max Wiedenhöft
TL;DR
Relational patterns extend equality-based patterns by imposing relations between variable substitutions, while decision results for these languages remain limited. This paper studies equivalence, inclusion, and membership across customary relations, establishing results that include a structural equivalence criterion and NP-complete membership.
Problem
Results for relational pattern languages remain limited, particularly for weaker relations, while erasing-pattern equivalence is a major open problem.
Source: §1 · p. 3Method
The paper studies equivalence, inclusion, and membership for relational pattern languages under a selection of customary binary relations.
Source: §1 · p. 3Results
Across the problems, non-erasing equivalence gets a structural criterion, membership is NP-complete, and erasing inclusion is decidable under common nonemptiness but undecidable under reversal and abelian equivalence.
Source: §3.1 · p. 6, §5 · p. 13Takeaways & Limitations
The results and remaining open cases provide a basis for future research on these decision problems and settings that encode problems into relational pattern languages.
Source: §6 · p. 13The paper considers only single-relation patterns; combining relations could increase expressiveness and may change decidability.
Source: §6 · p. 13
Abstract
from arXiv · showhide
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.
1 Introduction
Patterns provide a compact way to define formal languages and appear across computer science and discrete mathematics. This paper extends the study of equivalence, inclusion, and membership to relational pattern languages under selected relations.
1 Introduction
- Patterns appear in areas including algorithmic learning, databases, pattern matching, protein-data analysis, and program synthesis.Their practical and simple definition also makes them a compact device for defining formal languages.Source: §1 · p. 1
- For classical pattern languages, non-erasing equivalence is trivially decidable, while general equivalence for erasing languages remains a major open problem.Inclusion is undecidable for alphabets of fixed size at least two in both erasing and non-erasing cases, and membership is generally NP-complete in both.Source: §1 · p. 2
- Relational patterns use regular patterns with separate constraints on variables, allowing substitutions to be related by relations beyond equality.For example, reversal constraints on two variables can permit substitutions ab and ba, but not ab and ab.Source: §1 · p. 2
- Prior work on relational patterns leaves weaker relations largely unexplored after showing that regular or length constraints can make erasing equivalence undecidable.The paper selects representative relations, including equality, equal length, subsequence, reversal, and abelian equivalence, and studies all three decision problems.Source: §1 · pp. 2–3
- Table 1 summarizes the decision-problem status for the considered relations, marking new results and distinguishing erasing from non-erasing cases.The paper presents its results as a basis for further work across equivalence, inclusion, and membership.Source: Table 1 · p. 3, §1 · p. 3
2 Preliminaries
The preliminaries define patterns through terminal-preserving substitutions and distinguish erasing from non-erasing languages. Relational patterns add constraints among variables while restricting the study primarily to customary binary relations.
2 Preliminaries
- The preliminaries define word length, letter counts, alphabets, subsequences, and abelian equivalence as equality of counts for every letter.These conventions provide the notation used to state the relations and decision problems.Source: §2 · p. 3
- A pattern is a non-empty finite word over terminal letters and variables; substitutions fix terminals and map variables to terminal words.A substitution is non-erasing when every variable occurring in the pattern maps to a nonempty word.Source: §2 · pp. 3–4
- Relational patterns pair a regular pattern, where each variable occurs at most once, with relations constraining the substituted words.The erasing language allows empty variable images, while the non-erasing language requires each occurring variable to map to a nonempty word.Source: §2 · p. 4
- The study primarily considers one binary relation at a time, selected from customary relations listed in Table 2.The relation set includes equality, equal length, subsequence, abelian equivalence, alphabet permutation, reversal, commutation, star, and common (non)emptiness.Source: §2 · p. 4, Table 2 · p. 4
3 The Equivalence Problem
The section studies equivalence of relational pattern languages in non-erasing and erasing settings. It gives structural and algorithmic results for several relations, while leaving many erasing cases open.
3.1 The Non-Erasing Case
- For non-erasing reversal, subsequence, and star constraints, equality of patterns and constraint closures is insufficient, and decidability is conjectured rather than established.The paper notes that these relations are not equivalence relations.Source: §3 · p. 5, §3.1 · p. 6
- For non-erasing relations satisfying the stated alphabet conditions, equivalent languages require identical patterns and identical closures of their constraints.The result applies when the relation is an equivalence relation, relates each letter to itself, and relates no distinct letters.Source: §3.1 · pp. 5–6
- For non-erasing languages, equivalence under equality, abelian equivalence, and commutation is decidable in polynomial time.Equality of languages is characterized by equality of the patterns and the reflexive, symmetric, and transitive closures of their constraints.Source: §3.1 · p. 6
3.2 The Erasing Case
- Erasing equivalence is decidable for the common nonemptiness relation, and has linear-time or polynomial-time tests under specified pattern or alphabet conditions.The conditions include terminal-free patterns, a unary alphabet, or a letter absent from both patterns.Source: §3.2 · pp. 6–7
- The erasing common-nonemptiness procedure enumerates subsets of variable equivalence classes to erase, builds NFAs for the resulting languages, and compares them.The proof sketch bounds the number of subsets for a pattern by 2^|α|.Source: §3.2 · pp. 6–7
- Erasing equivalence for star, subsequence, and reversal constraints is at least as hard as erasing equivalence under equality, via polynomial-time many-one reductions.The reduction for reversal uses a more technical construction than those for star and subsequence.Source: §3.2 · p. 7
- Most erasing equivalence questions remain open, even for relatively weak structure-enforcing relations.The paper contrasts these cases with efficient non-erasing results and structural restrictions that may support future decidability proofs.Source: §3.2 · p. 8
4 The Inclusion Problem
The inclusion problem is undecidable for several relations in both erasing and non-erasing settings, while ε-equality admits decidable cases. Inclusion remains open for length, alphabet permutation, and commutation relations.
4.1 The Non-Erasing Cases; 4.2 The Erasing Cases
- For |Σ| ≥ 2, inclusion is undecidable in both erasing and non-erasing cases under equality, subsequence, or the star relation.The non-erasing case is also undecidable under abelian equivalence and reversal; the erasing case is undecidable under those two relations as well.Source: §4 · p. 8, §4.1 · p. 8, §4.2 · p. 10
- Under ε-equality, erasing inclusion is decidable, using NFAs to represent the two languages.For non-erasing ε-equality, substitutions cannot erase variables, so inclusion reduces to regular-pattern inclusion, known to be decidable in polynomial time.Source: §4.1 · p. 8, §4.2 · p. 10
4.2 The Erasing Cases
- For ε-equality, erasing inclusion is decidable in linear time when both patterns are terminal-free or the alphabet is unary.The tests use minimum equivalence-class sizes, and for unary alphabets also compare terminal counts.Source: §4.2 · p. 10
- Decidability remains open for inclusion under length, alphabet permutation, and either commutation relation.The reductions used here do not carry over: length and permutation do not enforce equality of letters or unary words over binary alphabets, while commutation does not enforce equal lengths.Source: §4.2 · p. 12
5 The Membership Problem
The membership problem is NP-complete for nearly all considered relations and cases over alphabets of size at least two. The exception is non-erasing membership under ε-equality, which is decidable in linear time.
5 The Membership Problem
- Membership is in NP because a substitution of output length can be guessed, its relational constraints checked, and its resulting word compared with the input.The paper obtains hardness for most relations by adapting a reduction from positive 1-in-3-SAT; the remaining commutation cases use a 3-SAT reduction.Source: §5 · pp. 12–13
- For |Σ| ≥ 2, membership is NP-complete in the erasing case for every considered relation and in the non-erasing case except under ε-equality.The non-erasing ε-equality case is decidable in linear time.Source: §5 · p. 13
6 Final Discussion
The paper establishes combinatorial and complexity results for equivalence, inclusion, and membership under a selection of ten relations. It identifies unstudied relations and combinations of relations as directions for further work.
6 Final Discussion
- The paper studies equivalence, inclusion, and membership for relational pattern languages under ten representative binary relations.The results are intended as a basis for settings that encode problems into relational pattern languages.Source: §6 · p. 13
- Other natural relations remain unexplored in this setting, including non-equality and cyclic shift.The authors describe non-equality as an interesting candidate and ask how inclusion and equivalence behave under it.Source: §6 · p. 13
- The analysis considers only one relation per pattern; combining relations could make decidable cases undecidable.The authors also note that adding relations weaker than regular or length constraints could affect the open erasing-equivalence case under equality.Source: §6 · p. 13