# A Fast Algorithm for Three-Way Object-Oriented Concept Acquisition
## 2 Preliminaries  
In this section, we briefly review some basic notions and relevant properties of three-way object-oriented concepts in order to clearly describe the acquisition process of these concepts in next section. **Definition 1** (Formal context [1; 2]). : _A formal context \((U,V,R)\) consists of two sets \(U\) and \(V\) and a relation \(R\) between \(U\) and \(V\). The elements of set \(U\) are called objects, while those of set \(V\) are called attributes of the context. For \(x\in U\) and \(y\in V\), \((x,y)\in R\) can be written as \(xRy\), which means that object \(x\) has attribute \(y\), or that attribute \(y\) belongs to object \(x\)._  
For a formal context \((U,V,R)\), let \(R^{c}=(U\times V)\setminus R\). \((U,V,R^{c})\) is then the complement context of \((U,V,R)\). For \(x\in U\) and \(y\in V\), if \((x,y)\in R^{c}\), this can be written as \(xR^{c}y\). This means that object \(x\) does not possess attribute \(y\), or that attribute \(y\) does not belong to object \(x\). For any \(X\subseteq U\) and any \(Y\subseteq V\) on a formal context \((U,V,R)\), [PERSON] and [PERSON] also defined two operators, \(f\) and \(g\)[1,2]:  
\[f(X) =\{y\in V|\forall x\in X,xRy\} \tag{1}\] \[g(Y) =\{x\in U|\forall y\in Y,xRy\} \tag{2}\]  
The \(f\) and \(g\) operators are also called positive operators, while the two corresponding operators, \(\tilde{f}\) and \(\tilde{g}\), on the complement context \((U,V,R^{c})\) are called negative operators in three-way concept analysis [19]. The \(\tilde{f}\) and \(\tilde{g}\) operators are defined as follows:  
\[\tilde{f}(X) =\{y\in V|\forall x\in X,xR^{c}y\} \tag{3}\] \[\tilde{g}(Y) =\{x\in U|\forall y\in Y,xR^{c}y\} \tag{4}\]  
**Example 1**. : _Table 1 shows a formal context \((U_{1},V_{1},R_{1})\), while Table 2 shows the complement context \((U_{1},V_{1},R_{1}^{c})\). \(U_{1}=\{1,2,3,4,5\}\) is the object set, and \(V_{1}=\{a,b,c,d,e\}\) is the attribute set. Each row represents an object and each column represents an attribute._  
Usually, \(\square\) is called the necessity operator and \(\Diamond\) the possibility operator. For a formal context \((U,V,R)\), \(X\subseteq U\) and \(Y\subseteq V\), \(X^{\square}\) is the set consisting of all necessary attributes of \(X\), while \(Y^{\Diamond}\) is the object set that possesses at least one attribute in \(Y\). They are defined as follows [16,17]: \begin{table}
\begin{tabular}{c c c c c c} \hline  & **a** & **b** & **c** & **d** & **e** \\ \hline
2 & 1 & 0 & 1 & 0 & 0 \\
3 & 0 & 1 & 0 & 0 & 1 \\
4 & 1 & 0 & 0 & 0 & 0 \\
5 & 1 & 1 & 0 & 0 & 1 \\ \hline \end{tabular}
\end{table} 
Table 1: The formal context \((U_{1},V_{1},R_{1})\). \[X^{\square} =\{y\in V|\forall x\in U(xRy\Rightarrow x\in X)\}\] \[=\{y\in V|Ry\subseteq X\} \tag{5}\] \[Y^{\lozenge} =\{x\in U|\exists y\in V(xRy\wedge y\in Y)\}\] \[=\{x\in U|xR\cap Y\
eq\varnothing\}\] \[=\bigcup_{y\in Y}Ry\] \[=RY \tag{6}\]  
Furthermore, \(\square\) and \(\lozenge\) have the following properties [16; 17]:  
\[X_{1}\subseteq X_{2}\Rightarrow X_{1}^{\square}\subseteq X_{2}^{\square} \tag{7}\] \[A_{1}\subseteq A_{2}\Rightarrow A_{1}^{\lozenge}\subseteq A_{2 }^{\lozenge}\] (8) \[X^{\square\lozenge}\subseteq X,A\subseteq A^{\lozenge\square}\] (9) \[X^{\square} =\{y\in V|\forall x\in U(xRy\Rightarrow x\in X)\}\]0 (10) \[X^{\square} =\{y\in V|\forall x\in U(xRy\Rightarrow x\in X)\}\]1  
For the complement context \((U,V,R^{c})\), operators \(\square\) and \(\lozenge\) are called negative approximation operators as a pair. To refer to them explicitly, they are denoted by \(\square\) and \(\bar{\lozenge}\), respectively. \(\square\) and \(\bar{\lozenge}\) have the same properties as \(\square\) and \(\lozenge\); thus, we do not list them here again.