On a Problem Concerning Dependence Spaces

Abstract

A set Y of attributes of an information system is said to be dependent on a set X of attributes if the classification of objects defined by X is finer or as fine as the classification defined by Y. An important problem reads as follows. If Y depends on X find a minimal ${\mathit{X}}^{\prime }\subseteq \mathit{X}$ such that Y depends on ${\mathit{X}}^{\prime }$ . A set ${\mathit{X}}^{\prime }$ is said to be a reduct of X if ${\mathit{X}}^{\prime }$ is a minimal subset of X defining the same classification of objects as X. The paper is devoted to the study of relationship between reducts and dependence. Both dependence and reducts can be defined in the so called dependence spaces and the above mentioned problem can be transformed into the problem of constructing reducts in a suitable dependence space. We also present some algorithms providing reducts in a dependence space; in this way, we obtain an algorithmic solution of our problem.