# A Fast Algorithm for Three-Way Object-Oriented Concept Acquisition
## 2 Preliminaries
However, the new pair derived from the merge operation may be not an OEO-concept. Thus, we introduced the definitions of the candidate k-granularity OEO-concept. **Definition 7** (Candidate k-granularity OEO-concept). : _For a formal context (U, V, R), \(c_{1}\) and \(c_{2}\) are any two OEO-concepts, and the pair obtained by \(M(c_{1},c_{2})\) is called the candidate OEO-concept. If \(|Ext(M(c_{1},c_{2}))|=k\), the pair can be called the candidate k-granularity OEO-concept and is denoted by \(c_{Candi}^{k}\)._  
For a formal context (U, V, R), the set of all candidate k-granularity concepts is denoted by \(C_{Candi}^{k}\), i.e.,  
\[=\{y\in V|Ry\subseteq X\} \tag{5}\]1 \[=\{y\in V|Ry\subseteq X\} \tag{5}\]2  
For any \(c\in C_{Candi}^{k}\), regardless of whether \(c\) is an OEO-concept or not, its extent part, i.e., \(Ext(c)\), must be the extent of a certain OEO-concept based on the definition of the supremum of two OEO-concepts (Equation (16)) and merge operation (Definition 6). Does the set of all candidate k-granularity concepts \(C_{Candi}^{k}\) include all extents of all k-granularity OEO-concepts \(C_{OEO}^{k}\), i.e., \(Ext(C_{Candi}^{k})=Ext(C_{OEO}^{k})\)? We answer this question by following proposition. **Proposition 4**. : _For a formal context (U, V, R), \(c_{1}\) and \(c_{2}\) are OEO-concepts. If \(c_{2}\) is an immediate sub-concept of \(c_{1}\), i.e., \(c_{2}<c_{1}\), then there must exist an OEO-concept \(c_{3}\) such that \(c_{3}\leq c_{1}\) and \(Ext(M(c_{2},c_{3}))=Ext(c_{1})\)._  
Proof. : Assume that \(c_{1}=(X_{1},(Y_{1},Z_{1}))\) and \(c_{2}=(X_{2},(Y_{2},Z_{2}))\). Because \(c_{2}<c_{1}\), there must at least exist an object \(x\in X_{1}\setminus X_{2}\). 1. If \(X_{1}^{\square}\cap f(x)\
eq\emptyset\), we obtain \(g(X_{1}^{\square}\cap f(x))\subseteq X_{1}\). Thus, let \(X_{3}=g(X_{1}^{\square}\cap f(x))\). Based on Proposition 1, let \(c_{3}=(X_{3}^{\square}\cup X_{3}^{\square},(X_{3}^{\square},X_{3}^{\square}))\); thus, it is an OEO-concept. According to the properties of \(\square\) and \(\lozenge\) (Equation (9)), \(X_{3}^{\square}\cup X_{3}^{\square}\subseteq X_{3}\cup X_{3}\subseteq X_{1}\). Thus, \(c_{3}\leq c_{1}\). Furthermore, according to the properties of OEO-concept lattices and the definition of supremum (Equation (16)), we obtain \(c_{2}\lor c_{3}=c_{1}\). Hence, \(Ext(M(c_{2},c_{3}))=Ext(c_{1})\). 2. If \(X_{1}^{\square}\cap f(x)=\emptyset\), we get \(x\
ot\in X_{1}^{\square}\lozenge\). Thus, \(X_{1}^{\square}\cap\overline{f}(x)\
eq\emptyset\). We thus let \(X_{3}=\overline{g}(X_{1}^{\square}\cap\overline{f}(x))\). Similarly, we can get \(c_{3}\) and \(Ext(M(c_{2},c_{3}))=Ext(c_{1})\). Based on (1) and (2), the proposition has been proven. According to Proposition 4, if \(c_{3}<c_{1}\), we can get \(|Ext(c_{3})|<|Ext(c_{1})|\) and \(M(c_{2},c_{3})\in C_{Candi}^{[Ext(c_{1})]}\). However, if \(c_{3}=c_{1}\), \(M(c_{2},c_{3})\
otin C_{Candi}^{[Ext(c_{1})]}\) owing to the definition of \(C_{Candi}^{k}\) (Equation (22)). However, if \(c_{3}=c_{1}\), we can obtain a further conclusion based on Proposition 4. We state it as the following proposition:  
**Proposition 5**. : _For a formal context (U, V, R), \(c_{1}=(X_{1},(Y_{1},Z_{1}))\) and \(c_{2}=(X_{2},(Y_{2},Z_{2}))\) are OEO-concepts, such that \(c_{2}<c_{1}\) and \(x\in X_{1}\setminus X_{2}\). If \(g(X_{1}^{\square}\cap f(x))=X_{1}\) or \(\overline{g}(X_{1}^{\square}\cap\overline{f}(x))=X_{1}\), then \(c_{1}\in B_{OEO}\)._  
Proof. : If \(g(X_{1}^{\square}\cap f(x))=X_{1}\) and \(\forall a\in X_{1}^{\square}\cap f(x)\), we can get \(g(a)\supseteq X_{1}\) based on the properties of operator \(g\). On the contrary, because \(a\) is a necessary attribute, we get \(g(a)\subseteq X_{1}\). Thus, it can be concluded that \(g(a)=X_{1}\). Furthermore, according to Definitions 2 and 4, we get \((X_{1},a)\in C_{s}\) and \(c_{1}\in B_{OEO}\). The same conclusion can be obtained for the case where \(\overline{g}(X_{1}^{\square}\cap\overline{f}(x))=X_{1}\). We omit its proof.