Matching patterns with variables under Simon’s congruence
Pamela Fleischmann, Sungmin Kim, Tore Koß, Florin Manea, Dirk Nowotka, Stefan Siemer and Max Wiedenhöft.
To be published in Journal of Automata, Languages and Combinatorics, 2026.
To be published in Journal of Automata, Languages and Combinatorics, 2026.
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 against regular patterns (i.e., each variable occurs at most once)
- Membership in P for $k$-universal patterns when $k=1$
Keywords
Simon’s congruence, matching patterns with variables, word equation, string solving