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.
Simplifying the disjoint union of wildcard strings
ds.algorithms;reference request;fl.formal languages;string matching