# Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data
## 4 Compatible Patterns  
We describe a procedure to compute \(P(S)\), that is the set of all compatible patterns for a set \(S\) of strings. The analysis of this procedure shows that the number of compatible patterns is polynomial (\(\leq O(|S|^{\log_{2}3})\)). We define a recursion that produces a set \(\mathcal{P}(S)\) of patterns and we will show that \(\mathcal{P}(S)=P(S)\). We assume there are no duplicates in \(S\). The recursive calls create string sets that satisfy this property. The length of each string in a generic set \(R\) of strings (clearly all of equal length) is denoted by \(n(R)\). For a generic set \(R\) and \(1\leq c\leq n(R)\), \(S(R,c)\) is the set of strings of length \((n-c+1)\) obtained from \(R\) by taking, for each \(s\in R\), only the elements \(s_{c},s_{c+1},\ldots,s_{n(R)}\). Furthermore, for \(s\) a string and \(X=\{x_{1},\ldots,x_{k}\}\) a set of strings, we denote by  
\[s\circ X=\{sx_{1},\ldots,sx_{k}\}\]  
the set obtained by appending \(s\) as a prefix to all strings in \(X\). The recursive algorithm to compute \(\mathcal{P}(S)\) consists of:  
\(\bullet\) base case: **if**\(|S|=1\) then \(\mathbf{return}(S)\) (the entire \(S\), seen as a single string);  
\(\bullet\) recursion: given an input set \(R\) of strings let \(c\leq n(R)\) be the first index such that there are two strings in \(R\) whose \(c\)-th elements are different (if there is not such an index all strings in \(R\) would be identical, contradicting the hypothesis of no duplicates). Hence all prefixes \(s_{1},\ldots,s_{c-1}\) are equal for each \(s\in R\). Let \(\bar{s}\) be this common prefix. Let \(\mathcal{P}_{0},\mathcal{P}_{1},\mathcal{P}_{*}\) be defined as follows:  
1. Let \(R_{0}=\{s\in R:s_{c}=0\}\) and \(S_{0}:=S(R_{0},c+1)\). Then \(\mathcal{P}_{0}:=\mathcal{P}(S_{0})\) (recursive call). 2. Let \(R_{1}=\{s\in R:s_{c}=1\}\) and \(S_{1}:=S(R_{1},c+1)\). Then \(\mathcal{P}_{1}:=\mathcal{P}(S_{1})\) (recursive call). 3. Let \(R_{*}\) be the set of all strings \(s\in R_{0}\) for which there exists \(s^{\prime}\in R_{1}\) such that \(s_{i}=s^{\prime}_{i}\) for all \(i>c\) (note that \(s\) and \(s^{\prime}\) differ only at the \(c\)-th element and that the strings \(s\) and \(s^{\prime}\) (if any) go in pairs due to the hypothesis of no duplicates) and let \(S_{*}:=S(R_{*},c+1)\) (recursive call). **If**\(R_{*}=\emptyset\)**then**\(\mathcal{P}_{*}:=\emptyset\)**else**\(\mathcal{P}_{*}:=\mathcal{P}(S_{*})\). Then, \(\mathbf{return}(s\circ((0\circ\mathcal{P}_{0})\cup(1\circ\mathcal{P}_{1})\cup( \mbox{\text@-}\circ\mathcal{P}_{*})))\)  
**Theorem 1**: _Let \(S\) be a string set and let \(\mathcal{P}(S)\) be the set produced by the recursive algorithm on \(S\). Then \(P(S)=\mathcal{P}(S)\)._  
Proof. : We use induction on \(|S|\). Base case: If \(|S|=1\) the assert is clearly true. Inductive step: Assume \(|S|>1\) and the theorem holds for all sets with \(|S|-1\) strings. With the notation of the algorithm,  
\[\mathcal{P}(S)=s\circ((0\circ\mathcal{P}_{0})\cup(1\circ\mathcal{P}_{1})\cup( \mbox{\text@-}\circ\mathcal{P}_{*})))\]  
Let \(p\in P(S)\). Since \(s\) (possibly null) is a prefix of each string in \(S\), \(p\) must start with \(s\) as well. Assume \(p=sxq\) with \(x\in\{0,1,-\}\). If \(x=0\) then \(q\) is a pattern compatible for \(S_{0}\) and, by induction, \(q\in\mathcal{P}(S_{0})\). Therefore, \(p\in s\circ(0\circ\mathcal{P}(S_{0}))\), so that \(p\in\mathcal{P}(S)\). A similar argument shows that also if \(x=1\) it is \(p\in\mathcal{P}(S)\). Now, if \(x=\mbox{\text@-}\), then for each string \(a\) generated by \(q\), the pattern \(p\) generates both \(s0a\) and \(s1a\). Therefore, \(a\) had to be a string both in \(S_{0}\) and in \(S_{1}\). This means that \(q\) had to be a pattern compatible for \(S_{*}\). Since, by induction, all such patterns are in \(\mathcal{P}_{*}\) then \(p\in s\circ(\mbox{\text@-}\circ\mathcal{P}_{*})\) so that \(p\in\mathcal{P}(A)\). Now, assume \(p\in\mathcal{P}(S)\). Let \(p=sxq\), with \(x\in\{0,1,-\}\). If \(x\in\{0,1\}\), let \(sxy\) be a string generated by \(p\).