The complexity of some regex crossword problems

Stephen A. Fenner

In a typical regular expression (regex) crossword puzzle, you are given two nonempty lists $R_1,\dots ,R_m$ and $C_1,\dots ,C_n$ of regular expressions over some alphabet, and your…