## 3 Minimal Patterns and Pattern Priority
**Definition 6**: _(Degeneracy of a sequence \(c(\cdot)\)) The degeneracy of a sequence, \(p\), of length, \(k\), is defined as \(c(p)=\sum_{j=1}^{k}|p_{j}|\). The degeneracy of a pattern, \(m=(p,\mathcal{L}_{m})\), denoted by \(c(m)\), is defined as the degeneracy of its sequence, \(c(p)\)._  
For instance, given two sequences, \(p=a[a,c,d][b,e]\) and \(p^{\prime}=[a,d]b[a,b]\), their degeneracy is \(c(p)=6\) and \(c(p^{\prime})=5\). Therefore, the degeneracy of the pattern, \(m=(a[a,c,d][b,e],\{1,5,8\})\), is equal to \(c(p)\), that is, 6. With this notion, we can define the _priority_ between patterns, as a means for comparing different patterns. Note that several notions of priority can be established at this stage. We choose a very intuitive combination of pattern length, pattern degeneracy and location list. **Definition 7**: _(Pattern priority '\(\rightarrow\)') A pattern, \(m\), of length, \(k\), has priority over another pattern, \(m^{\prime}\), of length, \(k^{\prime}\), denoted, \(m\to m^{\prime}\), if (1) \(k>k^{\prime}\), or (2) \(k=k^{\prime}\) and \(c(m)<c(m^{\prime})\), or (3) \(k=k^{\prime}\), \(c(m)=c(m^{\prime})\), \(\min\{\mathcal{L}_{m}\setminus\mathcal{L}_{m^{\prime}}\}\subset\min\{ \mathcal{L}_{m^{\prime}}\setminus\mathcal{L}_{m}\}\), when both minima exist._ \begin{table}
\begin{tabular}{c c c c} \hline \hline \(\boldsymbol{j}\) & **1** & **2** & **3** \\ \hline \(p_{j}\) & \([a,c,d]\) & \([a,c,d]\) & \([a,b,e]\) \\ \(\mu(p)_{j}\) & \(a\) & \([a,c,d]\) & \([b,e]\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Example of minimal representation of a pattern, \(m\), with sequence, \(p\). For instance, consider \(s=aabeadbace\), \(m=(a[a,c,d][b,e],\{1,5,8\})\) and \(m^{\prime}=([a,d]b[a,b,e],\{2,6\})\). Then, \(m\) has priority over \(m^{\prime}\), written \(m\to m^{\prime}\), because they have the same length and degeneracy, but \(1=\min\{\mathcal{L}_{m}\setminus\mathcal{L}_{m^{\prime}}\}<\min\{\mathcal{L}_ {m^{\prime}}\setminus\mathcal{L}_{m}\}=2\). If two patterns, \(m\) and \(m^{\prime}\), have the same length and degeneracy, but either \(\mathcal{L}_{m}\subseteq\mathcal{L}_{m^{\prime}}\) or \(\mathcal{L}_{m^{\prime}}\subset\mathcal{L}_{m}\), then we consider them _incomparable_; otherwise, they are comparable. Nevertheless, we will solve the non-comparability of two patterns with Theorem 2. Given our binary relation, called _pattern priority_, we want to prove that some basic properties holds:  
**Definition 8**: _(Sub-ordered, totally ordered) Given a set, \(\mathcal{M}\), if a binary relation, \(R\), over this set is (i) irreflexive; \(m\)\(R\)\(m^{\prime}\) never holds (ii) antisymmetric, \(m\
eq m^{\prime}\Rightarrow\) not \((m\)\(R\)\(m^{\prime}\) and \(m^{\prime}\)\(R\)\(m)\); and (iii) acyclic, then \(\mathcal{M}\) is said to be sub-ordered. If \(R\) is also total, that is \((m\)\(R\)\(m^{\prime}\) or \(m^{\prime}\)\(R\)\(m)\), then \(\mathcal{M}\) is said to be totally sub-ordered. Furthermore, \(\mathcal{M}\) is said to be totally ordered if \(R\) is irreflexive, antisymmetric, transitive, that is \((m\)\(R\)\(m^{\prime}\) and \(m^{\prime}\)\(R\)\(m^{\prime\prime})\Rightarrow m\)\(R\)\(m^{\prime\prime}\) and total._  
**Lemma 1**: _A set, \(\mathcal{M}\), is totally ordered under a binary relation, \(R\), if and only if it is totally sub-ordered._  
ProofIt is straightforward that transitivity implies acyclicity, that is, if \(\mathcal{M}\) is totally ordered, then \(\mathcal{M}\) is also totally sub-ordered. It is also easy to see that acyclicity and totality, together, imply transitivity. Consider a chain of patterns in \(\mathcal{M}\): \(m_{1}\)\(R\)\(m_{2}\), \(m_{2}\)\(R\)\(m_{3},\ldots\), \(m_{t-1}\)\(R\)\(m_{t}\). Since for acyclicity, \(m_{t}\)\(R\)\(m_{1}\) does not hold, then, for totality, \(m_{1}\)\(R\)\(m_{t}\). Hence, transitivity holds and, therefore, the definitions totally sub-ordered and totally ordered coincide. \(\Box\)  
Now, before showing that some of these properties hold, we need to prove two preliminary results for the pattern priority rule.