8
$\begingroup$

Setting: patterns with "don't care" symbols, binary alphabet.

For example, pattern $x = 001?$ represents the set $L(x) = \{0010, 0011\}$.

We are given a set $P$ of disjoint patterns: $L(x) \cap L(y) = \emptyset$ for all $x, y \in P$, $x \ne y$.

The task is to find the smallest possible set of disjoint patterns $Q$ such that $P$ and $Q$ represent the same set of strings: $$\bigcup_{x \in P} L(x) = \bigcup_{y \in Q} L(y).$$


Examples:

  • $P = \{01?, 1?0, ?01, 000, 111\}$, $Q = \{???\}$.
  • $P = \{01?, 1?0, ?01, 000\}$, $Q = \{0??, 10?, 110\}$.

Question: Does anyone recognise this problem? For example, is this a well-known NP-hard problem?

I am mainly interested in positive results — efficient algorithms for exact solutions or good approximations. Algorithms that are exponential in anything (the number of patterns, the length of a pattern, the number of wildcards in a pattern) are too slow for my purposes.


Notes: The problem is fairly easy to solve if we are lucky and there is a solution with $|Q| = 1$. Also it is fairly easy to verify that a given solution is feasible.


Motivation: We encountered a closely related problem recently when we were doing this work. Very briefly, our goal is to simplify a machine-generated case analysis by merging similar cases.

$\endgroup$
  • 4
    $\begingroup$ Your patterns seem to be conjunctions of Boolean literals. Literals involved in a conjunction correspond to 0 or 1, variables not in the conjunction are don't-care values. $P$ is then a DNF formula such that no assignment satisfies more than one disjunct; at first glance this seems to be the same as being in "irredundant DNF". You are asking for $Q$ equivalent to $P$, with the same restriction, but containing the fewest number of disjuncts. It may then be possible to reduce some version of TAUTOLOGY to this problem. Possibly relevant: dx.doi.org/10.1016/S0166-218X(99)00099-2 $\endgroup$ – András Salamon Apr 11 '13 at 22:04

Your Answer

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

Browse other questions tagged or ask your own question.