Pattern matching under ℛ-congruence

Sungmin Kim, Hyundong Jin and Yo-Sub Han.
To be presented at CIAA'26.

Definitions

$\mathcal{R}$-congruence: For an integer $k$, two strings $w_1$ and $w_2$ are $\sim_k^{\mathcal{R}}$-congruent ($w_1\sim_k^{\mathcal{R}} w_2$) if each prefix of $w_1$ and $w_2$ satisfies Simon’s congruence to some prefix of $w_2$ and $w_1$, respectively. The family of $\mathcal{R}$-congruence closures are exactly the languages whose syntactic monoid is $\mathcal{R}$-trivial (Brzozowski and Fich, 1980).
Pattern matching under $\mathcal{R}$-congruence: find all substrings of a text $\texttt{T}$ that matches a pattern $\texttt{P}$ (i.e., $\sim_k^{\mathcal{R}}$-congruent to $\texttt{P}$).

Summary of results

• A $O(|w|+|v|)$ time algorithm that decides $w\sim_k^{\mathcal{R}}v$
• A $O(|\Sigma||\texttt{P}|+|\Sigma||\texttt{T}|k)$ time algorithm for the pattern matching under $\mathcal{R}$-congruence problem when $k$ is given
• A $O(|\texttt{T}||\texttt{P}|)$ time algorithm for the pattern matching under $\mathcal{R}$-congruence problem for all $k\le |\texttt{T}|$

Keywords $\mathcal{R}$-congruence, Simon’s congruence, pattern matching, subsequences