I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one.

For example, say I have $N=3$, regular expression $c^*ab^*$ for rows and $b^*ac^*$ for columns. A solution would be

$\qquad\displaystyle\begin{pmatrix} a & b & b \\ c & a & b \\ c & c & a \end{pmatrix}$

I'm trying to find an algorithm that is faster than the brute force one. I am further looking for a way to split this algorithm in independent processes so I can use parallelism to decrease the time needed to reach a solution.

  • $\begingroup$ Since language described by regex might have infinite number of words, I suspect you either work with only finite language OR you only list some first words generated by regex ordered in someway. It would be good to clarify on that. $\endgroup$ – Apiwat Chantawibul Feb 28 '15 at 20:51
  • $\begingroup$ @D.W. Better now, isn't it? $\endgroup$ – Raphael Mar 4 '15 at 7:34
  • $\begingroup$ One simple approach might be to express this as an instance of SAT and apply a SAT solver. There's no reason to expect this to work well for large $N$, but it's so easy to try you could try implementing it and see how well it works. $\endgroup$ – D.W. Mar 4 '15 at 19:13

Here's one idea that may still take exponential time in $N$ but is polynomial in the (length of) the regular expressions.

Consider strings over the shared alphabet $\Sigma$ of length $N^2$; each such string represents an $N \times N$ matrix stored row-wise. We insert a separation character $\$ \not\in \Sigma$ between rows.

We will now construct a finite automaton the accepts exactly the set of such strings that fulfill your two regular expressions.

Let $r$ resp. $c$ be the row resp. column regular expression

  1. Clearly, $r_N = (r \cap \Sigma^N\$)^{N-1}(r \cap \Sigma^N)$ matches all matrices that match $r$ in every row. Transform $r_N$ into an NFA $A_{r,N}$.
  2. Denote with $A^{(i)}_{c,N}$ the automaton that matches only every $N$-th input symbol (ignoring $\$$) against $c$, starting with the $i$-th. I will leave the construction as an exercise; suffice to say that we need at most $N$ copies of $A_c$.

    Now, $A_{c,N} = A^{(1)}_{c,N} \cap \dots A^{(N)}_{c,N}$ accepts the set of all matrices each column of which matches $c$.

  3. The automaton $A_{r,c,N} = A_{r,N} \cap A_{c,N}$ accepts all the matrices you want.

  4. A simple graph traversal finds an accepting path in $A_{r,c,N}$ finds a solution matrix, if any.

The blowup in size is mild (i.e. at most a factor $N^2$) for all constructions but the intersections; these multiply sizes, so we may look at a factor $2^N$ for automaton size.

That's still way better than checking all $\Sigma^{N^2}$ possible matrices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.