<figure><img src="image_1.png" /></figure>

HAL
open science

# The Representation of Indiscernibility Relation Using ZBDDs

Qianjin Wei, Tianlong Gu, Fengying Li, Guoyong Cai

<figure><img src="image_2.png" /></figure>

► To cite this version:

Qianjin Wei, Tianlong Gu, Fengying Li, Guoyong Cai. The Representation of Indiscernibility Relation Using ZBDDs. 7th International Conference on Intelligent Information Processing (IIP), Oct 2012, Guilin, China. pp.216-225, 10.1007/978-3-642-32891-6_28 . hal-01524971

HAL Id: hal-01524971

https://inria.hal.science/hal-01524971

Submitted on 19 May 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Representation of Indiscernibility Relation Using ZBDDs

Qianjin Wei¹, ², Tianlong Gu², Fengying Li², Guoyong Cai²

¹School of Electronic Engineering, XiDian University, Xi’an 710071

²Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004

{wei_qj, cctlgu, lfy, ccycai}@guet.edu.cn

**Abstract.** The indiscernibility relation is the basic concept in Rough set theory, a novel representation of indiscernibility relation using Zero-Suppressed BDDs is proposed in this paper. Through introducing the indiscernibility matrix and the indiscernibility graph, we put forward the encoding of the variable and give the characteristic function. Once the characteristic function is constructed, it can be represented using ZBDDs. And further, combined with an example, we analyze the effectiveness of this method. It provides a basis for deal with rough set computing.

**Keywords:** rough set; Indiscernibility relation; Zero-Suppressed BDDs

## 1 Introduction

The problem of imperfect knowledge has been tackled for a long time by philosophers, logicians and mathematicians. Recently it became also a crucial issue for computer scientists, particularly in the area of artificial intelligence. There are many approaches to the problem of how to understand and manipulate imperfect knowledge. The most successful one is, no doubt, the fuzzy set theory proposed by Zadeh. In this approach sets are defined by partial membership, in contrast to crisp membership used in classical definition of set. The theory of Rough set, proposed by Z. Pawlak in 1982, is a new mathematical tool to deal with imprecise, incomplete and inconsistent data [1]. In Rough set theory, expresses vagueness, not by means of membership, but employing a boundary region of a set. If the boundary region of a set is empty it means that the set is crisp, otherwise the set is rough. Nonempty boundary region of a set means that our knowledge about the set is not sufficient to define the set precisely. The rough set theory has become an attractive field in recent years, and has already been successful applied in many scientific and engineering fields such as machine learning and data mining, it is a key issue in artificial intelligence. The indiscernibility relation plays a crucial role in Rough set theory. Due to its importance, the different representations have been developed. Most existing are indiscernibility matrix and indiscernibility graph [8-13].
Ordered Binary Decision Diagrams, graph-based representations of Boolean functions [18], have attracted much attention because they enable us to manipulate Boolean functions efficiently in terms of time and space. There are many cases in which conventional algorithms can be significantly improved by using BDDs [17][7]. Zero-suppressed BDDs [15] are a new type of BDDs that are adapted for representing sets of combinations. It can manipulate sets of combinations more efficiently than conventional BDDs, especially when dealing with sparse combinations. A Muir, I Düntsch and G Gediga discussed rough set data representation using binary decision diagrams [5], in which, a new information system representation is presented, called BDDIS. Chen Yuming and Miao Duoqian presented searching Algorithm for Attribute Reduction based on Power Graph [6], a new knowledge representation, called power graph, is presented in those paper, therefore, searching algorithms based on power graph are also proposed. Visnja Ognjenovic, etc presents a new form of indiscernibility relation based on graph [16]. In this paper, ZBDD is used to represent the family of all equivalence classes of indiscernibility relation; it has been shown how the indiscernibility relation can be obtained by ZBDD.

# 2 Indiscernibility relation in rough sets theory

The basic concepts, notations and results related to the theory of rough set are briefly reviewed in this section, others can be found in [1-4].

## 2.1 Information Systems for Rough Set

An information system is composed of a 4-tuples as follows:

$I = \langle U, Q, V, f \rangle$

Where

U is the closed universe, a finite set of N objects {$x_1, x_2... xn$}

Q is finite attributes {$q_1, q_2... q_m$}

$V = \cup_{q \in Q} V_q$ where $V_q$ is a value of the attribute q, called the domain of attribute q.

$f: U \times Q \rightarrow V$ is the total decision function called the information function

<table><caption>**Table 1.** An information table</caption><thead><tr><th>U</th><th>a</th><th>b</th><th>c</th></tr></thead><tbody><tr><td>x<sub>1</sub></td><td>0</td><td>0</td><td>0</td></tr><tr><td>x<sub>2</sub></td><td>0</td><td>1</td><td>0</td></tr><tr><td>x<sub>3</sub></td><td>0</td><td>1</td><td>1</td></tr><tr><td>x<sub>4</sub></td><td>1</td><td>0</td><td>0</td></tr><tr><td>x<sub>5</sub></td><td>0</td><td>0</td><td>1</td></tr><tr><td>x<sub>6</sub></td><td>0</td><td>1</td><td>1</td></tr><tr><td>x<sub>7</sub></td><td>1</td><td>0</td><td>1</td></tr></tbody></table>

Such that $f(x, q) \in V_q$ for every $q \in Q$, $x \in U$. Such that $f(x, q) = v$ means that the object $x$ has the value $v$ on attribute $q$. An information table is illustrated in Table 1,
which has five attributes and seven objects, with rows representing objects and columns representing attributes.

## 2.2 Indiscernibility relation and set approximation

Let $I=\langle U, Q, V, f \rangle$ be an information system, then with any non-empty subset $P \subseteq Q$ there is an associated indiscernibility relation denoted by IND (P), it is defined as the following way: two objects $x_i$ and $x_j$ are indiscernible by the set of attributes P in Q, if $f(x_i, q) = f(x_j, q)$ for every $q \in P$, More formally:

$$ \mathrm{IND}(P) = \{ (x_i, x_j) \in U \times U \mid \forall q \in P, f(x_i, q) = f(x_j, q) \} \quad (1) $$

Where IND (P) is called the P-indiscernibility relation. If $(x_i, x_j) \in \mathrm{IND}(P)$, then objects $x_i$ and $x_j$ are indiscernible from each other by attributes from P. Obviously IND (P) is an equivalence relation. The family of all equivalence classes of IND (P) will be denoted by $U/\mathrm{IND}(P)$, an equivalence class of IND(P) containing $x$ will be denoted by $[x]_{\mathrm{IND}(P)}$.

$$ U/\mathrm{IND}(P) = \{[x]_{\mathrm{IND}(P)} \mid x \in U\} \quad (2) $$

$$ [x]_{\mathrm{IND}(P)} = \{y \in U \mid (x, y) \in \mathrm{IND}(P)\} \quad (3) $$

Given any subset of attributes P, any concept $X \subseteq U$ can be precisely characterized in terms of the two precise sets called the lower and upper approximations. The lower approximation, denoted by $\underline{PX}$, is the set of objects in $U$, which can be classified with certainty as elements in the concept X using the set of attributes P, and is defined as follows:

$$ \underline{PX} = \{ x_i \in U \mid [x_i]_{\mathrm{IND}(P)} \subseteq X \} \quad (4) $$

The upper approximation, denoted by $\overline{PX}$, is the set of elements in $U$ that can be possibly classified as elements in X, and is defined as follows:

$$ \overline{PX} = \{ x_i \in U \mid [x_i]_{\mathrm{IND}(P)} \cap X \neq \emptyset \} \quad (5) $$

For any object $x_i$ of the lower approximation of X, it is certain that it belongs to X. For any object $x_i$ of the upper approximation of X, we can only say that it may belong to X.

According to Table 1, we have the following partitions defined by attribute sets $\{a\}$, $\{b\}$, and $\{c\}$, $\{d\}$:

$$ U/\mathrm{IND}(\{a\}) = \{ \{x_1, x_2, x_3, x_5, x_6\}, \{x_4, x_7\} \} $$

$$ U/\mathrm{IND}(\{b\}) = \{ \{x_2, x_3, x_6\}, \{x_1, x_4, x_5, x_7\} \} $$

$$ U/\mathrm{IND}(\{c\}) = \{ \{x_1, x_2, x_4\}, \{x_3, x_5, x_6, x_7\} \} $$

If we have the set $\{a, b\}$ we will have:

$$ U/\mathrm{IND}(\{a,b\}) = \{ \{x_1, x_5\}, \{x_2, x_3, x_6\}, \{x_4, x_7\} \} $$

### C. Indiscernibility Matrix

Given an information table $I=\langle U, Q, V, f \rangle$, two objects are discernible if their values are different in at least one attribute, the discernibility knowledge of the information system is commonly recorded in a symmetric $|U| \times |U|$ matrix $M_i(c_{ij}(x_i, x_j))$, called the indiscernibility matrix of I. Each element $c_{ij}(x_i, x_j)$ for an object pair $(x_i, x_j) \in U \times U$ is defined as follows:

$$ c_{ij}(x_i, x_j) = \begin{cases} \{q \in Q \mid f(x_i, q) \neq f(x_j, q)\} & f(x_i) \neq f(x_j) \\ \emptyset & \text{otherwise} \end{cases} \quad (6) $$
Since $M_1(c_{ij}(x_i,x_j))$ is symmetric and $c_{ii}(x_i, x_i)=\emptyset$, For $i=1, 2... m$, we represent $M_1(c_{ij}(x_i, x_j))$ only by elements in the lower triangle of $M_1(c_{ij}(x_i, x_j))$, i.e. the $c_{ij}(x_i, x_j)$ is with $1<i<j<m$.

The physical meaning of the matrix element $c_{ij}(x_i,x_j)$ is that objects $x_i$ and $x_j$ can be distinguished by any attribute in $c_{ij}(x_i, x_j)$. In another words, $c_{ij}(x_i,x_j)$ is defined as the set of all attributes which discern object $x_i$ and $x_j$. The pair $(x_i, x_j)$ can be discerned if $c_{ij}(x_i, x_j) \neq \emptyset$. The indiscernibility matrix of Table 1 is shown Table 2, for the underlined object pair $(x_1, x_2)$, the entry $\{b, c, d, e\}$ indicates that attribute b, c, d or e discerns the two objects.

<table><caption>**Table 2.** Indiscernibility matrix for the information system in Table 1</caption><thead><tr><th></th><th>x<sub>1</sub></th><th>x<sub>2</sub></th><th>x<sub>3</sub></th><th>x<sub>4</sub></th><th>x<sub>5</sub></th><th>x<sub>6</sub></th><th>x<sub>7</sub></th></tr></thead><tbody><tr><th>x<sub>1</sub></th><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>x<sub>2</sub></th><td></td><td>{b}</td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>x<sub>3</sub></th><td></td><td>{b,c}</td><td>{c}</td><td></td><td></td><td></td><td></td></tr><tr><th>x<sub>4</sub></th><td></td><td>{a}</td><td>{a,b}</td><td>{a,b,c}</td><td></td><td></td><td></td></tr><tr><th>x<sub>5</sub></th><td></td><td>{c}</td><td>{b,c}</td><td>{b}</td><td>{a,c}</td><td></td><td></td></tr><tr><th>x<sub>6</sub></th><td></td><td>{b,c}</td><td>{c}</td><td>Ø</td><td>{a,b,c}</td><td>{b}</td><td></td></tr><tr><th>x<sub>7</sub></th><td></td><td>{a,c}</td><td>{a,b,c}</td><td>{a,b}</td><td>{c}</td><td>{a}</td><td>{a,b}</td></tr></tbody></table>

# 3 Zero-suppressed BDDS

## 3.1 Combination Sets

Sets of combinations often appear in solving combinatorial problems. The representation and manipulation of sets of combinations are important techniques for many applications. A combination on $n$ objects can be represented by an $n$ bit binary vector, $(x_1x_2...x_n)$, where each bit, $x_k \in \{0, 1\}$, expresses whether the corresponding object is included in the combination or not. A set of combinations can be represented by a set of the $n$ bit binary vectors. In other words, combination sets is a subset of the power set of $n$ objects. We can represent a combination set with a Boolean function by using $n$-input variables for each bit of the vector. If we choose any one combination vector, a Boolean function determines whether the combination is included in the set of combinations. Such Boolean functions are called characteristic functions. For example, given three elements $\{a, b, c\}$, consider the set of subsets $\{{\{a, b\}, \{a, c\}, \{c\}\}}$. If we associate each element with a binary variable having the same name, the characteristic function of the set of subsets is $f=abc'+ab'c+a'b'c$. The first minterm corresponds to the subset $\{a, b\}$, and so on. The operations of sets, such as union, intersection and difference, can be executed by logic operations on characteristic functions.

Once the characteristic function is constructed, it can be represented using a OBDD or ZBDD. The two representations of the set of subsets $\{{\{a, b\}, \{a, c\}, \{c\}\}}$ are given in Fig. 1 (a). In both diagrams, there are three paths from the root node to the $1$-terminal node, which correspond to the subsets $\{a, b\}$, $\{a, c\}$, and $\{c\}$. By using
OBDD for characteristic functions, we can manipulate sets of combinations effi-
ciently. Due to the effect of node sharing, OBDD compactly represent sets of huge
numbers of combinations. Despite the efficiency of OBDD, there is one inconven-
ience that the forms of OBDD depend on the input domains when representing sets of
combinations. This inconvenience comes from the difference in the model on default
variables. In combination sets, default variables are regarded as zero when the charac-
teristic function is true, since the irrelevant objects never appear in any combina-
tion. Unfortunately, such variables cannot be suppressed in the OBDD representation,
and many useless nodes are generated when we manipulate sparse combinations. This
is the reason why we need another type of OBDD for manipulating sets of combina-
tions.

3.2 Zero-suppressed BDDs

Zero-suppressed BDDs are a new type of BDD adapted for representing sets of com-
binations. This data structure is more efficient and simpler than usual BDDs when we
manipulate sets in combinatorial problems. They are based on the following reduction
rules:

pD-deletion rule: Delete all nodes whose 1-edge points to the 0-terminal
node, and then connect the edges to the other subgraph directly, as shown in
Fig.2

Merging rule: Share all equivalent subgraphs in the same manner as with
conventional BDDs

Notice that we do not delete the nodes whose two edges point to the same node.
The zero-suppressed deletion rule is asymmetric for the two edges, as we do not de-
lete the nodes whose 0-edge points to a 0-terminal node.

Fig.1 (b) shows the ZBDDs for the same sets of combinations shown in Fig.1 (a).
The form of ZBDDs is independent of the input domain. The ZBDDs node deletion
rule automatically suppresses the variables which never appear in any combination.
This feature is important when we manipulate sparse combination.

<figure><img src="image_4.png" /><figcaption>Fig. 1. OBDD and ZBDD for the set of subsets {{a, b}, {a, c}, {c}}</figcaption></figure>

<caption>Fig. 2. pD-deletion rule</caption>
# 4 ZBDDs representation of indiscernibility relation

## 4.1 indiscernibility graph

It has been shown how the indiscernibility relations can be obtained by a graph. The application of the indiscernibility graph enables the partitioning or the universe of objects represented by their attributes [16]. Let $I=\{U, Q, V, f\}$ be an information system, where $U=\{x_1, x_2... x_n\}$, the indiscernibility graph is a tree structure to represent the family of all equivalence classes over $U$, we call this graph IR-tree. $P \subseteq Q$ is any subsets of $Q$, nodes equally distant from root node represent all equivalence classes over $U$ for $P$. To be able to observe entire indiscernibility classes by a certain attribute, each node needs to be associated with an attribute value label$<v_{q1}, v_{q2},...,v_{qm}$>, where $v_{qm}$ is a value of the attribute $q_m \in P$.

<figure><img src="image_5.png" /><figcaption>Fig. 3. The indiscernibility graph in Table 1</figcaption></figure>

For example, the indiscernibility graph for the information system in table I is shown in Fig.3. The root node of IR-tree is $U=\{x_1, x_2, x_3, x_4, x_5, x_6, x_7\}$, the children are nodes that represent the family of all equivalence class over $U$ for attribute $\{a\}$. For the node which represents the first indiscernibility class for the attribute $\{a\}$( $x_1, x_2, x_3, x_5, x_6,<0>$), its child nodes are equivalence classes for the attribute $\{a,b\}$, and so on. The leaf nodes represent indiscernibility relation classes for $Q=\{a,b,c\}$.

## 4.2 Zero-suppressed BDDs of indiscernibility relation

Let $I=\{U, Q, V, f\}$ be an information system, where $U=\{x_1, x_2... x_n\}$, $Q=\{q_1, q_2... q_m\}$. By formula (1), for any attribute $q \in Q$, there is an indiscernibility relation $IND(\{q\})$. The equivalence class $[x_i]_{IND(\{q_i\})}$ of any object $x_i \in U$ consists of all objects $x_j \in U$ such that $(x_i, x_j) \in IND(\{q\})$. In other words, an equivalence relation induces a partitioning of the universe $U$, the partitions can be used to build new subsets of the universe, a subset of $k$ objects can be represented by an $k$-bit binary vector, $[x_1, x_2... x_k]$, in which 1-compent $(x_i)$ means that the object $x_i$ is included in the subset and 0-compent $(\overline{x_i})$ means that the object $x_i$ is not included in the subset. For the information system in table 1, the ZBDDs of indiscernibility relation for attribute $\{a\}, \{b\}, \{c\}$ is given in Fig.4.
<figure><img src="image_6.png" /><figcaption>Fig. 4. ZBDDs of indiscernibility relation for attribute {a}, {b}, {c} in Table 1</figcaption></figure>

On the foundation of research above, the crucial problem is to create unique ZBDDs of indiscernibility relation for all subsets of attributes Q, this can be done by the following way. We can encode the attributes with m-bit binary vector [q₁ q₂... qₘ], where each bit, qₖ ∈ {0, 1}, expresses whether or not the attribute is included in the combination. Consider R⊆Q, the equivalence class of the equivalence relation of IND(R) can be represented by m+n-bit binary vector[q₁ q₂... qₘ x₁, x₂...xₖ]. We obtain the characteristic function of indiscernibility relation f (abc x₁x₂x₃x₄x₅x₆x₇) as follows:

$$f(abc x_1 x_2 x_3 x_4 x_5 x_6 x_7) = \begin{cases} 1 & \text{if } X \in \text{U/IND}(P) \text{ where [abc] corresponding to subset P of attributes, } [x_1 x_2 x_3 x_4 x_5 x_6 x_7] \text{ corresponding to subset X of objects} \\ 0 & \text{otherwise} \end{cases}$$

<table><caption>Table 3. characteristic function for the information system in Table 1</caption><thead><tr><th>abc</th><th>x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>x<sub>4</sub>x<sub>5</sub>x<sub>6</sub>x<sub>7</sub></th><th>f</th><th>abc</th><th>x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>x<sub>4</sub>x<sub>5</sub>x<sub>6</sub>x<sub>7</sub></th><th>f</th></tr></thead><tbody><tr><td>001</td><td>0 010111</td><td>1</td><td>101</td><td>0001000</td><td>1</td></tr><tr><td>001</td><td>1101000</td><td>1</td><td>101</td><td>0000001</td><td>1</td></tr><tr><td>010</td><td>0110010</td><td>1</td><td>110</td><td>1000100</td><td>1</td></tr><tr><td>010</td><td>1001101</td><td>1</td><td>110</td><td>0110010</td><td>1</td></tr><tr><td>011</td><td>1001000</td><td>1</td><td>110</td><td>0001001</td><td>1</td></tr><tr><td>011</td><td>0100000</td><td>1</td><td>111</td><td>1000000</td><td>1</td></tr><tr><td>011</td><td>0010010</td><td>1</td><td>111</td><td>0100000</td><td>1</td></tr><tr><td>011</td><td>0000101</td><td>1</td><td>111</td><td>0010010</td><td>1</td></tr><tr><td>100</td><td>1110110</td><td>1</td><td>111</td><td>0001000</td><td>1</td></tr><tr><td>100</td><td>0001001</td><td>1</td><td>111</td><td>0000100</td><td>1</td></tr><tr><td>101</td><td>1100000</td><td>1</td><td>111</td><td>0000001</td><td>1</td></tr><tr><td>101</td><td>0010110</td><td>1</td><td></td><td></td><td></td></tr></tbody></table>

For example, Based on the information table in Table 1, to subset{a,b}, U/IND({a,b}) = {{x₁, x₅}, {x₂, x₃, x₆}, {x₄, x₇}}, we can represent it using three vec-
tor:[1101000100],[1100110010]and [1100001001],we obtained the characteristic function as Table 3

Once the characteristic function is constructed, it can be represented using a ZBDDs, the ZBDDs of $f$ is shown in Fig. 5.

<figure><img src="image_7.png" /><figcaption>Fig. 5. ZBDDs of indiscernibility relation for information table in Table 1</figcaption></figure>

# 5 ZBDDs Of indiscernibility relation and state space

For evaluating the ZBDD node deletion, it can be proved that the upper bound on the size of the ZBDDs is the total number of elements appearing in all subsets of a set. Meanwhile, the upper bound on the size of the ZBDDs is given by the number of subsets multiplied by the number of all elements that can appear in them. This shows that ZBDDs should be much more compact when representing sets of subsets. The above theoretical upper bound on the ZBDDs size is rarely reached, this means that ZBDDs are particularly effective for representing sets of sparse combinations.

# 6 Conclusions

The indiscernibility relation is the mathematical basis of the Rough set theory; indiscernibility matrix is a widely accepted representation for it. In this paper, we gave a new representation of indiscernibility relation based on ZBDDs. Through introducing the method by a graph, we put forward the new method by the data structure of Zero-Suppressed BDDs. Then, the encoding variable and the characteristic functions have been introduced, and further, the implementation steps which construct ZBDDs of
indiscernibility relation is presented. At the same time, combined with ZBDDS and concrete example we analyze the effective of this method. the results is shown in Table 4.

<table><caption>**Table 4.** Storage efficiency comparison of ZBDDs with discernibility matrix</caption><thead><tr><th rowspan="2"></th><th rowspan="2">|U|</th><th rowspan="2">|Q|</th><th colspan="2">Size(KB)</th></tr><tr><th>discernibility matrix</th><th>ZBDDs</th></tr></thead><tbody><tr><td>1</td><td>7</td><td>5</td><td>0.19</td><td>0.16</td></tr><tr><td>2</td><td>50</td><td>5</td><td>9.76</td><td>6.89</td></tr><tr><td>3</td><td>80</td><td>6</td><td>28.58</td><td>16.86</td></tr><tr><td>4</td><td>100</td><td>7</td><td>53.67</td><td>29.38</td></tr><tr><td>5</td><td>100</td><td>9</td><td>71.23</td><td>37.59</td></tr><tr><td>6</td><td>150</td><td>10</td><td>175.78</td><td>108.62</td></tr><tr><td>7</td><td>150</td><td>12</td><td>202.56</td><td>118.51</td></tr><tr><td>8</td><td>200</td><td>10</td><td>299.34</td><td>151.12</td></tr><tr><td>9</td><td>400</td><td>7</td><td>872.69</td><td>396.21</td></tr><tr><td>10</td><td>500</td><td>11</td><td>2142.76</td><td>869.95</td></tr></tbody></table>

**Acknowledgment**

This work is supported by the National Natural Science Foundation of China (No.60963010, 60903079, 61063039) and the Natural Science Foundation of Guangxi Province (No. 2012GXNSFAA053220)

**References**

1. Pawlak Z. Rough sets [J]. International Journal of Information and Computer Science, vol.11, no.5, pp.341-356, 1982.

2. Skowron A, Rauszer. The discernibility matrices and functions in information systems, in: R. Slowinski (Ed.), Intelligent Decision Support-handbook of Applications and Advances of the Rough Sets Theory. Dordrecht: Kluwer Academic Publishers, pp.331-362, 1992.

3. Pawlak Z. Rough set approach to multi-attribute decision analysis [J]. European Journal of Operational Research, vol.72, no.3, pp.443-459, 1994.

4. Pawlak Z, Skowron A. Rudiments of rough set [J]. Information Sciences, vol.177, no.1, pp. 3-27, 2007.

5. A Muir, I Düntsch, G Gediga. Rough set data representation using binary decision diagrams [J]. Computational Sciences, vol.98, no.1, pp.197-211, 2004.

6. Chen Yuming, Miao Duoqian. Searching Algorithm for Attribute Reduction based on Power Graph [J]. Chinese Journal of Computers, vol.32, no.8, pp.1486-1492, 2009.

7. Tianlong Gu, Zhoubo Xu, Zhifei Yang. Symbolic OBDD representations for mechanical assembly sequences [J]. Computer-Aided Design, vol.40, pp.411-421, 2008.
8. YiYu Yao, Yan Zhao, and Jue Wang, On Reduct Construction Algorithms, Proceedings of the First International Conference on Rough Sets and Knowledge Technologies, Chongqing, China, pp.297-304, 2006.

9. Yiyu Yao, Yan Zhao. Discernibility matrix Simplification for constructing attribute ruducts[J]. Information Sciences, vol.179, no.7, pp. 867-882, 2009.

10. K.Thangavel, A. Pethalakshmi. Dimensionality reduction based on rough set theory: A review
[J]. Applied Soft Computing, no.9, pp. 1-12, 2009.

11. Hu X H, Cercone N. Learning in relational databases: A rough set approach [J]. Computational Intelligence, vol.11, no.2, pp.323-337, 1995.

12. Ye Dongyi, Chen Zhaojiong. A new discernibility matrix and the computation of a core [J]. Acta Electronica Sinica, vol.30no.7, pp.1086-1088, 2002.

13. Wang Guoyin. Calculation methods for core attributes of decision table [J]. Chinese Journal of Computer, vol.26, no. 5, pp. 611-615, 2003.

14. Gu Tianlong, Xu Zhoubo. Ordered binary decision diagram and its application [M]. Beijing: Science Press, pp.22-57, 2009.

15. S.Minato. Zero-suppressed BDDS for set manipulation in combinatorial problems [J]. Proceeding of 30th ACM/IEEE Design automation Conference: 272-277

16. Visnja Ognjenovic, Vladimir Brtka, Martin Jovanovic, Eleonora Brtka, Ivana Berkovic. The Representation of Indiscernibility Relation by Graph [J]. Proceeding of 9th IEEE International Symposium on Intelligent systems and Informatics:91-94

17. Y. Matsunaga and M. Fujita. Multi-level Logic Optimization Using Binary Decision Diagrams[J]. IEEE International Conference on Computer Aided Design'89, Santa Clara, November 1989

18. Bryant R E. Graph-based algorithms for Boolean function manipulation [J]. IEEE Transactions on Computers, vol.35, no. 8, pp.677-691, 1986