# Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data
## 4 Compatible Patterns
### ILP for Pattern Equivalence  
We assume that two sets \(P\) and \(Q\) of patterns are given. We introduce the following models  
\[ \begin{array}{ll}v=\min&\sum_{q\in Q}z_{q}\\ &\sum_{i:q_{i}=0}x_{i}+\sum_{i:q_{i}=1}(1-x_{i})\geq 1-z_{q}&q\in Q\\ &y_{p}\leq 1-x_{i}&i:p_{i}=0,\quad p\in P\\ &y_{p}\leq x_{i}&i:p_{i}=1,\quad p\in P\\ &\sum_{p\in P}y_{p}\geq 1\\ &x_{i}\in\{0,1\},y_{p}\in\{0,1\},z_{q}\geq 0\text{ integer}\\ w=\min&\sum_{p\in P}y_{p}\\ &\sum_{i:p_{i}=0}x_{i}+\sum_{i:p_{i}=1}(1-x_{i})\geq 1-y_{p}&p\in P\\ &z_{q}\leq 1-x_{i}&i:q_{i}=0,\quad q\in Q\\ &z_{q}\leq x_{i}&i:q_{i}=1,\quad q\in Q\\ &\sum_{q\in Q}z_{q}\geq 1\\ &x_{i}\in\{0,1\},z_{q}\in\{0,1\},y_{p}\geq 0\text{ integer}\end{array}  \tag{3}\]  
We have the following result:  
**Proposition 7**: \(-S(P)\subset S(Q)\) _if and only if \(v>0\) and \(w=0\); \(-S(Q)\subset S(P)\) if and only if \(w>0\) and \(v=0\); \(-S(Q)=S(P)\) if and only if \(v>0\) and \(w>0\)._  
We reiterate that \(\subset\) means strict inclusion. It is sufficient to prove that \(S(P)\subset S(Q)\) if and only if \(v>0\). If \(y_{p}=1\) then \(x\) is generated by \(p\in P\). The constraint \(\sum_{p\in P}y_{p}\geq 1\) implies that \(x\) is generated by at least one pattern in \(P\). Hence feasible \(x\) are in \(S(P)\). Consider now any \(x\in\{0,1\}^{n}\). If \(x\) is generated by \(q\in Q\) then \(z_{q}=1\), while if \(x\) is not generated by \(q\in Q\) then \(z_{q}=0\) is feasible (along with possible integer values \(z_{q}\geq 1\)). The objective function forces \(z_{q}\) to be zero in this case. Therefore, \(v=0\) if and only if \(x\in S(P)\) and \(x\
otin S(Q)\). If \(v>0\), for any pattern \(x\in S(P)\) we have that \(x\in S(Q)\), i.e., \(S(P)\subseteq S(Q)\). Note that, if \(S(P)\
ot\subseteq S(Q)\), i.e., when \(v=0\), the model (3) yields also a string \(x\) in \(S(P)\) but not in \(S(Q)\), whereas if \(S(P)\subseteq S(Q)\), i.e., when \(v>0\), model (3) yields also a string \(x\) in both \(S(P)\) and \(S(Q)\). Similarly if \(S(Q)\
ot\subseteq S(P)\), i.e., when \(w=0\), model (4) yields also a string \(x\) in \(S(Q)\) but not in \(S(P)\), whereas if \(S(Q)\subseteq S(P)\), i.e., when \(w>0\), model (4) yields also a string \(x\) in both \(S(Q)\) and \(S(P)\). We may further distinguish the case \(w=0\), \(v=0\), via the following model  
\[ \begin{array}{ll}\hat{w}=\min&w_{p}+w_{q}\\ &y_{p}\leq 1-x_{i}&i:p_{i}=0,\quad p\in P\\ &y_{p}\leq x_{i}&i:p_{i}=1,\quad p\in P\\ &\sum_{p\in P}y_{p}\geq 1-w_{p}\\ &z_{q}\leq 1-x_{i}&i:q_{i}=0,\quad q\in Q\\ &z_{q}\leq x_{i}&i:q_{i}=1,\quad q\in Q\\ &\sum_{q\in Q}z_{q}\geq 1-w_{q}\\ \end{array}  \tag{5}\]  
The following proposition follows easily from Proposition 7. **Proposition 8**. : \(S(P)\) _and \(S(Q)\) are disjoint if and only if \(\hat{w}>0\)._  
When \(S(P)\) and \(S(Q)\) are not disjoint, the model yields a string \(x\) shared by both sets. If we consider model (4) and take \(Q=\{(\)-\(\)-\(\)-\()\}\) we are actually solving the problem FULL PATTERN COVERAGE together with its complement PARTIAL PATTERN COVERAGE. Hence (4) becomes  
\[ \begin{array}{ll}u=\min&\sum_{p\in P}y_{p}\\ &\sum_{i:p_{i}=0}x_{i}+\sum_{i:p_{i}=1}(1-x_{i})\geq 1-y_{p}\qquad p\in P \\ &x_{i}\in\{0,1\},y_{p}\geq 0\text{ integer}\end{array}  \tag{6}\]  
and we may conclude, as a Corollary of Proposition 7, that  
**Proposition 9**. : \(S(P)=\{0,1\}^{n}\) _if and only if \(u>0\)._  
As a simple example of the previous results suppose we are given the two following sets of patterns \(P\) and \(Q\). \[P=\left[ \begin{array}{c}\texttt{-}\texttt{-}\texttt{1}\texttt{1}\\ \texttt{1}\texttt{0}\texttt{0}\texttt{-}\\ \texttt{0}\texttt{0}\texttt{-}\texttt{-}\texttt{-}\texttt{-}\texttt{1}\\ \texttt{-}\texttt{1}\texttt{-}\texttt{1}\\ \end{array} \right]\qquad\quad Q=\left[ \begin{array}{c}\texttt{0}\texttt{0} \texttt{-}\texttt{0}\\ \texttt{0}\texttt{-}\texttt{1}\texttt{1}\\ \texttt{-}\texttt{0}\texttt{-}\texttt{1}\\ \end{array} \right]\]  
We run in sequence (3) and (4) and obtain \(v=0\) and \(w>0\), that implies \(S(Q)\subset S(P)\), according to Proposition 7.