# A Fast Algorithm for Three-Way Object-Oriented Concept Acquisition
## 4 Algorithm Description and Time Complexity
### Algorithm Description  
The pseudo-code description of our proposed 3 WOC algorithm is as follows:  
Algorithm 1 is a structured algorithm. Lines 2 to 5 are used to generate the basic OEO-concepts, i.e., \(B_{OEO}\) (Definition 4). By Proposition 3, \(C_{OEO}^{1}\) was constructed. Lines 6 to 16 are then used to iteratively construct \(C^{2}_{OEO},C^{3}_{OEO},\ldots,C^{|U|}_{OEO}\). Lines 7 to 16 implement the function \(\varphi\) (Definition 9). Finally, all OEO-concepts are constructed and collected (line 17). The computational process of the 3 WOC algorithm involves a large number of search and union operations, i.e., the functions find() and M(). The hash key is not only used to improve the efficiency of searching for a concept in \(L\) but also to improve the efficiency of union operations by directly performing bitwise operations with their hash values in place of the union operations on the set. The hash function \(h()\), which maps the extent of an OEO-concept to a unique value, is defined as follows:  
**Definition 10** (Function h). : _Given a formal context \((U,V,R)\), we can provide a linear order on the object set \(U\), i.e., \(U=\{x_{1},x_{2},x_{3},\ldots,x_{|U|}\}\). Then, each object \(x_{i}\in U\), \(1\leq i\leq|U|\), has its ordered position \(i\) in \(U\). The function \(h\) is a mapping from an object set to a natural number, i.e., \(\mathcal{P}(U)\to N\):_  
\[h(X)=\sum_{x_{i}\in X}2^{i-1} \tag{25}\]  
_where \(X=\{x_{i},x_{m},\ldots,x_{j}\}\subseteq U\), \(1\leq i\leq m\leq\cdots\leq j\leq|U|\)._  
```
Input:\((U,V,R)\), \((U,V,R^{c})\); Output:\(L\);//OEOL(\(U,V,R\))
1\(L.C^{0}_{OEO}\leftarrow(\varnothing,(\varnothing^{\square},\varnothing^{ \square}))\)
2 for\(\forall a_{j},a_{h}\in V\)do//getsingle-attribute concepts
3\(C_{s}\leftarrow(g(a_{j}),a_{j}),C^{s}_{s}\leftarrow(g(a_{h}),a_{h})\)
4 for\(\forall(X,a_{j})\in C_{s}\cup C^{s}_{s}\)do//get\(B_{OEO}\)and\(C^{1}_{OEO}\)
5\(L.C^{|X|}_{OEO}\leftarrow\texttt{h}\left(X\right)\), \(\lambda((X,a_{i}))\)
6 for\(k=2\)to\(|U|\)do//get\(C^{2}_{OEO},\ldots,C^{|U|}_{OEO}\)
7 for\(\forall c_{1}\in\textit{List}.C^{k-1}_{OEO}\)do
8 for\(j=1\)to\(k-1\)do
9 for\(\forall c_{2}\in\textit{List}.C^{j}_{OEO}\)do
10\((X_{3},(Y_{3},Z_{3}))\)=\((c_{1},c_{2})\)
11\(key=\texttt{h}(X_{3})\)
12\((X_{4},(Y_{4},Z_{4}))=\texttt{L.find}\left(key\right)\)
13 if\((X_{4},(Y_{4},Z_{4}))\
ot\rightarrow\)NULLthen
14 update\((X_{4},(Y_{3}\cup Y_{4},Z_{3}\cup Z_{4}))\)
15
16 else
17\(L.C^{|X_{3}|}_{OEO}\leftarrow\)key, \((X_{3},(Y_{3},Z_{3}))\)
18
19 return\(L\)
```  
**Algorithm 1**3 WOC  
Due to the correspondence relationship between the hash value and the extent of a concept, the time complexity of \(Find(key)\) in line 12 is \(\mathcal{O}(1)\). Furthermore, we can obtain the extent that is composed of objects from the hash value by using the function \(h^{\prime}\):  
**Definition 11** (Function \(h^{\prime}\)). : _Function \(h^{\prime}\): \(N\to P(U)\)_  
\[h^{\prime}(key)=\{x_{i}|x_{i}\in U,2^{i-1}\text{ AND }key\
eq 0\} \tag{26}\]_where AND is the bitwise AND operation on the binary representation of two natural numbers._  
For a given formal context \((U,V,R)\), each \(X\subseteq U\) corresponds to a hash key \(h(X)\) based on the above functions, \(h\) and \(h^{\prime}\). Let \(KEY\) represent all hash values from \(P(U)\), i.e., \(KEY=\{h(X)|\forall X\in\mathcal{P}(U)\}\). Thus, \(|KEY|=2^{|U|}\). We can consider \(<\mathcal{P}(U),\cup>\) and \(<KEY,OR>\) as two algebraic systems, where \(OR\) is the bitwise \(OR\) operation on the binary representation of two natural numbers. They are isomorphic. Moreover, the proof is given in Proposition 8. Proposition 8: _The algebraic systems \(<\mathcal{P}(U),\cup>\) and \(<KEY,\ OR>\) are isomorphic._  
Proof. :
1. \(KEY\) is the non-empty set of natural numbers ranging from \(0\) to \(2^{|U|}-1\). Thus, \(|KEY|\) = \(|\mathcal{P}(U)|\). 2. For any \(X\in\mathcal{P}(U)\), there is an \(n\in KEY\) such that \(h(X)=n\). Thus, the function \(h\) is an injection.