## 3 Minimal Patterns and Pattern Priority
For instance, consider \(s=\texttt{aabeadbace}\) and the patterns \(m=(\texttt{[a,d][a,b][a,e]},\{2,6\})\) and \(m^{\prime}=(\texttt{[a,d][b,e][a,e]},\{2,6\})\) with the same list of occurrences: In short, \(|m|=|m^{\prime}|=3\), \(c(m)=c(m^{\prime})=6\) and \(\mathcal{L}_{m}=\mathcal{L}_{m^{\prime}}\). This means that we are not able to compare \(m\) and \(m^{\prime}\) using the pattern priority rule. Another example is given by \(m_{1}=(\texttt{a[a,c,d][b,e]},\{1,5,\,8\})\), \(m_{2}=(\texttt{[b,e][a,c,d]},\{4,7\})\) and \(m_{3}=(\texttt{[a,b][c,d][b,e]},\{5,8\})\). In this case, \(m_{1}\to m_{2}\) and \(m_{2}\to m_{3}\), but \(m_{1}\to m_{3}\) does not hold, since \(\mathcal{L}_{m_{3}}\subset\mathcal{L}_{m_{1}}\). The issue is that these patterns are not minimal, like most of the patterns in PROSITE. In the following, we set the basis to solve this problem. **Theorem 2**: _Given any set of patterns, \(\mathcal{M}\), its minimal set, \(\mu(\mathcal{M})\), is totally ordered under the binary relation of pattern priority._ProofAlong with Theorem 1, we have that any set of patterns, \(\mathcal{M}\), is sub-ordered under pattern priority; thus, also the set of minimal patterns, \(\mu(\mathcal{M})\), is sub-ordered. Following Lemma 1, we have to prove that the totality holds on this new set, \(\mu(\mathcal{M})\), that is, every pair of minimal patterns must be comparable under pattern priority. In other words, if \(m\
eq m^{\prime}\), it must hold either \(m\to m^{\prime}\) or \(m^{\prime}\to m\). From Remark 3, we have that \(\mathcal{L}_{m}\
eq\mathcal{L}_{m^{\prime}}\) for two minimal patterns, \(m\) and \(m^{\prime}\), with the same length, and thus, we have, without loss of generality, two cases to consider: \(\mathcal{L}_{m}\
subseteq\mathcal{L}_{m^{\prime}}\) or \(\mathcal{L}_{m}\subset\mathcal{L}_{m^{\prime}}\). From now, \(m\) and \(m^{\prime}\) will be two minimal patterns with the same length and, for the former case, also with the same degeneracy \(c(m)\). Thus, in the former case, if we consider \(\min\{\mathcal{L}_{m}\setminus\mathcal{L}_{m^{\prime}}\}\) and \(\min\{\mathcal{L}_{m^{\prime}}\setminus\mathcal{L}_{m}\}\), the two minima exist and are different from each other; hence, it holds that either \(m\to m^{\prime}\) or \(m^{\prime}\to m\), respectively, if the minimum of the two sets is either in \(\mathcal{L}_{m}\) or in \(\mathcal{L}_{m^{\prime}}\). In the latter case, \(\mathcal{L}_{m}\subset\mathcal{L}_{m^{\prime}}\Rightarrow c(m)<c(m^{\prime})\), since \(m\) and \(m^{\prime}\) are minimal patterns, and the respective location lists are complete (that is, the respective patterns of \(m\) and \(m^{\prime}\) must be different); therefore, it holds that \(m\to m^{\prime}\). Thus, for any set of minimal patterns under pattern priority, the totality holds. From Lemma 1, we can conclude that any set of minimal patterns is totally ordered under the pattern priority rule. \(\Box\)  
As a consequence of Theorem 2, all minimal patterns can be compared and ranked. We can further observe that every minimal pattern has priority over the patterns within its equivalence class, due to property (2) of pattern priority. Now, it is clear that any set of patterns can be mapped into its minimal representative set and that we can build a measure of total order over this set.