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.

Improve this question
$\endgroup$
1
  • 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, 2013 at 22:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.