A REPRESENTATION OF DEPENDENCE SPACES AND SOME BASIC ALGORITHMS

Article type: Research Article

Authors: Järvinen, Jouni

Affiliations: Department of Mathematics, University of Turku, FIN-20014 Turku, Finland, e-mail: [email protected]

Note: [] Supported by Turku Centre for Computer Science TUCS/Graduate School

Abstract: We give a simple representation of dependence spaces and a new characterization of the reducts of an arbitrary subset of a dependence space by the means of closure systems. We present an algorithm for finding the reducts of any given subset of a dependence space. The algorithm is based on a notion of difference function which connects the reduction problem to the general problem of identifying the set of all minimal vectors of values satisfying a positive (i.e., isotone) Boolean function.

DOI: 10.3233/FI-1997-29404

Journal: Fundamenta Informaticae, vol. 29, no. 4, pp. 369-382, 1997