On some types of covering rough sets from topological points of view

The concept of coverings is one of the fundamental concepts in topological spaces and plays a big part in the study of topological problems. This motivates the research of covering rough sets from topological points of view. From topological points of view, we can get a good insight into the essence of covering rough sets and make our discussions concise and profound. In this paper, we first construct a type of topology called the topology induced by the covering on a covering approximation space. This notion is indeed in the core of this paper. Then we use it to define the concepts of neighborhoods, closures, connected spaces, and components. Drawing on these concepts, we define several pairs of approximation operators. We not only investigate the relationships among them, but also give clear explanations of the concepts discussed in this paper. For a given covering approximation space, we can use the topology induced by the covering to investigate the topological properties of the space such as separation, connectedness, etc. Finally, a diagram is presented to show that the collection of all the lower and upper approximations considered in this paper constructs a lattice in terms of the inclusion relation ⊆.     

Data volume reduction in covering approximation spaces with respect to twenty-two types of covering based rough sets

In this paper, we investigate whether consistent mappings can be used as homomorphism mappings between a covering based approximation space and its image with respect to twenty-two pairs of covering upper and lower approximation operators. We also consider the problem of constructing such mappings and minimizing them. In addition, we investigate the problem of reducing the data volume using consistent mappings as well as the maximum amount of their compressibility. We also apply our algorithms against several datasets.     

Reduction about approximation spaces of covering generalized rough sets

The introduction of covering generalized rough sets has made a substantial contribution to the traditional theory of rough sets. The notion of attribute reduction can be regarded as one of the strongest and most significant results in rough sets. However, the efforts made on attribute reduction of covering generalized rough sets are far from sufficient. In this work, covering reduction is examined and discussed. We initially construct a new reduction theory by redefining the approximation spaces and the reducts of covering generalized rough sets. This theory is applicable to all types of covering generalized rough sets, and generalizes some existing reduction theories. Moreover, the currently insufficient reducts of covering generalized rough sets are improved by the new reduction. We then investigate in detail the procedures to get reducts of a covering. The reduction of a covering also provides a technique for data reduction in data mining.     

Four matroidal structures of covering and their relationships with rough sets

Covering is a common form of data representation, and covering-based rough sets serve as an efficient technique to process this type of data. However, many important problems such as covering reduction in covering-based rough sets are NP-hard so that most algorithms to solve them are greedy. Matroids provide well-established platforms for greedy algorithm foundation and implementation. Therefore, it is necessary to integrate covering-based rough set with matroid. In this paper, we propose four matroidal structures of coverings and establish their relationships with rough sets. First, four different viewpoints are presented to construct these four matroidal structures of coverings, including 1-rank matroids, bigraphs, upper approximation numbers and transversals. The respective advantages of these four matroidal structures to rough sets are explored. Second, the connections among these four matroidal structures are studied. It is interesting to find that they coincide with each other. Third, a converse view is provided to induce a covering by a matroid. We study the relationship between this induction and the one from a covering to a matroid. Finally, some important concepts of covering-based rough sets, such as approximation operators, are equivalently formulated by these matroidal structures. These interesting results demonstrate the potential to combine covering-based rough sets with matroids.     

On some covering designs

Let n ? k ? t be positive integers, and let Ω be a set of n elements. Let C(n, k, t) denote the number of k-tuples of Ω in a minimal system of k-tuples such that every t-tuple is contained in at least one k-tuple of the system. C(n, k, t) has been determined in all cases for which $\text{C(n, k, t) ?}\text{3(t + 1)}\text{2}$ [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case $\text{3(t + 1)}\text{2}\text{< C(n, k, t) ?}\text{3(t + 2)}\text{2}$.     

On visibility and covering by convex sets

A setX⊆ℝ ^d isn-convex if among anyn of its points there exist two such that the segment connecting them is contained inX. Perles and Shelah have shown that any closed (n+1)-convex set in the plane is the union of at mostn ⁶ convex sets. We improve their bound to 18n ³, and show a lower bound of order Ω(n ²). We also show that ifX⊆ℝ² is ann-convex set such that its complement has λ one-point path-connectivity components, λ<∞, thenX is the union ofO(n ⁴+n ²λ) convex sets. Two other results onn-convex sets are stated in the introduction (Corollary 1.2 and Proposition 1.4). Research supported by Charles University grants GAUK 99/158 and 99/159, and by U.S.-Czechoslovak Science and Technology Program Grant No. 94051. Part of the work by J. Matoušek was done during the author’s visits at Tel Aviv University and The Hebrew University of Jerusalem. Part of the work by P. Valtr was done during his visit at the University of Cambridge supported by EC Network DIMANET/PECO Contract No. ERBCIPDCT 94-0623.     

On covering of linear operators on polyhedral sets

We consider a problem of finding a covering constant for a restriction of a linear operator to a polyhedral set. The obtained result allows to reduce the initial problem to the problem of finding a covering constant for some linear bijective operators.     

Axiomatic systems for rough sets and fuzzy rough sets

Rough set theory is an important tool for approximate reasoning about data. Axiomatic systems of rough sets are significant for using rough set theory in logical reasoning systems. In this paper, outer product method are used in rough set study for the first time. By this approach, we propose a unified lower approximation axiomatic system for Pawlak’s rough sets and fuzzy rough sets. As the dual of axiomatic systems for lower approximation, a unified upper approximation axiomatic characterization of rough sets and fuzzy rough sets without any restriction on the cardinality of universe is also given. These rough set axiomatic systems will help to understand the structural feature of various approximate operators.     

On some new types of greedy chains and greedy linear extensions of partially ordered sets

Two new types of greedy chains, strongly and semi-strongly greedy, in posets are defined and their role in solving the jump number problem is discussed in this paper. If a poset P contains a strongly greedy chain C then C may be taken as the first chain in an optimal linear extension of P. If a poset P has no strongly greedy chains then it contains an optimal linear extension which starts with a semi-strongly greedy chain. Hence, every poset has an optimal linear extension which consists of strongly and semi-strongly greedy chains. Algorithmic issues of finding such linear extensions are discussed elsewhere (Syslo, 1987, 1988), where we provide a very efficient method for solving the jump number problem which is polynomial in the class of posets whose arc representations contain a bounded number of dummy arcs. In another work, the author has recently demonstrated that this method restricted to interval orders gives rise to 3/2-approximation algorithm for such posets.     

On some chains of fuzzy sets

A partial order relation σ is defined in the set $\text{F}$(X) of the fuzzy sets in X. If this ordering is induced in the subset F(X) of the measurable fuzzy sets in the set X with totally finite positive measure, then fσg implies that the entropy of the fuzyy set f is not less than the entropyof g. By means of this ordering a lattice L on $\text{F}$(X) is defined and a lattice structure is induced in the set of infinite chains in L. Furthermore the set F′(X) of the fuzzy sets of F(X) which assume value in a finite subset of the real interval [0,1] is considered and the following properties are stated: any chain of elements of F′(X) is an infinite sequence of functions convergent in the mean to an integrable function, and the entropy is a valuation of bounded variation on the sublattice of L whose elements are in F′(X). The chains on L can offer a model of a cognitive process in a fuzzy environment when their elements are determined by a sequence of decisions. The limit property traduces the determinism of a such procedure.     

On some sets of permutation matrices

In [5], a class Σ of p×p circulant matrices was studied where p is a prime, and necessary and sufficient conditions were presented for the matrices in Σ to be commutative and to be closed with respect to matrix multiplication. Here we show that these properties also hold for n×n circulant matrices, where n is a positive integer, with an additional condition, namely, Σ contains an n-cycle.     

On covering a product of sets with products of their subsets

Suppose that S₁,…,S_N are collections of subsets of X₁,…,X_N, respectively, such that n_i subsets belonging to S_i, and no fewer, cover X_i for all i. the main result of this paper is that to cover X₁ x…x X_N requires no fewer than σ^N_i=1 (n_i–1) + 1 and no more than Π^N_i=1n_i subsets of the form A₁ x…x A_N, where A_i∈S₁foralli. Moreo ver, these bounds cannot be improved. Identical bounds for the spanning number of a normal product of graphs are also obtained.