Structure of frequent itemsets with extended double constraints

Before formally describing the current problem, let us present practical examples that motivate us to study and propose the new results in this paper. Let us consider searching documents on the Internet where the finding needs of users are very diverse. The datasets of information regarding documents are usually saved into the tables. Each row in a table can contain keywords, appeared in a document, the author names of the document, the type of document (Article, Book, Sort Survey, and so on) and the research area. It is common that online users usually take interest in looking for documents that comprise of a given set of keywords. Expected documents also have to be related to a specific topic A (including one or more keywords belonging to A), but they are not involved in other topic B (not having any keywords belonging to B). A specific example of this problem is as follows. An online user wants to look for research results from websites or search engines such as CiteSeerX, Springer and ScienceDirect. His/her need is to find the results related to keywords in the set \(C^{\prime }_{21} =\) {‘sequential patterns’, ‘frequent sequence’, ‘web usage mining’, ‘sequential rules’}, but they are not of authors in the list \(C^{\prime }_{11}\) = {‘Peter’, ‘Chan’, ‘Carmona’, ‘Matthews’}. In addition, the found results are also ‘Article’ and belong to the area of ‘Computer Science’. Specifically, the purpose of this user is to find articles in the field of computer science (the results have to contain both words in the set \(C_{10}=\) {‘Article’, ‘Computer Science’}) that comprise of at least a keyword of \(C^{\prime }_{21} \) and contain no authors in the list \(C^{\prime }_{11} \). It is clear that the need above is practical and the interest of many researchers nowadays. Other example for the current problem is when we want to build a filter to allow children searching interesting movies on the internet. Then, a compulsory key to obtain desired results is one in the set \(C_{10}\) = {movie}. Here, we only allow them to watch movies that belong to kinds in the list, \(C^{\prime }_{21}=\) {‘Animated’, ‘Cartoons’, ‘Comedy’, ‘ Fiction’, or ‘Documentary’}, but they are forbidden to see types of movies in the list \(C^{\prime }_{11}=\) {‘Action’, ‘Horror’, ‘Violated’, ‘Secxual’, ‘Thriller’ and ‘Porn’}. In other words, the aim is to allow children to find all enjoyable and good videos (that are pulling in large audience) that are ‘movie’ and follow one or more kinds in \(C^{\prime }_{21}\) but are not any types in \(C^{\prime }_{11}\). In fact, it is able to see more different significant examples.

A formal statement of the problem in our current research is presented as follows.

Formal problem statement Let T be a dataset, \({\mathcal A}\) be the set of all attributes or items in T. An itemset A is a non-empty subset of \({\mathcal A}\) and a transaction in T is a set of items \(t \in 2^{\mathcal A}\). The support of A, denoted as supp(A), is the number of transactions that are superset of A. Given two threshold values, \(s_0\) and \(s_1\), and three subsets, \(C_{10}\), \(C_{11}\) and \(C_{21}\), of \({\mathcal A}\) such that \(0<s_0 \leqslant s_1 \leqslant 1\), \(C_{10} \subseteq C_{11} \not \subseteq C_{21}\). A is called frequent if \(supp(A)\in [s_0 , s_1]\). The task is to find the class \({\mathcal F}{\mathcal S}_{{C_{10}\subseteq C_{11},\nsubseteq C_{21}}} (s_0 ,s_1 )\) of all the frequent itemsets that (1) includes a subset \(C_{10}\), (2) contains no items of a subset \(C^{\prime }_{11} = {\mathcal A} \backslash C_{11}\) and (3) have at least an item belonging to subset \(C^{\prime }_{21}= {\mathcal A} \backslash C_{21}\). In our second example above, \(C_{10}=\) movies, \(C^{\prime }_{11}=L_{1}\) and \(C^{\prime }_{21} =L_{2}\). In other words, the goal is to discover all elements A of \({\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11},\nsubseteq C_{21}} (s_0 ,s_1)\) that can be stated formally as below:Note that the current problem is an extension of many of our formerly considered problems. If \(s_1 = 1\), \({\mathcal F}{\mathcal S}\) is the class of all frequent itemsets in the traditional meaning. When \(s_1<\) 1, we desire to consider frequent itemsets with supports that are not too high because they sometimes are valuable. For instance, they can help discover association rules with high confidences from abnormal phenomena appearing in frequent itemsets of which frequency is not necessary to be quite high (such as new, unusual rules for both positive and negative aspects in the field of network security or for finding out the falsehood on the figure of socioeconomic field). In addition, when the constraints are given special values, we obtain frequent itemsets without any constraint or with single constraints in simple forms, \({\mathcal F}{\mathcal S}(s_0)\) and \({\mathcal F}{\mathcal S}_{C_{11}} (s_0)\) in [2] or \({\mathcal F}{\mathcal S}_{\not \subseteq {C_{21}}} (s_0)\) in [3] or \({\mathcal F}{\mathcal S}_{\supseteq C_{10}}(s_0)\) in [16], or with double constraints presented in \({\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11}} ({s_0 ,s_1})\) [17]. So, we can find that the extended double constraint presented in this paper is more general than that, \({\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11}} ({s_0 ,s_1})\), shown in [17], by extending a new kind of constraint set, \(C_{21}\), which is an arbitrary subset of \({\mathcal A}\). Indeed, when we assign \(C_{21}\) = \(\varnothing \), we immediately obtain the problem \({\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11}}({s_0 ,s_1})\). The extension of the new constraint \(C_{21}\) or \(C^{\prime }_{21} \) has multiple practical meanings as shown in the examples above. A quite naïve thought for solving the problem \({\mathcal F}{\mathcal S}_{\varvec{C}_{\varvec{10}} \subseteq \varvec{C}_{\varvec{11}} ,\nsubseteq \varvec{C}_{\varvec{21}}} (s_0 ,s_1)\) is to filter from the results of \({\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11}} ({s_0 ,s_1})\) those that satisfy the constraint \(C_{21}\) in a post-processing step. However, this will do so many useless tests, and as a result, it will take much mining time. Thus, using the lattice of closed itemsets and their generators which is also used in [2, 3, 15‐17], we study and propose a new method to effectively mine frequent itemsets with above constraints, called extended double constraints (EDC). EDC can be categorized into two kinds, \({\mathcal C}_{m}(supp(L^{\prime }) \le s_1,C_{10} \subseteq L^{\prime }\) and \(L^{\prime }\not \subseteq C_{21})\) and \({\mathcal C}_{am}(supp(L^{\prime })\ge s_0\) and \(L^{\prime } \subseteq C_{11})\). Below are my contributions for the method to effectively discover frequent itemsets with EDC.

The contributions of this paper are as follows. First, the result of the paper is the generalization of our former problems which are to find frequent itemsets without constraints or with simpler constraints. Particularly, it is an extension of the problem \({\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11}} ({s_0,s_1})\) [17] of which the result has been published in a good international journal by further considering a significant constraint, \(C_{21}\) or \(C^{\prime }_{21}\).

Second, we showed sufficient and necessary conditions for the non-emptiness of the solution set. The conditions allow us to turn checking the constraints on the very large number of frequent itemsets into testing them on representative closed itemsets of equivalence classes with quite small amount. Our lattice-based approach becomes more effective when the conditions are combined with the techniques of creating upper and under borders to quickly eliminate branches or nodes on the lattice. It also has a high sustainability in face of regular changes of the constraints following user’s need. Third, we show a structure and a unique representation of frequent itemsets with EDC that help us test the conditions on the quite small number and size of generators. This representation also allows us to integrate the constraints into the process of generating constrained frequent itemsets without checks in a post-processing step. Finally, in practice, based on these theoretical results, we propose a new algorithm, MFS-EDC, to completely and distinctly exploit all frequent itemsets with EDC. The advantages of MFS-EDC are that: it quickly discovers all frequent itemsets that satisfy opposite constraints, \({\varvec{\mathcal C}}_{\varvec{am}}\) and \({\varvec{\mathcal C}}_{\varvec{m}}\), concurrently by pushing the constraints into MFS-EDC without direct checks on them (post-processing or naïve approaches can do this by directly testing the output results of \({\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11}} ({s_0,s_1})\) on \(C_{21}\) or the ones of \({\mathcal F}{\mathcal S}(s_0)\) on all constraints of EDC); it is easy to be turned into parallel algorithms to obtain real time in mining process; it only needs to access the original dataset once, even if the constraints are changed regularly. This considerably enhances mining performance.

The rest of this paper is organized as follows. Some preliminary concepts related to the problem are reviewed in Sect. 2. Approaches to deal with the current problem are also considered in this section. Section 3 presents a rough partition and then a stricter partition of the solution set. In Sect. 4, we propose a structure of the solution set based on a necessary and sufficient condition of closed itemsets and their generators for the emptiness of \({\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11}\nsubseteq , C_{21}}(s_0,s_1)\), and a unique representation of frequent itemsets with extended double constraint in each equivalence class based on closed itemsets and their generators. We also propose an efficient algorithm MFS_EDC to exploit all frequent ones with extended double constraint. Experimental results will be discussed in Sect. 5. The conclusions and future work is presented in Sect. 6. Finally, for easier to read, the proof of the theoretical results in this study is moved to “Appendix”.

For a binary dataset according to discovered data context \({\mathcal T}\buildrel \mathrm{def} \over = ({\mathcal O},{\mathcal A},{\mathcal R})\), where \({\mathcal O}\) is a non-empty set of transactions, \({\mathcal A}\) is the set of all items appearing in those transactions and \({\mathcal R}\) is a binary relation on \({\mathcal O}x{\mathcal A}\). A set of items is called an itemset. Consider two Galois connection operators \(\lambda : 2^{\mathcal O} \rightarrow 2^{\mathcal A}\) and \(\rho :2^{\mathcal A} \rightarrow 2^{\mathcal O}\) defined as follows: \(\forall O, A: \varnothing {\,\,\ne O}\subseteq {\mathcal O}, \varnothing \ne A \subseteq {\mathcal A}\), \(\lambda (O)\buildrel \mathrm{def} \over = \{a\in {\mathcal A}{\vert (o, a)}\in {\mathcal R}, \forall o\in O\}, \rho (A) \buildrel \mathrm{def} \over = \{o\in {\mathcal O}{\vert (o, a)\in \,\, }{\mathcal R}, \forall a\in A \}\) and, as convention, \(\lambda (\varnothing ) \buildrel \mathrm{def} \over = {\mathcal A}, \rho (\varnothing ) \buildrel \mathrm{def} \over = {\mathcal O}\). We denote h(A) \(\buildrel \mathrm{def} \over = \lambda (\rho (\mathrm{A}))\) as the closure of A (h is called the closure operation in \(2^{\mathcal A})\). An itemset A is called closed itemset iff¹ \(h(A) = A\) [25]. The support of \(A\subseteq {\mathcal A}\), denoted as supp(A), is the ratio of cardinality \({\vert }\rho {(A)}\vert \) to \({\vert } {\mathcal O} {\vert }\), i.e. \(supp({A}) \buildrel \mathrm{def} \over = \vert \rho {(A)}\vert / \vert {\mathcal O} {\vert }\). The minimum and maximum support thresholds are denoted as \(s_0\) and \(s_1\), respectively, where \(0< 1/n \le s_0 \le s_1 \le 1\) and \({n} \buildrel \mathrm{def} \over = \vert {\mathcal O} {\vert }\). We only consider non-trivial items in \({\mathcal A}^{\mathcal F} \,\,{\buildrel \mathrm{def} \over = }\,\, {{\{}a} \in {\mathcal A}{\vert supp({\{}a{\}}) } \ge s_0 {{\}}}\). Let \({\mathcal C}{\mathcal S}\) be the class of all closed itemsets together with their supports. With normal order relation “\(\subseteq \)” over subsets of \({\mathcal A}\), \({\mathcal L}{\mathcal C} \buildrel \mathrm{def} \over =({\mathcal C}{\mathcal S},\subseteq \)) is the lattice of all closed itemsets organized by Hass diagram. A non-empty itemset A (subset of \({\mathcal A}^{\mathcal F})\) is called frequent iff \(s_0 \le \) supp(\(A) \le s_1 \). Note that if \(s_{1}\) is equal to 1, then the traditional frequent itemset concept is obtained. Briefly, \({\mathcal F} {\mathcal S} \,\,{\buildrel \mathrm{def} \over =}\,\,{\mathcal F}{\mathcal S}(s_0 ,s_1 )\,\buildrel \mathrm{def} \over = \{L^{\prime }: \varnothing \ne L^{\prime }\subseteq {\mathcal A},s_0 {\le supp(L^{\prime }) \le }s_1{{\}}}\) denotes the class of all frequent itemsets and \({\mathcal F}{\mathcal C}{\mathcal S} \buildrel \mathrm{def} \over = {\mathcal F}{\mathcal C}{\mathcal S}(s_0,s_1)\,\,\buildrel \mathrm{def} \over ={\mathcal F}{\mathcal S}(s_0 ,s_1 )\cap {\mathcal C}{\mathcal S}\) denotes the class of all frequent closed itemsets. For any two non-empty sets \(G, A: \varnothing \ne G \subseteq A \subseteq {\mathcal A}, G\) is called a generator [25] of A iff \(h(G) = h(A)\) and \((h(G^{\prime }) \subset {h(G), \forall G^{\prime }:} \varnothing \ne G^{\prime }\subset G)\). Let \({\mathcal G}(A)\) be the class of all generators of A. Since \({\mathcal G}(A)\) is non-empty and finite [4], \({\vert } {\mathcal G}(A)\vert = k\), all generators of A are indexed: \({\mathcal G}(A) {= {\{}} A_1 , A_2 ,\ldots , A_k {{\}}}\). Let \({\mathcal L}{\mathcal C}{\mathcal G} {\buildrel \mathrm{def} \over = {\{} \langle L, supp(L), }{\mathcal G}(L){\rangle \vert }{L} \in {\mathcal L}{\mathcal C} {{\}}}\) be the lattice \({\mathcal L}{\mathcal C}\) of closed itemsets together with their generators and \({\mathcal L}{\mathcal F}{\mathcal C}{\mathcal G}(s_0 ,s_1 ) {\buildrel \mathrm{def} \over = {\{} \langle L, supp(L), }{\mathcal G}(L)\rangle \in {\mathcal L}{\mathcal C}{\mathcal G} {\vert L } \in {\mathcal F}{\mathcal C}{\mathcal S}(s_0 ,s_1 ){{\}}}\) be the lattice of frequent ones and the generators.

From the partition in Proposition 1, we immediately obtain the following rough partition for \({\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11},\nsubseteq C_{21}}(s_0,s_1)\).

The results are shown in Fig. 1b. Let us consider the constraints on supports \(s_0=2/7,s_1=1\). For briefness, we denote itemset \(\{a_1, a_2, \ldots , a_k\}\) as \(a_1 a_2 \ldots a_k\), for example, \({{\{}a, f, h{\}}}\) as afh. It is possible that there are many values of constraints and closed itemsets \(L \in {\mathcal F}{\mathcal C}{\mathcal S}(s_0,s_1)\) such that \({\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11}},\nsubseteq C_{21},} = \varnothing \), even \({\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11} ,\nsubseteq C_{21},} (s_0,s_1) = \varnothing \). Indeed, we consider examples as follows:Then, the post-processing approach takes quite much time to generate all frequent itemsets in equivalence sub-classes [L], corresponding to closed frequent itemsets L, and then so many or even all sub-classes are eliminated because they do not satisfy the constraints. From this example, we find it is important to have sufficient and necessary conditions and then impose them on the constraints and closed itemsets L to narrow \({\mathcal F}{\mathcal C}{\mathcal S}({s}_0 ,{s}_1 )\) into \({\mathcal F}{\mathcal S}_{{C}_{10} \subseteq {C_{11}} ,\nsubseteq C_{21}} (s_0,s_1)\). Here, \({\mathcal F}{\mathcal S}_{{C}_{10} \subseteq {C_{11}} ,\nsubseteq C_{21}} (s_0 ,s_1 )\) includes closed itemsets which are not only frequent but they also satisfy constraints regarding sub-items \({{\{}}C_{10} ,C_{11} ,C_{21} {{\}}}\) so that corresponding solution subsets are not empty, i.e. \({\mathcal F}{\mathcal S}_{{C}_{10} \subseteq L_{C_{11}} ,\nsubseteq C_{21}} \ne \,\,\varnothing .\)

To briefly present the remaining results, we consider the following lemma which will be used to prove Propositions 3 and 4 in the next section.

The following algorithm, MFCS-EDC, is to extract \({\varvec{\mathcal F}}{\varvec{\mathcal C}}{\mathcal S}_{{\varvec{C}}_{\varvec{10}} \subseteq {\varvec{C}}_{\varvec{11}} ,\nsubseteq {\varvec{C}}_{\varvec{21}} } ({\varvec{s}}_{\varvec{0}} ,{\varvec{s}}_{\varvec{1}})\) (the set of constrained frequent closed itemsets which is the output of the algorithm) from the input data which is the lattice \({\varvec{\mathcal L}}{\varvec{\mathcal C}}{\varvec{\mathcal G}}\) of all closed itemsets and their generators together with user constraints, \({\varvec{s}}_{\varvec{0}} ,{\varvec{s}}_{\varvec{1}}, {\varvec{C}}_{\varvec{10}}, {\varvec{C}}_{\varvec{11}}\) and \({\varvec{C}}_{\varvec{21}}\) (Fig. 2).

When implementing the algorithm MFCS-EDC, to quickly determine \({\mathcal F}{\mathcal C}{\mathcal S}_{{C}_{10} \subseteq {C}_{11} ,\nsubseteq {C}_{21}}({s}_\mathrm{0} ,{s}_\mathrm{1})\) from \({\mathcal L}{\mathcal C}{\mathcal G}\), we can use the methods of eliminating nodes and branches of nodes, or creating upper and under borders while travelling the lattice. We split the constraints in \({\mathcal F}{\mathcal C}{\mathcal S}_{{C}_{10} \subseteq {C}_{11} ,\nsubseteq {C}_{21}} ({s}_\mathrm{0} ,{s}_\mathrm{1})\) into the groups: monotonic \({\mathcal C}_{m} {\buildrel \mathrm{def} \over = (supp(L)}\leqslant s_1 \ and \ C_{10}{\subseteq \,\, L and\,\, L\,\,\cap \,\,}C_{11} {\not \subseteq }C_{21} )\), anti-monotonic \({\mathcal C}_{am} {\buildrel \mathrm{\mathrm{def}} \over = (supp(L)} \geqslant s_0 )\) and \({\mathcal C}_\mathrm{non} {\buildrel \mathrm{def} \over = (}{\mathcal G}_{C_{11}} (L)\ne \varnothing )\) (that is neither monotonic nor anti-monotonic. An itemset satisfies a constraint \({\mathcal C}_\mathrm{non}\) if it does not satisfy both \({\mathcal C}_{am}\) and \({\mathcal C}_{m})\).

To use the advantages of the properties of \({\mathcal C}_{m}\), when travelling in the bottom-up direction of the lattice, standing at one node L, if:Similarly, we use five steps above when going in the top-down direction of the lattice to consider \({\mathcal C}_{am}\).

Note that we often pre-select one of two groups, \({\mathcal C}_{am}\) and \({\mathcal C}_{m}\), which is much more likely to be not satisfied, such as the group with more constraints in the form of AND than other. We also choose the bottom-up or the top-down first so that eliminating branches is done before borders are created. For the considering problem, it is more suitable to select \({\mathcal C}_{am}\) and go in the bottom-up direction of the lattice first.

It is able to be found from this example that, for post-processing approach, we have to take a lot of time to generate all \(\vert {\mathcal F}{\mathcal S}(s_0,s_1){\vert =35}\) frequent itemsets and then check them on the constraints about sub-items. But, we only obtain two of them, ahf and af, satisfying the constraints. Meanwhile, based on the condition \({L}\in {\mathcal F}{\mathcal C}{\mathcal S}_{C_{10} \subseteq C_{11}, \not \subseteq C_{21},}(s_0,s_1)\) and the methods of eliminating branches and nodes as well as creating borders on the lattice, we quickly wiped out eight of nine equivalence sub-classes (corresponding with 29 of 35 frequent itemsets), which did not meet the requirements of the constraints, and only need to check one node.

Note that, in the final sub-class \([L=afh],\) after generating six frequent itemsets, we have to check them on the constraints in the post-processing step which can still consume time a lot. In next section, we will show the way to partition \({\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11}},\not \subseteq C_{21}}\) into two disjoint solution subsets based on dividing the generators in \({\mathcal G}_{C_{11} }(L)\) into two parts according to \(C_{21}\).

Going on the idea of partition, for \(\forall L \,\,\in {\mathcal F}{\mathcal C}{\mathcal S}_{C_{10} \subseteq C_{11} ,\nsubseteq C_{21}}(s_0,s_1)\), we divide each equivalence class \({\mathcal F}{\mathcal S}_{{C}_{10} \subseteq L_{C_{11}} ,\nsubseteq C_{21}} {\buildrel \mathrm{def} \over = {\{}L^{\prime }\in [L] \vert }C_{10} {\subseteq L^{\prime } \subseteq }L_{C_{11}}, L^{\prime } \not \subseteq C_{21}{{\}}}\) into two disjoint parts based on the partition of generators in \({\mathcal G}_{C_{11} } (L)\) as follows, \({\mathcal G}_{C_{11} } (L)={\mathcal G}_{C^+} (L)+{\mathcal G}_{C_{11} ,\nsubseteq C_{21} } (L)\), where \({\mathcal G}_{C^+} (L) \buildrel \mathrm{def} \over = {\{}L_i \in {\mathcal G}(L): L_i \subseteq C^+{\}} = {\{}L_i \in {\mathcal G}_{C_{11} } (L): L_i \subseteq C_{21} {\}}, {\mathcal G}_{C_{11} ,\nsubseteq C_{21}} (L) \buildrel \mathrm{def} \over = {\{}L_i \in {\mathcal G}_{C_{11}}(L): L_i \not \subseteq C_{21} {\}}\).

We first number all \(K_i \in K_\mathrm{min,C_{-}\subseteq L_{C^+} } {\buildrel \mathrm{def} \over = Minimal{\{}}K_i \mathop =\limits ^{\text{ def }} L_i {\backslash C{\_},} \ L_i \,\, {\in } \,\, {\mathcal G}_{C^+} (L), 1\le i\le {M{\}}} \ \mathrm{from} \ 1\, \mathrm{to}\, M\, \mathrm{if} \ {\mathcal G}_{C^+} (L) \,\, {\ne } \,\, \varnothing \) or set M \(=\) 0, if \({\mathcal G}_{C^{+}}(L) = \varnothing \). Then, we continue to number, from \(M+1\), subsets in \(K_\mathrm{min, C_{10} \subseteq L_{C_{11} } ,\mathrm{G} \not \subseteq {C}_{21} } \buildrel \mathrm{def} \over =\) Minimal \({\{}K_i \mathop =\limits ^{\mathrm{def}} L_i \backslash C_{10}\), \(L_i \in {\mathcal G}_{C_{11} ,\nsubseteq C_{21}} (L), \forall i>M{\}}\) and denote \(K_\mathrm{min,C_{10} \subseteq L_{C_{11}}, \not \subseteq {C}_{21} }^+\buildrel \mathrm{def} \over = K_\mathrm{min,C\subseteq L_{C^+}}\cup K_\mathrm{min ,C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21}}\).

Note that if \({\mathcal G}_{C^+} (L)=\varnothing \) (like when \(C^+ = \varnothing \)), then we setOtherwise, if \({\mathcal G}_{C^+} (L) \ne \varnothing \), we define: \(\lfloor {L}\rfloor _{C_-\subseteq L_{C^{+}} ,+L_{C^*}} {\buildrel \mathrm{def} \over =} \{L^{\prime }\in {\mathcal F}{\mathcal S}_{{C}_{10} L_{C_{11}} ,\nsubseteq C_{21} } {\vert \exists }L_i \,\, {\in } \,\, {\mathcal G}_{C^+} (L): L^{\prime } \supseteq L_i \} \ \mathrm{and}\ 2^{\left[ {C_{10} \backslash C_{21} \subseteq L_{C^*} } \right] *}{\buildrel \mathrm{def} \over =} \{ L^{\sim }{\ne } \,\, \varnothing {\vert }C_{10} \backslash C_{21} {\subseteq L}^{\sim }{\subseteq } L_{C^*} \}, K_{U,C_{-}\subseteq L_{C^+} }^i {\buildrel \mathrm{def} \over = }\mathop \bigcup \nolimits _{K_k \in K_\mathrm{min,C_{-}\subseteq L_{C^+} } ,k\le i} K_k , K_{U,C_{-}\subseteq L_{C^+} ,i} {\buildrel \mathrm{def} \over = } \left\{ {{\begin{array}{ll} {K_{U,C_{-}\subseteq L_{C^+} }^{i-1} \backslash K_i,\quad \mathrm{if} \,\, i \ge 2}\\ {\varnothing ,\quad \mathrm{if} \,\, i=1}\\ \end{array}}}\right. , K_{-,C_{-}\subseteq L_{C^+} ,i} {\buildrel \mathrm{def} \over = }L_{C^+} \backslash (C\_+K_{U,C_{-}\subseteq L_{C^+} }^i) = L_{C^{+}} \backslash (C_{10} \cup K_{U,C_{-}\subseteq L_{C^+} }^i)\) and \({\mathcal F}{\mathcal S}_{C_{-}\subseteq L_{C^+} }^*{ \buildrel \mathrm{def} \over =} \{L^{\prime \prime } \, {\buildrel \mathrm{def} \over = } \, C\_+K_i +K_i^{\prime } +K_i^{\sim } {\vert }K_i \in K_\mathrm{min,C_{-}\subseteq L_{C^+} } , K_i^{\prime } \subseteq K_{U,C_{-}\subseteq L_{C^+} ,i} , K_i^{\sim } \subseteq K_{-,C_{-}\subseteq L_{C^+} ,i}\) and \((K_k {\not \subseteq }K_i +K_i^{\prime },\forall K_k \in K_\mathrm{min,C_{-}\subseteq L_{C^+} } : 1\le k<i)^{(*)},1\leqslant i\leqslant M \}.\) And if \(\,\, {\mathcal G}_{C_{11} ,\nsubseteq C_{21}} (L)=\varnothing \) then we assign \({\mathcal F}{\mathcal S}_{C_{10}\subseteq L_{C_{11}}, C_{20}\not \subseteq , G \nsubseteq C_{21} }^*\equiv \lfloor {L}\rfloor _{C_{10}\subseteq L_{C_{11}}, C_{20} \not \subseteq , G \nsubseteq C_{21}} \buildrel \mathrm{def} \over = \varnothing \). On the contrary, we denote \(\lfloor {L}\rfloor _{C_{10}\subseteq L_{C_{11}}, G \not \subseteq C_{21} } \buildrel \mathrm{def} \over = \{L^{\prime }\in \,\, {\mathcal F}{\mathcal S}_{\text{ C }_{10} \subseteq L_{C_{11}}, \nsubseteq C_{21}} {\vert (\exists }L_i {\in }{\mathcal G}_{C_{11} ,\nsubseteq C_{21}} (L): L^{\prime } \supseteq L_i)\) and \((L_k \not \subseteq L^{\prime }, \forall L_k \in {\mathcal G}_{C^+} (L))\}, K_{U,C_{10}\subseteq L_{C_{11} } }^i \buildrel \mathrm{def} \over = \mathop \bigcup \nolimits _{K_k \in K_\mathrm{min,C_{10} \subseteq L_{C_{11}},\not \subseteq {C}_{21}}^{+},{\mathrm{k}\le \mathrm{i}}} K_k \), \(K_{U,C_{10}\subseteq L_{C_{11}},i} \buildrel \mathrm{def} \over = \left\{ {{\begin{array}{ll} {K_{U,C_{10} \subseteq L_{C_{11} } }^{i-1} \backslash K_i ,\mathrm{if} \ i \ge 2}\\ {\varnothing , \mathrm{if} \ i=1}\\ \end{array} }} \right. \), \(K_{-,C_{10}\subseteq L_{C_{11} } ,i} \buildrel \mathrm{def} \over = \quad L_{C_{11}}\backslash (C_{10} +K_{U,C_{10}\subseteq L_{C_{11}}}^i)\) and:

Obviously, \({\mathcal F}{\mathcal S}_{\text{ C }_{10} \subseteq L_{C_{11}},\nsubseteq C_{21},}=\lfloor {L}\rfloor _{C_{-} \subseteq L_{C^+},+L_{C^*}}+\lfloor {L}\rfloor _{C_{10} \subseteq L_{C_{11}},G \not \subseteq C_{21}}\).

Obviously, \(\forall L^{\prime }\in {\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11} ,\nsubseteq C_{21},} (s_0,s_1) \subseteq {\mathcal F}{\mathcal S}(s_0,s_1),\) we have \(L \buildrel \mathrm{def} \over = h(L^{\prime })\in {\mathcal F}{\mathcal C}{\mathcal S}(s_0 , s_1), {\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11} ,\nsubseteq C_{21},} (s_0, s_1) = \sum \nolimits _{L\in {\mathcal F}{\mathcal C}{\mathcal S}(s_0, s_1)} \{[L] \cap {\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11} ,\not \subseteq C_{21},} (s_0,s_1)\}\) and \({[L]}\cap {\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11} ,\not \subseteq C_{21},} (s_0, s_1 )= \{L^{\prime } \in [L] \vert C_{10} \subseteq L^{\prime } \subseteq L_{C_{11}} , L^{\prime } \not \subseteq C_{21} \} = \{L^{\prime } \in {\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} }} \vert L^{\prime } \not \subseteq C_{21} \} = {\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11}}, \not \subseteq C_{21}} \). \(\square \)

(b) Consider \(\forall L^{\prime }\subseteq A: L^{\prime } \ne \varnothing , L^{\prime }\supseteq A, h(L^{\prime }) = L: \exists L_i \in {\mathcal G}(L^{\prime }), Cond(L_i ). \) Then, \(K_i \mathop =\limits ^{\mathrm{def}} L_i \backslash A{\in U}\) and \(U \ne \varnothing .\) For any \(K_k \mathop =\limits ^{\mathrm{def}} L_k {\backslash A\in U:} L_k \in {\mathcal G}(L^{\prime }) \subseteq {\mathcal G}(L), Cond(L_k)\), then \(L_k \in {\mathcal G}(L)\) and \(K_k {\in V,}\) thus, \( U\subseteq V\). Due to \(\varnothing {\subset U} \ \subseteq V,U\) and V is finite, then \(Minimal(V)\ne \varnothing , Minimal(U) \ne \varnothing \). Consider \(\forall K_j {\in Minimal(U),}\) then \(L^{\prime }\supseteq A\cup L_j = A+K_j \) and \(K_j {\in Minimal(V).}\) Indeed, assume \(K_j \notin Minimal(V),\) then \(\exists K_k \mathop =\limits ^{\mathrm{def}} L_k \backslash A \in Minimal(V): K_k {\subset }K_j , L_k \ {\in } \ {\mathcal G}(L)\) and \(Cond(L_k )\); since \(L_k \subseteq A+K_k \subseteq A+K_j \subseteq L^{\prime }\subseteq L,\) so \(L = h(L_k ) = h(L^{\prime }), L_k \in {\mathcal G}(L^{\prime }), K_k \in U\cap Minimal(V),\) thus \(K_k \in Minimal(U)\): it is a contradiction of the facts \(K_j \in Minimal(U)\) and \(K_k \subset K_j !\) Hence, \(Minimal(U) \subseteq Minimal(V)\). We can always assume that i is the minimum index in all ones of \(K_i\) in Minimal(U).

(c) If \(L^{\prime } = A+K_i +K_i^{\prime } +K_i^{\sim },\) where \(K_i \in K_\mathrm{min} , K_i^{\prime } \subseteq K_{U,i} , K_i^{\sim } \subseteq K_{-,i} ,\) then, since \(K_i \subseteq L_B , K_{-,i} \subseteq L_B , \)so \(K_{U,i} \subseteq K_U^{i-1} \subseteq L_B .\) Hence, \( A \subseteq L^{\prime }\subseteq L_B .\) If \(K_i \buildrel \mathrm{def} \over = L_i \backslash A,\) with \(L_i \in {\mathcal G}(L),\) then \(\varnothing \subset L_i \subseteq A+K_i \subseteq L^{\prime }\subseteq L_B \subseteq L, \) so \( L^{\prime } \ne \varnothing , L = h(L^{\prime }) = h(L_i ) = h(L_B ) \) and \(L^{\prime }\in FS_{A \subseteq L_B }.\)

\(\square \)

\(+ ``(a). \Rightarrow \) và b. \(\subseteq ^{\prime \prime }: \forall { L^{\prime }\in }{\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11} ,\nsubseteq C_{21} ,} (s_0 ,s_1 ),{ L^{\prime }\in }{\mathcal F}{\mathcal S}(s_0 ,s_1 ), C_{10} \subseteq L^{\prime }\subseteq C_{11} {, L^{\prime } \not \subseteq }C_{21} , \mathrm{call} \ { L=h(L^{\prime }), }L_i {\in }{\mathcal G}(L^{\prime })\subseteq {\mathcal G}(L)\) (by Lemma 1a(i)) then \({ supp(L) =} supp(L^{\prime })\in [s_0 ,s_1 ], C_{10} \subseteq L^{\prime } \subseteq L_{C_{11} } , \varnothing \subset L_i \subseteq L_i \cup C_{10} \subseteq L^{\prime }\subseteq L_{C_{11} } \subseteq L \) and \(L = h(L_i ) = h(L^{\prime }) = h(L_{C_{11}} )\). Due to \(\varnothing \subset L^{\prime }\backslash C_{21} = L^{\prime }\backslash L_{C_{21} } \subseteq L_{C_{11}} \backslash C_{21} , \) then \({L^{\prime }\in } {\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11}} ,\nsubseteq C_{21}} ,{ L\in }{\mathcal F}{\mathcal C}{\mathcal S}(s_0, s_1), C_{10} \subseteq L_{C_{11}} \nsubseteq C_{21}\) and \(L_i \in {\mathcal G}_{C_{11} } (L) \ne \varnothing , \) i.e. \({L\in }{\mathcal F}{\mathcal C}{\mathcal S}_{C_{10} \subseteq C_{11} ,\nsubseteq C_{21} ,} (s_0 ,s_1 ) \ne \varnothing .\)

“\({(a).\Leftarrow \text {''}: } \ \forall {L\in }{\mathcal F}{\mathcal C}{\mathcal S}_{C_{10} \subseteq C_{11} ,\nsubseteq C_{21} ,} (s_0,s_1), C_{10} \subseteq L_{C_{11} } \nsubseteq C_{21} , {\mathcal G}_{C_{11} } (L) \ne \varnothing , \) let \(L_i \in {\mathcal G}_{C_{11} } (L)\subseteq {\mathcal G}(L): L_i \subseteq C_{11} \) and \( L^{\prime } \buildrel \mathrm{def} \over = (C_{10} {\cup L_i )\cup {\{}a{\}}}\), where \({a\in }L_{C_{11}}{\backslash } C_{21} \ne \varnothing \). Then, \( {a\in L^{\prime }\backslash } C_{21} \ne \varnothing \), so \(C_{10} \subseteq L^{\prime } \subseteq L_{C_{11} } \subseteq C_{11} {, L^{\prime } \not \subseteq }C_{21} , \varnothing \ {\subset } \ L_i \subseteq L^{\prime }\subseteq L_{C_{11} } \subseteq L\) and \( L = h(L_i) = h(L^{\prime }) = h(L_{C_{11} }), supp(L^{\prime }) = supp(L)\in [s_0 ,s_1 ], L^{\prime }\in {\mathcal F}{\mathcal S}(s_0 ,s_1 ). \) Thus, \(L^{\prime }\in {\mathcal F}{\mathcal S}_{C_{10} \subseteq C_{11} ,\nsubseteq C_{21} } (s_0 ,s_1 ) \ne \varnothing \).

\({+ ``b. \supseteq }^{\prime \prime }\): It is a consequence of Proposition 2 and \({\mathcal F}{\mathcal C}{\mathcal S}_{C_{10} \subseteq C_{11} ,\nsubseteq C_{21},}(s_0,s_1) \subseteq {\mathcal F}{\mathcal C}{\mathcal S}(s_0,s_1).\) \(\square \)

Note that, \({\mathcal F}{\mathcal S}_{C_{10} \subseteq {C_{11} } ,\nsubseteq C_{21} } = \lfloor {L}\rfloor _{C_{-} \subseteq L_{C^+} ,+\lfloor {L}\rfloor _{C^*}} +L_{C_{10} \subseteq {C_{11} } ,G \not \subseteq C_{21} } \). Consider \(\forall {L\in }{\mathcal F}{\mathcal C}{\mathcal S}_{C_{10} \subseteq C_{11} ,\nsubseteq C_{21} ,}(s_0 ,s_1)\).

(i) + The uniqueness in the representation of \(L^{\prime \prime }\in {\mathcal F}{\mathcal S}_{\text{ C }_{-} \subseteq L_{C^+} ,}^*\): Assume that \( L^{\prime }\) has two representations: \( { L^{\prime \prime } = C{\_}+}K_k +K_k^{\prime } +K_k^{\sim } {= C{\_}+}K_i +K_i^{\prime } +K_i^{\sim } , \) where \({ 1 \le k < i, }K_k \) and \( K_i \in K_{\mathrm{min},C_{-} \subseteq L_{C^+} } , K_i^{\prime } \subseteq K_{U,\mathrm min,C_{-}\subseteq L_{C^+} ,i} , K_i^{\sim } \subseteq K_{-,C_{-}\subseteq L_{C^+} i} , K_k^{\prime } \subseteq K_{U,C_{-}\subseteq L_{C^+},k} , K_k^{\sim } \subseteq K_{-,C_{-}\subseteq L_{C^+} ,k} \). Then, \(K_k \subseteq K_i +K_i^{\prime } +K_i^{\sim } , \) but due to \(K_k\subseteq K_{U,C_{-} \subseteq L_{C^+} }^{k} \subseteq K_{U,C_{-}\subseteq L_{C^+} }^{i} , K_i^{\sim } {\cap } K_{U,C_{-}\subseteq L_{C^+} }^i = \varnothing \),so \(K_k \cap K_i^{\sim } =\varnothing \) and \(K_k \subset K_i +K_i^{\prime }\) (the equality does not happen, because \(K_{k}\) and\( K_{i}\) are two different minimal sets in \(K_\mathrm{min,C\subseteq L_{C^+} }):\) it is a contradiction of the selection of \(\mathrm{K}_\mathrm{i}\)!

+ The uniqueness in the representation of \(L^{\prime }\in {\mathcal F}{\mathcal S}_{\text{ C }_{10} \subseteq L_{C_{11} } ,,\text{ G }\not \subseteq \text{ C }_{21} }^*\): Assume that \(L^{\prime }\) have two representations: \( L^{\prime } = C_{10} +K_k +K_k^{\prime } +K_k^{\sim } =C_{10} +K_i +K_i^{\prime } +K_i^{\sim }\), where \({M \le k < i}, K_i {\in }K_\mathrm{min,C_{10} \subseteq L_{C_{11} } ,\text{ G }\not \subseteq \text{ C }_{21}} ,\) \(K_k {\in }K_\mathrm{min,C_{10} \subseteq L_{C_{11} } ,\text{ G }\not \subseteq \text{ C }_{21} } \subseteq K_\mathrm{min,C_{10} \subseteq L_{C_{11} } ,\not \subseteq \text{ C }_{21} }^+ \), \(K_k \ne K_i \), \(K_i^{\prime } \subseteq K_{U,C_{10} \subseteq L_{C_{11} } ,\not \subseteq \text{ C }_{21} ,i} \), \(K_i^{\sim } \subseteq K_{-,C_{10} L_{C_{11} } ,\not \subseteq \text{ C }_{21} ,i} \),\(_{ }K_k^{\prime } \subseteq K_{U,C_{10}L_{C_{11} } ,\not \subseteq \text{ C }_{21} ,k} \), \(K_k^{\sim } \subseteq K_{-,C_{10} \subseteq L_{C_{11} } ,\not \subseteq \text{ C }_{21} ,k} \). Then, \(K_k \subseteq K_i +K_i^{\prime } +K_i^{\sim } \), but since \(K_k\subseteq K_{U,C_{10} \subseteq L_{C_{11} } ,\not \subseteq \text{ C }_{21} }^k \subseteq K_{U,C_{10} \subseteq L_{C_{11}} ,\not \subseteq \text{ C }_{21} }^i \), \(K_i^{\sim } \cap K_{U,C_{10} \subseteq L_{C_{11} } ,\not \subseteq \text{ C }_{21} }^i =\varnothing \), so \(K_k \cap K_i^{\sim } = \varnothing \) and \(K_k \subset K_i +K_i^{\prime }\) ((the equality does not also happen, because \(K_{k}\) and\( K_{i}\) are two different minimal sets in \(K_\mathrm{min,C_{10} \subseteq L_{C_{11} },\text{ G }\not \subseteq \text{ C }_{21}})\): it contradicts the selection of \(K_i\)!

(ii) + “\({\mathcal F}{\mathcal S}_{{C}_{10} \subseteq L_{C_{11}} ,\nsubseteq C_{21} } \subseteq {\mathcal F}{\mathcal S}_{\text{ C }_{10} \subseteq L_{C_{11} } ,\nsubseteq C_{21} }^*\)”: We will prove that \(\lfloor {L}\rfloor _{C_{-} \subseteq L_{C^+},+L_{C^*}} \subseteq {\mathcal F}{\mathcal S}_{\text{ C }_{-} \subseteq L_{C^+} ,+L_{C^*} }^*\) and \(\lfloor {L}\rfloor _{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} } \subseteq {\mathcal F}{\mathcal S}_{\text{ C }_{10} \subseteq L_{C_{11} } ,\nsubseteq C_{21} }^*\), thus, \({\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,\nsubseteq C_{21} } \subseteq {\mathcal F}{\mathcal S}_{\text{ C }_{10} \subseteq {C_{11} } ,\nsubseteq C_{21} }^*\).

. “\(\lfloor {L}\rfloor _{C_- L_{C^+} ,+L_{C^*} } \subseteq {\mathcal F}{\mathcal S}_{\text{ C }_- L_{C^+} ,+L_{C^*} }^{*}\)”: \(\forall {L^{\prime }} \ \in \ {\mathcal F}{\mathcal S}_{C_{10} \subseteq {C_{11} } ,\nsubseteq C_{21} } , \exists L_i \ \in {\mathcal G}_{C^+} (L) \subseteq {\mathcal G}(L): L_i \subseteq L^{\prime },\) then \(L^{\prime } \ne \varnothing \) and \(L^{\prime } \supseteq C_{10}, L_i \subseteq L^{\prime } \subseteq L_{C_{11} } \subseteq C_{11}, L_i \subseteq C^+ \subseteq C_{21} .\) Since \(L^{\prime }\subseteq L_{C_{11} } \), so based on \(C_{21},\) we can partition \(L'\) into disjoint subsets \({L' \buildrel \mathrm{def} \over = L^{\prime \prime }+L}^{\sim }, \) where \(C_-\subseteq { L^{\prime \prime } \buildrel \mathrm{def} \over = L^{\prime }\cap }C_{21} \subseteq L_{C_{11} } \cap C_{21} = L_{C^+} \subseteq L_{C_{21}}\) and \(C_{10} \backslash C_{21} \subseteq L^{\sim } \buildrel \mathrm{def} \over = L^{\prime }\backslash C_{21} \subseteq L_{C_{11}} \backslash C_{21} = L_{C^*}\). Moreover, due to \(L^{\prime \prime }\backslash C_{21} = \varnothing , L^{\sim } \cap C_{21} = \varnothing {, L^{\prime } \not \subseteq }L_{C_{21} } ,\) so \(\varnothing \subset L^{\prime } \backslash L_{C_{21} } = L^{\sim } \backslash L_{C_{21}} = L^{\sim }, L^{\sim } \in 2^{\left[ {\text{ C }_{10} \backslash C_{21} \subseteq L_{C^*} } \right] *}.\) We need to prove that \(L^{\prime \prime }\in {\mathcal F}{\mathcal S}_{C_{-} \subseteq L_{C^+} }^*\). Let \(K_i \buildrel \mathrm{def} \over = L_i \backslash C\_ = L_i \backslash C_{10} (\mathrm{v}\)ì \(L_i \subseteq C_{21} ), Cond(L_k ) {\buildrel \mathrm{def} \over =} (L_k \subseteq C^+),\) \(U \buildrel \mathrm{def} \over = \{K_k {\buildrel \mathrm{def} \over = }L_k \backslash C\_{\vert }L_k {\in }{\mathcal G}(L^{\prime \prime }), Cond(L_k )\}, V {\buildrel \mathrm{def} \over =} \{K_k {\buildrel \mathrm{def} \over =} L_k {\backslash }C\_{\vert }L_k \in {\mathcal G}(L), Cond(L_k )\} = \{K_k \buildrel \mathrm{def} \over =L_k {\backslash }C\_{\vert }L_k \in {\mathcal G}_{C^+} (L)\},\) then \(L_i \subseteq C\_+K_i = C\_{\cup }L_i \subseteq L^{\prime \prime } \subseteq L, h(L_i) = h(L^{\prime \prime }) =L\) and \(L_i {\in }{\mathcal G}(L^{\prime \prime })\), thus, \(K_i {\in U }\subseteq V, K_\mathrm{min,C_{-}\subseteq L_{C^+}} = Minimal(V).\) From Lemma 1b, we can always assume that i is the minimum index such that \(K_i {\in Minimal(U).}\) Then, \(K_i {\in Minimal(V) }\) và \({L^{\prime \prime } \supseteq }C\_+K_i \). We can represent \(L^{\prime \prime }\) as follows: \({L^{\prime \prime } \buildrel \mathrm{def} \over = }C\_+K_i +K_i^{\prime } +K_i^{\sim },\) where \(K_i^{\prime } \ {\buildrel \mathrm{def} \over = [L^{\prime \prime }\backslash (}C\_+K_i {)]\cap }K_{U,C_{-} \subseteq L_{C^+} }^i \subseteq K_{U,C_{-}\subseteq L_{C^+} }^i {\backslash }K_i =K_{U,C_{-}\subseteq L_{C^+} ,i} , K_i^{\sim }{\buildrel \mathrm{def} \over = [L^{\prime \prime }\backslash (}C\_+K_i )\backslash K_{U,C_{-}\subseteq L_{C^+} }^i \subseteq K_{-,C_{-}\subseteq L_{C^+} ,i}.\) Finally, assume that the condition \(^{(*)}\) is false, i.e. \(\exists K_k \equiv L_k {\backslash }C_- {\in }K_\mathrm{min,C_{-} \subseteq L_{C^+} } {: 1 \le k < i}\) and \(K_k {\subset }K_i +K_i^{\prime },\) then \(L_k {\in }{\mathcal G}_{C^+} (L) \subseteq {\mathcal G}(L), L_k \subseteq C_{-} +K_k \subseteq C_{-} +K_i +K_i^{\prime } \subseteq L^{\prime \prime } \subseteq L \) and \(L_k {\in }{\mathcal G}(L^{\prime \prime }).\) Hence, \(K_k \in U \cap Minimal(V), K_k \in Minimal(U)\) and \(k<i\): it contradicts the selection of the index i! Thus, \({ L''\in }{\mathcal F}{\mathcal S}_{C_{-} L_{C^+} }^*.\)

. \(``\lfloor {L}\rfloor _{C_{10} \subseteq L_{C_{11} } ,G\not \subseteq C_{21} } \subseteq {{\mathcal F}{\mathcal S}_{{C}_{10} \subseteq L_{C_{11} } ,G\not \subseteq C_{21}}^{*}} ^{\prime \prime }\): cxv \(\forall \) \({L^{\prime }} \in \lfloor {L}\rfloor _{{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} }},\) we have \(L^{\prime } \in {\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,\nsubseteq C_{21} } , \exists L_i \in {\mathcal G}_{C_{11} ,\nsubseteq C_{21} } (L) \subseteq G(L): L_i \subseteq L^{\prime }, \) so \( L^{\prime } \ne \varnothing , { L^{\prime } \supseteq }C_{10} , L_i \subseteq L^{\prime } \subseteq L_{C_{11} } \subseteq C_{11} , L_i \not \subseteq C_{21} \) and \((L_k {\not \subseteq L^{\prime }, } \forall L_k \in {\mathcal G}_{C^+} (L))^{(-)}. \) From Lemma 1a, we have \({h(L^{\prime }) = L}\) and \(L_i \in {\mathcal G}(L^{\prime }).\) Let \(Cond^{\prime }(L_k) \buildrel \mathrm{def} \over = (L_k {\not \subseteq }C_{21} , L_k \subseteq C_{11} ),\) \(U \buildrel \mathrm{def} \over = \{K_i \mathop =\limits ^{\mathrm{def}} L_i {\backslash }C_{10} {\vert }L_k \ {\in } \ {\mathcal G}(L^{\prime }), Cond^{\prime }(L_k )\},\) \(V \buildrel \mathrm{def} \over = \{K_i \mathop =\limits ^{\mathrm{def}} L_i {\backslash }C_{10} {\vert }L_k \ {\in } \ {\mathcal G}(L), Cond^{\prime }(L_k )\} =\{K_i \mathop =\limits ^{\mathrm{def}} L_i \backslash C_{10} \vert L_k \in {\mathcal G}_{C_{11} ,\nsubseteq C_{21} } (L)\}\). From Lemma 1b, due to \(K_i \mathop =\limits ^{\mathrm{def}} L_i \backslash C_{10} \in U,\) then \(\varnothing \ne U \subseteq V \) and we can choose the minimum index i such that \(K_i \in Minimal(U)\). Then, \({L^{\prime } \supseteq } C_{10} +K_i \) and \(K_i \in {Minimal(V) \equiv }K_\mathrm{min,C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} } \ne \varnothing \). Since \(C_{10} +K_i \subseteq L^{\prime } \subseteq L_{C_{11} } ,\) call \(L_i^{\prime \prime } \buildrel \mathrm{def} \over = L'\backslash (C_{10} +K_i ) \subseteq L_{C_{11}} {\backslash (}C_{10} +K_i ), \) so \(L^{\prime } = (C_{10} +K_i )+L_i^{\prime \prime } = C_{10} +K_i +K_i^{\prime } +K_i^{\sim }\), where \(K_i^{\prime } = L_i^{\prime \prime } \cap K_{U,C_{10} \subseteq L_{C_{11} } }^{i-1} \subseteq K_{U,C_{10} \subseteq L_{C_{11} } }^{i-1} \backslash K_i = K_{U,C_{10} \subseteq L_{C_{11} } ,i} , K_i^{\sim } = L_i^{\prime \prime } \backslash K_{U,C_{10} \subseteq L_{C_{11}} }^{i-1} \subseteq L_{C_{11}} \backslash (C_{10} +K_{U,C_{10} \subseteq L_{C_{11} } }^i)= K_{-,C_{10} \subseteq L_{C_{11}},i}\). Finally, assume that the condition \(^{(**)}\) is not true, i.e. \(\exists K_i \mathop =\limits ^{\mathrm{def}} L_i \backslash C_{10}\in K_\mathrm{min},C_{10} \subseteq L_{C_{11}}\), \(\text{ C }_{21}^+ {: 1 \le k < i }\) and \(K_k \subseteq K_i +K_i^{\prime },\) then \(L_k \in {\mathcal G}_{C_{11} } (L) \subseteq {\mathcal G}(L), L_k \subseteq C_{11} , L_k \subseteq C_{10} +K_k \subseteq C_{10} +K_i +K_i^{\prime } \subseteq L^{\prime } \subseteq L \) and \( h(L_k {) = h(L^{\prime }) = L.}\) Hence, \(L_k \in (L^{\prime })\), \(L_k \not \subseteq C_{21}\) (because if \(L_k \subseteq C_{21} ,\) then \(L_k \subseteq C^+\) and \(L_k\in {\mathcal G}_{C^+} (L):\) it contradicts the above condition \(^{(-)}\)!). Moreover, \(L_k \in {\mathcal G}_{C_{11} ,\nsubseteq C_{21} } (L)\), \(K_k\in K_\mathrm{min},C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21}\cap U\), \(K_k \in Minimal(U)\) and \( k<i: \) it is a contradiction of the selection the minimum index i such that \(K_i \in Minimal(U)!\) Thus, the condition \(^{(**)}\) in \({\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} }^*\) is true and \(\mathrm{L}\prime \in {\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} }^*.\)

+ “\({\mathcal F}{\mathcal S}_{\text{ C }_{10} \subseteq L_{C_{11} } ,\nsubseteq C_{21} ,}^*\subseteq {\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,\nsubseteq C_{21} }\)” We will prove that \({\mathcal F}{\mathcal S}_{\text{ C }_{-} \subseteq L_{C^+} ,+L_{C^*} }^*\subseteq \lfloor {L}\rfloor _{C_{-} \subseteq L_{C^+} ,+L_{C^*} } \) and \({\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} }^*\subseteq \lfloor {L}\rfloor _{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} } \), thus, \({\mathcal F}{\mathcal S}_{\text{ C }_{-} \subseteq L_{C^+},+L_{C^*}}^*\) \(\cap \) \({\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} }^*=\varnothing \) an \({\mathcal F}{\mathcal S}_{{C}_{10} \subseteq L_{C_{11}} ,\nsubseteq C_{21} ,}^*\) \({\subseteq {\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,\nsubseteq C_{21}}}\).

. “\({\mathcal F}{\mathcal S}_{\text{ C }_{-} \subseteq L_{C^+} ,+L_{C^*} }^*\subseteq \lfloor {L}\rfloor _{C_{-} \subseteq L_{C^+} ,+L_{C^*} } \)”: \(\forall L^{\prime } \buildrel \mathrm{def} \over \!=\! L^{\prime \prime }\!+L^{\sim } \in \) \({\mathcal F}{\mathcal S}_{C_{-} \subseteq L_{C^+} ,+L_{C^*}}^*{, L^{\prime \prime }\buildrel \mathrm{def} \over = }C\_+K_i +K_i^{\prime } +K_i^{\sim } {\in }{\mathcal F}{\mathcal S}_{C_{-} \subseteq L_{C^+} }^*, L^{\sim } \in 2^{\left[ {\text{ C }_{10} \backslash \nsubseteq C_{21} \subseteq L_{C^*}} \right] *}\), where \(K_i \mathop =\limits ^{\mathrm{def}} L_i \backslash C_{-} = L_i \backslash C_{10} \) (because \(L_i \in {\mathcal G}_{C^+} (L) \subseteq {\mathcal G}(L)\), \(L_i \subseteq C^+ \subseteq \nsubseteq C_{21} )\) and from Lemma 1c, \({L^{\prime \prime }\,\, \in \,\, }{\mathcal F}{\mathcal S}_{C_{-} \subseteq L_{C^+} } . \) On the other hand, since \({C}_{10} = (\ne ) + ({C}_{10} \nsubseteq C_{21} ) \subseteq L^{\prime } = L^{\sim }+L^{\prime \prime } \subseteq L_{C^*} +L_{C^+} = L_{C_{11} } \), \(L_i \subseteq C\_+K_i \subseteq L^{\prime \prime } \subseteq L^{\prime } \subseteq L_{C_{11} } \subseteq L, h(L_{C_{11} } {) = h(L^{\prime }) = h(}L_i ) = L, \varnothing \subset L^{\sim } = L^{\sim }{\backslash }C_{21} \subseteq { L^{\prime }\backslash }C_{21} , \) then \({L^{\prime } \not \subseteq } C_{21} \). Hence, \(L^{\prime }\,\, {\in }\,\, {\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,\nsubseteq C_{21} } \) and \({L'\in }L_{C_- L_{C^+} ,+L_{C^*} } .\)

.“\({\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} }^*\subseteq \lfloor {L}\rfloor _{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} } \text {''}: \forall {L^{\prime } \buildrel \mathrm{def} \over = }C_{10} +K_i +K_i^{\prime } +K_i^{\sim } {\in }{\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} }^*, K_i \mathop =\limits ^{\mathrm{def}} L_i \backslash C_{10} , L_i \in {\mathcal G}_{C_{11} ,\nsubseteq C_{21} } (L)\) and (\(K_k \not \subseteq K_i +K_i^{\prime } , \forall K_k \in K_{\mathrm{min},C_{10} \subseteq L_{C_{11} } ,\not \subseteq {C}_{21} }^+ {: 1\le k<i)}^{(**)}, \) then from Lemma 1a and c, due to \({\mathcal G}_{C_{11} ,\nsubseteq C_{21} } (L) \subseteq {\mathcal G}(L), \) we obtain \(h(L^{\prime }) = L, L^{\prime }\in {\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } } \) and \({L^{\prime }\backslash }C_{21} \supseteq L_i \backslash C_{21} \supset \varnothing \), \(L_i \subseteq K_i +C_{10} \subseteq L^{\prime }\), thus \({L^{\prime }\in }{\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11} } ,\nsubseteq C_{21} } \). To prove \(L^{\prime } \in \lfloor {L}\rfloor _{C_{10} \subseteq L_{C_{11} } ,G \not \subseteq C_{21} } , \) in addition, we need to test the condition \(^{(-)}: (L_k \not \subseteq L^{\prime }\), \(\forall L_k \,\, \in \,\, {\mathcal G}_{C^+} (L)) \) by contradiction. Assume that \(\exists L_k \,\, \in \,\,{\mathcal G}_{C^+} (L) \subseteq {\mathcal G}_{C_{11} } (L) \subseteq {\mathcal G}(L): L_k \subseteq L^{\prime } = C_{10} +K_i +K_i^{\prime } +K_i^{\sim } \subseteq L, L_k \subseteq L_{C^+} \subseteq \nsubseteq C_{21} , \) then \(L_k \in {\mathcal G}(L^{\prime })\) and \({ k \leqslant M<i }\) (from the above indexing k of \(K_k)\). Using Lemma 1b, with \({U^{\prime \prime } \buildrel \mathrm{def} \over = {\{}}K_i \mathop =\limits ^{\mathrm{def}} L_i \backslash C_{10} , L_i \,\, \in \,\, {\mathcal G}(L^{\prime }), \mathrm{Cond}(L_k){\}}\) and \(K_i \mathop =\limits ^{\mathrm{def}} L_i \backslash C_{10} = L_k \backslash C_- \in U^{\prime \prime } \ne \varnothing , U^{\prime \prime } \subseteq V, \) we can choose the minimum index k such that \(K_k \in Minimal(U^{\prime \prime }) \) and \(K_k \in Minmal(V) = K_{\mathrm{min},C_{-}\subseteq L_{C^+} } \subseteq K_{\mathrm{min},C_{10} \subseteq L_{C_{11} } ,{C}_{21} }^+.\) Since \(K_k \subseteq { L^{\prime }\backslash }C_{10} = K_i +K_i^{\prime } +K_i^{\sim } , K_k \subseteq K_{U,C_{-} \subseteq L_{C^+} }^k = K_{U,C_{10} \subseteq L_{C_{11} } }^k \subseteq K_{U,C_{10} \subseteq L_{C_{11} } }^i \) and \(K_i^{\sim }\,\, \cap \,\,K_{U,C_{10} \subseteq L_{C_{11} } }^i = \varnothing ,\) so \(K_k \,\, \cap \,\, K_i^{\sim } = \varnothing \) and \(K_k \subseteq K_i +K_i^{\prime }:\) It is a contradiction of the selection of the index i in \(^{(**)}!\) Thus, the condition \(^{(-)}\) is true.

Finally, all itemsets in \({\mathcal F}{\mathcal S}_{C_{10} \subseteq L_{C_{11}} ,\nsubseteq C_{21}}\) have a unique representation and are generated completely and distinctly by itemsets in \({\mathcal F}{\mathcal S}_{{C}_{10} \subseteq L_{C_{11}} ,\nsubseteq C_{21} }^*\). \(\square \)