# Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data
## 4 Compatible Patterns
Then \(y\in R_{0}\cup R_{1}\) and therefore \(sxy\in R\), so \(p\in P(S)\). If \(x=\mbox{\text@-}\) let \(s0y\) be a string generated by \(p\). Then also \(s1y\) is generated by \(p\). Then \(y\in R_{0}\cap R_{1}\) so that \(s0y,s1y\in R\) and \(p\in P(S)\). **Theorem 2**: \(|P(S)|\leq|S|^{\log_{2}3}\)_._  
Proof. : Let \(T(m)\) be an upper bound to the cardinality of \(P(S)\) for a set \(S\) with \(m=|S|\). From the previous theorem and from the algorithm recursive calls we see that  
\[T(m)=\max\,\{T(m-k)+2\,T(k):k=1,\ldots,\lfloor m/2\rfloor\},\qquad T(1)=1 \tag{1}\]  
By applying the Master Theorem (see p. 66 [18]) we get  
\[T(m)\leq m^{\log_{2}3}\]These are the first values of \(T(m)\) for \(m=1,\ldots,16\), according to (1):  
\[T(m)=1,3,5,9,11,15,19,27,29,33,37,45,49,57,65,81\ldots \tag{2}\]  
This the sequence A006046 as listed in the On-line Encyclopedia of Integer Sequences (OEIS) and our derivation seems to add a new meaning to that sequence. Note from (2) that in particular for \(m=2^{k}\) we have \(T(m)=3^{k}=m^{\log_{2}3}\). Clearly, if \(S\) consists of all strings of length \(k\), so \(|S|=2^{k}\), then \(|P(S)|=3^{k}\). So the bound \(T(m)\) for \(|P(S)|\) is strict in this particular case. In fact, we can prove that the bound is strict for every \(m\) and not just for \(m=2^{k}\). Consider the following Procedure 1 that generates a set \(S\) of \(T(m)\) strings of size \(m\). ```
begin if\(m=1\) thenreturn(1); else begin \(h_{1}=\left\lfloor m/2\right\rfloor\); \(S_{0}=f[h_{0}]\); \(S_{1}=S_{0}\); if\(h_{1}\
eq h_{0}\)then\(S_{1}:=(0,0,\ldots,0)\cup S_{1}\); \(S_{0}:=0\circ S_{0}\); \(S_{1}:=1\circ S_{1}\); return(\(S_{0}\cup S_{1}\));  end if  end
```  
**Procedure 1**\(f[m]\)  
These are the sets produced by the procedure for \(m=1,\ldots,6\), for which  
\[m=1\to S=\{1\}\to P(S)=S=\{1\}\] \[m=2\to S=\{01,11\}\to P(S)=S\cup\{-1\}=\{01,11,-1\}\] \[m=3\to S=(01,10,11)\to P(S)=S\cup(-1,1-)\] \[m=4\to S=(001,011,101,111)\to P(S)=S\cup(0-1,-01,1-1,-11,-1)\] \[m=5\to S=(001,011,100,101,111)\to P(S)=S\cup(0-1,10-,1-1,-01,-11,- -1)\] \[\mathcal{P}(S)=s\circ((0\circ\mathcal{P}_{0})\cup(1\circ\mathcal{P}_{1})\cup( \mbox{\text@-}\circ\mathcal{P}_{*})))\]0 \[\mathcal{P}(S)=s\circ((0\circ\mathcal{P}_{0})\cup(1\circ\mathcal{P}_{1})\cup( \mbox{\text@-}\circ\mathcal{P}_{*})))\]1  
It is easy to show that \(|P(S)|=T(m)\) for the sets produced by the above procedure, and so the bound \(T(m)\) is strict for all \(m\). However, in most cases, as for covering problems, we may be interested only in maximal patterns \(P^{*}(S)\) and we may wonder how the number of maximal patterns grows with \(m\). In the particular case of the strings produced by the above procedure, which corresponds to the worst case in terms of generic patterns, the number of maximal patterns grows very slowly, indeed as \(\log m\). In the following table we report the value \(m,|P(S)|=T(m)\), and the number \(|P^{*}(S)|\) of maximal patterns for the above set of strings  
\[\left( \begin{array}{cccccccccccccccccccc}m&1&2&3&4&5&6&7&8&9&10&11&12&13&14& 15&16\\ |P(S)|&1&3&5&9&11&15&19&27&29&33&37&45&49&57&65&89\\ |P^{*}(S)|&1&1&2&1&2&2&3&1&2&2&3&2&3&3&4&1\end{array} \right)\]  
It turns out that \(|P^{*}(S)|\) is equal to the number of ones in the binary expression of \(m\). However, the number \(|P^{*}(S)|\) can be much larger for other sets of strings. There are  
in our computational experiments we have seen that generating the full matrix and then solving the problem outperforms the column generation approach, which requires running the recursive algorithm for each column generation, while only one run is necessary for generating the full matrix.