2 ms·

Could you elaborate on the encoding? What are valid mappings?

• eutectic 9y ago
  A variable becomes '1' in the corresponding position and '.' everywhere else, and similarly with negations of variables and '0'. The regex is then just an alternation of these sub-regexes. This incurs just a linear blow-up in the number of variables, for the '.'s. For an n x m grid, you can encode any CNF formula with n clauses on m variables. See here if you are unfamiliar with CNF: https://en.wikipedia.org/wiki/Conjunctive_normal_form https://en.wikipedia.org/wiki/Conjunctive_normal_form