# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## Appendix A Missing Proofs
Now, if the support set of \(\mathbf{y}_{\tau}\) in \(W\) does not coincide with \(W\), that is, \(T_{W}(\mathbf{y}_{\tau})\subset W\), then for each transaction \(\tau\in W\) we have \(|T_{W}(\mathbf{y}_{\tau})|<|T_{W}(p_{1})|=|T_{W}(p_{2})|=|W|\). Note that this could happen because the set of itemsets of \(p_{1}\) and \(p_{2}\) may not appear in the same order in all transactions. Hence each super-sequence of both \(p_{1}\) and \(p_{2}\) has support lower than the support of \(p_{1}\) (that is equal to the support of \(p_{2}\)). Thus, each super-sequence of \(p_{i}\) has a lower support compared to the support of \(p_{i}\), for \(i=1,2\)This implies that \(p_{1}\) and \(p_{2}\) are closed sequences in \(\mathcal{D}\) and since their support set is \(W\), they belong to \(CS_{W}(\mathcal{D})\). Thus, the case \(C=2\) could happen. Now we generalize this concept for a generic number \(C\) of closed sequential patterns, where \(2\leq C\leq|CS(\mathcal{D})|\). Let \(H=\{p_{1},p_{2},\ldots,p_{C}\}\) be a set of \(C\) sequential patterns with \(W\) as support set. Assume that each super-sequence of \(p_{i}\) but not of \(p_{k}\) has support lower than the support of \(p_{i}\), for each \(i,k\in[1,\ldots,C]\) with \(k\
eq i\). Let \(H_{p}\) be the power set of \(H\) without the empty set and the sets made of only one sequence, that is, \(H_{p}=P(H)\setminus\{\{\emptyset\},\{p_{1}\},\{p_{2}\},\ldots,\{p_{C}\}\}\). So, in \(H_{p}\) there are every possible subset of \(H\) of size greater than one. For a transaction \(\tau\in W\) and \(h_{p}\in H_{p}\), we define \(\mathbf{y}_{\tau}(h_{p})=\tau_{h_{p}}\) as the subsequence of \(\tau\) restricted to \(h_{p}\), that is, to only the sequences \(p\in h_{p}\), preserving the relative order of their itemsets. If \(\forall h_{p}\in H_{p}\) there exits a transaction \(\tau\in W\) such that the support set of \(\mathbf{y}_{\tau}(h_{p})\) in \(W\) does not coincide with \(W\), that is, \(T_{W}(\mathbf{y}_{\tau}(h_{p}))\subset W\), then for each transaction \(\tau\in W\) we have \(|T_{W}(\mathbf{y}_{\tau}(h_{p}))|<|T_{W}(p_{1})|=\cdots=|T_{W}(p_{C})|=|W|\). Hence each super-sequence made of only sequences of \(h_{p}\) has support lower than the support of \(p_{i}\), for \(i=1,\ldots,C\). Thus, each super-sequence of \(p_{i}\) has a lower support compared to the support of \(p_{i}\), for \(i=1,\ldots,C\). This implies that all sequences of \(H\) are closed sequence in \(\mathcal{D}\) and since their support set is \(W\), they belong to \(CS_{W}(\mathcal{D})\). Lemma 2: \(V_{\mathcal{D}}=\{v_{\mathcal{D}}(p):\ p\in CS(\mathcal{D})\}\cup\{(0,\ldots,0)\}\) _and \(|V_{\mathcal{D}}|\leq|CS(\mathcal{D})|+1\), that is, each vector of \(V_{\mathcal{D}}\) different from \((0,\ldots,0)\) is associated with at least one closed sequential pattern in \(\mathcal{D}\)._  
Proof: Let \(V_{\mathcal{D}}=\overline{V}_{\mathcal{D}}\cup\{(0,\ldots,0)\}\), where \(\overline{V}_{\mathcal{D}}=\{v\in V_{\mathcal{D}}:\ v\
eq(0,\ldots,0)\}\). Let \(p\in\mathbb{U}\) be a sequence of non-empty support set in \(\mathcal{D}\), that is, \(v_{\mathcal{D}}(p)\
eq(0,\ldots,0)\). There are two possibilities: \(p\) is or is not a closed sequence in \(\mathcal{D}\). If \(p\) is not a closed sequence, then there exists a closed super-sequence \(\mathbf{y}\sqsupset p\) with support equal to the support of \(p\), so with \(v_{\mathcal{D}}(p)=v_{\mathcal{D}}(\mathbf{y})\). Thus, \(v_{\mathcal{D}}(p)\) is associated with at least one closed sequence. Combining this with the fact that each vector \(v\in\overline{V}_{\mathcal{D}}\) is associated with at least one sequence \(p\in\mathbb{U}\) and Lemma 1, then each vector of \(V_{\mathcal{D}}\) different from \((0,\ldots,0)\) is associated with at least one closed sequential pattern of \(\mathcal{D}\). To conclude our proof is sufficient to show that there are no closed sequences associated with the vector \((0,\ldots,0)\). Let \(SP_{\infty}=\{p\in\mathbb{U}:\ v_{\mathcal{D}}(p)=(0,\ldots,0)\}\). Note that \(|SP_{\infty}|=\infty\).