Sub-base local reduct in a family of sub-bases

1.   Introduction

Rough set theory, proposed by Pawlak ^[1], provides an approach to uncertainty management. In ^[2], the theoretical relationships connecting rough set theory and belief function theory were investigated, and their applications in knowledge representation and machine learning were researched. Covering rough sets ^[3], generalizations of the classical rough sets, have been proved to be suitable for discussing covering information systems. As a significant problem, the reduct problem has captured considerable attention of numerous scholars. Many methods were provided to find reducts of covering rough sets ^[4,5,6,7,8]. In addition, the invariant of separation in covering approximation spaces was concerned in ^[9].

Topology is a useful tool for investigating rough set theory and its applications. The inter-dependencies of topology and rough set theory were emphasized in ^[10]. The object of general topology is to study topological properties, namely, invariants of homeomorphism ^[11]. In the light of the properties of the topological rough membership function, sub-base reducts in a family of sub-bases were defined in ^[12]. To further research sub-base reducts in a family of sub-bases from the point of view of general topology, the concept of a minimal family of sub-bases was presented in ^[13]. By showing the relationship between reducts in covering information systems and minimal families of sub-bases, ^[13] provided an approach to deriving a minimal family of sub-bases. Moreover, minimal bases and minimal sub-bases were considered in ^[14,15].

It is not hard to see that the above-cited works are focused on sub-base reducts on a given universal set. But some elements in the given universal set may be not important for specific problems. Motivated by that, this paper intents to discuss sub-base local reducts in a family of sub-bases, which has not been considered in the existing references. The main contributions are twofold. (i) The properties of sub-base local reducts in a family of sub-bases are investigated. (ii) The approach to finding sub-base local reducts in a family of sub-bases is provided, along with an algorithm for achieving it.

The remainder of this paper is organized as follows. Section 2 gives some basic information about sub-base local reducts. Section 3 illustrates how to obtain sub-base local reducts according to Boolean matrices. Section 4 has some concluding remarks.

2.   Sub-base local reduct

Suppose $\mathscr{S}_{i}$ is a sub-base for finite topological space $(X, \tau_{i})$ for $i = 1, 2, \cdots, n$, $\Delta = \{\mathscr{S}_{1}, \mathscr{S}_{2}, \cdots, \mathscr{S}_{n}\}$, and $\mathscr{S}_{\Delta} = \bigwedge_{i = 1}^{n}\mathscr{S}_{i} = \{\bigcap_{i = 1}^{n}S_{i}|S_{i}\in\mathscr{S}_{i}, i = 1, 2\cdots, n\}$. Then $\mathscr{S}_{\Delta}$ is a sub-base for a topology $\tau_{\Delta}$ of finite set $X$. Suppose $\mathscr{P}$ is a family of subsets of $X$. A minimal set containing $x$ with respect to $\mathscr{P}$ is denoted by $N_{\mathscr{P}}(x) = \bigcap\{U|x\in U\in\mathscr{P}\}$.

Under the premise of keeping topology unchanged, the sub-base reduct of a family of sub-bases is defined according to the unique open neighborhood in ^[12,13]. However, one may concern sub-base reducts related to several open sets. Hence, the concept of the sub-base local reduct is provided.

Definition 2.1. Let $\mathscr{S}_{i}$ be a sub-base for finite topological space $(X, \tau_{i})$ for $i = 1, 2, \ldots, n$ and $\Delta = \{\mathscr{S}_{1}, \mathscr{S}_{2}, \ldots, \mathscr{S}_{n}\}$. Suppose $\mathscr{F} = \{F|F\in\mathscr{S}_{\Delta}\}$. $\Delta_{1}\subset\Delta$ is called a sub-base local consistent set with respect to $\mathscr{F}$ of $\Delta$ if $\mathscr{F}\subset\mathscr{S}_{\Delta}$. If $\Delta$ is a sub-base local consistent set with respect to $\mathscr{F}$ of $\Delta$, and for any proper subset $\Delta_{2}$ of $\Delta_{1}$, $\mathscr{F}\subset\mathscr{S}_{\Delta}$, then $\Delta_{1}$ is called a sub-base local reduct with respect to $\mathscr{F}$ of $\Delta$.

Remark 2.1. Compared with the local reduct discussed in rough set theory, the sub-base local reduct in a family of sub-bases also focuses on a subset $A$ of the given universal set $X$. Thus, the sub-base local reduct in a family of sub-bases is consistent with the local reduct discussed in rough set theory. When discussing the sub-base local reduct in a family of sub-bases, subset $A$ is obtained via the union of those concerned open sets. But considering the local reduct in rough set theory, subset $A$ is determined according to elements that are indispensable for certain decision classes.

The sub-base local discernibility matrix is defined in the following.

Definition 2.2. Let $\mathscr{S}_{i}$ be a sub-base for finite topological space $(X, \tau_{i})$ for $i = 1, 2, \ldots, n$ and $\Delta = \{\mathscr{S}_{1}, \mathscr{S}_{2}, \ldots, \mathscr{S}_{n}\}$. Suppose $\mathscr{F} = \{F|F\in\mathscr{S}_{\Delta}\}$. The sub-base local discernibility matrix with respect to $\mathscr{F}$ of $\Delta$ is denoted by $\mathcal{D}_{\mathscr{F}}(\Delta) = \{\mathcal{D}(x, y)|x, y\in X\}$, where

(1) if there exists $F\in\mathscr{F}$ such that $x\in F$, but $y\not\in F$, then $\mathcal{D}(x, y) = \{\mathscr{S}\in\Delta|y\not\in N_{\mathscr{S}}(x)\}$.

(2) Otherwise, $\mathcal{D}(x, y) = \varnothing$.

Using the sub-base local discernibility matrix, a result of the sub-base local consistent set is presented.

Theorem 2.1. Let $\mathscr{S}_{i}$ be a sub-base for finite topological space $(X, \tau_{i})$ for $i = 1, 2, \ldots, n$, and $\Delta = \{\mathscr{S}_{1}, \mathscr{S}, \ldots, \mathscr{S}_{n}\}$.Suppose $\mathscr{S} = \{F|F\in\mathscr{S}_{\Delta}\}$.$\Delta_{1}\subset\Delta$ is a sub-base local consistent set with respect to $\mathscr{F}$ of $\Delta$ if and only if $\Delta_{1}\cap\mathcal{D}(x, y)\neq\varnothing$ for $\mathcal{D}(x, y)\neq\varnothing$.

Proof. Necessity. Assume there exist two points $x, y\in X$ such that $\mathcal{D}(x, y)\not\in\varnothing$, but $\Delta_{1}\cap\mathcal{D}(x, y) = \varnothing$. Then $\mathscr{S}\not\in\mathcal{D}(x, y)$ for each $\mathscr{S}\in\Delta_{1}$, which means $y\in N_{\mathscr{S}}(x)$ for each $\mathscr{S}\in\Delta_{1}$. That is, $y\in N_{\mathscr{S}_{\Delta_{1}}}(x)$. Since $\mathcal{D}(x, y)\not\in\varnothing$, for each $F\in\mathscr{F}$ satisfying $x\in F, y\not\in F$, there exists $\mathscr{S}\in\Delta$ such that $y\not\in N_{\mathscr{S}}(x)$. Because $\Delta_{1}\subset\Delta$ is a sub-base local consistent set with respect to $\mathscr{F}$ of $\Delta$, we have $\mathscr{F}\subset\mathscr{S}_{\Delta_{1}}$. Thus, $N_{\mathscr{S}_{\Delta_{1}}}(x) = (\bigcap\limits_{x\in A, A\in\mathscr{S}_{\Delta_{1}}, A\neq F}A)\cap F$, which contradicts with $y\in N_{\mathscr{S}_{\Delta_{1}}}$. Hence, $\Delta_{1}\cap\mathcal{D}(x, y)\neq\varnothing$ for $\mathcal{D}(x, y)\neq\varnothing$.

Sufficiency. Assume $\Delta_{1}$ is not a sub-base local consistent set with respect to $\mathscr{F}$ of $\Delta$. Then there exists $F\in\mathscr{F}$ such that $F\not\in\mathscr{S}_{\Delta_{1}}$. Thus, there exists a point $x\in X$ such that $N_{\mathscr{S}_{\Delta_{1}}\cup\{F\}}(x)\neq N_{\mathscr{S}_{\Delta_{1}}}(x)$. Since $N_{\mathscr{S}_{\Delta_{1}}\cup\{F\}}(x)\subset N_{\mathscr{S}_{\Delta_{1}}}(x)$, there exists a point $y\in X$ such that $y\in N_{\mathscr{S}_{\Delta_{1}}}(x)$, but $y\not\in N_{\mathscr{S}_{\Delta_{1}\cup\{F\}}}(x)$. That is, $y\not\in N_{\mathscr{S}_{\Delta}}(x)$ and $y\in N_{\mathscr{S}}(x)$ for each $\mathscr{S}\in\Delta_{1}$, which implies $\mathcal{D}(x, y) = \varnothing$, but $\Delta_{1}\cap\mathcal{D}(x, y) = \varnothing$, which is a contradiction. Hence, $\Delta_{1}$ is a sub-base local consistent set with respect to $\mathscr{F}$ of $\Delta$.

The definition of the sub-base local core is proposed.

Definition 2.3. Let $\mathscr{S}_{i}$ be a sub-base for finite topological space $(X, \tau_{i})$ for $i = 1, 2, \ldots, n$, and $\Delta = \{\mathscr{S}_{2}, \mathscr{S}_{2}, \ldots, \mathscr{S}_{n}\}$. Suppose $\mathscr{F} = \{F|F\in\Delta\}$. If $\mathcal{C}_{\mathscr{F}}(\Delta) = \cap\{\Delta_{1}|\mathscr{F}\subset\mathscr{S}_{\Delta_{1}}\}$, then $\mathcal{C}_{\mathscr{F}}(\Delta)$ is called a sub-base local core with respect to $\mathscr{F}$ of $\Delta$.

Some equivalent conditions about the sub-base local core are provided.

Theorem 2.2. Let $\mathscr{S}_{i}$ be a sub-base for finite topological space $(X, \tau_{i})$ for $i = 1, 2, \ldots, n$, and $\Delta = \{\mathscr{S}_{1}, \mathscr{S}_{2}, \ldots, \mathscr{S}_{n}\}$, Suppose $\mathscr{F} = \{F|F\in\mathscr{S}_{\Delta}\}$.Then the following conclusions are equivalent.

(1) $\mathscr{S}\in\mathcal{C}_{\mathscr{F}}(\Delta)$.

(2) There exist $x, y\in X$ such that $\mathcal{D}(x, y) = \{\mathscr{S}\}$.

(3) There exists $F\in\mathscr{F}$ such that $F\not\in\mathscr{S}_{\Delta\setminus\{\mathscr{S}\}}$.

Proof. (1)$\Rightarrow$(2). Assume $|\mathcal{D}(x, y)|\geq 2$ for any points $x, y\in X$. Denote $\Delta' = \bigcap\{\mathcal{D}(x, y)\setminus\{\mathscr{}S\}|x, y\in X\}$. It is easy to see that $\Delta'\cap\mathcal{D}(x, y)\neq\varnothing$ for $\mathcal{D}(x, y)\neq\varnothing$. According to Theorem 2.1, $\Delta'$ is a sub-base local consistent set with respect to $\mathscr{F}$ of $\Delta$. Thus, there exists $\Delta_{1}\subset\Delta'$ such that $\Delta_{1}$ is a sub-base local reduct with respect to $\mathscr{F}$ of $\Delta$, which contradicts with $\mathscr{S}\in\mathcal{C}_{\mathscr{F}}(\Delta)$. Hence, there exist $x, y\in X$ such that $\mathcal{D}(x, y) = \{\mathscr{S}\}$.

(2)$\Rightarrow$(3). Assume $\mathscr{F}\subset\mathscr{S}_{\Delta\setminus\{\mathscr{S}\}}$. Then, $\Delta\setminus\{\mathscr{S}\}$ is a sub-base local consistent set with respect to $\mathscr{F}$ of $\Delta$. Based on Theorem $2.1$, $(\Delta\setminus\{\mathscr{S}\})\cap \mathcal{D}(x, y)\neq\varnothing$ for $\mathcal{D}(x, y)\neq\varnothing$, which contradicts with (2). Hence, there exists $F\in\mathscr{F}$ such that $F\not\in\mathscr{S}_{\Delta\setminus\{\mathscr{S}\}}$.

(3)$\Rightarrow$(1). Since there exists $F\in\mathscr{F}$ such that $F\not\in\mathscr{S}_{\Delta\setminus\{\mathscr{S}\}}$, one concludes that $\Delta\setminus\{\mathscr{S}\}$ is not a sub-base local consistent set with respect to $\mathscr{F}$ of $\Delta$. Thus, for any $\Delta'\subset\Delta\setminus\{\mathscr{S}\}$, $\Delta'$ is not a sub-base local reduct with respect to $\mathscr{F}$ of $\Delta$, which contradicts with (1). Hence, $\mathscr{S}\in\mathcal{C}_{\mathscr{F}}(\Delta)$ is proved.

3.   Sub-base local reducts based on Boolean matrices

To provided a simple method to find a sub-base local reduct of a given $\Delta$, the following definitions are used to construct a Boolean matrix.

Definition 3.1. ^[5] Let $X = \{x_{1}, x_{2}, \ldots, x_{m}\}$ and $A\subset X$. The characteristic function is defined as $f(A) = (f_{1}, f_{2}, \ldots, f_{m})'$ ($'$ denotes the transpose throughout this paper), where

Definition 3.2. ^[13] Let $\mathscr{P}$ be a family of subsets of $X$ with $X = \{x_{1}, x_{2}, \ldots, x_{m}\}$ and $\mathscr{P} = \{P_{1}, P_{2}, \ldots,$ $P_{k}\}$. The characteristic matrix of $\mathscr{P}$ is defined as $M_{\mathscr{P}} = (f(P_{1}), f(P_{2}), \ldots,$ $f(P_{k}))$.

Definition 3.3. ^[4] Let $M = (m_{ij})_{n\times m}$ be a matrix. Define two matrix operators $\sim$ and $\approx$ as follows:

(1) $\sim M = (\sim m_{ij})_{n\times m}$, where

(2) $\approx M = (\approx m_{ij})_{n\times m}$, where

Definition 3.4. ^[16] Let $A = (a_{ij})_{n\times m}$ and $B = (b_{ij})_{n\times m}$ be two matrices. The Hadamard product of $A$ and $B$ is defined as $A\circ B = (a_{ij}b_{ij})_{n\times m}$.

The sub-base local discernibility Boolean matrix is defined.

Definition 3.5. Let $\mathscr{S}_{i}$ be a sub-base for finite topological space $(X, \tau_{i})$ for $i = 1, 2, \ldots, n$ with $X = \{x_{1}, x_{2}, \ldots, x_{m}\}$, and $\Delta = \{\mathscr{S}_{1}, \mathscr{S}_{2}, \ldots, \mathscr{S}_{n}\}$. Suppose $\mathscr{F} = \{F|F\in\mathscr{S}_{\Delta}\}$. For any $\Delta_{1}\subset\Delta$, define a sub-base local discernibility Boolean matrix $D_{\mathscr{F}}(\Delta_{1}) = (d_{ij})_{m\times m}$ satisfying:

(1) If there exists $F\in\mathscr{F}$ such that $x_{i}\in F, x_{j}\not\in F$ and $x_{j}\not\in N_{\mathscr{S}_{\Delta_{1}}}(x_{i})$, then $d_{ij} = 1$.

(2) Otherwise, $d_{ij} = 0$.

From the following theorem, the sub-base local discernibility Boolean matrix is computed.

Theorem 3.1. Let $\mathscr{S}_{i}$ be a sub-base for finite topological space $(X, \tau_{i})$ for $i = 1, 2, \ldots, n$ with $X = \{x_{1}, x_{2}, \ldots, x_{m}\}$.Suppose $\mathscr{F} = \{F|F\in\mathscr{S}_{\Delta}\}$.Then the following results hold.

(1) $D_{\mathscr{F}}(\mathscr{S}) = \approx(M_{\mathscr{S}}(\sim M'_{\mathscr{S}})\circ(M_{\mathscr{F}}(\sim M'_{\mathscr{F}})))$ for each $\mathscr{S}\in\Delta$.

(2) $D_{\mathscr{F}}(\mathscr{S}_{\Delta_{1}}) = \approx (\sum\limits_{\mathscr{S}\in\Delta_{1}}D_{\mathscr{F}}(\mathscr{S}))$ for any $\Delta_{1}\subset\Delta$.

Proof. Given a matrix $M$, denote its $i$-th row by $Row_{i}(M)$ and its element in the $i$-th row and $j$-th column by $M_{ij}$.

(1) Denote $\mathscr{S} = \{S_{1}, S_{2}, \ldots, S_{k}\}$ and $\mathscr{F} = \{F_{1}, F_{2}, \ldots, F_{q}\}$. It is easy to find that $Row_{i}(M_{\mathscr{S}}(\sim M'_{\mathscr{S}})) = \sum\limits_{1\leq j\leq k}(M_{\mathscr{S}})_{ij}Row_{j}(\sim M'_{\mathscr{S}})$. According to Definitions 3.1 and 3.2, $(M_{\mathscr{S}})_{ij} = 1$ means $x_{i}\in S_{j}$, and $(M_{\mathscr{S}})_{ij} = 0$ means $x_{i}\not\in S_{j}$. Thus, we get $Row_{i}(M_{\mathscr{S}}(\sim M'_{\mathscr{S}})) = \sum\limits_{1\leq j\leq k}(M_{\mathscr{S}})_{ij}Row_{j}(\sim M'_{\mathscr{S}}) = \sum\limits_{x_{i}\in S_{j}}Row_{j}(\sim M'_{\mathscr{S}})$. That is, $(M_{\mathscr{S}}(\sim M'_{\mathscr{S}}))_{il} = \sum\limits_{x_{i}\in S_{j}}(\sim M'_{\mathscr{S}})_{il}$. Similarly, $(M_{\mathscr{F}}(\sim M'_{\mathscr{F}}))_{il} = \sum\limits_{x_{i}\in S_{j}}(\sim M'_{\mathscr{F}})_{il}$. If $(D_{\mathscr{F}}(\mathscr{S}))_{il} = 1$, then there exists $F_{p}\in\mathscr{F}$ such that $x_{i}\in F_{p}, x_{l}\not\in F_{p}$ and $x_{l}\not\in N_{\mathscr{S}_{\Delta}}(x_{i})$. Hence, we obtain $(M_{\mathscr{F}})_{ip} = 1$ and $(\sim M'_{\mathscr{F}})_{pl} = 1$. That is, $(M_{\mathscr{F}}(\sim M'_{\mathscr{F}}))_{il}\geq 1$. Since $x_{l}\not\in N_{\mathscr{S}_{\Delta}}(x_{i})$, there exists $S_{j_{0}}\in\mathscr{S}$ such that $x_{i}\in S_{j_{0}}$ but $x_{l}\not\in S_{j_{0}}$. So we have $(M_{\mathscr{S}}(\sim M'_{\mathscr{S}}))_{il}\geq 1$. Therefore, we prove $(\approx(M_{\mathscr{S}}(\sim M'_{\mathscr{S}})\circ(M_{\mathscr{F}}(\sim M'_{\mathscr{F}}))))_{il} = 1$. Similarly, if $(D_{\mathscr{F}}(\mathscr{S}))_{il} = 0$, then $(\approx(M_{\mathscr{S}}(\sim M'_{\mathscr{S}})\circ(M_{\mathscr{F}}(\sim M'_{\mathscr{F}}))))_{il} = 0$. Consequently, $D_{\mathscr{F}}(\mathscr{S}) = \approx(M_{\mathscr{S}}(\sim M'_{\mathscr{S}})\circ(M_{\mathscr{F}}(\sim M'_{\mathscr{F}})))$ for each $\mathscr{S}\in\Delta$.

(2) If $(D_{\mathscr{F}}(\mathscr{S}_{\Delta_{1}}))_{ij} = 1$, then there exists $F\in\mathscr{F}$ such that $x_{i}\in F, x_{j}\not\in F$ and $x_{j}\not\in N_{\mathscr{S}_{\Delta_{1}}}(x_{i})$. Thus, there exists $\mathscr{S}\in\Delta_{1}$ such that $x_{j}\not\in N_{\mathscr{S}}(x_{i})$. From (1), we conclude that $(D_{\mathscr{F}}(\mathscr{S}))_{ij} = 1$, i.e., $(\approx (\sum\limits_{\mathscr{S}\in\Delta_{1}}D_{\mathscr{F}}(\mathscr{S})))_{ij} = 1$. If $(D_{\mathscr{F}}(\mathscr{S}_{\Delta_{1}}))_{ij} = 0$, then it is similar to proving $(\approx (\sum\limits_{\mathscr{S}\in\Delta_{1}}D_{\mathscr{F}}(\mathscr{S})))_{ij} = 0$. Consequently, $D_{\mathscr{F}}(\mathscr{S}_{\Delta_{1}}) = \approx (\sum\limits_{\mathscr{S}\in\Delta_{1}}D_{\mathscr{F}}(\mathscr{S}))$ for any $\Delta_{1}\subset\Delta$.

Based on the results above, Theorem 3.2 is proved.

Theorem 3.2. Let $\mathscr{S}_{i}$ be a sub-base for finite topological space $(X, \tau_{i})$ for $i = 1, 2, \ldots, n$ with $X = \{x_{1}, x_{2}, \ldots, x_{m}\}$.Suppose $\mathscr{F} = \{F|F\in\mathscr{S}_{\Delta}\}$.Then the following results hold.

(1) For each $\Delta_{1}\subset\Delta$, $\Delta_{1}$ is a sub-base local consistent set with respect to $\mathscr{F}$ of $\mathscr{S}$ if and only if $D_{\mathscr{F}}(\Delta_{1}) = D_{\mathscr{F}}(\Delta)$.

(2) For each $\mathscr{S}\in\Delta$, $\mathscr{S}\in\mathcal{C}_{\mathscr{F}}(\Delta)$ if and only if $D_{\mathscr{F}}(\Delta\setminus\{\mathscr{S}\})\neq D_{\mathscr{F}}(\Delta)$.

Proof. (1) According to Theorem 2.1, $\mathscr{S}$ is a sub-base local core with respect to $\mathscr{F}$ if and only if $\Delta_{1}\cap\mathcal{D}(x_{i}, _{j})\neq\varnothing$ for $\mathcal{D}(x_{i}, x_{j})\neq\varnothing$. From Definitions 2.2 and 3.5, $\mathcal{D}(x_{i}, x_{j})\neq\varnothing$ is equivalent to $(D_{\mathscr{F}}(\Delta))_{ij} = 1$. $\Delta_{1}\cap\mathcal{D}(x_{i}, x_{j})\neq\varnothing$ is equivalent to $x_{j}\not\in N_{\mathscr{S}_{\Delta_{1}}}(x_{i})$, i.e., $(D_{\mathscr{F}}(\Delta_{1}))_{ij} = 1$. Hence, we conclude that $D_{\mathscr{F}}(\Delta_{1}) = D_{\mathscr{F}}(\Delta)$.

(2) From Theorem 2.2, $\mathscr{S}$ is a sub-base local core with respect to $\mathscr{F}$ if and only if there exists $x_{i}, x_{j}\in X$ such that $\mathcal{D}(x_{i}, x_{j}) = \{\mathscr{S}\}$. It is equivalent to $(D_{\mathscr{F}}(\Delta))_{ij} = 1$, but $(D_{\mathscr{F}}(\Delta\setminus\{\mathscr{S}\}))_{ij} = 0$. Hence, $D_{\mathscr{F}}(\Delta\setminus\{\mathscr{S}\})\neq D_{\mathscr{F}}(\Delta)$.

Moreover, a necessary and sufficient condition for the sub-base local reduct is presented.

Corollary 3.1. Let $\mathscr{S}_{i}$ be a sub-base for finite topological space $(X, \tau_{i})$ for $i = 1, 2, \ldots, n$ with $X = \{x_{1}, x_{2}, \ldots, x_{m}\}$.Suppose $\mathscr{F} = \{F|F\in\mathscr{S}_{\Delta}\}$.Then $\Delta_{1}\subset\Delta$ is a sub-base local reduct with respect to $\mathscr{F}$ of $\Delta$ if and only if $\Delta_{1}$ is a minimal subfamily of $\Delta$ satisfying $D_{\mathscr{F}}(\Delta_{1}) = D_{\mathscr{F}}(\Delta)$.

On the basis of the analysis above, an algorithm is devised to find sub-base local reducts.

Algorithm 1 Sub-base local reducts based on Boolean matrices

Input: A family $\Delta$ of sub-bases and $\mathscr{F}=\{F|F\in\mathscr{S}_{\Delta}\}$. Output: A minimal family $\Delta'$ of sub-bases. 1: Let $\Delta'=\varnothing$; 2: for each $\mathscr{S}\in\Delta$ do 3:  Compute $D_{\mathscr{F}}(\Delta\setminus\{\mathscr{S}\})$ according to Theorem 3.1; 4:  if $D_{\mathscr{F}}(\Delta\setminus\{\mathscr{S}\})\neq D_{\mathscr{F}}(\Delta)$; then 5:    Let $\Delta'=\Delta'\cup\{\mathscr{S}\}$.//find all sub-base local cores; 6:  end if 7: end for 8: while $D_{\mathscr{F}}(\Delta')\neq D_{\mathscr{F}}(\Delta)$ do 9:  Let $\Delta'=\Delta'\cup\{\mathscr{S}_{0}\}$, 10: where $\mathscr{S}_{0}$ satisfies $|D_{\mathscr{F}}(\Delta'\cup\{\mathscr{S}_{0}\})|=max\{|D_{\mathscr{F}}(\Delta'\cup\{\mathscr{S}_{0}\})|\mid\mathscr{S}\in\Delta\setminus \Delta'\}$, and $|\cdot|$ is the total number of $1$ in a matrix; 11: end while 12: Return $\Delta'$.

---

 | Show Table

DownLoad: CSV

Remark 3.1. The time complexities of Steps 3-6 and Steps 8-10 are $O(\sum_{\mathscr{S}\in\Delta}\alpha^{2}|\mathscr{S}|)$ and $O(\sum_{i = 1}^{|\Delta|-1}\alpha^{2}(|\Delta|-i))$, respectively, where $\alpha = |\bigcup_{F\in\mathscr{F}}F|$. Thus, the time complexity of Algorithm 1 is $O(\sum_{\mathscr{S}\in\Delta}\alpha^{2}|\mathscr{S}|+\sum_{i = 1}^{|\Delta|-1}\alpha^{2}(|\Delta|-i))$.

4.   Conclusions

Sub-base local reducts in a family of sub-bases have been investigated in this paper. Firstly, using the defined sub-base local discernibility matrix, a necessary and sufficient condition for the sub-base local consistent set has been provided. Then the sub-base local discernibility matrix has been employed to study properties of the sub-base local core. Finally, an algorithm has been devised to obtain sub-base local reducts via the sub-base local discernibility matrix.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 11871259), the Natural Science Foundation of Fujian Province (No. 2019J01748), and the Key Program of the Natural Science Foundation of Fujian Province (No. 2020J02043).

Conflict of interest

The authors declare that they have no conflict of interest.