## 3 Minimal Patterns and Pattern Priority  
In this section, we introduce the notions of _minimality_ and _pattern priority_. The former will be used to avoid useless characters in the definition of a pattern, the latter as a means for comparison. **Definition 4**: _(Minimal representation \(\mu(\cdot)\)) Given a sequence, \(p\), of length, \(k\), the minimal representation of \(p\) is a sequence, \(\mu(p)\), of length, \(k\), with symbols, \(\mu(p)_{j}=\bigcup_{l\in\mathcal{L}_{m}}s_{l+j-1}\), for \(1\leq j\leq k\)._  
**Remark 1**: _The minimal representation of a sequence is unique._  
**Remark 2**: _Since \(\mu(p)\) is more specific than \(p\), that is, \(\mu(p)\) cannot have more occurrences in \(s\) than \(p\), then the list of occurrences of \(\mu(p)\) must be the same as \(p\)._  
Let \(\mu(m)=(\mu(p),\mathcal{L}_{m})\) be the minimal representation of a pattern, \(m\), with sequence, \(p\), then Remark 2 suggests to us that \(\mu(m)\) agrees with the definition of pattern (that is, \(\mathcal{L}_{\mu(m)}\) is complete): \begin{table}
\begin{tabular}{|r|c c c c c c c c c c|} \hline \(j\) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \(s_{j}\) & \(a\) & \(a\) & \(b\) & \(e\) & \(a\) & \(d\) & \(b\) & \(a\) & \(c\) & \(e\) \\ \hline \end{tabular} \begin{tabular}{|r|c c c c c c c c c|} \hline \(j\) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \end{tabular} \begin{tabular}{|r|c c c c c c c c c|} \hline \(j\) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \(s\) & \(a\) & \(a\) & \(b\) & \(e\) & \(a\) & \(d\) & \(b\) & \(a\) & \(c\) & \(e\) \\ \hline \end{tabular} \
\begin{tabular}{|r|c c c c c c c c c|} \hline \(j\) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \(s\) & \(a\) & \(a\) & \(b\) & \(e\) & \(a\) & \(d\) & \(b\) & \(a\) & \(c\) & \(e\) \\ \hline \end{tabular}
\begin{tabular}{|r|c c c c c c c c c|} \hline \(occurrences\) & & & & & & & & & & & & & \\ \hline \end{tabular}
\end{table} 
Table 2: Example of pattern. The occurrences of \(p\) in \(s\) are drawn in black. **Definition 5**: _(Minimal pattern) The minimal representation of \(m\), given by \(\mu(m)=(\mu(p),\mathcal{L}_{m})\), is called a minimal pattern._  
Computing the minimal representation of a pattern is useful when a pattern is composed by character classes. To have a more concrete idea about this concept, Table 3 shows an example of minimal representation of the pattern \(m=(p=[a,c,d][a,c,d][a,b,e],\{1,5,8\})\), where the reference string is \(s=aabeadbace\) and the classes are \(C_{1}=\{a,c,d\}\) and \(C_{2}=\{a,b,e\}\). In this case, we say that \(\mu(m)=(\mu(p)=a[a,c,d][b,e],\{1,5,8\})\) is a minimal pattern. In practice, most of the functional patterns reported by PROSITE are not minimal. Let \(\mathcal{M}\) be a set of patterns with character classes lying on the string, \(s\). From Remark 1 we have that each pattern, \(m\in\mathcal{M}\), has a unique minimal representation, \(\mu(m)\). Thus, one can easily check that \(\mu(m)=\mu(m^{\prime})\) is an equivalence relation. Let us map all the patterns in \(\mathcal{M}\) into the set of their minimal version, \(\mu(\mathcal{M})\), where each pattern, \(m\in\mu(\mathcal{M})\), is the minimal, \(m=\mu(m^{\prime})\), of some pattern, \(m^{\prime}\in\mathcal{M}\). Then, the set of patterns, \(\mathcal{M}\), is partitioned into equivalence classes by the binary relation of equality between minimal patterns. **Remark 3**: _Two patterns, \(m\) and \(m^{\prime}\), in \(\mathcal{M}\) may have the same location list; thus, they will be mapped into the same minimal pattern, \(\mu(m)=\mu(m^{\prime})\). On the other hand, two minimal patterns with the same location list must have different lengths._  
We call \(\mu(\mathcal{M})\) the _minimal set_ of \(\mathcal{M}\). Since mapping \(\mathcal{M}\) in \(\mu(\mathcal{M})\) could mean a drastic reduction in the number of patterns, this is, in practice, a first step in filtering. Now, we define a simple property of patterns with character classes, the _degeneracy_, that is, the number of characters in a pattern.