On a Problem Concerning Dependence Spaces

Article type: Research Article

Authors: Novotný, Miroslav^a | Pawlak, Zdzisław^b

Affiliations: [a] Masaryk University Brno, Burešova 20, Czechoslovakia | [b] University of Technology Warsaw, Nowowiejska 15/19, Poland

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 X′⊆X such that Y depends on X′. A set X′ is said to be a reduct of X if X′ 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.

Keywords: information system, dependence space, reduct, dependence

DOI: 10.3233/FI-1992-163-405

Journal: Fundamenta Informaticae, vol. 16, no. 3-4, pp. 275-287, 1992