Matching patterns with variables under Simon’s congruence
Pamela Fleischmann, Sungmin Kim, Tore Koß, Florin Manea, Dirk Nowotka, Stefan Siemer and Max Wiedenhöft.
Presented at RP'23.
Presented at RP'23.
Definitions
Simon’s congruence: For an integer $k$,
two strings $w_1$ and $w_2$ are $k$-congruent ($w_1\sim_k w_2$)
if they have the same set of subsequences
of at most $k$.
Matching patterns with variables problem
under Simon’s congruence:
given a pattern $\alpha$ over the set of variables and terminals
and a string $w$ over the set of terminals,
find a substitution $h$
that satisfies $h(\alpha)\sim_k w$.
Summary of results
- NP-completeness proofs for the following problems:
- matching patterns with variables under Simon's congruence when the pattern is $k$-universal (i.e., contains all subsequences of length at most $k$)
- matching patterns with variables under Simon's congruence against general patterns
- word equation problems under Simon's congruence (i.e., when $w$ also contains variables and the substitution should satisfy $h(\alpha)\sim_k h(w)$) when $k\le |\alpha|+|w|$
- Membership in P for matching patterns with variables against regular patterns (i.e., each variable occurs at most once)
Keywords
Simon’s congruence, matching patterns with variables, word equation, string solving